PROOF. Recall that the set Q of all rationals consists of ratios m/n with m 2 Z and
n 2 N. Thus, f(m, n) = m/n defines a surjection from Z×N onto Q. Since Z and N
are countable, so is Z×N by the preceding theorem. Hence, Q is countable by Lemma
3.1. 2
3.4 THEOREM. The union of a countable collection of countable sets is countable.
PROOF. Let I be a countable set, and let Ai be a countable set for each i in I. The
claim is that A =
S
i2I Ai is countable. Now, there is a surjection fi : N 7! Ai for
each i, and there is a surjection g : N 7! I; these follow from the countability of I and
the Ai. Note that, then, h(m, n) = fg(m)(n) defines a surjection h from N × N onto
A. Since N × N is countable, this implies via Lemma 3.1 that A is countable. 2
The following theorem exhibits an uncountable set. As a corollary, we show that R
is uncountable.
3.5 THEOREM. Let E be the set of all sequences whose terms are the digits 0 and 1.
Then, E is uncountable.
PROOF. Let A be a countable subset of E. Let x1, x2, . . . be an enumeration of the
elements of A, that is, A is the range of (xn). Note that each xn is a sequence of zeros
and ones, say xn = (xn,1, xn,2, . . .) where each term xn,m is either 0 or 1. We define
a new sequence y = (yn) by letting yn = 1?xn,n. The sequence y differs from every
one of the sequences x1, x2, . . . in at least one position. Thus, y is not in A but is in E.
We have shown that if A E and is countable, then there is a y 2 E such that
y 62 A. If E were countable, the preceding would hold for A = E, which would be
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
الرجوع الى لوحة التحكم
|