2.5 Cardinality of Sets Flashcards
same cardinality:
The sets A and B have the same cardinality if and only if there is a one-to-one correspondence
from A to B. When A and B have the same cardinality, we write |A| = |B|.
what does cardinality of infinite sets tell us?
For infinite sets the definition of cardinality provides a relative measure of the sizes of two sets,
rather than a measure of the size of one particular set
In Cards 1 and 3 we introduced the notations |A| = |B| and |A| < |B| to denote
that A and B have the same cardinality and that the cardinality of A is less than the cardinality
of B. However, these definitions do not give any separate meaning to |A| and |B| when A and B
are arbitrary infinite sets.
Define what it means for one
set to have a smaller cardinality than another set.
If there is a one-to-one function from A to B, the cardinality of A is less than or the same
as the cardinality of B and we write |A| ≤ |B|. Moreover, when |A| ≤ |B| and A and B have
different cardinality, we say that the cardinality of A is less than the cardinality of B and we
write |A| < |B|.
Countable (notations..) and Uncountable set.
A set that is either finite or has the same cardinality as the set of positive integers is called
countable. A set that is not countable is called uncountable. When an infinite set S is countable, we denote the cardinality of S by ℵ0 (where ℵ is aleph, the first letter of the Hebrew
alphabet).
We write |S| = ℵ0 and say that S has cardinality “aleph null.”
An infinite set is countable if and only if:
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 that a one-to-one correspondence f from the set of positive integers to a set S can be expressed in terms of a sequence
a1, a2, … , an, … , where a1 = f(1), a2 = f(2), … , an = f(n), … .
HILBERT’S GRAND HOTEL
The famous mathematician David Hilbert
invented the notion of the Grand Hotel, which has a countably infinite number of rooms, each occupied by a guest.
Show that the set of all integers is countable.
We can list all integers in a sequence by starting with 0 and alternating between positive and negative integers: 0, 1,−1, 2,−2, …. Alternatively, we could find a one-to-one correspondence between the set of positive integers and the set of all integers. We leave it to the
reader to show that the function f(n) = n∕2 when n is even and f(n) = −(n − 1)∕2 when n is
odd is such a function. Consequently, the set of all integers is countable.
Show that the set of positive rational numbers is countable.
The key to listing the rational numbers in a sequence is to first list the positive rational
numbers p∕q with p + q = 2, followed by those with p + q = 3, followed by those with p + q =
4, and so on.
Check the figure, page 182.
Whenever we encounter a number p∕q that
is already listed, we do not list it again. For example, when we come to 2∕2 = 1 we do not
list it because we have already listed 1∕1 = 1
Comment on a subset of a countable set?
Its also countable.
Cantor diagonalization argument:
Show that set of real numbers in uncountable:
Example 5, page 184.
Comment on every real number has a unique decimal expansion:
A number with a decimal expansion that terminates has a second decimal expansion ending with an infinite sequence of 9s because 1 = 0.999… . So, every real number has a unique decimal expansion (when the possibility that the expansion has a tail end that consists entirely of the digit 9 is excluded).
Theorem of union of two countable sets:
If A and B are countable sets, then A ∪ B is also countable.
SCHRODER-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.
Show that the |(0, 1)| = |(0, 1]|.
It is not at all obvious how to find a one-to-one correspondence between (0, 1) and
(0, 1] to show that |(0, 1)| = |(0, 1]|. Fortunately, we can use the Schroder-Bernstein theorem ¨
instead. Finding a one-to-one function from (0, 1) to (0, 1] is simple. Because (0, 1) ⊂ (0, 1],
f(x) = x is a one-to-one function from (0, 1) to (0, 1]. Finding a one-to-one function from (0, 1]
to (0, 1) is also not difficult. The function g(x) = x∕2 is clearly one-to-one and maps (0, 1] to
(0, 1∕2] ⊂ (0, 1). As we have found one-to-one functions from (0, 1) to (0, 1] and from (0, 1] to
(0, 1), the Schroder-Bernstein theorem tells us that ¨ |(0, 1)| = |(0, 1]|.
Uncomputable Functions:
We say that a function is computable if there is a computer program in some programming
language that finds the values of this function. If a function is not computable we say it is
uncomputable.
show that there are uncomputable functions:
To show that there are uncomputable functions, we need to establish two results.
First, we
need to show that the set of all computer programs in any particular programming language is
countable.
This can be proved by noting that a computer program in a particular language can
be thought of as a string of characters from a finite alphabet (see Exercise 37).
Next, we show
that there are uncountably many different functions from a particular countably infinite set to
itself.
In particular, Exercise 38 shows that the set of functions from the set of positive integers
to itself is uncountable.
This is a consequence of the uncountability of the real numbers between 0 and 1 (see Example 5).
Putting these two results together (Exercise 39) shows that there are uncomputable functions.
The power set of Z+ and R.. Comment on it:
same cardinality |P(Z+)| = |R| = 𝔠 𝔠 denotes the cardinality of the set of real numbers. (𝔠 is the lowercase Fraktur c)
Theorem regarding cardinality of Power Set:
and 𝔠 is how much?
The cardinality of a set is always less than the cardinality of its power set. |Z+| < |P(Z+)| or ℵ0 < 2^ℵ0 which means 𝔠 = 2^ℵ0
THE CONTINUUM HYPOTHESIS
which asserts that there is no cardinal number
X between ℵ0 and 𝔠. [DOUBT]
In other words, the continuum hypothesis states that there is no set A such that ℵ0, the cardinality of the set of positive integers, is less than |A| and |A| is less than 𝔠, the
cardinality of the set of real numbers. It can be shown that the smallest infinite cardinal numbers
form an infinite sequence ℵ0 < ℵ1 < ℵ2 < … . If we assume that the continuum hypothesis is
true, it would follow that 𝔠 = ℵ1, so that 2^ℵ0 = ℵ1.
It was the
first problem posed by David Hilbert in his 1900 list of open problems in mathematics.
However, it has been shown that it can be neither proved nor disproved under the standard set
theory axioms in modern mathematics, the Zermelo-Fraenkel axioms.
