Welcome to Gaia! ::

Your conclusion is correct, but your reasoning is not. Think about how one would be able to determine whether or not two sets are equinumerous For example, let X = {1,2,3}, Y = {a,b,c}, and Z = {bob,fred}. Take the elements of X and Y and pair them up: {(1,a),(2,c),(3,b)} (there are six ways of doing so; this is just one of them) such that each member of X is paired with exactly one member of Y and vice versa. Mathematically, this is called a bijection. Since it is possible to pair up X and Y this way, they are equinumerous. It is not possible to pair up X and Z in this manner, so that X and Z are not equinumerous.

Now, are the intervals [1,2] and [1,3] equinumerous? Absolutely. There are infinitely many bijections between them, but we only need one: say, f(x) = 2x-1. Therefore, there is "the same amount" of numbers between 1 and 2 as between 1 and 3.

There is also the same amount of rational numbers as whole numbers, but it does not mean that all infinities are the same. On the contrary, it is possible to prove that there are more real numbers than whole numbers, and hence also more than rational ones. The most famous method of proving it is called Cantor diagonalization, although alternative methods such as using the Baire category theorem exist.

Correct. The abive two sets have the same cardinality, i.e., are equinumerous. Moreover, the interval [0,1] is equinumerous with the entire real line. In the case of the open interval, this is actually obvious--just map (0,1) to (-inf,inf) via some function like f(x) = tan(π(x-1/2)) or somesuch. Constructing an explicit bijection between [0,1] and R is a bit tricker, but can be done a rather numerous number of ways. In ZFC, its existence is a very straightforward corollary of the Cantor-Bernstein-Schröder theorem.


No. The power set is not equinumerous with the original set, for example. Every bijection is also a surjection, i.e., its range is the entire codomain. Given a set A, consider any f:A→P(A), and define the set B = {a in A: a is not in f(a)}. Then clearly B is in P(A) but is not the image of any b in A, so that f is not surjective. This is called Cantor diagonalization and holds regardless of whether A is finite or infinite. Therefore, the power set operation applied to an infinite set constructs a set with a 'higher order' of infinity, at least in ZFC or stronger. In pure ZF set theory, the cardinalities of sets may simply be incomparable.

For a set A, the power set P(A) is the set containing all the subsets of A, including A.
For example, if A = {0, 1} then P(A) = {{}, {0}, {1}, {0, 1}}. Note that the size of the power set, |P(A)|, is equal to 2^|A|.

Consider Neko's construction then. B = {a in A: a is not in f(a)} is a subset of A and contains at least the preimage of the empty-set in P(A) if such a preimage exists. The important part is that B is well-defined.
Because B is a subset of A, B is in P(A).
Suppose there were some element b such that f(b) = B. If b were contained in B, then b would be contained in f(b), but no element a in B is contained in f(a), so b cannot be in B.
If, however, b were not in B, then b would not be in f(b), and thus b would have to be in B.
Therefore there cannot be such a b. Thus B does not correspond to any element in A. Since this construction does not rely on any particular f, for any function from A to P(A), there exists such a set B in P(A), and thus P(A) cannot be equinumerous to A, but must in fact be larger than it.

The proof that P(A) is larger than A even for infinite sets is called Cantor diagonalization. The connection between it and the standard proof that the set of reals is larger than the set of naturals is very straightforward. Consider the set of reals in [0,1], for example, and represent them in binary. The proof actually works in any natural base of more than 1, but binary makes the connection explicit later on. This representation is not unique, e.g., 0.1000... = 0.0111... (analogously in decimal, 0.1000.. = 0.0999...), but those cases can be easily removed from consideration, either explicitly or by positing that a certain type of representation is preferred. The proof then proceeds thusly: if you have a function f:N→(0,1), consider the binary digits of
f(0) = . a_00 a_01 a_02 ...
f(1) = . a_10 a_11 a_12 ...
f(2) = . a_20 a_21 a_22 ...
... etc., and construct the number a defined by its nth digit as a_n = 1-(a_{nn}). Then clearly a differs from each number f(n) in the list on the nth digit, and thus is not on the list, and therefore f is not a surjection. Note that a_nn is the diagonal of this gigantic list, which is why it is called "diagonalization."

The connection with the set-theoretic Cantor diagonalization is then straightforward. Each member of B of P(A) is a subset of A, which can be described as a characteristic function χ_B:A→{0,1} defined by χ_B(x) = 1 iff x in B. Thus, the only difference with the binary real number case, other than a few (countably few) cases of alternative representations, is that real numbers have digits indexed by the natural numbers, whereas the subsets have 'digits' indexed by members of A. No order on A is implied.


The initialism ZF stands for Zermelo-Fraenkel, the standard axiomatization of set theory. The extra C in ZFC is the system of Zermelo-Fraenkel axioms appended by the axiom of choice. Almost all of mathematics is reducible to ZFC or equivalent, although it has a few competitors.

I thought Cantor diagonalization was a general process, simply noting that any set that can be formed in a sequence or an array is at most countable. I've seen it used in the proof that the real numbers are uncountable, but I just didn't make the generalized connection.

Of your list, the only one I haven't seen a proof of before is (2). I understand how you could impose an injective function between [0,1] and (0,1), but not a surjective one...I can think of a bijection between [0,1] and [/epsilon,1-/epsilon], but I know in analysis that's a terrible no-no.

Why is the subset B re-interpreted as a function, and what will that function read? I'm not understanding the purpose of this for some arbitrary subset B.

So in short, the diagonalization process becomes a set algorithm for proving that no bijection between A and B exist? Perhaps I'm simply not seeing how this diagonalization is applied explicitly.