A large cardinal in the constructible universe

In this post, we shall provide a proof of Silver’s theorem that the Erdos caridnal $\kappa(\omega)$ relativizes to Godel’s constructible universe.

First, recall some definitions. Given a function $f:[\kappa]^{<\omega}\rightarrow \mu$, we say that $I\subseteq\kappa$ is a set of indiscernibles for $f$ iff for every $n<\omega$ and every $x,y\in [I]^n$, we have $f(x)=f(y)$. Let $\kappa\rightarrow(\alpha)^{<\omega}_\mu$ denote the assertion that every function $f:[\kappa]^{<\omega}\rightarrow \mu$ admits a set of indiscernibles of order-type $\alpha$. Then, one defines the $\alpha_{th}$-Erdos cardinal, as follows:
$\kappa(\alpha)$ is the least cardinal $\kappa$ (if exists) for which $\kappa\rightarrow(\alpha)^{<\omega}_2$.
We mention that Erdos and Hajnal proved that $\alpha<\beta$ entails $\kappa(\alpha)<\kappa(\beta)$, and that a cardinal $\kappa$ is said to be Ramsey iff it is the $\kappa_{th}$-Erdos cardinal, i.e., $\kappa(\kappa)=\kappa$.

Silver’s idea for relativizing $\kappa(\omega)$ goes through a reformulation of the statement concerning the existence of a set of indiscenribles, in terms of the failure of well-foundedness of a related poset. This leads us to revisiting this subject:

Definition. A poset $(P,\le)$ is said to be well-founded iff every non-empty subset $A\subseteq P$ has a $\le$-minimal element $x$. (the latter means that $y\le x\rightarrow y=x$ for all $y\in A$)

Fact (ZF). Suppose that $(P,\le)$ is a poset whose underlying set $P$ admits a well-ordering $\unlhd$, then all of the following are equivalent:

1. $(P,\le)$ is well-founded (slang: “$P$ does not admit an infinite $\le$-descending chain”);
2. if $f:\omega\rightarrow P$ is an order-reversing map, then its image is finite;
3. there exists an ordinal $\theta$ and a function $\rho:P\rightarrow\theta$ such that for every distinct elements $x,y\in P$: $x\le y$ implies $\rho(x)< \rho(y)$.

Proof. $(1\Rightarrow 3)$ Recursively define

• $R_0:=\emptyset$;
• $R_{\alpha+1}:=\{ x\in P\mid \forall y\in P\setminus\{x\}(y\le x\rightarrow y\in R_\alpha)\}$;
• $R_\alpha:=\bigcup_{\beta<\alpha}R_\beta$ for all limit $\alpha$.

Of course, $\{ R_\alpha\mid \alpha\in On\}$ is an increasing chain of subsets of $P$, and so by the axiom of replacement, there exists some $\theta\in On$ such that $R_{\theta+1}=R_\theta$. Note that $R_\theta=P$, because otherwise, $P\setminus R_\theta$ would be non-empty, and one could find a minimal $x\in P\setminus R_\theta$; it will then follow from the minimality of $x$ in $P\setminus R_\theta$, that $y<x\rightarrow y\in P_\theta$. So $x\in R_{\theta+1}\setminus R_\theta$, contradicting the definition of $\theta$.
Thus, define (the rank function) $\rho:P\rightarrow\theta$ by letting $\rho(x):=\min\{ \alpha<\theta\mid x\in R_{\alpha+1}\}$ for all $x\in P$. Then $\rho$ has the desired properties.

$(3\Rightarrow 2)$ Let $\rho:P\rightarrow\theta$ witness (3). Suppose that $f:\omega\rightarrow P$ is order-reversing. Then $(\rho\circ f):\omega\rightarrow\theta$ is an order-reversing map from ordinal to ordinals, and hence $(\rho\circ f)[\omega]$ is finite. Since $f[\omega]$ is linearly-ordered by $\le$, $(\rho\circ f)[\omega]$ is finite iff  $f[\omega]$ is finite. Consequently, the image of $f$ is indeed finite.

$(\neg1\Rightarrow \neg2)$ Suppose that $A$ is non-empty subset of $P$ without a minimal element. Define a relation $R$ of $\le$ over $A$, as follows: $yRx$ iff $x=\min_{\unlhd}(y_{\downarrow})$, that is, $$x=\min_{\unlhd}\{z\in A\setminus\{y\} \mid z\le y\}.$$

