#### Supplement to Set Theory

## Basic Set Theory

The following basic facts are excerpted from “Introduction to Set Theory,” Third Edition, by Karel Hrbacek and Thomas Jech, published by Marcel Dekker, Inc., New York 1999.

- 1. Ordered Pairs
- 2. Relations
- 3. Functions
- 4. Natural Numbers
- 5. Cardinalities of Sets
- 6. Finite Sets
- 7. Countable Sets
- 8. Real Numbers
- 9. Uncountable Sets

### 1. Ordered Pairs

We begin by introducing the notion of the *ordered pair*. If
*a* and *b* are sets, then the *unordered pair*
{*a*, *b*} is a set whose elements are exactly
*a* and *b*. The “order” in which *a*
and *b* are put together plays no role; {*a*,
*b*} = {*b*, *a*}. For many applications, we
need to pair *a* and *b* in a way making possible to
“read off” which set comes “first” and which
comes “second.” We denote this *ordered pair* of
*a* and *b* by (*a*, *b*); *a* is
the *first coordinate* of the pair (*a*, *b*),
*b* is the *second coordinate*.

As any object of our study, the ordered pair has to be a set. It
should be defined in such a way that two ordered pairs are equal if
and only if their first coordinates are equal and their second
coordinates are equal. This guarantees in particular that (*a*,
*b*) ≠ (*b*,*a*) if
*a* ≠ *b*.

Definition.(a,b) = {{a}, {a,b}}.

If *a* ≠ *b*, (*a*,
*b*) has two elements, a singleton {*a*} and an
unordered pair {*a*, *b*}. We find the first coordinate
by looking at the element of {*a*}. The second coordinate is
then the other element of {*a*, *b*}. If *a* =
*b*, then (*a*, *a*) = {{*a*},
{*a*,*a*}} = {{*a*}} has only one element. In any
case, it seems obvious that both coordinates can be uniquely “read
off” from the set (*a*, *b*). We make this statement
precise in the following theorem.

Theorem.(a,b) = (a′,b′) if and only ifa=a′ andb=b′.

Proof. Ifa=a′ andb=b′, then, of course, (a,b) = {{a}, {a,b}} = {{a′}, {a′,b′}} = (a′,b′). The other implication is more intricate. Let us assume that {{a}, {a,b}} = {{a′}, {a′,b′}}. Ifa≠b, {a} = {a′} and {a,b} = {a′,b′}. So, first,a=a′ and then {a,b} = {a,b′} impliesb=b′. Ifa=b, {{a}, {a,a}} = {{a}}. So {a} = {a′}, {a} = {a′,b′}, and we geta=a′ =b′, soa=a′ andb=b′ holds in this case, too. □

With ordered pairs at our disposal, we can define *ordered
triples*

(a,b,c) = ((a,b),c),

*ordered quadruples*

(a,b,c,d) = ((a,b,c),d),

and so on. Also, we define ordered “*one-tuples*”

(a) =a.

### 2. Relations

A binary relation is determined by specifying all ordered pairs of objects in that relation; it does not matter by what property the set of these ordered pairs is described. We are led to the following definition.

Definition.A setRis abinary relationif all elements ofRare ordered pairs, i.e., if for anyz∈Rthere existxandysuch thatz= (x,y).

It is customary to write *xRy* instead of (*x*,
*y*) ∈ *R*. We say that *x is
in relation R with y* if *xRy* holds.

The set of all *x* which are in relation *R* with some
*y* is called the *domain* of *R* and denoted by
“dom *R*.” So dom *R* = {*x* | there
exists *y* such that *xRy*}. dom *R* is the set
of all first coordinates of ordered pairs in *R*.

The set of all *y* such that, for some *x*, *x*
is in relation *R* with *y* is called the *range*
of *R*, denoted by “ran *R*.” So ran
*R* = {*y* | there exists *x* such that
*xRy*}.

### 3. Functions

Function, as understood in mathematics, is a procedure, a rule,
assigning to any object *a* from the domain of the function a unique
object *b*, the value of the function at *a*. A function, therefore,
represents a special type of relation, a relation where every object
*a* from the domain is related to precisely one object in the range,
namely, to the value of the function at *a*.

