Infinity and its

cardinalities
No one shall expel us from the Paradise
that Cantor has created. David Hilbert
How to use the concept of infinity
coherently
The whole difficulty of the subject lies in the
necessity of thinking in an unfamiliar way, and
in realizing that many properties which we
have thought inherent in number are in fact
peculiar to finite numbers. If this is
remembered, the positive theory of
infinity...will not be found so difficult as it is to
those who cling obstinately to the prejudices
instilled by the arithmetic which is learnt in
childhood. Bertrand Russell (Salmon 1970, 58) 2
19th century mathematics
In the nineteenth century mathematics experienced a
movement towards a progressively abstract style with an
increased emphasis on putting itself on a sound and rigorous
basis and on examining its foundations. This movement
happened in the calculus, algebra and geometry.
In the 1820s the French mathematician Cauchy, the most
prolific mathematician of the century, made a major advance
in making the calculus rigorous by clarifying the concept of a
limit. This idea of a limit is needed in the calculus, for
example, where we have the ratio of two quantities and we
want to see what happens to this ratio as both quantities
move simultaneously towards zero so becoming infinitely
small.
3
19th century mathematics
It was later in the century that the German
mathematician, Weierstrass, gave a mathematically
and logical solid definition of a limit and it is his
definition of a limit that we use today and on which
the calculus is founded.

However, as often happens, the resolution of one

problem drew attention to another problem. It
turned out that getting a sound definition of a limit
necessitated a rigorous definition of the real
numbers which in turn led to the study of infinite
sets by Cantor. 4
Basic Set Theory
Set: any collection into a whole M of definite and
separate objects m of our intuition or of our thought

Broadly speaking a set is a collection of objects.

Examples:
A={1, 3, 4, 6, 8}
B={1, 2, 3, …, 66}
C={2, 4, 6, 8, …}
D={n ∈ ℤ | n is even}
E={x ∈ ℕ | x is a prime number ≤ 106 } 5
Set Equality
Definition: Two sets are equal if and only if
they have the same elements.
Therefore if A and B are sets, then A and B are
equal if and only if .
We write A = B if A and B are equal sets.
For example, in set notation order and repetition
does not matter since:
{1,3,5} = {3, 5, 1}
{1,5,5,5,3,3,1} = {1,3,5}
6
Cardinality

The number of elements in a set is called the

cardinal number, or cardinality of the set.

The symbol n(A), read “n of A,” represents the

cardinal number of set A.

7
Cardinality

Find the cardinal number of each set.

a) K = {a, l, g, e, b, r}
b) M = {0}
c) C = { 13, 14, 15,…,22, 23}

Solution
a) n(K) = 6
b) n(M) = 1
c) n(C) = 11
8
Finite and Infinite Sets

If the cardinal number of a set is a particular

whole number, we call that set a finite set.

Whenever a set is so large that its cardinal

number is not found among the whole numbers,
we call that set an infinite set. This is Intuitive
but an informal definition.

9
Galileo’s Paradox of Equinumerosity
“There are as many squares as there are numbers because they are just as
numerous as their roots.” — Galileo Galilei, 1632

Consider the set of natural numbers Ν = {1, 2, 3, 4, …} and the set of perfect
squares (i.e. the squares of the naturals) S = {1, 4, 9, 16, 25, …}. After careful
thought, Galileo produced the following contradictory statements regarding
these two sets:

1 – While some natural numbers are perfect squares, some are clearly not.
Hence the set N must be more numerous than the set S, or |N|>|S|.

2 – Since for every perfect square there is exactly one natural that is its
square root, and for every natural there is exactly one perfect square, it
follows that S and N are equinumerous, or |N|=|S|.
10
Galileo’s Paradox of Equinumerosity
Here, Galileo’s exact matching of the naturals with the perfect squares
constitutes an early use of a one-to-one correspondence between sets – the
conceptual basis for Cantor’s theory of sets.

To resolve the paradox, Galileo concluded that the concepts of “less,” “equal,”
and “greater” were inapplicable to the cardinalities of infinite sets such
as S and N, and could only be applied to finite sets.

In fact, Cantor would prove that, in general, this is not true. He showed that
some infinite sets have a greater cardinality than others, thus implying the
existence of different “sizes” for infinity. 11
Equivalent Sets

Set A is equivalent to set B if and only if n(A) = n(B).