Note that $yRx$ entails $x\le y$, and that for every $y\in A$, there exists a unique $x\in A$ such that $yRx$. Let us say that a function $f$ is good, if $\text{dom}(f)$ is a positive integer, $f(0)=\min_{\unlhd}A$, and if $n+1\in\text{dom}(f)$, then $f(n)Rf(n+1)$.
Let $\mathcal F=\{ f\in{}^{<\omega}P\mid f\text{ is good}\}$. Then a second look at the definition of $R$ reveals that $f:=\bigcup\mathcal F$ is a function. Moreover, since $A$ does not contain a minimal element, we get that $\text{Im}(f)$ is infinite. As $yRx$ implies $x\le y$, we conclude that $f:\omega\rightarrow P$ is an order-reversing function with an infinite image. $\square$

Proposition (ZF). ${}^{<\omega}\kappa$ admits a well-ordering.
Proof. Given $x,y\in{}^{<\omega}\kappa$, we let $x\unlhd y$ iff one of the following holds:

1. $x=y$;
2. $|x|<|y|$;
3. $|x|=|y|$ and $x\neq y$ and $x(\Delta(x,y))<y(\Delta(x,y))$. (here, $\Delta(x,y):=\min\{ n<\omega\mid x(n)\not=y(n)\}$.)

We need to show that $({}^{<\omega}\kappa,\unlhd)$ is linearly-ordered, and well-founded. It is obvious that for every $x,y\in{}^{<\omega}\kappa$, we either have $x\unlhd y$ or $y\unlhd x$, and that if $x\unlhd y$ and $y\unlhd x$, then $x=y$. Next, suppose that $x\unlhd y$ and $y\unlhd z$. We need to verify that $x\unlhd z$. To avoid trivialities, we may assume that $|\{ x,y,z\}|=3$. If $|x|<|y|$ or $|y|<|z|$, then $|x|<|z|$, and we are done. So, we assume that $|x|=|y|=|z|$. Put $n_0:=\Delta(x,y), n_1:=\Delta(y,z)$.

• If $n_0\le n_1$, then $x(n_0)<y(n_0)\le z(n_0)$ and $x\restriction n_0=y\restriction n_0=z\restriction n_0$. So $\Delta(x,z)=n_0$ and $x(\Delta(x,z))<z(\Delta(x,z))$.
• If $n_1<n_0$, then $x(n_1)=y(n_1)<z(n_1)$ and $x\restriction n_1=y\restriction n_1=z\restriction n_1$. So $\Delta(x,z)=n_1$ and $x(\Delta(x,z))<z(\Delta(x,z))$.

Next, we verify well-foundedness. Suppose that $A$ is a non-empty subset of ${}^{<\omega}\kappa$. If $\emptyset\in A$, then it is the minimal element of $A$, and we are done. Suppose now that this is not the case, and let $n$ be the least natural number for which there exists $x\in A$ with $|x|=n+1$. Put $B:=\{ x\in A\mid |x|=n+1\}$. Next, let $k_0:=\min\{ x(0)\mid  x\in B\}$, and put $B_0:=\{ x\in B\mid x(0)=k_0\}$. Then for $i<n$, let $k_{i+1}:=\min\{ x(i+1)\mid x\in B_i\}$, and put $B_{i+1}:=\{ x\in B_i \mid x(i+1)=k_{i+1}\}$. Then $B_{n}$ is a singleton whose element is the minimal element of $A$. $\square$

Terminology. Let us say that two functions $g,h$ are compatible iff for every $i,j\in\text{dom}(g)\cap\text{dom}(h)$, we have $$g(i)\in g(j)\text{ iff }h(i)\in h(j).$$

Lemma (ZF). Given a function $f:[\kappa]^{<\omega}\rightarrow X$, a (countable) ordinal $\alpha$, and bijection $g:\omega\leftrightarrow\alpha$, denote $$S(f,g):=\{ h\in{}^{<\omega}\kappa\mid g,h\text{ are compatible, and }Im(h)\text{ are indiscenrnibles for }f\}.$$ Then $f$ has a set of indiscernibles of order-type $\alpha$ iff $(S(f,g),\supseteq)$ is not well-founded.

