Author & Citation Info | Friends PDF Preview | InPho Search | PhilPapers Bibliography

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 if a = a′ and b = b′.

Proof. If a = a′ and b = 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 ′}}. If a ≠ b, {a} = {a′} and {a, b} = {a ′, b′}. So, first, a = a′ and then {a, b} = {a, b′} implies b = b′. If a = b, {{a}, {a, a}} = {{a}}. So {a} = {a′}, {a} = {a′,b ′}, and we get a = a′ = b′, so a = a ′ and b = 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 set R is a binary relation if all elements of R are ordered pairs, i.e., if for any z ∈ R there exist x and y such that z = (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 relation F is called a function (or mapping, correspondence) if aFb₁ and aFb₂ imply b₁ = b₂ for any a, b₁, and b₂. In other words, a binary relation F is a function if and only if for every a from dom F there is exactly one b such that aFb. This unique b is called the value of F at a and is denoted F(a) or F_a. [F(a) is not defined if a ∉ dom F.] If F is a function with dom F = A and ran F ⊆ B, it is customary to use the notations F : A B, <F(a) | a ∈A>, <F_a | a ∈ A>, <F_a >_{a ∈ A} for the function F. The range of the function F can then be denoted {F(a) | a ∈ A} or {F_a}_{a ∈A}.

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

Lemma. Let F and G be functions. F = G if and only if dom F = dom G and F(x) = G(x) for all x ∈ dom F.

A function f is called one-to-one or injective if a₁ ∈ dom f, a₂ ∈ dom f, and a₁ ≠ a₂ implies f(a₁) ≠ f(a₂). In other words if a₁ ∈ dom f, a ₂∈ dom f, and f(a₁) = f(a₂), then a₁ = a₂.

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. The successor of a set x is the set S(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:

1. 0 is a natural number.
2. If n is a natural number, then its successor n + 1 is also a natural number.
3. 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 set I is called inductive if

1. 0∈ I.
2. 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 numbers is the set

= {x | x ∈ I for every inductive set I}.

The elements of are called natural numbers. Thus a set x is 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. Sets A and B have the same cardinality if there is a one-to-one function f with domain A and range B. We denote this by |A| = |B|.

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

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.

1. If |A| ≤ |B| and |A| = |C|, then |C| ≤ |B|.
2. If |A| ≤ |B| and |B| = |C|, then |A| ≤ |C|.
3. |A| ≤ |A|.
4. 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 set S is finite if it has the same cardinality as some natural number n ∈ . We then define |S| = n and say that S has n elements. A set is infinite if it is not finite.

7. Countable Sets

Definition. A set S is countable if |S| = ||. A set S is at most countable if |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. Let A be a countable set, and let B ⊆ A be infinite. There is an infinite one-to-one sequence <a_n>, whose range is A. We let b₀ = a_k0, where k₀ is the least k such that a_k ∈ B. Having constructed b_n, we let b_{n + 1} = a_{kn + 1}, where k_{n + 1} is the least k such that a_k ∈ B and a_k ≠ b_i for every i ≤ n. Such k exists since it is easily seen that B = {b_n | n ∈ } and that <b_n> is one-to-one. Thus B is 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 let b₀ = a₀, and, having constructed b_n, we let b_{n + 1} = a_{kn + 1}, where k_{n + 1} is the least k such that a_k ≠ b_i for all i ≤ n. (If no such k exists, 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 = {2k | k ∈ } of all even numbers, and the set O = {2k + 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₀ = 2, p₁ = 3, etc.). Let

S₀ = {2^k | k ∈ }, S₁ = {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_ns 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. Let A = {a_n | n ∈ } and B = {b_n | n ∈ } be countable. We construct a sequence <c_n> as follows:

c_2k = a_kand c_{2k + 1} = b_k for all k ∈ .

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. If A and B are countable, then A × B is 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 function

f(k, n) = 2^k · (2n + 1) − 1.

It is easy to verify that f is one-to-one and that the range of f is . □

Corollary. The cartesian product of a finite number of countable sets is countable. Consequently, ^m is countable, for every m > 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 of A_n; i.e., for each n ∈ , a_n = <a_n(k) | k ∈> is an infinite sequence, and A_n = {a_n(k) | k ∈}. Then ∪ A_n is at most countable.

Proof. Define f : × ∪ A_n by f(n, k) = a_n(k). f maps × onto ∪ A_n, so the latter is at most countable. □

As a corollary of this result we can now prove

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

Proof. It is enough to prove the theorem for A = . As Seq () = ∪ ⁿ, the theorem follows if we can produce a sequence <a_n | n ≥ 1> of enumerations of ⁿ. We do that by recursion.

Let g be a one-to-one mapping of onto × . Define recursively

a₁(i) = <i> for all i ∈ ;
a_{n + 1}(i) = <b₀, …, b_{n − 1}, i₂> where g(i)=(i₁, i₂) and <b₀, …, b_{n − 1}> = a_n(i₁),for all i ∈ .

The idea is to let a_{n + 1}(i) be the (n + 1)-tuple resulting from the concatenation of the (i₁)^th n-tuple (in the previously constructed enumeration of n-tuples, a_n) with i₂. An easy proof by induction shows that a_n is onto ⁿ, for all n ≥ 1, and therefore ∪ ⁿ is countable. Since ⁰ = {<>}, ∪ ⁿ is also countable. □

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

Proof. The function F defined by F(<a₀, …, a_{n − 1}>) = {a₀, …, a_{n − 1}} maps the countable set Seq (A) onto the set of all finite subsets of A. □

Other useful results about countable sets are the following.

Theorem. The set of all integers Z and the set of all rational numbers Q are countable.

Proof. Z is countable because it is the union of two countable sets:

Z = {0, 1, 2, 3, …} ∪ {-1, -2, -3, …}.

Q is countable because the function f : Z × (Z − {0}) Q defined by f(p, q) = p / q maps a countable set onto Q. □

8. Real Numbers

Definition. An ordered set (X, <) is dense if it has at least two elements and if for all a, b ∈ X, a < b implies that there exists x ∈ X such that a < 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. P is complete if every non-empty S ⊆ P bounded 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.

Theorem The set ℜ of all real numbers is uncountable.

Proof. Assume that ℜ is countable, i.e., ℜ is the range of some infinite sequence <r_n>. Let a₀⁽ⁿ⁾.a₁⁽ⁿ⁾a₂⁽ⁿ⁾a₃⁽ⁿ⁾… be the decimal expansion of r_n. Let b_n = 1 if a_n⁽ⁿ⁾ = 0, b_n = 0 otherwise; and let r be the real number whose decimal expansion is 0.b₁b₂b₃ ···. We have b_n ≠ a_n⁽ⁿ⁾, hence r ≠ r_n, for all n = 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 function f : ℘() defined by f(n) = {n} is one-to-one, so || ≤ |℘()|. We prove that for every sequence <S_n | n ∈ > of subsets of there is some S ⊆ such that S ≠ S_n for all n ∈ . This shows that there is no mapping of onto ℘(), and hence || < |℘()|.

We define the set S ⊆ as follows: S = {n ∈ | n ∉S_n}. The number n is used to distinguish S from S_n: If n ∈ S_n, then n ∉ S, and if n ∉ S_n, then n ∈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 each S ⊆ define the characteristic function of S, χ_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.

1. We have constructed real numbers as cuts in the set Q of all rational numbers. The function that assigns to each real number r = (A, B) the set A ⊆ Q is a one-to-one mapping of ℜ into ℘(Q). Therefore |ℜ| ≤ |℘(Q)|. As |Q| = ||, we have |℘(Q)| = |℘()|. Hence |ℜ| ≤ |℘()|.
2. 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₀a₁a₂··· 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

Copyright © 2002 by
Thomas Jech <jech@math.cas.cz>