Cantor's diagonal argument: Difference between revisions
no edit summary
RhubarbJayde (talk | contribs) (Created page with "Cantor's diagonal argument is a method for showing the uncountability of the set of real numbers. It is a proof by contradiction - one assumes that, towards contradiction, there is a bijection from the natural numbers to the real numbers, and then one constructs a real number not in the range of this function, which contradicts surjectivity. It may be rephrased as the assertion that every function from the naturals to the reals is non-surjective,...") |
RhubarbJayde (talk | contribs) No edit summary |
||
Line 5:
The proof is known as the "diagonal argument" because of a common visual representation. Namely, one writes out the decimal expansions of all the supposed real numbers on a grid, so that \(f(n)[m]\) is equal to the entry at the \(m+1\)st column and \(n+1\)st row, and then constructs a new real number by "inverting" the decimal expansion of the diagonal.
The conclusion can be strengthened to show that just the real interval \([0,1]\) is uncountable.
== P(N) ==
Line 12:
Assume \(f: \mathbb{N} \to \mathcal{P}(\mathbb{N})\) is a supposed function enumerating the entirety of the powerset of the natural numbers. We define a set \(X\) like so: \(n \in X\) iff \(n \notin f(n)\). Now, since \(f\) is surjective, there is some \(m\) so that \(f(m) = X\). Then, we have \(m \in X\) iff \(m \notin f(m)\) iff \(m \notin X\). This is impossible!
And this can be
The general form of diagonalization-type arguments is similar to the barber paradox, or, more precisely, Russel's paradox.
| |||