Editing Cardinality (section)

=== Uncountable sets ===
{{Main|Uncountable set}}
[[File:Diagonal argument powerset svg.svg|thumb|250px|<math>\N</math> does not have the same cardinality as its [[power set]] <math>\mathcal{P}(\N)</math>: For every function ''f'' from '''<math>\N</math>''' to <math>\mathcal{P}(\N)</math>, the set <math>T = \{n \in N : n \notin f(n) \}</math> disagrees with every set in the [[range of a function|range]] of <math>f</math>, hence <math>f</math> cannot be surjective. The picture shows an example <math>f</math> and the corresponding <math>T</math>; {{color|#800000|'''red'''}}: <math>n \notin T</math>, {{color|#000080|'''blue'''}}: <math>n \in T</math>.]]A set is called ''[[uncountable]]'' if it is not countable. That is, it is infinite and strictly larger than the set of natural numbers. The usual first example of this is the set of [[real numbers]] <math>(\R)</math>, which can be understood as the set of all numbers on the [[number line]]. One method of proving that the reals are uncountable is called [[Cantor's diagonal argument]], credited to Cantor for his 1891 proof,<ref name="Cantor.1891">{{cite journal |author=Georg Cantor |year=1891 |title=Ueber eine elementare Frage der Mannigfaltigkeitslehre |url=https://www.digizeitschriften.de/dms/img/?PID=GDZPPN002113910&physid=phys84#navi |journal=[[Jahresbericht der Deutschen Mathematiker-Vereinigung]] |volume=1 |pages=75–78}} English translation: {{cite book |title=From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Volume 2 |publisher=Oxford University Press |year=1996 |isbn=0-19-850536-1 |editor-last=Ewald |editor-first=William B. |pages=920–922}}</ref> though his differs from the more common presentation.

It begins by assuming, [[Proof by contradiction|by contradiction]], that there is some one-to-one mapping between the natural numbers and the set of real numbers between 0 and 1 (the interval <math>[0,1]</math>). Then, take the [[decimal expansion]]s of each real number, which looks like <math>0.d_1d_2d_3...</math> Considering these real numbers in a column, create a new number such that the first digit of the new number is different from that of the first number in the column, the second digit is different from the second number in the column and so on. We also need to make sure that the number we create has a unique decimal representation, that is, it cannot end in [[0.999...|repeated nines]]. For example, if the digit isn't a 7, make the digit of the new number a 7, and if it was a seven, make it a 3.<ref>{{Cite book |last=Bloch |first=Ethan D. |url=https://link.springer.com/book/10.1007/978-1-4419-7127-2 |title=Proofs and Fundamentals |date=2011 |publisher=Springer Science+Business Media |series=Undergraduate Texts in Mathematics |pages=242–243 |language=en |doi=10.1007/978-1-4419-7127-2 |isbn=978-1-4419-7126-5 |issn=0172-6056 |archive-url=https://archive.org/details/proofsfundamenta0002bloc/ |archive-date=2022-01-22}}</ref> Then, this new number will be different from each of the numbers in the list by at least one digit, and therefore must not be in the list. This shows that the real numbers cannot be put into a one-to-one correspondence with the naturals, and thus must be strictly larger.<ref>{{Cite book|last1=Ashlock |first1=Daniel |last2=Lee |first2=Colin |date=2020 |title=An Introduction to Proofs with Set Theory |url=https://link.springer.com/book/10.1007/978-3-031-02426-9 |publisher=Springer Cham |series=Synthesis Lectures on Mathematics & Statistics |language=en |pages=181–182 |doi=10.1007/978-3-031-02426-9 |isbn=978-3-031-01298-3 |issn=1938-1743}}</ref>

Another classical example of an uncountable set, established using a related reasoning, is the [[power set]] of the natural numbers, denoted <math>\mathcal{P}(\N)</math>. This is the set of all [[subsets]] of <math>\N</math>, including the [[empty set]] and <math>\N</math> itself. The method is much much closer to Cantor's original diagonal argument. Consider any function <math>f: \N \to \mathcal{P}(\N)</math>. One may define a subset <math>T \subseteq \N</math> which cannot be in the image of <math>f</math> by: if <math>1 \in f(1)</math>, then <math>1 \notin T</math>, and if <math>2 \notin f(2) </math>, then <math>2 \in T</math>, and in general, for each natural number <math>n</math>, <math>n \in T</math> if and only if <math>n \notin f(n) </math>. Then if the subset <math>T = f (t)</math> was in the image of <math>f</math>, then <math>t \in f (t) \iff t \notin f (t)</math> a contradiction. So <math>f</math> cannot be surjective. Therefore no bijection can exist between <math>\N</math> and <math>\mathcal{P}(\N)</math>. Thus <math>\mathcal{P}(\N)</math> must be not be countable. The two sets, <math>\R</math> and <math>\mathcal{P}(\N)</math> can be shown to have the same cardinality (by, for example, assigning each subset to a decimal expansion). Whether there exists a set <math>A</math> with cardinality between these two sets <math>|\N| < |A| < |\R|</math> is known as the [[continuum hypothesis]].

[[Cantor's theorem]] generalizes the second theorem above, showing that every set is strictly smaller than its powerset. The proof roughly goes as follows: Given a set <math>A</math>, if <math>f</math> is a function from <math>A</math> to <math>\mathcal{P}(A)</math>, let the subset <math>T \subseteq A</math> be given by <math>T = \{ a \in A : a \notin f(a) \}</math>. If <math>T = f (t)</math>, then <math>t \in f (t) \iff t \notin f (t)</math> a contradiction. So <math>f</math> cannot be surjective and thus cannot be a bijection. So <math>|A| < |\mathcal{P}(A)|</math>. (Notice that a trivial injection exists -- map <math>a</math> to <math>\{ a \}</math>.) Further, since <math>\mathcal{P}(A)</math> is itself a set, the argument can be repeated to show <math>|A| < |\mathcal{P}(A)| < |\mathcal{P}(\mathcal{P}(A))|</math>. Taking <math>A = \N</math>, this shows that <math>\mathcal{P}(\mathcal{P}(\N))</math> is even larger than <math>\mathcal{P}(\N) </math>, which was already shown to be uncountable. Repeating this argument shows that there are infinitely many "sizes" of infinity.