Exercise · ZW-INFINITE-SET-009 · ★★★ Advanced
Let \(f(n)=n+1\) from \(\mathbb{N}\) to \(\mathbb{N}\). Why does it prove that \(\mathbb{N}\) is infinite?
Choose one option.
A Because \(f\) is not injective B Because \(f\) is injective but not surjective, and a finite set admits no injection into a proper subset of itself C Because \(f\) maps \(\mathbb{N}\) into \(\{1,2,\dots\}\), which proves that \(\mathbb{N}\) is countable D Because \(f\) is bijective, and that implies infinitude Show answer B. Because \(f\) is injective but not surjective, and a finite set admits no injection into a proper subset of itself← Back to the question
Explanation If \(\mathbb{N}\) were finite, it could not admit an injection into a proper subset of itself, yet \(f\) is one. That contradiction is the idea of the proof.
A set \(A\) is infinite if it is not finite, that is, if there is no bijection between \(A\) and \(\{1,\dots,n\}\) for any \(n\in\mathbb{N}\).
\[A\not\sim\{1,\dots,n\}\ \ \forall n\in\mathbb{N}\]
More practice problems: infinite set