Definition.A binary relationFis called afunction(ormapping,correspondence) ifaFb_{1}andaFb_{2}implyb_{1}=b_{2}for anya,b_{1}, andb_{2}. In other words, a binary relationFis a function if and only if for everyafrom domFthere is exactly onebsuch thataFb. This uniquebis called thevalue of F at aand is denotedF(a) orF_{a}. [F(a) is not defined ifa∉ domF.] IfFis a function with domF=Aand ranF⊆B, it is customary to use the notationsF:AB, <F(a) |a∈A>, <F_{a}|a∈A>, <F_{a}>_{a ∈ A}for the functionF. The range of the functionFcan then be denoted {(Fa) |a∈A} or {F_{a}}_{a ∈A}.

The Axiom of Extensionality can be applied to functions as follows.

Lemma.LetFandGbe functions.F=Gif and only if domF= domGandF(x) =G(x) for allx∈ domF.

A function *f* is called *one-to-one* or
*injective* if *a*_{1} ∈
dom *f*, *a*_{2} ∈ dom
*f*, and *a*_{1} ≠
*a*_{2} implies *f*(*a*_{1})
≠ *f*(*a*_{2}). In other
words if *a*_{1} ∈ dom
*f*, *a* _{2}∈ dom
*f*, and *f*(*a*_{1}) =
*f*(*a*_{2}), then *a*_{1} =
*a*_{2}.

### 4. Natural Numbers

In order to develop mathematics within the framework of the axiomatic set theory, it is necessary to define natural numbers. We all know natural numbers intuitively: 0, 1, 2, 3, ..., 17, …, 324, etc., and we can easily give examples of sets having zero, one, two, or three elements.

To define number 0, we choose a representative of all sets having no
elements. But this is easy, since there is only one such set. We
define 0 = ∅. Let us proceed to sets having one
element (singletons): {∅},
{{∅}}, {{∅,
{∅}}}; in general, {*x*}. How should we choose a
representative? Since we already defined one particular object, namely
0, a natural choice is {0}. So we define

1 = {0} = {∅}.

Next we consider sets with two elements: {∅, {∅}}, {{∅}, {∅, {∅}}}, {{∅}, {{∅}}}, etc. By now, we have defined 0 and 1, and 0 ≠ 1. We single out a particular two-element set, the set whose elements are the previously defined numbers 0 and 1:

2 = {0,1} = {∅, {∅}}.

It should begin to be obvious how the process continues:

3 = {0, 1, 2} = {∅, {∅}, {∅,{∅}}}

4 = {0, 1, 2, 3} = {∅,{∅}, {∅,{∅}}, {∅, {∅}, {∅, {∅}}}}

5 = {0, 1, 2, 3, 4} etc.

The idea is simply to define a natural number n as the set of all
smaller natural numbers: {0, 1, …, *n* − 1}. In
this way, *n* is a particular set of *n* elements.

This idea still has a fundamental deficiency. We have defined 0, 1,
2, 3, 4, and 5 and could easily define 17 and—not so
easily—324. But no list of such definitions tells us what a
natural number is in general. We need a statement of the form: A set
*n* is a natural number if …. We cannot just say that a
set *n* is a natural number if its elements are all the smaller
natural numbers, because such a “definition” would involve the very
concept being defined.

Let us observe the construction of the first few numbers again. We defined 2 = {0, 1}. To get 3, we had to adjoin a third element to 2, namely, 2 itself:

3 = 2 ∪ {2} = {0, 1} ∪ {2}.

Similarly,

4 = 3 ∪ {3} = {0, 1, 2} ∪ {3},

5 = 4 ∪ {4},etc.

Given a natural number *n*, we get the “next”
number by adjoining one more element to *n*, namely, *n*
itself. The procedure works even for 1 and 2: 1 = 0 ∪ {0}, 2 =
1∪{1}, but, of course, not for 0, the least natural number.

These considerations suggest the following.

Definition.Thesuccessorof a setxis the setS(x) =x∪ {x}.

Intuitively, the successor *S*(*n*) of a natural number
*n* is the “one bigger” number *n* + 1. We use
the more suggestive notation n+1 for S(n) in what follows. We later
define addition of natural numbers (using the notion of successor) in
such a way that *n* + 1 indeed equals the sum of *n* and
1. Until then, it is just a notation, and no properties of addition
are assumed or implied by it.

We can now summarize the intuitive understanding of natural numbers as follows:

- 0 is a natural number.
- If
*n*is a natural number, then its successor*n*+ 1 is also a natural number. - All natural numbers are obtained by application of (a) and (b), i.e., by starting with 0 and repeatedly applying the successor operation: 0, 0 + 1 = 1, 1 + 1 = 2, 2 + 1 = 3, 3 + 1 = 4, 4 + 1 = 5, …etc.

