[ Pobierz całość w formacie PDF ]
set whose unique element is the empty set), {", {"}}, etc. For any objects a,
b, and c, we can form the set {a, b, c} whose elements are exactly a, b, and c.
The cardinality of this set will be one, two or three depending on which of a,
b, and c are equal to each other. Some examples of infinite sets are N (the
set of natural numbers), R (the set of real numbers), P(N), P(R), P(P(R)),
etc. Another source of examples is subsets defined by properties, for example
{n " N | n is prime} and {X †" R | X is countably infinite}. Further sets can
be obtained using the set operations discussed below.
Given two objects a and b, there is an object (a, b) called the ordered pair of
a and b. The ordered pair operation is assumed to have the following property:
(a, b) = (a2 , b2 ) Ô! (a = a2 '" b = b2 ) .
Given two sets X and Y , the Cartesian product X × Y is the set of all ordered
pairs (a, b) such that a " X and b " Y .
For any set X, a function with domain X is a rule f associating to each
object a " X a definite, unique object f(a). In this case we write dom(f) = X
and rng(f) = {f(a) | a " X}. The latter is again a set, called the range of F .
70
If f is a function and Z is a set, there is a unique function f¾!Z, the restriction
of f to Z, whose domain is dom(f) )" Z and such that (f¾!Z)(a) = f(a) for all
a in its domain.
We write f : X ’! Y to mean that f is a function, dom(f) = X, and
X
rng(f) †" Y . The set of all such functions is denoted Y .
Summarizing some of the above points, we have the following binary opera-
tions on sets:
X *" Y = {a | a " X (" a " Y } (union) ,
X )" Y = {a | a " X '" a " Y } (intersection) ,
X \ Y = {a | a " X '" a " Y } (difference) ,
/
X × Y = {(a, b) | a " X '" b " Y } (product) ,
XY = {f | f : Y ’! X} (exponential) .
By an indexed collection with index set I, we mean simply a function f
whose domain is I. In discussing indexed collections, we use notation such as
f = ai i"I where ai = f(i). For example, an ordered n-tuple a1, . . . , an is
a function whose domain is {1, . . . , n}, and a sequence an n"N is a function
whose domain is N.
Given an indexed collection of sets Xi i"I, the following operations are
defined.
Xi = {a | "i " I (a " Xi)} (union) ,
i"I
Xi = {a | "i " I (a " Xi)} (intersection) ,
i"I
Xi = { ai i"I | "i " I (ai " Xi)} (product) .
i"I
If in the latter operation we take all of the sets Xi to be the same set X, we get
the Cartesian power
X = XI
i"I
which is the same as the previously mentioned exponential.
The Axiom of Choice is the assertion that, for any indexed collection of sets
Xi i"I, if "i " I (Xi = ") then Xi = ". This implies that it is possible
i"I
to choose one element ai " Xi for each i " I. In the early years of set theory,
there was some controversy about the Axiom of Choice. Nowadays the Axiom of
Choice is accepted as being intuitively obvious, but we shall follow the custom
of indicating which proofs use it.
4.2 Cardinal Numbers
A function f is said to be one-to-one if for all a, a2 " dom(f), a = a2 implies
f(a) = f(a2 ). Note that in this case there is an inverse function f-1 with
dom(f-1) = rng(f) and rng(f-1) = dom(f), defined by
f-1(b) = a Ô! f(a) = b .
71
Definition 4.2.1. If X and Y are sets, we say X is equinumerous with Y ,
written X H" Y , if there exists a one-to-one correspondence between X and Y ,
i.e., a one-to-one function f with dom(f) = X and rng(f) = Y .
Lemma 4.2.2.
1. X H" X.
2. X H" Y if and only if Y H" X.
3. X H" Y and Y H" Z imply X H" Z.
Proof. Straightforward.
Because of the preceding lemma, we can associate to any set X an object
card(X), the cardinality or cardinal number of X, in such a way that
X H" Y Ô! card(X) = card(Y ) .
If X is finite, we take card(X) to be the number of elements in X. For infinite
sets X, it is not important at this stage what sort of object the cardinal number
card(X) is, so long as the above property holds. We use Greek letters º, », µ,
½, . . . to denote cardinal numbers.
Definition 4.2.3. We write X Y to mean that X H" X1 for some X1 †" Y .
Lemma 4.2.4.
2 2
1. If X H" X2 and Y H" Y , then X Y if and only if X2 Y .
2. X X.
3. X Y and Y Z imply X Z.
4. X Y and Y X imply X H" Y .
5. For all sets X and Y , either X Y or Y X.
Proof. Parts 1, 2, and 3 are straightforward. Parts 4 and 5 will be proved
later, as consequences of the Well-Ordering Theorem. Part 4 is known as the
Cantor-Schroeder-Bernstein Theorem.
We can now make the following definition for cardinal numbers: º d" » if and
[ Pobierz całość w formacie PDF ]