Example:
D={ a, b, c }; E={apple, orange, pear}
n(D) = n(E) = 3
So set A is equivalent to set B.

12
Equivalent Sets
Any sets that are equal must also be
equivalent.
Not all sets that are equivalent are equal.

Example: D ={ a, b, c }; E ={apple, orange, pear}

n(D) = n(E) = 3; so set A is equivalent to set B,

but the sets are NOT equal, since they do not
contain the elements of each other.
2.6-13
13
Cardinality and Finite Sets
DEF: Two sets A and B have are in one to one
correspondence (bijection) if there’s a pairing
(function) between the elements of one set to the
other such that:
for each element of one set there is one and only one
partner on the other set (function is one-to-one), and
vice versa. There are no unpaired elements (function
is onto).
{,} {1, 8, 12}

{ , } {61, 121}
14
Infinite Set
An infinite set is a set that can be placed in a one-
to-one correspondence with a proper subset of
itself.

A proper subset does not contain all the elements

of the set.

This a nonintuitive definition, that is more formal,

and independent of the notion of cardinality. It
takes us away from our “finite” experience. 2.6-15
15
The Set of Natural Numbers

Show that N = {1, 2, 3, 4, 5, …, n,…} is an infinite

set.

2.6-16
16
The Set of Natural Numbers

Solution
Remove the first element of set N, to get the
proper subset P of the set of counting numbers
N = {1, 2, 3, 4, 5,…, n,…}

P = {2, 3, 4, 5, 6,…, n + 1,…}

For any number n in N, its corresponding number
in P is n + 1.
An explicit one-to-one and onto function
(bijection) f:N→P is given by f(n)=n+1
17
The Set of Natural Numbers

Solution
We have shown the desired one-to-one
correspondence, therefore the set of counting
numbers is infinite.

N = {1, 2, 3, 4, 5,…, n,…}

P = {2, 3, 4, 5, 6,…, n + 1,…}

2.6-18
18
Understanding Proper subsets
Careful visualizing One-to-one correspondence
between an infinite set and its proper subsets
Not including some of the elements of the original
set does not disqualify having the same cardinality

19
Countable Sets
A set is countable if it is finite or if it can be
placed in a one-to-one correspondence with
the set of counting numbers (countable
infinite).

All infinite sets that can be placed in a one-to-

one correspondence with a set of counting
numbers have cardinal number aleph-naught
or aleph-zero, symbolized ℵ0.

2.6-20
20
The Cardinal Number of the Set of
Odd Numbers

Show the set of odd counting numbers has

cardinality ℵ0.

2.6-21
21
The Cardinal Number of the Set of
Odd Numbers
Solution
We need to show a one-to-one correspondence
between the set of counting numbers and the set
of odd counting numbers.
N = {1, 2, 3, 4, 5,…, n,…}

O = {1, 3, 5, 7, 9,…, 2n–1,…}

An explicit one-to-one and onto function

(bijection) f:N→O is given by f(n)=2n-1 22
The Cardinal Number of the Set of
Odd Numbers
Solution
Since there is a one-to-one correspondence, the
odd counting numbers have cardinality ℵ0; that is
n(O) = ℵ0.

N = {1, 2, 3, 4, 5,…, n,…}

O = {1, 3, 5, 7, 9,…, 2n–1,…}

2.6-23
Infinite Countable Sets
By similar one to one correspondences, one
can show that the following sets have
cardinality ℵ0.

Even numbers
Perfect squares, cubes or perfect nth powers
Prime numbers
Fibonacci numbers
Any infinite subset of the counting numbers
24
The Cardinal Number of the Integers
That makes sense, ℵ0 is the smallest infinity.
Obviously we need bigger sets to possibly find
bigger sizes of infinity
Integers = {…-3,-2,-1,0,1, 2,3,…}
Is the set of all integers countable infinite?
Can we find a pairing (1-to-1 correspondence)
with the counting numbers?

25
 The Cardinal Number of the