Definition.A setIis calledinductiveif

- 0∈
I.- If
n∈I, then (n+ 1) ∈I.

An inductive set contains 0 and, with each element, also its
successor. According to (c), an inductive set should contain all
natural numbers. The precise meaning of (c) is that the set of natural
numbers is an inductive set which contains no other elements but
natural numbers, i.e., it is the *smallest* inductive set. This
leads to the following definition.

Definition.The set of all natural numbersis the set= {x|x∈Ifor every inductive setI}.The elements of are called

natural numbers. Thus a setxis a natural number if and only if it belongs to every inductive set.

### 5. Cardinality of Sets

From the point of view of pure set theory, the most basic question
about a set is: How many elements does it have? It is a fundamental
observation that we can define the statement “sets *A* and
*B* have the same number of elements” without knowing
anything about numbers.

Definition.SetsAandBhavethe same cardinalityif there is a one-to-one functionfwith domainAand rangeB. We denote this by |A| = |B|.

Definition.The cardinality ofAis less than or equal to the cardinality ofB(notation: |A| ≤ |B|) if there is a one-to-one mapping ofAintoB.

Notice that |*A*| ≤ |*B*| means that
|*A*| = |*C*| for some subset *C* of
*B*. We also write |*A*| < |*B*| to mean that
|*A*| ≤ |*B*| and not |*A*| =
|*B*|, i.e., that there is a one-to-one mapping of *A*
onto a subset of *B*, but there is no one-to-one mapping of
*A* onto *B*.

Lemma.

- If |
A| ≤ |B| and |A| = |C|, then |C| ≤ |B|.- If |
A| ≤ |B| and |B| = |C|, then |A| ≤ |C|.- |
A| ≤ |A|.- If |
A| ≤ |B| and |B| ≤ |C|, then |A|≤|C|.

**Cantor-Bernstein Theorem.** If | *X*|
≤ |*Y*| and |*Y*| ≤
|*X*|, then |*X*| = |*Y*|.

### 6. Finite Sets

Finite sets can be defined as those sets whose size is a natural number.

Definition.A setSisfiniteif it has the same cardinality as some natural numbern∈ . We then define |S| =nand say thatShas n elements. A set isinfiniteif it is not finite.

### 7. Countable Sets

Definition.A setSiscountableif |S| = ||. A setSisat most countableif |S| ≤ ||.

Thus a set *S* is countable if there is a one-to-one mapping
of
onto *S*, that is, if *S* is the range of an infinite
one-to-one sequence.

Theorem.An infinite subset of a countable set is countable.

Proof. LetAbe a countable set, and letB⊆Abe infinite. There is an infinite one-to-one sequence <a_{n}>_{}, whose range isA. We letb_{0}=a_{k0}, wherek_{0}is the leastksuch thata_{k}∈B. Having constructedb_{n}, we letb_{n + 1}=a_{kn + 1}, wherek_{n + 1}is the leastksuch thata_{k}∈Banda_{k}≠b_{i}for everyi≤n. Suchkexists since it is easily seen thatB= {b_{n}|n∈ } and that <b_{n}>_{}is one-to-one. ThusBis countable. □

Corollary.A set is at most countable if and only if it is either finite or countable.

The range of an infinite one-to-one sequence is countable. If
<*a*_{n}>_{}
is an infinite sequence which is not one-to-one, then the set
{*a*_{n}}_{}
may be finite (e.g., this happens if it is a constant sequence). However,
if the range is infinite, then it is countable.

Theorem.The range of an infinite sequence <a_{n}>_{}is at most countable, i.e., either finite or countable. (In other words, the image of a countable set under any mapping is at most countable.)

Proof. By recursion, we construct a sequence <b_{n}> (with either finite or infinite domain) which is one-to-one and has the same range as <a_{n}>_{}. We letb_{0}=a_{0}, and, having constructedb_{n}, we letb_{n + 1}=a_{kn + 1}, wherek_{n + 1}is the leastksuch thata_{k}≠b_{i}for alli≤n. (If no suchkexists, then we consider the finite sequence <b_{i}|i≤n>.) The sequence <b_{i}> thus constructed is one-to-one and its range is {a_{n}}_{}. □

One should realize that not all properties of size carry over from
finite sets to the infinite case. For instance, a countable set
*S* can be decomposed into two disjoint parts, *A* and
*B*, such that |*A*| = |*B*| = |*S*|; that
is inconceivable if *S* is finite (unless *S* =
∅).

