The set of sets that are equipolent are equivalence classes. Cardinal numbers are simply the equivalence classes under the relation of equipolency. One establishes the cardinality of a finite set by putting it into a one-to-one correspondence with one of the sets, {1}, {1, 2}, {1, 2, 3}, ... In other words one counts the elements of the set.

The Addition of Cardinal Numbers

Let n₁ and n₂ be cardinal numbers. There are then sets A₁ and A₂ such that #(A₁) = n₁ and #(A₂) = n₂. It is essential that A₁ and A₂ be disjoint. From A₁ and A₂ we can create A'₁= {(a₁,1)|a₁∈A₁}=A₁×{1} and A'₂={(a₂,2)|a₂∈A₂}=A₂×{2}. The sum of cardinals is the cardinality of the union of the representative sets for the cardinals; i.e.,

n₁ + n₂ = #(A'₁) + #(A'₂)
= #(A'₁∪A'₂)

To be rigorous we must establish that addition of cardinals is well defined. This means that we must show that if

#(A'₁) = #(A"₁) and
#(A'₂) = #(A"₂)
then #(A'₁∪A'₂) = #(A"₁∪A"₂)

To do this consider an element x from #(A'₁∪A'₂). Let f₁ be the one-to-one function from A'₁ to A"₁) and f₂ be the one-to-one function from A'₂ to A"₂. The one-to-one onto function from A'₁∪A'₂ to A"₁∪A"₂ is then merely f₁ on A'₁ and f₂ on A'₂.

Infinite Cardinal Numbers

If a set can be put into a one-to-one correspondence with the natural numbers it is said to be countably infinite or denumerable. The cardinality of the natural numbers {0, 1, 2, 3, ... } is denoted as aleph null, ₀. If a set is finite or denumerable it is said to be countable.

The original definition of infinite is "not finite," meaning "cannot be put into a one-to-one correspondence with any finite set. Another criteria of infiniteness is whether a set contains a proper subset that can be put into a one-to-one correspondence with the set itself. It is easy to establish that if a set is equipotent to a proper subset of itself then it cannot be finite. The proof is by contradiction. Suppose a set S has one-to-one correspondences with a proper subset T and with a finite set {1,2,...,n}. Then there is a one-to-one correspondence between the proper subset T and the finite set. But since T is a proper subset of S there exists an element of S which does not belong to T, call it u. This would mean there would be a one-to-one correspondence between T∪{u} and {1,2,..,n,n+1} and hence between {1,2,..,n} and {1,2,..,n+1}. Therefore S cannot be finite.

The other proposition of interest is that if a set is not finite there exists a one-to-one correspondence between the set and one of its proper subsets.

This property of infinite sets provide the basis for some amusing illustrations. N. Ya. Vilenkin in his Stories About Sets hypothesizes a hotel with an infinite number of rooms. When a hotel with a finite number of rooms is filled any new customers have to be turned away. For an infinite hotel that is filled new customers still can be accomodated. The occupant in the first room is moved to the second room. The second room's occupant is moved to the third room and so on. The new customer can then be put in the first room. If n new customers show the present occupant of room i can be moved to room n+i for all values of i, thus freeing up space for the n new customers. If an infinite number of new customers arrive they also can be accomodated by moving the present occupant of any room, say room i, is moved into room 2i thus freeing up all of the odd numbered rooms for the infinity of new customers.

The Ordering of Cardinal Numbers

If a set A can be put into a one-to-one correspondence with a subset of set B then the cardinality of A is less than or equal to the cardinality of set B; #(A)≤#(B). If set B can also be put into a one-to-one correspondence with a subset of set A then it can be shown that set A and set B have the same cardinality (The Schroeder-Bernstein Theorem).

For sets there is:

The Law of Trichotomy:

For any two sets A and B exactly one of the following three possibilities is true:

• #(A) < #(B)
• #(A) = #(B)
• #(A) > #(B).

 

