Infinite Set has Countably Infinite Subset/Proof 1

From ProofWiki
Jump to: navigation, search

Theorem

Every infinite set has a countably infinite subset.


Proof

Let $S$ be an infinite set.

We use Between Two Sets Exists Injection or Surjection.


Suppose that there exists an injection $\psi: \N \to S$.

Let $T$ be the image of $\psi$.

From Injection to Image is Bijection, it follows that $\psi^{-1}: T \to \N$ is a bijection.

Hence, $T$ is a countably infinite subset of $S$.


Now, suppose that that there exists a surjection $\phi: \N \to S$.

From Surjection from Natural Numbers iff Countable, it follows that $S$ is countably infinite.

So, from Set is Subset of Itself, we have that $S$ is a countably infinite subset of $S$.

$\blacksquare$


Axiom of Choice

This proof depends on the Axiom of Choice, by way of Between Two Sets Exists Injection or Surjection.

Because of some of its bewilderingly paradoxical implications, the Axiom of Choice is considered in some mathematical circles to be controversial.

Most mathematicians are convinced of its truth and insist that it should nowadays be generally accepted.

However, others consider its implications so counter-intuitive and nonsensical that they adopt the philosophical position that it cannot be true.