Integers
Since there is a one-to-one correspondence, the Integers have
cardinality ℵ0
N = {1, 2, 3, 4, 5, 6, 7,…,

Z = {0,1, -1, 2, -2,3, -3…}

An explicit one-to-one and onto
function (bijection) f:N→Z is given by An explicit one-to-one and onto
function (bijection) f:Z→N is given by
𝑛𝑛
𝑖𝑖𝑖𝑖 𝑛𝑛 𝑖𝑖𝑖𝑖 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒
2 2𝑛𝑛 𝑖𝑖𝑖𝑖 𝑛𝑛 𝑖𝑖𝑖𝑖 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝
𝑓𝑓 𝑛𝑛 = 𝑓𝑓 𝑛𝑛 = �
𝑛𝑛 − 1 2 𝑛𝑛 + 1 𝑖𝑖𝑖𝑖 𝑛𝑛 𝑖𝑖𝑖𝑖 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛
− 𝑖𝑖𝑖𝑖 𝑛𝑛 𝑖𝑖𝑖𝑖 𝑜𝑜𝑜𝑜𝑜𝑜
2

26
The Cardinal Number of the
Integers
Since there is a one-to-one correspondence, the Integers have
cardinality ℵ0
N = {1, 2, 3, 4, 5, 6, 7,…,

Z = {0,1, -1, 2, -2,3, -3…}

“cut number line in half” and interleave the integers 27

Hilbert’s Paradox of the Grand Hotel
In the early 1900’s, the German mathematician David Hilbert
proposed a hypothetical scenario that keenly illustrates
Cantor’s counter-intuitive results on infinite sets.

He called it the paradox of the Grand Hotel (or Hotel Infinity).

Consider a hotel with infinitely many rooms, all of which are

occupied (filled at capacity).

He showed that it was possible then to accommodate a

countably infinite number of passengers arriving at the hotel in
a countably infinite number of buses!

28
Hilbert’s Grand Hotel

Lets start analysing finite

new arrivals to the filled
hotel.
One new arrival

29
Hilbert’s Grand Hotel

One new arrival

Everybody moves up ONE
room.
Since no LAST room! Everyone
gets a room.
New arrival put in room 1
Done!
Correspondence n → n+1
1 + ℵ0 = ℵ0

30
 Hilbert’s Grand Hotel
• 259 new arrivals

31
 Hilbert’s Grand Hotel
• 259 new arrivals
• Everybody moves up 259
rooms, so if they are in
room n they move to room
n + 259
• New arrivals put in rooms
1 to 259. Done!
• Works for any finite k
number of new arrivals.
• Correspondence n → n+k
• k + ℵ0 = ℵ0 32
Hilbert’s Grand Hotel
Suppose now an infinite
long buss arrives fully
filled with an infinite
number of new arrivals

33
 Hilbert’s Grand Hotel

Everybody moves to the room

with number twice that of their
current room: n → 2n N: 1 2 3 4 5 … n …
All the odd numbered rooms are
now free and he uses them to
accommodate the infinite number E: 2 4 6 8 10 … 2n …
of people on the bus

ℵ0 + ℵ0 = ℵ0 34
Hilbert’s Grand Hotel
Countably infinite
number of buses each
with countably infinite
passengers

35
Hilbert’s Grand Hotel

36
Countably infinite number of buses each
with countably infinite passengers

37
Hilbert’s Grand Hotel

38
Hilbert’s Grand Hotel

39
Hilbert’s Grand Hotel

ℵ0 times ℵ0 = ℵ0 40
Hilbert’s Paradox of the Grand Hotel
A more tangible algorithm for selection of room numbers
Empty the odd numbered rooms by sending the guest in room
n to room 2n
Put the nth passenger of the first infinite bus load in rooms 3n
The nth passenger of the second infinite bus in rooms 5n
In general, the nth passenger in bus number k uses the rooms
Pn where P is the kth odd prime number.
This solution leaves certain rooms empty (which may or may
not be useful to the hotel); specifically, all odd numbers that
are not prime powers, such as 15 or 847, will no longer be
occupied.
But what a wonderful discovery, an infinite amount busses
filled with infinite passengers, fit into a single infinite hotel!!!
https://www.youtube.com/watch?v=Uj3_KqkI9Zo 41
Only one size of infinity?
I see what might be going on – we can do this because these
infinite sets are discrete, have gaps, and this is what allows
the method to work because we can somehow interleave
them and this is why we always end up with ℵ0.
Lets fill in the gaps. A rational number or fraction is any
integer divided by any nonzero integer, for example, 5/4,
87/32, -567/981.
The rationals don’t have gaps in the sense that between any
two rationals there is another rational.
Even more the rational numbers are dense in the reals,
meaning that for every real number there is always a rational
number “arbitrarily close” to it.
Surely the rationals are not countable, right?? 42
Cardinality of the Rational numbers
Rationals=all fractions
𝒑𝒑
𝑸𝑸 = 𝒑𝒑, 𝒒𝒒 ∈ 𝒁𝒁, 𝒒𝒒 ≠ 𝟎𝟎
𝒒𝒒
Is the set of all rationals countable
infinite?
If we can find a one-to-one
correspondence with the positive
rationals we play the same game as
integers to get the negative ones.

43
Cardinality of the Rational numbers

44
 Cardinality of the Rational numbers

In particular, the one to one correspondence is given by

1↔0/1, 2↔1/1, 3 ↔2/1, 4↔1/2, 5 ↔1/3, 6 ↔1/4,…

So Cardinality of the Rational numbers is ℵ0 45

Cardinality of the Rational numbers

𝑝𝑝
The function f:Q→N, 𝑓𝑓 = 2𝑝𝑝 3𝑞𝑞
𝑞𝑞
Injects the rational into the counting numbers

Thm: The following are equivalent

a) Set A is countable infinite
b) There is an onto function f:N →A
c) There is an injection (one-to-one) function f:A →N