Proof. As ${}^{<\omega}\kappa$ admits a well-ordering, we know that $(S(f,g),\supseteq)$ is well-founded iff it does not admit an infinite $\supseteq$-descending chain iff if does not admit an infinite $\subseteq$-increasing chain.
$\Rightarrow$ Suppose that $f$ has a set of indiscernibles of order-type $\alpha$. Fix an order-preserving injection $i:\alpha\rightarrow\kappa$ such that $i“\alpha$ is a set of indiscernibles for $f$. Define $h:\omega\rightarrow\kappa$ by letting $h(n)=i(g(n))$ for all $n<\omega$. As $i$ is order-preserving, we get that $g$ and $h$ are compatible, and then $h\restriction n\in S(f,g)$ for all $n<\omega$. As  $\{ h\restriction n\mid n<\omega\}$ is an increasing $\subseteq$-chain, we infer that  $(S(f,g),\supseteq)$ is not well-founded.
$\Leftarrow$ Suppose that $(S(f,g),\supseteq)$ is not well-founded, and let $\langle h_n\mid n<\omega\rangle$ be an increasing $\subseteq$-chain within $S(f,g)$. Let $h:=\bigcup_{n<\omega}h_n$. Then $\text{dom}(h)=\omega$, and $g,h$ are compatible. Put $I:=Im(h)$. Then $I$ is a set of indiscerinbles for $f$. Finally, since $g,h$ are compatible and $\text{dom}(h)=\text{dom}(g)$, we get that $Im(g)$ and $Im(h)$ has the same order-type. That is $\text{otp}(I)=\alpha$. $\square$

We know that $\Delta_0$ properties (e.g., being an ordinal, being a function) are absolute for all transitive models of $ZF$, and hence $\Sigma_1$ properties are upward absolute, and $\Pi_1$ properties are downward absolute. In particular, $\Delta_1$ properties are absolute. Let us point out that this is indeed the case here:

Suppose that $f,\alpha,g$ are as in the preceding lemma. Then $f$ has a set of indiscernibles of order-type $\alpha$ iff the following $\Pi_1$ formula (with a parameter $S:=S(f,g)$) fails:

$$\forall A[((A\neq\emptyset)\wedge(A\subseteq S))\rightarrow(\exists x\in A\forall y\in A(y\supseteq x\rightarrow y=x))].$$

Recalling the fact that we proved at the beginning of this post, we get as well that $f$ has a set of indiscerinbles of order-type $\alpha$ iff the following $\Sigma_1$ formula (with a parameter $S:=S(f,g)$) fails:

$$\exists\theta\exists\rho[(\theta\text{ is an ordinal})\wedge(\rho:S\rightarrow\theta\text{ is a function})\wedge(\forall x\in S\forall y\in S(x\supsetneq y\rightarrow \rho(x)\in\rho(y))].$$

[Note that the negation of a $\Delta_1$ statement is again $\Delta_1$]

Corollary (Silver, 1970). Suppose that $\mathcal M$ is transitive model of ZF, and $\alpha,\kappa,\mu\in\mathcal M$ with $\alpha<(\omega_1)^{\mathcal M}$. If $\kappa\rightarrow(\alpha)_\mu^{<\omega}$ holds (in the universe), then $$\mathcal M\models \kappa\rightarrow(\alpha)_\mu^{<\omega}.$$
In particular, if $\kappa(\omega)$ exists, say it is $\kappa$, then $L\models \kappa(\omega)\text{ exists, and }\kappa(\omega)=\kappa$.
Proof. Suppose that $f:[\kappa]^{<\omega}\rightarrow\mu$ is a given coloring in $\mathcal M$, and $\alpha<(\omega_1)^{\mathcal M}$. Our goal is to find (within $\mathcal M$) a set of indiscernibles for $f$ of order-type $\alpha$.
Fix in $\mathcal M$, a bijection $g:\omega\leftrightarrow\alpha$. As $\kappa\rightarrow(\alpha)_\mu^{<\omega}$ holds in the universe, there exists a set of indiscernibles for $f$ of order-type $\alpha$. So $S(f,g)$ is not well-founded. Since $f,g\in\mathcal M$, we infer that $S(f,g)\in\mathcal M$, and so by absoluteness for $\Delta_1$ properties: $$\mathcal M\models S(f,g)\text{ is not well-founded}.$$ It now follows from the lemma that $\mathcal M$ contains a set of indiscernibles for $f$ of order-type $\alpha$. $\square$

For completeness, we mention that Rowbottom proved in his dissertation that the existence of the Erdos cardinal $\kappa(\omega_1)$ contradicts the axiom $V=L$. (Thus, improving Scott’s famous theorem that the existence of a measurable cardinal implies $V\neq L$.) It follows that Silver’s theorem that $\kappa(\alpha)$ relativizes to $L$ for all $\alpha<(\omega_1)^L$ is best possible.