2.5 Cardinality of Sets

Question 1

same cardinality:

Answer 1

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|.

Question 2

what does cardinality of infinite sets tell us?

Answer 2

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.

Question 3

Define what it means for one

set to have a smaller cardinality than another set.

Answer 3

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|.

Question 4

Countable (notations..) and Uncountable set.

Answer 4

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.”

Question 5

An infinite set is countable if and only if:

Answer 5

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), … .

Question 6

HILBERT’S GRAND HOTEL

Answer 6

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.

Question 7

Show that the set of all integers is countable.

Answer 7

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.

Question 8

Show that the set of positive rational numbers is countable.

Answer 8

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

Question 9

Comment on a subset of a countable set?

Answer 9

Its also countable.

Question 10

Cantor diagonalization argument:

Show that set of real numbers in uncountable:

Answer 10

Example 5, page 184.

Question 11

Comment on every real number has a unique decimal expansion:

Answer 11

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).

Question 12

Theorem of union of two countable sets:

Answer 12

If A and B are countable sets, then A ∪ B is also countable.

Question 13

SCHRODER-BERNSTEIN THEOREM

Answer 13

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.

Question 14

Show that the |(0, 1)| = |(0, 1]|.

Answer 14

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]|.

Question 15

Uncomputable Functions:

Answer 15

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.

Question 16

show that there are uncomputable functions:

Answer 16

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.

Question 17

The power set of Z+ and R.. Comment on it:

Answer 17

same cardinality 
|P(Z+)| = |R| = 𝔠
𝔠 denotes the cardinality of the set of real numbers.
(𝔠 is the lowercase
Fraktur c)

Question 18

Theorem regarding cardinality of Power Set:

and 𝔠 is how much?

Answer 18

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

Question 19

THE CONTINUUM HYPOTHESIS

Answer 19

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.