Need discrete math or beyond to go deeper into such

proofs.
46
 Cantor’s infinities

Bronze monument to Cantor

in Halle-Neustadt
Georg Cantor 1845 – 1918 47
 Uncountability of the set of
Real Numbers
So Far all of the sets we have encountered are countable
infinity. Is there only one “size” of infinity?
In order to prove that other sized of infinity exist we
must show that there is a set of numbers that is not
countable. That is bigger than “first size” of infinity.
Suppose that R were countable. In particular, any
subset of R, being smaller, would be countable also.
So the interval (0,1) would be countable.
So if we can show that all the decimal numbers between
0 and 1 are not countable we have discovered that
they are of a different size of infinity.

48
 Uncountability of R
Cantor’s Diabolical Diagonal
Suppose that all real numbers between 0 and 1 are
countable. So there exist a pairing with the
countable numbers.
That means we can we have a list, were we can see the
first number, second, etc.
r1 , r2 , r3 , r4 , r5 , r6 , r7, …
Suppose the above list contains EVERY real number
between 0 and 1.
Cantor’s diabolical diagonalization argument will take
this supposed list, and create a number between 0
and 1 which is not on the list. This will contradict
the countability assumption hence proving that R is
not countable.
49
 Cantor's Diagonalization
Argument
 Decimal expansions of ri 

r1 0.
r2 0.
r3 0.
r4 0.
r5 0.
r6 0.
r7 0.
:
revil 0. 50
 Cantor's Diagonalization
Argument
 Decimal expansions of ri 

r1 0. 1 2 3 4 5 6 …
r2 0.
r3 0.
r4 0.
r5 0.
r6 0.
r7 0.
:
revil 0. 51
 Cantor's Diagonalization
Argument
 Decimal expansions of ri 

r1 0. 1 2 3 4 5 6 …
r2 0. 1 1 1 1 1 1 …
r3 0.
r4 0.
r5 0.
r6 0.
r7 0.
:
revil 0. 52
 Cantor's Diagonalization
Argument
 Decimal expansions of ri 

r1 0. 1 2 3 4 5 6 …
r2 0. 1 1 1 1 1 1 …
r3 0. 2 5 4 2 0 9 …
r4 0.
r5 0.
r6 0.
r7 0.
:
revil 0. 53
 Cantor's Diagonalization
Argument
 Decimal expansions of ri 

r1 0. 1 2 3 4 5 6 …
r2 0. 1 1 1 1 1 1 …
r3 0. 2 5 4 2 0 9 …
r4 0. 7 8 9 0 6 2 …
r5 0.
r6 0.
r7 0.
:
revil 0. 54
 Cantor's Diagonalization
Argument
 Decimal expansions of ri 

r1 0. 1 2 3 4 5 6 …
r2 0. 1 1 1 1 1 1 …
r3 0. 2 5 4 2 0 9 …
r4 0. 7 8 9 0 6 2 …
r5 0. 0 1 1 0 1 0 …
r6 0.
r7 0.
:
revil 0. 55
 Cantor's Diagonalization
Argument
 Decimal expansions of ri 

r1 0. 1 2 3 4 5 6 …
r2 0. 1 1 1 1 1 1 …
r3 0. 2 5 4 2 0 9 …
r4 0. 7 8 9 0 6 2 …
r5 0. 0 1 1 0 1 0 …
r6 0. 5 5 5 5 5 5 …
r7 0.
:
revil 0. 56
 Cantor's Diagonalization
