Definition 3
Definition 1
A set that is either finite or has the same cardinality as the set of
The sets A and B have the same cardinality if and only if positive integers is countable (可数的或可列的).
there is a one-to-one correspondence from A to B.
正在载⼊…
A set that is not countable is called uncountable.
When A and B have the same cardinality, we write |A| = |B|.
When an infinite set S is countable, we denote the cardinality of S
by 0( אaleph, the first letter of the Hebrew alphabet).
infinite set ≠
uncountable Further explanation of countable sets.
An infinite set is countable if and only if it is possible to list
the elements of the set in a sequence (indexed by the positive
integers).
The reason for this is:正在载⼊…
set of odd positive countabl a1, a2, ….., an, ……
integer e where：
a1=f(1), a2=f(2), ……, an=f(n)
R n∈
∈(0, 1) Previous Number of n
?
(page 171)
？
Example 3 Show that the set of Real numbers is an uncountable set.
Show that the set of all integers is countable.
Solution: To show that the set of real numbers is uncountable,
Solution: we can assume that it is countable, So it corresponds one-to-one
All integers can be listed as: with the set of natural numbers according to the definition.
0, 1, -1, 2, -2, 3, -3, …, n, -n, ….
One to one correspondence (from the set of At the same time, its subset (0,1) should also have such
positive integers to the set of all integers): properties.
f(n) = n/2, if n is even
-(n-1)/2, if n is odd
Under this assumption, the real numbers between 0
and 1 can be listed in some order. Let the decimal
Next, we need to prove that (0,1) does not (0,1) N
representation of these real numbers be
correspond one-to-one with N.
s1=0.a11a12a13a14...... ,
Our goal is to find a number n that belongs s2=0.a21a22a23a24…… ,
to (0,1) and cannot correspond to any s3=0.a31a32a33a34…… ,
number in the natural number set, as ………………………………………
shown in the diagram. sn=0.an1an2an3an4…… ,
n
……………………………………..
Theorem 1
Form a new real number with decimal expansion If A and B are countable sets, then A ∪ B is also countable.
s= 0.a1a2a3a4 . . . , where every decimal digits are
determined by the following rule:
Definition 2
ai = 5 if aii = 4 ai = aii +1 if ai ≠ 9 If there is a one-to-one function from A to B, the
ai=4 if aii ≠ 4 or ai = 0 if ai = 9 cardinality of A is less正在载⼊…
than or the same as the cardinality
of B and we write |A| ≤ |B|.
Because the number is not in the list, the assumption
that all the real numbers between 0 and 1 could be Moreover, when |A| ≤ |B| and A and B have
listed must be false. different cardinality, we say that the cardinality of A is less
than the cardinality of B and we write |A| < |B|.
SCHRÖDER-BERNSTEIN THEOREM
If A and B are sets with |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|.
In other words, if there are one-to-one functions f from A to B
and g from B to A, then there is a one-to-one correspondence
between A and B.
1, Consider the set of finite and infinite sequences over {0,1} such that in a sequence the 0s are always before the 1s. 2. Consider the set of all functions from positive integers to positive integers. Is the set countable or uncountable?
Is the set countable or uncountable? Prove your result by using basic concepts and definitions. Prove your result by using basic concepts and definitions.
(0∞),(1∞),(011∞),(021∞),
(031∞)......
