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 }\to \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 \to (\alpha {)}_{\mu }^{<\omega }$ denote the assertion that every function $f:[\kappa {]}^{<\omega }\to \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 \to (\alpha {)}_2^{<\omega }$.
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\to y=x$ for all $y\in A$)

Fact (ZF). Suppose that $(P,\le )$ is a poset whose underlying set $P$ admits a well-ordering $⊴$, 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 \to P$ is an order-reversing map, then its image is finite;
3. there exists an ordinal $\theta$ and a function $\rho :P\to \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:=\mathrm{\varnothing }$;
• $R_{\alpha +1}:=\{x\in P\mid \mathrm{\forall }y\in P\setminus \{x\}(y\le x\to 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\to 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\to \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\to \theta$ witness (3). Suppose that $f:\omega \to P$ is order-reversing. Then $(\rho \circ f):\omega \to \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.

$(\mathrm{\neg }1\Rightarrow \mathrm{\neg }2)$ 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=\underset{⊴}{min}(y_{\downarrow })$, that is, $$x=\underset{⊴}{min}\{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)=\underset{⊴}{min}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 \to P$ is an order-reversing function with an infinite image. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

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

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

We need to show that $({}^{<\omega }\kappa ,⊴)$ is linearly-ordered, and well-founded. It is obvious that for every $x,y\in {}^{<\omega }\kappa$, we either have $x⊴y$ or $y⊴x$, and that if $x⊴y$ and $y⊴x$, then $x=y$. Next, suppose that $x⊴y$ and $y⊴z$. We need to verify that $x⊴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:=\mathrm{\Delta }(x,y),n_1:=\mathrm{\Delta }(y,z)$.

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

Next, we verify well-foundedness. Suppose that $A$ is a non-empty subset of ${}^{<\omega }\kappa$. If $\mathrm{\varnothing }\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$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

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 }\to 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 \to \kappa$ such that $i“\alpha$ is a set of indiscernibles for $f$. Define $h:\omega \to \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\upharpoonright n\in S(f,g)$ for all $n<\omega$. As  $\{h\upharpoonright 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 $⟨h_n\mid n<\omega ⟩$ 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$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

We know that ${\mathrm{\Delta }}_0$ properties (e.g., being an ordinal, being a function) are absolute for all transitive models of $ZF$, and hence ${\mathrm{\Sigma }}_1$ properties are upward absolute, and ${\mathrm{\Pi }}_1$ properties are downward absolute. In particular, ${\mathrm{\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 ${\mathrm{\Pi }}_1$ formula (with a parameter $S:=S(f,g)$) fails:

$$\mathrm{\forall }A[((A\ne \mathrm{\varnothing })\wedge (A\subseteq S))\to (\mathrm{\exists }x\in A\mathrm{\forall }y\in A(y\supseteq x\to 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 ${\mathrm{\Sigma }}_1$ formula (with a parameter $S:=S(f,g)$) fails:

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

[Note that the negation of a ${\mathrm{\Delta }}_1$ statement is again ${\mathrm{\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 \to (\alpha {)}_{\mu }^{<\omega }$ holds (in the universe), then $$\mathcal{M}\models \kappa \to (\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 }\to \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 \to (\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 ${\mathrm{\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$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

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\ne L$.) It follows that Silver’s theorem that $\kappa (\alpha )$ relativizes to $L$ for all $\alpha <({\omega }_1{)}^L$ is best possible.