Argument
 Decimal expansions of ri 

r1 0. 1 2 3 4 5 6 …
r2 0. 1 1 1 1 1 1 …
r3 0. 2 5 4 2 0 9 …
r4 0. 7 8 9 0 6 2 …
r5 0. 0 1 1 0 1 0 …
r6 0. 5 5 5 5 5 5 …
r7 0. 7 6 7 9 5 4 …
:
revil 0. 57
 Cantor's Diagonalization
Argument
 Decimal expansions of ri 

r1 0. 1 2 3 4 5 6 …
r2 0. 1 1 1 1 1 1 …
r3 0. 2 5 4 2 0 9 …
r4 0. 7 8 9 0 6 2 …
r5 0. 0 1 1 0 1 0 …
r6 0. 5 5 5 5 5 5 …
r7 0. 7 6 7 9 5 4 …
:
revil 0. 2 9 7 5 0 4 … 58
 Is New decimal number in our
original list?
revil 0. 2 9 7 5 0 4 …

revil Is constructed by changing the digits of

the main diagonal number.

59
 Is New decimal number in our
original list?
revil 0. 2 9 7 5 0 4 …
Is this the same as the first number in our list?
NO, we changed the first digit.
It cannot be the second number since we changed the second digit.
It cannot be the nth number in the list since we changed the nth digit.

Conclusion: This new decimal number is not in our list. But it is still a
decimal number between 0 and 1.

So all the real numbers between 0 and 1 are UNCOUNTABLE

Eureka!, you have found a new “size” of infinity.

60
Cardinality of the real line
If the cardinality of all real numbers between (0,1) is
uncountable, what about all real numbers?
Let the decimals in the interval (0,1) be represented
as a line segment and bend into a semicircle, position
it above the real line:

61
 Cardinality of the real line
Rays emanating from point P will establish a
geometric pairing for the points on the
semicircle with the points on the line.
So the cardinality of the real number line is
same as (0,1), namely uncountable infinite

−10100

2 𝜋𝜋
62
The cardinality of the reals is the same as that of
the interval of the reals between 0 and 1

The cardinality of the reals is

often denoted by c
for the continuum of real
numbers.

Consider the one-to-one

correspondence: f:(0,1)→ ℝ

2𝑥𝑥 − 1
𝑓𝑓(𝑥𝑥) =
𝑥𝑥 − 𝑥𝑥 2
63
 Power set of a set
Given a set A, the power set of A, denoted by P(A), is the
set of all subsets of A.

For example, for set A = {a, b, c}, has cardinality n(A)=3,

and has 23 =8 subsets, namely:

