San José State University 

appletmagic.com Thayer Watkins Silicon Valley & Tornado Alley USA 


Abstract: This is an explanation of the concept of cardinal numbers from the viewpoint of naive set theory. The concept of equal number of elements in sets can be extended to infinite sets. This leads to the fact that there are different levels of infinity. The concepts of addition, multiplication and exponentiation of cardinal numbers are introduced by means of the operations of set union, Cartesian product and function. Some simple calculations are carried out for addition, multiplication and exponentiation of infinite cardinals. Finally some of the paradoxes of set theory are examined to show the need for an axiomatic set theory.
Two sets are said to be equipollent if a onetoone correspondence between their elements can be established. There is a onetoone correspondence between set A and set B if and only if there is function f:A→B such that for any element a of A f(a) is defined and for any element b of B there is one and only one element of A such that f(a)=b.
We can imagine all sets being grouped into classes in which all sets in a class are equipollent. We say the relation of being equipolent is an equivalence relation. A relation R is an equivalence relation if three conditions hold:
The set of sets that are equipollent are equivalence classes. Cardinal numbers are simply the equivalence classes under the relation of equipollency. One establishes the cardinality of a finite set by putting it into a onetoone correspondence with one of the sets, {1}, {1, 2}, {1, 2, 3}, ... In other words one counts the elements of the set.
Let n_{1} and n_{2} be cardinal numbers. There are then sets A_{1} and A_{2} such that #(A_{1}) = n_{1} and #(A_{2}) = n_{2}. It is essential that A_{1} and A_{2} be disjoint. From A_{1} and A_{2} we can create A'_{1}= {(a_{1},1)a_{1}∈A_{1}}=A_{1}×{1} and A'_{2}={(a_{2},2)a_{2}∈A_{2}}=A_{2}×{2}. The sum of cardinals is the cardinality of the union of the representative sets for the cardinals; i.e.,
To be rigorous we must establish that addition of cardinals is well defined. This means that we must show that if
To do this consider an element x from #(A'_{1}∪A'_{2}). Let f_{1} be the onetoone function from A'_{1} to A"_{1}) and f_{2} be the onetoone function from A'_{2} to A"_{2}. The onetoone onto function from A'_{1}∪A'_{2} to A"_{1}∪A"_{2} is then merely f_{1} on A'_{1} and f_{2} on A'_{2}.
If a set can be put into a onetoone 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, _{0}. 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 onetoone correspondence with any finite set. Another criterion of infiniteness is whether a set contains a proper subset that can be put into a onetoone 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 onetoone correspondences with a proper subset T and with a finite set {1,2,...,n}. Then there is a onetoone 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 onetoone 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 onetoone correspondence between the set and one of its proper subsets.
This property of infinite sets provides 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 accommodated. 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 accommodated 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.
If a set A can be put into a onetoone 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 onetoone correspondence with a subset of set A then it can be shown that set A and set B have the same cardinality (The SchroederBernstein Theorem).
For sets there is:
For any two sets A and B exactly one of the following three possibilities is true:
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 denoted as P(A). Thus Cantor's Theorem is that #(A) < #(P(A)). Thus for any cardinal number we can find a larger cardinal number.
Since addition of cardinal numbers is well defined we can find the sum of any two cardinal numbers, n_{1} and n_{2}, by finding any two disjoint sets A_{1} and A_{2} such that #(A_{1}) = n_{1} and #(A_{2}) = n_{2} and finding the cardinality of their union. For example, if n_{1} is a finite number n and n_{2} = _{0} 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 _{0} and then find the cardinality of the union of the two sets. The following demonstrates that the sum of n and _{0} is equal to _{0}.
We find that _{0} + _{0} = _{0} because we can use the set of odd numbers to represent the first _{0} on the left and the set of even numbers to represent the second _{0} on the left. The union of the odd numbers and even numbers gives the set of positive integers which has the cardinality of _{0}.
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 _{0} so the sum of the cardinality of the real number, usually denoted by a script c and _{0} is equal to the cardinality of the real 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_{1} and n_{1} be two cardinals and let A_{1} and A_{1} such that #(A_{1}) = n_{1} and #(A_{2}) = n_{2}. There is no necessity that A_{1} and A_{2} be disjoint. The product of n_{1} and n_{2} is defined as:
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, _{0}.
The indicated pattern for the enumeration of the ordered pairs of integers establishes a onetoone correspondence between the set positive integers P and the set of pairs of positive integers, P×P. Thus #(P×P)=#(P) and hence _{0}*_{0}= _{0}. This obviously implies that for any finite cardinal n
Raising one cardinal number to a power equal to that of another cardinal number can 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^{n}. 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:
As with addition and multiplication we must establish that exponentiation is well defined; i.e., if there are onetoone correspondences between A and A' and B and B', respectively, then there is a onetoone correspondence between B^{A} and B'^{A'}. Suppose f:A→A' and g:B→B' are the onetoone 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
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:
Thus there is a onetoone 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:
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:
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
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 Apart of A∪ and any function from C to B for the Cpart 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.
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 onetoone 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 is 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 equipollent 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.
HOME PAGE OF Thayer Watkins 