Is it true that if $I$ is an infinite set, then $I\times \mathbb{N}$ has the same cardinality as $I$? I believe it, but I have minimal background in set theory. My guess is that we can construct an injection from $I\times \mathbb{N}$ to $I,$ but I don't see an obvious way to do so.

  • 3
    For infinite cardinals $\kappa,\lambda$, $\kappa\cdot \lambda=\max\{\kappa,\lambda\}$. – Hayden Feb 26 '14 at 4:06
  • and what is the explicit bijection? – cats Feb 26 '14 at 4:08
  • 2
    The result is true, but it is not obvious, since it requires some amount of the axiom of choice. In some specific cases, the existence of these injections can be established directly, of course (for example, if $I=\mathbb N$, or $\mathbb R$). – Andrés E. Caicedo Feb 26 '14 at 4:08
  • thanks - would you be able to provide an argument, or does it require some extra background? – cats Feb 26 '14 at 4:13
  • One way (that requires some understanding of ordinals) is to well-order $I$, say in type a limit ordinal $\kappa$. Now, use an explicit bijection from $\mathbb N\times \mathbb N$ to $\mathbb N$, to map $\kappa\times\mathbb N$ to $\mathbb N$ by mapping each $\omega$-block $[\omega\alpha,\omega(\alpha+1))\times\omega$ to $[\omega\alpha,\omega(\alpha+1))$. – Andrés E. Caicedo Feb 26 '14 at 4:20
up vote 3 down vote accepted

As mentioned in the comments, the equality of cardinals $\alpha \cdot \beta = \max\{\alpha,\beta\}$ holds when at least one of $\alpha$ and $\beta$ is an infinite cardinal. In particular, if $I$ is infinite with cardinality $\alpha$, then $|I\times\Bbb N| = \alpha\cdot\aleph_0 = \max\{\alpha,\aleph_0\} = \alpha$.

The proofs I've seen of $\alpha \cdot \beta = \max\{\alpha,\beta\}$ all go through the simpler-looking special case $\alpha \cdot \alpha = \alpha$ (again for $\alpha$ infinite). Unfortunately, I don't know a proof of this special case that avoids well-ordering and ordinals, although it's still simpler to prove since one can use transfinite induction on $\alpha$. Fortunately, the derivation of the full case from this special case is easy: if $\alpha > \beta > 1$ then $\alpha \le \alpha + \beta \le \alpha + \alpha = \alpha\cdot2 \le \alpha\cdot\beta \le \alpha\cdot\alpha = \alpha$ (where all inequalities follow easily from definitions); hence we must have $\alpha\cdot\beta=\alpha$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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