(b) (Symmetric property) A B if and only if B A.
(c) (Transitive property) A B and B C implies A C.
Proof of this theorem is left as Exercise 4.
Definition 1.6.3.
(a) A set, A, is finite if and only if A = . orthere exists n* E N such that A { 1, 2, 3, ... , n *} . If A {l, 2, 3, ..., n *}, then n* E N represents the number of elements in A. The empty set /, has 0 elements. If A is not finite, then it is infinite.
(b) A set, A, is countably infinite, denumerable, if and only if A ^- N.
(c) A set, A, is countable if and only if A is finite or countably infinite. If A is not countable, then it is uncountable.
THEOREM 1.6.4. The set of all natural numbers N, is infinite.
Proof of this theorem is left as Exercise 5.
Remark 1.5.5. For the case in which A and B are finite, A B if and only if A has the same number of elements as B, but for the case in which both A and B are infinite, counting elements is irrelevant. For example, if A = W, the set of all nonnegative integers, and B = N, then A has one more element than B, but A B, because we can pair off every element of
W with every element of N by setting up a bijection with the function f W - N, where
f(x)=x+1.
The idea of an infinite set being equivalent to one of its proper subset really puzzled Galileo24 who strongly believed that "the whole is greater than any one of its proper parts?' Thus, the standard notion of size does not apply to infinite sets. In fact, some mathematicians define A to be an infinite set if and only if it is equivalent to a proper subset of itself.
In the case A B, we will say that A and B have the same cardinality. Thus, in view of Definition 1.6.3, part (b), an infinite set A is countably infinite if and only if it has the cardinality of N.
24Galileo Galilei (1564-1642) was an Italian pioneer of modern mathematics, physics, and astronomy.
Galileo is known for his study of free fall and for his use of the telescope. He was persecuted for supporting the Copernican theory of the solar system. It is worth noting that Nicolaus Copernicus (1473-1543), whose theory was that the Earth has a daily motion about its axis and a yearly motion around a stationary sun, was born in Poland under the name Mikotaj Kopernik.
:
Sec. 1.6* Finite and Infinite Sets 41 THEOREM 1.6.6. Any subset of a countable set must be countable.
Leaving the proof of this result as Exercise 6, we proceed to state the next theorem, with the proof left as Exercise 7.
THEOREM 1.6.7. If A and B are countable sets, then (a) A x B is countable.
(b) A U B is countable.
Part (b) of Theorem 1.6.7 can be extended to cover the union of a countable number of countable sets. Note also that from Theorem 1.6.7 it follows that Z x N is countable. This can be used to prove that Q is countable. We do this by defining the set A, for each n E N, by
An={mfmEZ}.
n
Then A is countable. Since Q = U=1 An, the set of all rational numbers is countable. This is an informal proof of the next theorem.
THEOREM 1.6.8. The set Q is countable.25
Next we would like to observe that not all infinite sets are countable. We do this by proving the next result.
THEOREM 1.6.9. The interval (0, 1) is uncountable.
Proof Before we even get started with the proof, let us observe that each number in the interval (0, 1) can be expressed in the form of an infinite decimal as 0.x1x2x3... , where xn E {0, 1, 2, ... , 9} for all n E N, and where each decimal contains an infinite number of nonzero elements. For example, we write 3 = 0.333... and1 2 = 0.707106.... But
1 = 0.5000... we will write as ? = 0.4999...; similarly' 1 = 0.24999... instead of
2 2 4
0.25000.... Thus, two numbers in (0, 1) are equal if and only if the corresponding digits in their decimal expansions are identical. For example, suppose that we have two numbers from (0, 1), x = 0.x i x2x3 and y = 0. y i y2 y3 . If in the kth decimal place xk yk, then x y. This idea will be vital in our proof.
25Georg Ferdinand Ludwig Philipp Cantor (1845-1918) was born in Russia to a Danish family that moved to Germany permanently when he was 11 years old. Cantor introduced the concept of infinity, was the first to prove that the set of rational numbers is countable, and came up with other amazing and revolutionary discoveries. Cantor's findings were supported by Weierstrass, Dedekind, Hilbert, and Zermelo, but were attacked very strongly by Cantor's own teacher Kronecker. Cantor was stripped of well-deserved recognition, suffered numerous nervous breakdowns, and died in a men- tal institution. Ernst Friedrich Ferdinand Zermelo (1871-1951) was a German mathematician best known for his work in axiomatic set theory.
2
We will prove the given theorem by contradiction, so we assume that (0, 1) is countable.
Thus, there exists a bijection f from N to (0, 1). Therefore, we can list all elements of (0, 1) as
f (l) =
f(2) = O.a21a22a23 - f(3) = O.a31a32a33
f (k) = O.akiak2ak3 .. .
where each ail E {O, 1, 2, ... , 9). Since all elements of (0, 1) are in the listing above, to get a contradiction our goal is to construct a number z which is in the interval (0, 1), but is not in the listing above of f (k)'s.
We construct the above mentioned number z , written as z = O.z Z2Z3 - , as follows.
Choose
Zi = 2 if a 11 2 2 if a22 2
ii if a11 = 2, Z2
_
ji if a22 = 2, Zk ~ 2
ii
if akk 2 if akk = 2
for each k E Z. The number z is obviously in the interval (0, 1). But z f(1) since z a 11, z f(2) since Z2 a22, and in general, for each k E Z we can see that z f (k) since
Zk akk, Thus, z f (N). But we assumed that f (N) _ (0, 1). Hence, we have a contradiction
and the proof is complete. p
COROLLARY 1.6.10. The set of all real numbers Ill is uncountable.
The truth of Corollary 1.6.10 follows from Exercise 8.
THEOREM 1.6.11. The set of all irrational numbers is uncountable.
The proof, which is quick by assuming the contrary is left to Exercise 9.
Exercises 1.6
1. Prove that the set of all counting numbers is equivalent to the set of all even counting numbers.
2. Show that closed intervals [0, 1] and [a, b] are equivalent for any a, b E )l.
3. Show that the given sets are countable.
(a) all even integers (together with zero) (b) {2n n E N and n? 3}
4. Prove Theorem 1.6.2.
5. Prove Theorem 1.6.4.
.. .
1
_
l
Sec. 1.7 * ordered Field and a Real Number System 43 6. Prove Theorem 1.6.6.
7. (a) Prove part (a) of Theorem 1.6.7.
(b) Prove part (b) of Theorem 1.6.7.
8. (a) Show that intervals (0, 1) and (-1, 1) are equivalent.
(b) Show that the interval (-1, 1) is equivalent to.
(c) Verify that (0, 1) 91.
9. Prove Theorem 1.6.11.
1.7* Ordered Field and a Real Number System
In this section we discuss very briefly the structure of the real number system. Instead of constructing real numbers, we will assume their existence. As we know well, real numbers have an abundance of properties. An obvious question is whether there is a short list of properties from which all others will follow. These basic properties are called axioms. One of the most fundamental structures in mathematics is a field, characterized by eight axioms. To those, we will add order axioms to form an ordered field. Then we will get more refined structure by further assuming the completeness axiom. This will yield a structure called a complete ordered field. Real numbers are such a structure. So let us get on the way by presenting the first
definition.
Definition 1.7.1. Afield, F, is a nonempty set together with the operations of addition and multiplication, denoted by + and , respectively, that satisfies the following eight axioms:
(Al) (Closure) For all a, b E F, we have a + b, a b E F.
(A2) (Commutative) For all a, b E F, we have a + b = b + a and a b = b a.
(A3) (Associative) For all a, b, c E F, we have (a +b) + c = a + (b + c) and (a b) c= a (b . c) . (A4) (Additive identity) There exists a zero element in F, denoted by 4, such that a + 0 = a
for any a E F.
(A5) (Additive Inverse) For each a E F, there exists an element -a in F, such that a + (-a) =
0.
(A6) (Multiplicative Identity) There exists an element in F, distinct from 0, which we denote by 1, such that a 1 a for any a E F.
(A7) (Multiplicative Inverse) For each a E F with a 0 there exists an element in F denoted by i or a1 such that a- a1 1.
a
(AS) (Distributive) For all a, b, c E F, we have a (b + c) = (a b) + (a . c).