Uncountable Cardinals without AC

Question

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.

Answer 1

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$.

Answer 2

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$!

Answer 3

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$.