3
$\begingroup$

I see the following definition of cardinal number in notes:

An ordinal $\alpha$ is a cardinal number if $|\beta|<|\alpha|$ for all $\beta\in\alpha$.

Why $\omega+1$ and $\omega^2$ are not cardinal numbers?

For $\omega+1$, is it because $\omega\in\omega+1$ but $|\omega|=|\omega+1|$?

$\endgroup$
4
$\begingroup$

It is precisely because $| \omega | = | \omega + 1 | = | \omega^2 |$ (and $\omega < \omega+1 < \omega^2$). Perhaps to make this clear, we can define well-orderings on $\mathbb{N}$ with these prescribed order-types (meaning that the underlying set of any well-ordering with these order-types is countably infinite; i.e., equinumerous to $\omega$):

  • $\omega + 1$ is the order type of the following well-ordering on $\mathbb{N}$: $$m \preceq n \Leftrightarrow \begin{cases} 0 < m \leq n, &\text{or} \\ n = 0 \end{cases}$$ So this well-order looks like $$ 1 \preceq 2 \preceq 3 \preceq \cdots \preceq 0$$

  • $\omega^2$ is the order-type of the following well-ordering on $\mathbb{N}$: $$m \preceq n \Leftrightarrow \begin{cases} m = 0, &\text{or} \\ ( \forall i ) ( 2^i \mid m \leftrightarrow 2^i \mid n ) \wedge m \leq n, &\text{or} \\ ( \exists i ) ( 2^i \not\mid m \wedge 2^i \mid n) \wedge n \neq 0 \end{cases}$$ So this well-order looks like $$0 \preceq 1 \preceq 3 \preceq 5 \preceq \cdots \preceq 2 \preceq 6 \preceq 10 \preceq \cdots \preceq 4 \preceq 12 \preceq 20 \preceq \cdots $$

$\endgroup$
2
$\begingroup$

Indeed, we have $\omega\in\omega+1$ and $\omega\in\omega^2,$ but $|\omega+1|=|\omega|$ and $|\omega^2|=|\omega|^2=|\omega|.$

$\endgroup$
  • $\begingroup$ Why $|\omega^2|=|\omega|^2$? Could you prove it? $\endgroup$ – setvomega Dec 4 '13 at 18:43
  • $\begingroup$ Certainly. What is your definition of ordinal exponentiation? $\endgroup$ – Cameron Buie Dec 4 '13 at 18:47
  • $\begingroup$ $\omega^2=\omega\cdot\omega$ is the unique ordinal isomorphic to the lexicographic order of $\omega\times\omega$. $\endgroup$ – setvomega Dec 4 '13 at 19:29
  • $\begingroup$ By the same token, $|\omega|^2$ is the unique cardinal in bijection with $|\omega|\times|\omega|.$ Now, if $A$ and $B$ are sets of (respective) cardinality $\kappa,\lambda,$ then letting $f:A\to\kappa$ and $g:B\to\lambda$ be bijections, we can readily define a bijection $h:A\times B\to\kappa\times\lambda$ by $$h(a,b)=\bigl(f(a),g(b)\bigr),$$ so $$|A\times B|=\kappa\times\lambda=|A|\times|B|$$ in general. In particular, when $A=B=\omega,$ we find that $|\omega^2|=|\omega|^2.$ $\endgroup$ – Cameron Buie Dec 4 '13 at 21:35
2
$\begingroup$

Remember these two theorems:

  1. The union of two countable sets is countable.
  2. The product of two countable sets is countable.

Now we have that $\omega+1$ is the union of a countable set with a finite set; and $\omega^2$ is order isomorphic to the product $\omega\times\omega$ with the lexicographic order. Therefore the underlying sets of both these ordinals are countable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.