Two sets A and B are said to have the same cardinality, and then we write A B, if
there exists a bijection from A onto B. Obviously, having the same cardinality is an
equivalence relation; it is
1. reflexive: A A,
2. symmetric: A B ) B A,
3. transitive: A B and B C ) A C.
A set is said to be finite if it is empty or has the same cardinality as {1, 2, . . . , n} for
some n in N; in the former case it has 0 elements, in the latter exactly n. It is said to
be countable if it is finite or has the same cardinality as N; in the latter case it is said to
have a countable infinity of elements.
In particular, N is countable. So are Z, N × N in view of exercises 2.3 and 2.4.
Note that an infinite set can have the same cardinality as one of its proper subsets. For
instance, Z N, R+ (0, 1], R R+ (0, 1); see exercise 2.2 for the latter.
Incidentally, R+, R, etc. are uncountable, as we shall show shortly.
A set is countable if and only if it can be injected into N, or equivalently, if and
only if there is a surjection from N onto it. Thus, a set A is countable if and only if
there is a sequence (xn) whose range is A. The following lemma follows easily from
these remarks.
3. COUNTABILITY 7
3.1 LEMMA. If A can be injected into B and B is countable, then A is countable. If
A is countable and there is a surjection from A onto B, then B is countable.
3.2 THEOREM. The product of two countable sets is countable.
PROOF. Let A and B be countable. If one of them is empty, then A×B is empty and
there is nothing to prove. Suppose that neither is empty. Then, there exist injections
f : A 7! N and g : B 7! N. For each pair (x, y) in A × B, let h(x, y) = (f(x), g(y));
then h is an injection from A × B into N × N. Since N × N is countab
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
|