P(A) = { { }, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

{ } is the empty set and if a set has n elements it has 2n

subsets. So the cardinality of the power set is: n(P(A))= 2n(A)

The power set is itself a set 64

𝒄𝒄 = ℵ
𝟐𝟐 𝟎𝟎
Indeed we can show that the reals (the
continuum) have the cardinality of the power
set of the natural numbers which is often
written as above.

65
 Cardinality of some sets
Set Description Cardinality
Natural numbers 1, 2, 3, 4, 5, … ℵ0
Integers …, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, … ℵ0
Rational numbers or All the decimals which terminate or ℵ0
fractions repeat
Irrational numbers All the decimals which do not C
terminate or repeat
Real numbers All decimals C

66
 Cardinality of some sets
Set Description Cardinality
Real numbers All decimals c
Algebraic numbers All solutions of polynomial ℵ0
equations with integer coefficients.
All rationals are algebraic as well as
many irrationals e. g. √2.
Transcendental numbers All reals which are not algebraic c
numbers e.g. π, e, 2√2

67
 𝒏𝒏
𝒏𝒏 ℝ = 𝒏𝒏(ℝ)
“I see it, but I don’t believe it”. Cantor
If we can show a one-to-one correspondence
between 0,1 × (0,1) × ⋯ (0,1) ↔ (0,1), we
can extend this result for ℝ𝒏𝒏 ↔ ℝ, proving
that 𝒏𝒏 ℝ𝒏𝒏 =c=𝒏𝒏(ℝ)
Let 𝑥𝑥 ∈ (0,1)𝒏𝒏 decimal expansion be given by:
(0. 𝑎𝑎1 𝑎𝑎2 𝑎𝑎3 … , 0. 𝑏𝑏1 𝑏𝑏2 𝑏𝑏3 … , ⋯ , 0. 𝑧𝑧1 𝑧𝑧2 𝑧𝑧3 … ),
then we can match it to y ∈ (0,1) by
interleaving digits (“chunks”) as
(0. 𝑎𝑎1 𝑏𝑏1 𝑐𝑐1 … 𝑧𝑧1 𝑎𝑎2 𝑏𝑏2 𝑐𝑐2 … 𝑧𝑧2 𝑎𝑎3 𝑏𝑏3 𝑐𝑐3 … 𝑧𝑧3 … )
68
 𝒏𝒏
𝒏𝒏 ℝ = 𝒏𝒏(ℝ)
Cantor originally tried interleaving the digits himself, but
Dedekind pointed out the problem of nonunique decimal
representations, namely how ½=0.5=0.4999…., or 0.999….=1
In order to resolve the interleaving digits not being reversible
in those cases, we need to use “chunking” by always choosing
the non terminating zero representation of the decimal,
meaning 0.199… instead of its equal representation 0.200…,
and going to the next nonzero digit, inclusive.
For example For example, 1/200=0.00499… is broken up as
004 9 9 9…, and 0.01003430901111… is broken up as
01 003 4 3 09 01 1 1…
Now instead of interleaving digits, we interleave chunks. To
interleave 0.004999… and 0.01003430901111…, we get
0.004 01 9 003 9 4 9…. 69
 𝒏𝒏
𝒏𝒏 ℝ = 𝒏𝒏(ℝ)
Lets visualize this extraordinary result
The result was proved by Cantor in 1878, but
only became intuitively apparent in 1890,
when Giuseppe Peano introduced the space-
filling curves.
Curved lines that twist and turn enough to
fill the whole of any square, or cube, or
hypercube, or finite-dimensional space.
Pictured on the right are the first three steps
of a fractal construction whose limit is a
space-filling curve, showing that there are as
many points in a one-dimensional line as in a
two-dimensional square.
70
Cantor’s Theorem
For any set A, the power set of A, P(A) has a strictly
greater cardinality than A itself.

Clearly we can inject A→P(A), by taking each element

x →{x} to the singleton set containing it.

So n(A)≤n(P(A)), but now we need to show equality

cannot happen and thus strict inequality exist.

So in order to show no one-to-one correspondence

exist, it suffices to show no onto function exist.
71
Cantor’s Theorem
Complete proof of Cantor’s power set theorem

𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝑓𝑓: 𝐴𝐴 → 𝑃𝑃 𝐴𝐴 . 𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑥𝑥 ∈ 𝐴𝐴|𝑥𝑥 ∉ 𝑓𝑓(𝑥𝑥) ∉ 𝑓𝑓 𝐴𝐴 . 𝑄𝑄. 𝐸𝐸. 𝐷𝐷.

Feel free to use it to impress family and friends.

Not clear?
Ok, lets break this proof down for us mere mortals.

72
No set can be placed in one-to-one
correspondence with its power set
Proof by contradiction. Suppose there is such onto
function from A→P(A), and correspondence given by:
Elements of A Elements of P[A]
(i.e. subsets of A)
a {c, d}
b {e}
c {b, c, d, e}
d {}
e A
f {a, c, e, g, …}
g {b, k, m, …}

. .
. .
. . 73
 No set can be placed in one-to-one
correspondence with its power set
Elements of A Elements of P[A]
(i.e. subsets of A)
a {c, d}
b {e}
c {b, c, d, e}
d {}
e A
f {a, c, e, g, …}
g {b, k, m, …}
. .
. .
. .
Let B be the set of each and every element of the original set A that is
not a member of the subset with which it is matched.
For the matching above, B = {a, b, d, f, g, …} 74
Now B is just a subset of A so must appear
somewhere in the right-hand column and so is
matched with some element of A say z
. .
. .
. .
z B

. .
. .
. .

75
 Now B is just a subset of A so must appear
somewhere in the right-hand column and so is
matched with some element of A say z
. .
. .
. .
z B

. .
. .
. .

Now for the fatal question! Is z an element of B?

Since z is an element of A, it must be in B or not be in B
76
Case 1: Suppose z is an element of B
Then by definition of set B, which consists of
elements which do not belong to their matching
subset, z must not belong to B! Contradiction

. .
. .
. .
z B

. .
. .
. .

77
Case 2: Suppose z is not an element of B
Then z satisfies the defining property of B which
is that it consists of elements which do not
belong to their matching subset, so z does
belong to B! Contradiction!
. .
. .
. .
z B

. .
. .
. .

Thus proving, that for any set A, the power set of A,

P(A) has a strictly greater cardinality than A itself. 78
Infinity of infinities
Reals have smaller cardinality than the power set
of the reals.
Which is smaller than the power set of the power
set of the reals
Which is smaller than the power set of the power
set of the power set of the reals
Which is smaller than the power set of the power
set of the power set of the reals, etc!
𝑛𝑛 ℝ < 𝑛𝑛 𝑃𝑃 ℝ < 𝑛𝑛 𝑃𝑃 𝑃𝑃 ℝ < 𝑛𝑛 𝑃𝑃 𝑃𝑃 𝑃𝑃 ℝ <⋯
79
“Infinitely
many more
cardinals”

80
The continuum Hypothesis
So far, 𝑛𝑛 ℕ = ℵ0 and 𝑛𝑛 ℝ = 𝑐𝑐, called the
continuum.
The proposal originally made by Georg Cantor
that there is no infinite set with a cardinal
number between that of the "small" infinite
set of integers ℵ0 and the "large" infinite set
of real numbers 𝑐𝑐 (the "continuum").
Symbolically, the continuum hypothesis is that
ℵ1 = 𝑐𝑐
81
Continuum hypothesis
The Continuum hypothesis states:
there is no transfinite cardinal falling strictly
between ℵ0 and c

Work of Gödel (1940) and of Cohen (1963)

together implied that the continuum hypothesis
was independent of the other axioms of set
theory

82
Cantor’s assessment of his theory
of the infinite
My theory stands as firm as a rock;
every arrow directed against it will
return quickly to its archer. How do
I know this? Because I have
studied it from all sides for many
years; because I have examined all
objections which have ever been
made against the infinite numbers;
and above all because I have
followed its roots, so to speak, to
the first infallible cause of all
created things. Cantor circa 1870 83
Transfinite Arithmetic
When Cantor proposed his cardinal numbers (informally, the
sizes of all finite or infinite sets), he also devised a new type of
arithmetic for these generalized numbers.

If the cardinal numbers are finite, then the operations are

those of ordinary arithmetic.

If the cardinal numbers are transfinite, then we have the

following identities:

(Cantor’s Power Set Theorem)

Hence we have, for example

84
Historical Background (Pre-Cantor)
5th Century B.C. The Greek philosopher Zeno of Elea proposes his
paradoxes of motion, all rooted in some misconceptions of the infinite
(but also in deeper questions relating to the nature of time and space...)

4th Century B.C. Aristotle’s work in metaphysics makes a distinction

between the “potential” infinite and the “actual” infinite.

Early 17 th Century Galileo shows the equinumerosity of the natural

numbers with the perfect squares, leading to his celebrated paradox.
His attempt to resolve this problem launches the first modern line of
inquiry towards the infinite.

Late 17th Century Isaac Newton and Gottfried Leibniz independently

develop the infinitesimal calculus, effectively paving the way for abstract
analysis – a pillar of modern mathematics. 85
Historical Background (Post-Cantor)
1870’s The Russian mathematician Georg Cantor proposes his ground-
breaking theory of sets and an arithmetic for “transfinite” cardinal
numbers. His work grounds the concept of infinity on a rigorous
mathematical basis and equips mathematics with a firm logical foundation.

1900’s The British logician Bertrand Russell points to the simplest and
most damaging paradox that emerges from Cantorian set theory.

1920’s The German mathematicians Ernst Zermelo and Abraham

Fraenkel formulate an axiomatic theory of sets (known as ZFC when
including the axiom of choice) and resolve all standing paradoxes.

1960’s - The American mathematician Paul Cohen builds on previous work

by the Austrian logician Kurt Gödel to show that the continuum hypothesis
is independent from ZFC. 86
 Devil's staircase

“No one shall

expel us from
the Paradise
that Cantor
has created.”
David Hilbert
1926
Cantor Set
87
Expand your knowledge with
https://www.youtube.com/watch?time_continue=65
2&v=23I5GS4JiDg

https://www.youtube.com/watch?v=i7c2qz7sO0I

https://www.youtube.com/watch?v=KDCJZ81PwVM

https://www.youtube.com/watch?v=SrU9YDoXE88

88