Namely, consider the set *E* = {2*k* | *k*
∈ } of all even numbers, and the
set *O* = {2*k* + 1 | *k*
∈
}
of all odd numbers. Both *E* and *O* are infinite,
hence countable; thus we have
||
= |*E*| = |*O*| while
= *E* ∪ *O* and *E* ∩ *O* =
∅.

We can do even better. Let *p*_{n} denote the
*n*^{th} prime number (i.e., *p*_{0} =
2, *p*_{1} = 3, etc.). Let

S_{0}= {2^{k}|k∈ },S_{1}= {3^{k}|k∈ }, …,S_{n}= {p_{n}^{k}|k∈ }, ….

The sets *S*_{n} (*n* ∈
)
are mutually disjoint countable subsets of
.
Thus we have
⊇
∪
*S*_{n}, where
|*S*_{n}| =
||
and the *S*_{n}s are mutually disjoint.

The following two theorems show that simple operations applied to countable sets yield countable sets.

Theorem.The union of two countable sets is a countable set.

Proof. LetA= {a_{n}|n∈ } andB= {b_{n}|n∈ } be countable. We construct a sequence <c_{n}>_{}as follows:c_{2k}=a_{k}andc_{2k + 1}=b_{k}for allk∈ .Then

A∪B= {c_{n}|n∈ } and since it is infinite, it is countable. □

Corollary.The union of a finite system of countable sets is countable.

Proof. By induction (on the size of the system). □

Theorem.IfAandBare countable, thenA×Bis countable.

Proof. It suffices to show that | × | = ||, i.e., to construct either a one-to-one mapping of × onto or a one-to-one sequence with range × . Consider the functionf(k,n) = 2^{k}· (2n+ 1) − 1.It is easy to verify that

fis one-to-one and that the range offis . □

Corollary.The cartesian product of a finite number of countable sets is countable. Consequently,^{m}is countable, for everym> 0.

Theorem.Let <A_{n}|n∈ > be a countable system of at most countable sets, and let <a_{n}|n∈ > be a system of enumerations ofA_{n}; i.e., for eachn∈ ,a_{n}= <a_{n}(k) |k∈> is an infinite sequence, andA_{n}= {a_{n}(k) |k∈}. Then ∪A_{n}is at most countable.

Proof. Definef: × ∪A_{n}byf(n,k) =a_{n}(k).fmaps × onto ∪A_{n}, so the latter is at most countable. □

As a corollary of this result we can now prove

Theorem.IfAis countable, then the set Seq (A) of all finite sequences of elements ofAis countable.

Proof. It is enough to prove the theorem forA= . As Seq () = ∪^{n}, the theorem follows if we can produce a sequence <a_{n}|n≥ 1> of enumerations of^{n}. We do that by recursion.Let

gbe a one-to-one mapping of onto × . Define recursivelya_{1}(i) = <i> for alli∈ ;

a_{n + 1}(i) = <b_{0}, …,b_{n − 1},i_{2}> whereg(i)=(i_{1},i_{2}) and <b_{0}, …,b_{n − 1}> =a_{n}(i_{1}),for alli∈ .The idea is to let

a_{n + 1}(i) be the (n+ 1)-tuple resulting from the concatenation of the (i_{1})^{th}n-tuple (in the previously constructed enumeration ofn-tuples,a_{n}) withi_{2}. An easy proof by induction shows thata_{n}is onto^{n}, for alln≥ 1, and therefore ∪^{n}is countable. Since^{0}= {<>}, ∪^{n}is also countable. □

Corollary.The set of all finite subsets of a countable set is countable.

Proof. The functionFdefined byF(<a_{0}, …,a_{n − 1}>) = {a_{0}, …,a_{n − 1}} maps the countable set Seq (A) onto the set of all finite subsets ofA. □

Other useful results about countable sets are the following.

Theorem.The set of all integersZand the set of all rational numbersQare countable.

Proof.Zis countable because it is the union of two countable sets:Z= {0, 1, 2, 3, …} ∪ {-1, -2, -3, …}.Qis countable because the functionf:Z× (Z− {0})Qdefined byf(p,q) =p/qmaps a countable set ontoQ. □

### 8. Real Numbers

Definition.An ordered set (X, <) isdenseif it has at least two elements and if for alla,b∈X,a<bimplies that there existsx∈Xsuch thata<x<b.

Let us call the least and the greatest elements of a linearly ordered
set (if they exist) the *endpoints* of the set.

