2

I suppose the answer is trivially no, but I haven't actually seen it stated precisely this way in the general. I've only seen specific cases, such as the proof by Cantor's diagonal argument that $\nexists f$ such that $f:\mathbb{N} \mapsto [0,1]$ is a bijection.

Here is my attempt at a proof. Is it correct?

  1. Let $S_c$ be a countably infinite set, and let $S_u$ be an uncountably infinite set.
  2. By definition of countably infinite sets, $\exists f$ such that $f:S_c \mapsto \mathbb{N}$ is a bijection.
  3. By definition of uncountably infinite sets, $\nexists g$ such that $g:S_u\mapsto\mathbb{N}$ is a bijection.
  4. Suppose $\exists h$ such that $h:S_c \mapsto S_u$ is a bijection.
  5. Since a function is a bijection iff it has an inverse that is also a bijection, $\exists h^{-1}$ such that $h^{-1}:S_u \mapsto S_c$ is a bijection.
  6. Let $k = f \circ h^{-1}$, in which case $\exists k$ such that $k:S_u \mapsto \mathbb{N}$.
  7. Since the composition of two bijections is a bijection, $k:S_u \mapsto \mathbb{N}$ is a bijection.
  8. But this contradicts (3), which says there cannot be a bijection from $S_u$ to $\mathbb{N}$.
  9. Therefore by contradiction, $\nexists h$ such that $h:S_c \mapsto S_u$ is a bijection.
Andrés E. Caicedo
  • 79,201
Ben Simmons
  • 465

1 Answers1

4

Yes, although you may find it more straightforward to prove the positive form of the statement:

By definition, a set is countably infinite if it has a bijection with $\mathbb N$. If $X$ is countably infinite and has a bijection with $Y$, then composing gives us a bijection between $Y$ and $\mathbb N$, so $Y$ is also countably infinite.

Chris Culter
  • 26,806