Some meaning can be made of this question by assuming that the concept of "having the same number of elements as" is equivalent to that of a one-to-one or bijective correspondence. This notion is reasonable, since if S and T are in bijective correspondence, then each element of S is associated to a unique element of T, and vice versa. Let S and T be sets. Write S ~ T if there is a bijective map between S and T.

For technical reasons, ~ is not an equivalence relation. (On what set is the relation being defined, the set of sets?) It is nonetheless easy to check that the following three properties hold, which imply that the the collection of sets will be partitioned into subclasses with the property that any two sets in a given subclass are in one-to-one correspondence.

Exercise. For sets A, B, and C, ~ satisfies the following three properties

(a) A ~ A,

(b) If A ~ B, then B ~ A.

(c) If A ~ B and B ~ C, then A ~ C.

Exercise. Let cl(S) denote the collection of all sets which are in bijective correspondence with S. Show that if S and T are not in bijective correspondence, then cl(S) and cl(T) have no sets in common.

Definition. cl(S) is called the cardinal number of S.

The cardinal number of a set can be thought of as telling how many elements are in the set. For example, cl({1,2,3}) consists of all sets in bijective correspondence with {1,2,3}, which are those sets with three elements.

The first question is whether all infinite sets have the same cardinal number. This is answered by a theorem of Cantor.

Theorem. (Cantor) For any set S, there is no bijective correspondence between S and the power set of S.

Proof. Let P(S) denote the power set of S and assume that j: S ® P(S) is surjective. For each s in S, j(s) = T Í S, so either s Îj(s)or sÏj(s). Let A = {s Î S | s Ïj(s)}. Since j is assumed to be surjective, A = j(c), for some c ÎS. If c Î A, then by definition of A, c Ïj(c)= A. Hence c  Ï A = j(c), which means that cÎA, another contradiction. Thus j cannot be surjective, and we have shown that there is no surjective mapping of S onto P(S), so, in particular, no bijective correspondence. ·

The theorem implies that there are different infinite cardinals, since cl(S) and cl(P(S)) must be distinct. Because all the elements of S are in P(S) as a singleton set (a set with only one element), one would like to say that cl(S) < cl(P(S)), in the same sense that n < 2ⁿ.

Definition: cl(S) £ cl(T) if for A Î cl(S) and B Î cl(T) there is an injective mapping of A into B.

Exercise: If cl(A) £ cl(B) and cl(B) £ cl(C), then cl(B) £ cl(C).

Exercise: cl(S) £ cl(P(S)).

The definition leaves open the awkward possibility that cl(S) £ cl(T) and cl(T) £ cl(S) while cl(S) ¹ cl(T); that is, there may exist an injective mapping of S into T and an injective mapping of T into S but no bijective correspondence between S and T. That this cannot happen is the content of the Schroeder-Bernstein Theorem.

Theorem. (Schroeder-Bernstein) If cl(S) £ cl(T) and cl(T) £ cl(S) for sets S, T, then cl(S) = cl(T).

The theorem will follow easily from the following lemma.

Lemma: Let A be a set, B a subset of A. If there exists an injective map j: A ® B, then there exists a bijective map y: A ® B.

Note: Note that  in the case that B is a subset of A, we clearly have cl(B) £ cl(A).   This lemma shows that the Schroeder-Bernstein Theorem holds in this special case. We'll see below that this special case is all that's needed.

Proof: If A = B, then putting y  to be the identity map satisfies our needs. So suppose that B is a proper subset of A. Let j⁰ be the identity map on A. Define j ⁱ: A® A, for i > 0, to be the composition of j with itself  i-many times. Let C₀ = j⁰(A - B) = A - B. Define C_i Í B, for i > 0, by C_i  = j(C_i-1) = j ⁱ(C₀). Finally set C to be the union of the C_i , for all i. Now define y as follows.

Let's see that this map does the job. First let's show that y is surjective. Let b Î B. If b Ï C, then b = y(b). Suppose that b Î C. Then b Î C_i, for some i. Thus there exists a Î C_i-1 with j(a) = b and so y(a) = b. Therefore y is surjective.

Next let's show that y is injective. Notice that y maps C to itself , and A - C to itself. Let a, a' be distinct elements of A. If a and a' are not both in C or not both in A -- C, then y(a) and y(a') are unequal. If both a and a' are in A - C, then y(a) = a which is unequal to a' = y(a'). If both a and a' are from C, then y(a) = j(a) and y(a') = j(a'). As j is injective j(a) is unequal to j(a'). Therefore y is injective. This proves the lemma. ·

We can now prove the theorem as follows. Let j: A ® B, and y: B ® A be injective. Then it is easy to see that the composition yj: A ® y(B) is an injective map. As y(B) is a subset of A, there is, by the lemma, a bijective map l from A to y(B). As y, viewed as a map from B to y(B) is bijective, there exists an inverse y ^-1:y(B) ® B. It is now easy to see that the composition y^-1l is a bijection between A and B. ·