The most important example of a countable dense linearly ordered set
is the set **Q** of all rational numbers, ordered by
size. The ordering is dense because, if *r*, *s* are
rational numbers and *r* < *s*, then *x* =
(*r* + *s*) / 2 is also a rational number, and
*r* < *x* < *s*. Moreover,
(**Q**,<) has no endpoints (if *r*
∈ **Q** then *r* + 1, *r* − 1
∈ **Q** and *r* − 1 <
*r* < *r* + 1).

Definition.Let (P, <) be a dense linearly ordered set.Piscompleteif every non-emptyS⊆Pbounded from above has a supremum.

The ordered set (**Q**, <) of rationals has a unique
completion (up to isomorphism); this is the ordered set of real
numbers. The completion of (**Q**, <) is denoted
(ℜ,
<); the elements of
ℜ
are the *real numbers*.

Theorem.(ℜ, <) is the unique (up to isomorphism) complete linearly ordered set without endpoints that has a countable subset dense in it.

### 9. Uncountable Sets

All infinite sets whose cardinalities we have determined up to this point turned out to be countable. Naturally, a question arises whether perhaps all infinite sets are countable. If it were so, this book might end with the preceding section. It was a great discovery of Georg Cantor that uncountable sets, in fact, exist. This discovery provided an impetus for the development of set theory and became a source of its depth and richness.

TheoremThe set ℜ of all real numbers is uncountable.

Proof. Assume that ℜ is countable, i.e., ℜ is the range of some infinite sequence <r_{n}>_{}. Leta_{0}^{(n)}.a_{1}^{(n)}a_{2}^{(n)}a_{3}^{(n)}… be the decimal expansion ofr_{n}. Letb_{n}= 1 ifa_{n}^{(n)}= 0,b_{n}= 0 otherwise; and letrbe the real number whose decimal expansion is 0.b_{1}b_{2}b_{3}···. We haveb_{n}≠a_{n}^{(n)}, hencer≠r_{n}, for alln= 1, 2, 3, …, a contradiction. □

The combinatorial heart of the diagonal argument (quite similar to Russell's Paradox, which is of later origin) becomes even clearer in the next theorem.

Theorem.The set of all sets of natural numbers is uncountable; in fact, |℘()| > ||.

Proof. The functionf: ℘() defined byf(n) = {n} is one-to-one, so || ≤ |℘()|. We prove that for every sequence <S_{n}|n∈ > of subsets of there is someS⊆ such thatS≠S_{n}for alln∈ . This shows that there is no mapping of onto ℘(), and hence || < |℘()|.We define the set

S⊆ as follows:S= {n∈ |n∉S_{n}}. The numbernis used to distinguishSfromS_{n}: Ifn∈S_{n}, thenn∉S, and ifn∉S_{n}, thenn∈S. In either case,S≠S_{n}, as required. □

The set
2^{}
= {0, 1}^{}
of all infinite sequences of 0's and
1's is also uncountable, and, in fact, has the same cardinality as
℘()
and
ℜ.

Theorem.|℘()| = |2^{}| = |ℜ|.

Proof. For eachS⊆ define thecharacteristic functionofS, χ_{S}: {0, 1}, as follows:

χ _{S(n)}= {

0 if n∈S;1 if n∉S.It is easy to check that the correspondence between sets and their characteristic functions is a one-to-one mapping of ℘() onto {0,1}

^{}.To complete the proof, we show that |ℜ| ≤ |℘()| and also |2

^{}| ≤ |ℜ| and use the Cantor-Bernstein Theorem.

- We have constructed real numbers as cuts in the set
Qof all rational numbers. The function that assigns to each real numberr= (A,B) the setA⊆Qis a one-to-one mapping of ℜ into ℘(Q). Therefore |ℜ| ≤ |℘(Q)|. As |Q| = ||, we have |℘(Q)| = |℘()|. Hence |ℜ| ≤ |℘()|.- To prove |2
^{}| ≤ |ℜ| we use the decimal representation of real numbers. The function that assigns to each infinite sequence <a_{n}>_{}of 0s and 1s the unique real number whose decimal expansion is 0.a_{0}a_{1}a_{2}··· is a one-to-one mapping of 2^{}into ℜ. Therefore we have |2^{}| ≤ |ℜ|.□

### Acknowledgments

The editors would like to thank Gert-Jan Lokhorst for his assistance in using Otfried Cheong' Hyperlatex system, which helped us to convert the LaTeX source to HTML.

Return to Section 1 (paragraph 2) of Set Theory

Return to Section 1 (paragraph 5) of Set Theory

Return to Section 2 of Set Theory