Simple proof showing a subset has smaller cardinal

Question

In Shoenfield, page 254, I read a proof of the following fact: $x \subseteq y \implies Card(x) \le Card(y)$.

Recall

$Card(x)$ is the least ordinal $\alpha$ that is bijective to $x$.

Thus the above inequality just means that $Card(x) = Card(y) \lor Card(x) \in Card(y)$.

Simple proof

The proof uses a remark issued from the proof that the axiom of choice implies Zermelo's theorem. I'm looking for a direct proof which assumes already Zermelo's theorem to be equivalent to the axiom of choice and simple facts about ordinals such as the facts gathered here.

Answer 1

Here is my work on the way Shoenfield proves it. It does not provide an alternative proof. As it can be seen, the procedure doesn't use Zermelo's theorem. As one can see, simplicity comes when understanding that each proof is essentially counting the elements of a particular object using the ordinals.

Count of a set

Every set is equipotent to an ordinal.

Proof

Let $A$ be a set. We are going to count the elements of $A$ and put them in bijection with the elements of some ordinal $\alpha$. First thing to realize is that if we count an element, then we shouldn't count its parts (if they also belong to $A$) because their parts come for free to the ordinal $\alpha$.

So set $\delta = \mathcal{P}(A) \setminus \{\emptyset\}$ and $g$ its choice function. Since $A$ is a set, it cannot be equal to $V$ and there exists $b \notin A$. We will use transfinite recursion to define such an iteration. Here is the function $F: V \to V$: [ F x = \begin{cases} g(A \setminus range(x)) & range(x) \subset A \\ b & otherwise \end{cases} ] here is the corresponding transfinite recursive function $G: On \to V$: [ F \xi = \begin{cases} g(A \setminus range(F \upharpoonright \xi)) & range(F \upharpoonright \xi) \subset A \\ b & otherwise \end{cases} ] Some calculation will show $F 0 = g A \in A$, $F 1 = g(A \setminus g A) \in A \setminus g A$ when $gA \subset A, \ldots$. So we already see that at each iteration we choose a fresh element and that iteration stops when the previously chosen elements exhaust $A$. Iteration has to stop since otherwise that would give an injection $On \to A$ contradicting that $A$ is a set. By transfinite induction, there will be a least stopping ordinal $\alpha$. At that point, $F\upharpoonright_{\alpha}: \alpha \to A$ is an injection and $range(F \upharpoonright_{\alpha}) = \{ F x. x \in \alpha \} \subseteq A$ cannot be a proper subset of $A$, thus $range(F \upharpoonright_{\alpha}) = A$. Thus, $F\upharpoonright_{\alpha}$ is a bijection with $\alpha$.

Count of a set of ordinals

If $x \subset \sigma \in On$ then $\exists \tau \in On. \tau \le \sigma$ and $\tau$ is bijective to $x$.

Proof

The counting theorem on sets gives as an ordinal $\tau$ that is equipotent to $x$ via a counting function $F: \tau \to x$ such that $F(\rho) = g ` (x - range(F \upharpoonright \rho))$. By contradiction, if $\sigma < \tau$ then it is mapped by $F$ to $F `\sigma \in x \subset \sigma \implies F `\sigma < \sigma$. But this doesn't match our intuition that we are counting our set $x$. So let $\rho$ be the least ordinal such that this unordering happens, i.e. $F `\rho < \rho$. Then necessarily $F ` F ` \rho = F ` \rho$. This violates the injectivity of F.

What we wanted

Note that $x$ will be bijective with a subset of $Card(y)$. So by the count of a set of ordinals. There is $\tau \le Card(y)$ bijective to $x$. So $Card(x) \le \tau \le Card(y)$.

Answer 2

The thing here is that not everyone have their copy of Shoenfield's open, or even at reach (maybe it's in the office), or even a copy of the book.

In general, in $\sf ZF$ we say that for two arbitrary sets, the cardinal of $x$ is less or equal the cardinal of $y$ if and only if there is an injection from $x$ into $y$. So if $x\subseteq y$, the identity function is such injection.

Shoenfield's book, in contrast, defines $Card(x)$ as the smallest initial ordinal which is in bijection with $x$. Now the axiom of choice is equivalent to the statement "For every $x$, $Card(x)$ exists".

But you don't need the axiom of choice for most basic cardinal arithmetic results when involving ordinals, and certainly not for this one. Shoenfield's argument is as follows (and I apologise in advance if my notation is different):

1. $x\subseteq y$, so if $f\colon y\to\sigma=Card(y)$ is a bijection, $f\restriction x$ is a bijection between $x$ and a subset of $\sigma$, say $f``x$.
2. Looking at the function mapping $f``x$ to its order-type, say $\chi$, then $\chi$ is an ordinal and $\chi\leq\sigma$.
3. Therefore, $Card(x)=Card(\chi)\leq\chi\leq\sigma=Card(y)$.

The axiom of choice is only used to claim that if $y$ is any arbitrary set, then $Card(y)$ exists. But the proof does not use any more choice than that. And if we consider a broader notion of cardinals which allow for sets which are not well-orderable to have a cardinal (which is not an ordinal, in this case), then the definition of $Card(x)\leq Card(y)$ is aligned with making this statement trivial (although we still need to prove that for initial ordinals the cardinal ordering coincides with the ordinal ordering which coincides with the inclusion ordering).