# Uncountable Cardinals without AC

I am doing an exercise, proving that without AC or Replacement that there are uncountable cardinals.

As a point of reference I looked at the proof in Kunen's "The Foundations of Mathematics" that shows the existence of larger cardinals without AC but does use replacement (the idea is attributed to Hartogs). Right now I'm confused by the proof and I guess I need help understanding it. Here it is:

Suppose $A$ is a set. We want to show that there is a cardinal $\kappa$ such that $\kappa \not \preccurlyeq A$.

Let $W$ be the set of pairs $(X,R) \in \mathcal{P}(A) \times \mathcal{P}(A \times A)$ such that $R \subseteq X \times X$ and $R$ Well Orders $X$. So, $W$ is the set of all well-orderings of all subsets of $A$. Observe that $\alpha \preccurlyeq X$ iff $\alpha = \text{type}(X;R)$ for some $(X,R) \in W$ (See Exercise I.11.19). Applying the Replacement Axiom, we can set $\beta = \text{sup}\{\text{type}(X,R)+1 : (X,R) \in W\}$. Then $\beta$ $\alpha$ whenever $\alpha \preccurlyeq A$, so $\beta \not \preccurlyeq A$. Let $\kappa = |\beta|$. Then $\kappa \approx \beta$, so $\kappa \not \preccurlyeq A$.

I'll try to describe my confusion to the best of my ability. First, let's suppose that $A = \omega$. These are my issues:

1. This seems odd to me: $\alpha \preccurlyeq X$ iff $\alpha = \text{type}(X;R)$ for some $(X,R) \in W$. Say $X$ is the set $\{2,4,6\}$ and $R$ is the relation $\{(2,4),(2,6),(4,6)\}$. The ordinal $\alpha = 2$ has a 1-1 function into $X$ but $\alpha \not = 3 = \text{type}(X;R)$. Is this perhaps a typo that should say "$\approx$" instead of "$\preccurlyeq$"?
2. If $(X,R) \in W$ then $X$ is a subset of $A = \omega$ ($A = \omega$ is an added assumption I made just to help my understanding), and $R$ is just a well-ordering of $X$. So the type of $(X;R)$ is either a finite ordinal $n$ or $\omega$ itself. So then $\beta$ is just the least upper bound of the set of finite ordinals (plus one) and $\omega+1$. $\omega+1$ is the largest thing in that set (and so the least upper bound). Then according to the proof $\kappa = \beta = \omega+1$ is supposed to be the larger cardinal we desire, but it isn't even a cardinal. It also is the same size as the set we started with.
-

First of all, a word of terminology. Cardinals may or may not apply to the general term meaning "sets which represent an equivalence class of sets in the relation 'there exists a bijection between two sets'", and not just a particular class of ordinals. In the broader sense, it is easy to prove there are uncountable cardinals because the power set of the natural numbers is always uncountable, and it has a cardinal number (just not necessarily an ordinal).

1. I agree that it seems like a typo. It should be the case that $\alpha\preccurlyeq A$ if and only if $\alpha$ is the order type of some $(X;R)\in W$. The statement you wrote quantify on $X$ on the right-hand side of the equivalence, but not on the left-hand side of it; which does seem a bit strange.

2. You're making one of the most common mistakes here. Just because a set has a "natural structure", doesn't mean every well-order which can be given to a subset of it must respect that structure. Your claim would be similar to saying that $\Bbb Q$ cannot be well-ordered because there is no successor to $0$.

The well-orders in $W$ need not respect the natural $\in$ which defines a well-ordering of $\omega$.

-
That clears up the questions I had. Another question... what justifies the use of the supremum in the proof. $ON$ is well ordered, so any set of ordinals with an upper bound should have a least upper bound. What guarantees that the set of order types of well orderings of subsets of $\omega$ has an upper bound at all? – objectivesea Mar 3 '14 at 16:16
Actually, I think I got it. Every set of ordinals has an upper bound because we can just take the union of the set. – objectivesea Mar 3 '14 at 16:19

For (1) After edit: After actually reading the problem, I think Asaf is correct and that $\alpha \preceq X$ should be $\alpha \preceq A$ (that was how I originally read it). So if this is the case, there is a problem, and so your problem is fixed by taking $X = 2 = \{0,1 \}$ with the usual ordering.

For (2), you are getting confused on ordinals and cardinals. For example, what if I order $\omega$ where all the evens come first, and then all the odds. This has order type $\omega + \omega$ and is in $W$. In the end, $W$ will give you all the countable order types, but that exhausts all ordinals up to $\omega_1$.

-
Is $X$ supposed to be $R$ in the first part of your answer? – GME Feb 27 '14 at 7:12
How do you mean? My $X$ is $\{0,1\}$ and $R$ here would be $\in \cap 2 \times 2 = \{ (0,1) \}$. – Ryan Sullivant Feb 27 '14 at 7:16
Nevermind, I see the problem. I read the sentence in the question wrong. I had read $\alpha \preceq X$ as $\alpha \preceq A$. My apologies! – Ryan Sullivant Feb 27 '14 at 7:21
I mean, the OP didn't chose the wrong $X$ (it's supposed to hold for all $X$). Rather, it looks like they chose the wrong $R$. I guess it depends on what Kunen means by "$R$ well-orders $X$". If it implies that the field of $R$ is $X$, then Kunen is wrong. If not, the OP needed to pick a different $R$, not a different $X$. – GME Feb 27 '14 at 7:22
Yes, you are correct. – Ryan Sullivant Feb 27 '14 at 7:23

On (1): see Asaf or Ryan's answer. Since on Kunen's definition $R$ only well-orders $X$ if $X$ is the field of $R$ (at least when $X$ has at least two elements), it's clearly a typo.

On (2): When $X\subseteq \omega$, the type of $(X; R)$ can be bigger than $\omega$. For instance, take $R$ to be the natural ordering on $\omega\setminus\{0\}$ with $0$ added at the end (so that $nR 0$ for all $n\in\omega\setminus\{0\}$). Then $type(\omega; R) = \omega +1$.

Since we can code ordered pairs as natural numbers, we have more drastic examples. For instance, we can define $R$ such that:

$(n,m)R(n', m')$ iff $n< n'$ or $n = n'$ and $m<m'$.

Then the order type of $(\omega; R)$ is $\omega\times\omega$!

-