Proofs of Theorems

Proof that a Dedekind-infinite set contains a set just as large as the natural numbers.

If we let \(f\) be such a bijection between a set and some proper subset of itself, and let \(x\) be an element of the set that is not in that proper subset, then we can consider the sequence \(x, f(x), f(f(x)), f(f(f(x))),\ldots\) We can then define a function \(g\) from the natural numbers to this sequence, by letting \(g(0)=x\), and for any \(n, g(n+1)=f(g(n))\). This function is defined for every natural number, and is one-to-one, and so it shows that this sequence has just as many elements as the set of natural numbers. (To see that it is one-to-one, assume not, so there would be two numbers \(m\lt n\) such that \(g(m)=g(n)\). Since \(f\) is one-to-one, if \(m\) and \(n\) were both non-zero, then we would have \(g(m-1)=g(n-1).\) By taking the earliest such pair, we would have \(g(0)=g(n-m).\) But \(g(0)=x,\) and \(x\) is not in the subset to which \(f\) maps all elements, while if \(n-m\gt 0\), then \(g(n-m)\) is. So this is impossible.)

Proof that the cardinality of the positive real numbers is strictly greater than the cardinality of the positive integers.

This proof and the next one follow Cantor’s proofs. Suppose, as hypothesis for reductio, that there is a bijection between the positive integers and the real numbers between 0 and 1. Given that there is such a bijection, there is a list of the real numbers between 0 and 1 of the following form (where d\(_{ij}\) is the \(j\)th digit in the decimal representation of the \(i\)th real number on our list:

1. \(0.\rd_{11}\rd_{12}\rd_{13}\ldots \rd_{1k}\ldots\)
2. \(0.\rd_{21}\rd_{22}\rd_{23}\ldots \rd_{2k}\ldots\)
\(\vdots\)
\(n\). \(0.\rd_{n1}\rd_{n2}\rd_{n3}\ldots \rd_{nk}\ldots\)
\(\vdots\)

By hypothesis, every real number between 0 and 1 appears exactly once on this list. But consider the real number \(r = 0.\rd_1 \rd_2 \rd_3\ldots\rd_n\ldots\), where \(\rd_i =\rd_{nn}+1\) if \(\rd_{nn} \in \{0,1,2,3,4,5,6,7\}\) and \(\rd_i =\rd_{nn} -1\) otherwise. Since \(r\) differs from the \(n\)th number in the list in the \(n\)th digit, \(r\) is clearly not a number on our list. So we can conclude, by reductio, that there is no bijection between the positive integers and the real numbers between 0 and 1.

Proof that the cardinality of a power set is strictly greater than the cardinality of the set itself.

Suppose, as hypothesis for reductio, that there is a set \(N\) for which the cardinality of \(P(N)\)—the power set of \(N\)—is the same as the cardinality of \(N.\) Given this assumption, there is a bijection \(I\) from \(P(N)\) to \(N\) such that (i) for each \(s \in P(N),\) there is a unique member \(I(s)\in N,\) and (ii) for each \(r \in N,\) there is a unique member \(I^-(r) \in P(N)\) under the inverse of our bijection, \(I^-.\) But we can construct a member \(M \in P(N)\) that is not mapped onto by any member of \(N\) under the mapping \(I^-\): for each \(r\in N,\) \(r\in M\) iff \(r\not\in I^-(r).\)

So we can conclude that it is not the case that there is a set \(N\) for which the cardinality of \(P(N)\) is the same as the cardinality of \(N\). But it is obvious that the cardinality of \(P(N)\) is not smaller than the cardinality of \(N\) (because \(P(N)\) includes all of the unit sets of members of \(N\), and more besides). So the cardinality of the power set of a set is strictly greater than the cardinality of the set itself.