Cantor showed (Cantor's Theorem) that for any set A, the cardinality of the set of all subsets of A is strictly greater than the cardinality of A. The set of all subsets of A is called the Powerset of A, which is denoed as P(A). Thus Cantor's Theorem is that #(A) < #(P(A)). Thus for any cardinal number we can find a larger cardinal number.

The Addition of Infinite Cardinal Numbers

Since addition of cardinal numbers is well defined we can find the sum of any two cardinal numbers, n₁ and n₂, by finding any two disjoint sets A₁ and A₂ such that #(A₁) = n₁ and #(A₂) = n₂ and finding the cardinality of their union. For example, if n₁ is a finite number n and n₂ = ₀ then we find their sum by choosing two disjoint sets such that the cardinality of one set is equal to n and the cardinality of the other set is equal to ₀ and then find the cardinality of the union of the two sets. The following demonstrates that the sum of n and ₀ is equal to ₀.

#({1,2,3,...,n})=n and
#({n+1,n+2,...}) = ₀
#({1,2,3,...,n}∪{n+1,n+2,...}) =
#({1,2,3,...})=₀

We find that ₀ + ₀ = ₀ because we can use the set of odd numbers to represent the first ₀ on the left and the set of even numbers to represent the second ₀ on the left. The union of the odd numbers and even numbers gives the set of positive integers which has the cardinality of ₀.

#({1,3,5,...}) = ₀
#({2,4,6,...}) = ₀
so
₀ + ₀ =
#({1,3,5,...})∪ {2,4,6,..}) =
#({1,2,3,...}) = ₀

Note that cancellation does not apply in the matter of infinite cardinal numbers; i.e. a+c = b+c does not imply that a=b.

The sum of two transfinite cardinal numbers is equal to the larger of the two. The cardinality of the real numbers is greater than ₀ so the sum of the cardinality of the real number, usually denoted by a script c and ₀ is equal to the cardinality of the real numbers.

Multiplication of Cardinal Numbers

Multiplication of two cardinal numbers is defined as the cardinality of the Cartesian product of two sets having cardinalities equal to the two cardinals. Let n₁ and n₁ be two cardinals and let A₁ and A₁ such that #(A₁) = n₁ and #(A₂) = n₂. There is no necessity that A₁ and A₂ be disjoint. The product of n₁ and n₂ is defined as:

n₁*n₂ = #(A₁)*#(A₂)
= #(A₁×A₂)

The Cartesian product of the set of positive integers may be enumerated in a systematic manner as indicated below. This establishes that the set of ordered pairs of positive integers has the same cardinality as the set of positive integers, ₀.

The indicated pattern for the enumeration of the ordered pairs of integers establishes a one-to-one correspondence between the set positive integers P and the set of pairs of positive integers, P×P. Thus #(P×P)=#(P) and hence ₀*₀= ₀. This obviously implies that for any finite cardinal n

₀ⁿ = ₀.

Exponentiation of Cardinal Numbers

Raising one cardinal number to a power equal to that of another cardinal number can defined defined in terms of the set of functions mapping from one set into another. Let the notation B^A denoted the set of all functions from a domain of set A to a range of set B. For finite sets the number of different functions from a set A of n elements into a set B of m elements is mⁿ. The raising of one cardinal number to a power of another cardinal number is defined as follows. Let m and n be cardinal numbers and the sets A and B such that #(A)=n and #(B)=m. Then:

mⁿ = #(B^A).

As with addition and multiplication we must establish that exponentiation is well defined; i.e., if there are one-to-one correspondences between A and A' and B and B', respectively, then there is a one-to-one correspondence between B^A and B'^A'. Suppose f:A→A' and g:B→B' are the one-to-one correspondences between A and A' and B and B'. Let h be any function from A to B, h:A→B. Consider the function h' ∈ B'^A' defined by

h'(a') = b' = g(h(f^-1(a'))).

This function takes any element a' belonging to A' and first obtains the corresponding element a of A, then obtains the element b of B given by h(a) and from b obtains the corresponding element of B', b'=g(b). Thus for any function in B^A there is one and only one function corresponding to it in B'^A'. The crucial question is whether given any function in B'^A' there is one and only one function in B^A corresponding to it. The corresponding function is determined as follows. For any function h':A' → B' the corresponding function h in B^A is given by:

h(a) = g^-1(h'(f(a))).

Thus there is a one-to-one correspondence between the set of functions B^A and the set of functions B'^A'. There the exponentiation of cardinal numbers defined previously is well defined.

There are two important properties of the powers of finite cardinal numbers:

(mⁿ)^p) = m^np
m^n+p = mⁿm^p.

Below are proofs that these properties apply to all cardinal numbers.

Let A, B, and C be sets such that #(A)=n, #(B)=m and #(C)=p. The first property requires that we show that:

#((B^A)^C) = #(B^A×C).

The right hand side involves functions of the form f(a,c)=b, where a, b and c are from the sets A, B and C, respectively. If we hold c fixed we get a function from A to B, which might be expressed as f_c(a)=b. For different values of c we get the different functions of B^A. This is just a function of the form C→B^A. Thus the two sides describe the same set and thus the cardinalities are the same.

To prove the second property the sets A and C must be disjoint. To prove the second property we must establish that

#(B^A∪C) = #(B^A×B^C).

The set involved on the right side of the above equation is the set of ordered pairs of functions of the form (f(a), g(c)) where a belongs to A and c belongs to C and the values of both functions belong to B. The set on the left hand side is the set of functions from A∪C to B. But, because A and C are disjoint, the functions from A∪C to B can be composed by taking any function from A to B for the A-part of A∪ and any function from C to B for the C-part of A∪C to B. Thus the left side involves the same set of functions as the right side. Therefore the cardinalities are the same.

Paradoxes of Set Theory Involving Cardinal Numbers

In formulating the notion of a cardinal number as an equivalence class of sets are equipotent; i.e., sets that can be put into a one-to-one correspondence there was the presumption that we could envision a set of all sets and also a set of all sets that are equipotent. These presumptions are not valid and this fact shows the need for a more sophisticated version of set theory, an axiomatic set theory.

Consider the assumption that there is a set of all sets. This like assuming that there a largest integer. Given any candidate for a largest integer one can construct a larger integer; i.e., that integer plus one. Thus the concept of a largest integer is contradictory.

Suppose there were a set of all sets, S. From S we can construct the power set of S, which by Cantor's Theorem is strictly larger than S.

Suppose now that C is the set of all sets which are equipotent. Consider the power set of C and any function from P(C) to C×P(C), say f:P(C)→C×P(C). Then f(P(C)) is a subset of C because for each c∈C, f(c) is a set with the cardinality of C. Thus the cardinality of f(P(C)) is less than or equal to the cardinality of C. Since the sets in f(P(C)) are disjoint the cardinality of f(P(C)) is the same as the cardinality of P(C). By Cantor's Theorem then #(P(C)) is strictly greater than #(C). Thus there is a contradiction and therefore the concept of the set of all equipolent sets is invalid; i.e., contradictory.

Thus great care must be exercised in making set theory rigorous when dealing with sets that are not finite.