Cantor's theorem

In elementary set theory, Cantor's theorem is a fundamental result that states that, for any set A {displaystyle A} , the set of all subsets of A {displaystyle A} (the power set of A {displaystyle A} , denoted by P ( A ) {displaystyle {mathcal {P}}(A)} ) has a strictly greater cardinality than A {displaystyle A} itself. For finite sets, Cantor's theorem can be seen to be true by simple enumeration of the number of subsets. Counting the empty set as a subset, a set with n {displaystyle n} members has a total of 2 n {displaystyle 2^{n}} subsets, so that if c a r d ( A ) = n , {displaystyle { m {card}}(A)=n,} then c a r d ( P ( A ) ) = 2 n {displaystyle { m {card}}({mathcal {P}}(A))=2^{n}} , and the theorem holds because 2 n > n {displaystyle 2^{n}>n} is true for all non-negative integers.Theorem (Cantor). Let f {displaystyle f} be a map from set A {displaystyle A} to its power set P ( A ) {displaystyle {mathcal {P}}(A)} . Then f : A → P ( A ) {displaystyle f:A o {mathcal {P}}(A)} is not surjective. As a consequence, c a r d ( A ) < c a r d ( P ( A ) ) {displaystyle mathrm {card} (A)<mathrm {card} ({mathcal {P}}(A))} holds for any set A {displaystyle A} . In elementary set theory, Cantor's theorem is a fundamental result that states that, for any set A {displaystyle A} , the set of all subsets of A {displaystyle A} (the power set of A {displaystyle A} , denoted by P ( A ) {displaystyle {mathcal {P}}(A)} ) has a strictly greater cardinality than A {displaystyle A} itself. For finite sets, Cantor's theorem can be seen to be true by simple enumeration of the number of subsets. Counting the empty set as a subset, a set with n {displaystyle n} members has a total of 2 n {displaystyle 2^{n}} subsets, so that if c a r d ( A ) = n , {displaystyle { m {card}}(A)=n,} then c a r d ( P ( A ) ) = 2 n {displaystyle { m {card}}({mathcal {P}}(A))=2^{n}} , and the theorem holds because 2 n > n {displaystyle 2^{n}>n} is true for all non-negative integers. Much more significant is Cantor's discovery of an argument that is applicable to any set, which showed that the theorem holds for infinite sets, countable or uncountable, as well as finite ones. As a particularly important consequence, the power set of the set of natural numbers, a countably infinite set with cardinality ℵ0 = card(ℕ), is uncountably infinite and has the same size as the set of real numbers, a cardinality larger than that of the set of natural numbers that is often referred to as the cardinality of the continuum: ? = card(ℝ) = card(?(ℕ)). The relationship between these cardinal numbers is often expressed symbolically by the equality and inequality c = 2 ℵ 0 > ℵ 0 {displaystyle {mathfrak {c}}=2^{aleph _{0}}>aleph _{0}} . The theorem is named for German mathematician Georg Cantor, who first stated and proved it at the end of the 19th century. Cantor's theorem had immediate and important consequences for the philosophy of mathematics. For instance, by iteratively taking the power set of an infinite set and applying Cantor's theorem, we obtain an endless hierarchy of infinite cardinals, each strictly larger than the one before it. Consequently, the theorem implies that there is no largest cardinal number (colloquially, 'there's no largest infinity').