Cardinality, Diagonalization, Computability

In this lecture we will learn about:

• Cardinality
• Diagonalization
• Computability
Lecture Credo

“I see, I forget.
I hear, I remember.
I do, I understand.”
— Confucius

Student Name:

Student ID:

Semester:
1 INTRODUCTION 1

1 Introduction
Classification via Mappings

“A recurrent theme in mathematics is the classification of mathematical

objects by means of structure- preserving mapping between them.
In the case of sets considered themselves as spaces, there is no extra struc-
ture beyond the set and hence, the structure may be taken to be the empty
set.”

To carry out the classification of SET, which is based on the cardinality of a given SET, we need the(notion)
concepts of functions.
Using one-to-one and onto (bijective) functions, we can rigorously establish the classification of sets.

1.1 Let us first build our understanding through intuition.

Consider the sets

A = {Alan Turing, Grace Hopper, Ramanujan, John von Neumann}

and

B = {Enigma, Lambda, MockTheta, Infinity, Compiler, Debugger, Architecture, Memory}.

Intuitively, we observe that set B is larger than set A, because B contains more elements than A.
Ex. Write your intuitive answer below

Now, let us give a rigorous explanation.

If we attempt to construct a mapping between A and B that is both one-to-one and onto, we will
always fail.
Why?
Ex. Write your answer below

Now, let us try this on another interesting set, namely the set of all natural numbers N.
Now, we consider a proper subset of N, which is
E = { x ∈ N | x ≡ 0 (mod 2) }

Ex. Describe the set

1 INTRODUCTION 2

a) Is E a proper subset of N?

2 Yes 2 No

Let’s try same thing, we tried for sets A and B before!

2 1

4 2

6 3

8 4

.. ..
. .

2022 1011

2024 1012

E N

If we define a mapping f from E to N,

f : E −→ N

f (n) =

a) Show that the above function is one-one and onto.

Ex. Write your answer below

1 INTRODUCTION 3

See, did you notice something surprising?

In case of Set A and B In case of N

Set A=

Set B=

E
1–1 and
onto
not
possible
N E
B

Ex. Describe the mapping

A B

Even then, we can establish a one-to-one and onto

mapping. This is possible only because “N is an
infinite set”.
“Make sure you take a moment to
appreciate how remarkably, wonderfully
weird this is.”

Thus, the existence of a one-to-one and onto function from a proper subset to the set from
which it is chosen helps us characterize the infinite nature of a set.
Furthermore, the existence of a bijective function between any set A and the set of natural numbers N
allows us to further classify sets.
2 CHARACTERIZING INFINITE 4

Terminology Alert!

Definition: A set X is said to be finite if ∃ a positive integer n such that

X ∼ {1, 2, 3, . . . , n}

Definition: A set X is said to be infinite if ∄ a positive integer n such that

X ∼ {1, 2, 3, . . . , n}

2 Characterizing Infinite
Given any set A, how to judge/characterize it is infinite.
we explored before if we get a subset of given set A and find a bijection between the proper
subset and given set A, then A is .

First, we classified sets between finite and infinite, now we can further classify infinite set into
countable and uncountable.

Terminology Alert!

If a set A is similar to N (denoted by A ∼ N), then A is said to be countable.

If we can not establish bijection between any set A and set of naturals. then A is said to be un-
countable. i.e. A set A is called uncountable if A ≁ N.

(a) Show that the set Z of all integers is countable.

Ex. Write your proof below

2 CHARACTERIZING INFINITE 5

(b) Show that the set Q+ of all positive rational numbers is countable.
Ex. Write your proof below

Theorem: (|Z| = |Q|). There are the same number of integers as rational numbers.

1 2 3 4 5 6 7 8
···
1 2 3 4 5 6 7 8
1 1 1 1 1 1 1 1 1
···
1 2 3 4 5 6 7 8
2 2 2 2 2 2 2 2 2
···
1 2 3 4 5 6 7 8
3 3 3 3 3 3 3 3 3
···
1 2 3 4 5 6 7 8
4 4 4 4 4 4 4 4 4
···
1 2 3 4 5 6 7 8
5 5 5 5 5 5 5 5 5
···
1 2 3 4 5 6 7 8
6 6 6 6 6 6 6 6 6
···
1 2 3 4 5 6 7 8
7 7 7 7 7 7 7 7 7
···
1 2 3 4 5 6 7 8
8 8 8 8 8 8 8 8 8
···
.. .. .. .. .. .. .. .. ..
. . . . . . . . .
..
.

Ex. Write your proof below

2 CHARACTERIZING INFINITE 6

– A game of deduction –

Setup. Instructors: Here is a fun in-class game. Write down a set of five length-5 sequences of 0s and
1s. These are kept secret from the students.
Goal. The students’ goal is to come up with a length-5 sequence of 0s and 1s which is not one of the
instructor’s five.
Game Rules. The students can ask the instructor any yes/no questions about the sequences, and receive
a truthful reply. When the students make their final guess, they should be 100% confident that this guess is
not one of the instructor’s sequences. And they should try to figure it out while asking as few questions as
possible.
Ex. Write your answer below

Theorem: (|R| > |N|). There are more real numbers than natural numbers.
1 ↔ 0.a11 a12 a13 a14 a15 a16 a17 a18 · · ·
2 ↔ 0.a21 a22 a23 a24 a25 a26 a27 a28 · · ·
3 ↔ 0.a31 a32 a33 a34 a35 a36 a37 a38 · · ·
4 ↔ 0.a41 a42 a43 a44 a45 a46 a47 a48 · · ·
5 ↔ 0.a51 a52 a53 a54 a55 a56 a57 a58 · · ·
6 ↔ 0.a61 a62 a63 a64 a65 a66 a67 a68 · · ·
7 ↔ 0.a71 a72 a73 a74 a75 a76 a77 a78 · · ·
8 ↔ 0.a81 a82 a83 a84 a85 a86 a87 a88 · · ·
Ex. Write your proof below
2 CHARACTERIZING INFINITE 7

Story Corner

Cantor, Georg (1845–1918) — Cantor was a German mathematician and born in Saint Petersburg,
Russia. He initiated the theory of sets and the theory of transfinite num- bers/cardinals. Famously,
Cantor was institutionalized to an asylum a number of times most likely suffering depression brought
on by being unremittingly assailed by his con- temporaries in mathematics. His correspondence with
colleagues reflects that he and his work were under constant criticism, particularly from Leopold
Kronecker (1823– 1891) in Berlin.
2 CHARACTERIZING INFINITE 8

Try to solve it!

Challenge Problem

(Rain and rational umbrellas). The rationals are out on the real line and want to stay dry — it is
raining on the continuum interval [0, 1]. You give each rational point a finite-width umbrella to stay
dry, but of different widths; see the given figure. You give the first rational, your favorite rational, an
ε-umbrella (width of ε). The second rational gets an ε/2-umbrella, the third gets an ε/4-umbrella,
and so on. Since each umbrella covers a finite interval then each rational is happy and dry. The
question is: how much of the continuum gets wet as ε → 0?

Theorem: Let A be a set. There is no bijective map between A and P(A), and hence |A| < |P(A)|.
Ex. Write your proof below
2 CHARACTERIZING INFINITE 9

Theorem 1
Every infinite set contains a countably infinite subset.

Proof. Let X be an infinite set.

Since X is infinite, we can choose an element

x1 ∈ X.

Remove this element from the set. The remaining set

X \ {x1 }

is still infinite.
Hence, we can choose another element
x2 ∈ X \ {x1 }.
Again, the set
X \ {x1 , x2 }
is infinite.
Ex. Write further steps of your proof below

■
2 CHARACTERIZING INFINITE 10

Theorem 2
Given an infinite set A, the following strict inequality of cardinalities holds:

|A| < |P(A)| < |P(P(A))| < |P(P(P(A)))|.

If A is countably infinite, then

|A| = ℵ0 , |P(A)| = 2ℵ0 .

Define a sequence of sets {Sn }n≥0 recursively by

S0 = A, Sn = P(Sn−1 ) for n ≥ 1.

Then, for each n ≥ 1,

|Sn | = |P(Sn−1 )|.

Consequently, the sequence of cardinal numbers {ℵn } satisfies

ℵn = 2ℵn−1 for n ≥ 1.

Ex. Try to prove the theorem

3 SCENARIO 11

3 Scenario
When you write a piece of code, it is eventually executed as a finite string of binary symbols. Therefore, we
can establish the following statement:

Statement
The set of all computer programs written in a particular programming language is countable.
Ex. Write your answer below

We also know that the set of real numbers R is uncountable. Hence, there are far more real numbers
than computer programs.
Consequently, it is impossible to establish a one-to-one and onto mapping between the set of all computer
programs and the set of real numbers.

mapping

·
These real numbers are never
·
associated with any program

Set of all programs R

Note

There are real numbers which can never be output of any program/algorithm.

Terminology Alert

Definition:A computable number is a number which is an output of an algorithm.

There are far more uncountable numbers than computable numbers.

4 COMPUTABILITY 12

4 Computability

We are trying to know the story how computers took birth?

Not the electronics/physics of computer parts but way before building physical computing devices, we are
right now interested in the
4 COMPUTABILITY 13

Computers from Thought

Computers as we know them grew out of a desire to avoid bugs in math-

ematical reasoning.

Hilbert in a famous speech at the International Congress of Mathematicians in 1900

set out the goal to mechanize all of mathematics.

In the 1930s, work of Gödel and Turing showed that Hilbert’s program is impos-
sible.

Gödel’s Incompleteness Theorem

Undecidability of the Halting Problem

Both of these employ an idea we will see called diagonalization.

The ideas are simple but so revolutionary that their inventor Georg Cantor was
initially shunned by the mathematical leaders of the time:
Poincaré referred to them as a “grave disease infecting mathematics.”
Kronecker fought to keep Cantor’s papers out of his journals.

Full employment for mathematicians

and computer scientists!!

Exercise

Theorem:The union of countable collection of countable sets is countable.

Proof: Let S0 , S1 , S2 , . . . be a countable collection of countable sets,
[∞
Claim: S = Si is countable.
i=1
*(This notation is in sheet – sets, summation & function)
Each set Si is . which implies, Si can be “listed” with tags 1, 2, 3, . . .,
i.e.
∃ : N to Si

So,
(i) (i) (i)
Si : (a1 , a2 , a3 , . . . , a(i)
n , . . .)
4 COMPUTABILITY 14

Exercise Continue...
Let us list some:
(1) (1) (1)
S1 : (a1 , a2 , a3 , . . . , a(1)
n , . . .)

(2) (2) (2)

S2 : (a1 , a2 , a3 , . . . , a(2)
n , . . .)

(3) (3) (3)

S3 : (a1 , a2 , a3 , . . . , a(3)
n , . . .)

..
.
[
S= Si

Try to list the elements of S.

b1 =

b2 =

b3 =

b4 =
Question: what “rule” (one-one & onto function) did you choose to list down the element?
Ex. Write your answer below

Now, we will apply all these set of techniques in understanding the essence of computation.

From PSP → DSA → ADA you must have written not just tens but hundreds of python programs.
→ Each python program is essentially a string of 0s & 1s which takes input from the user, also converts
it into 0s & 1s & wait for it . . .

COMPUTES

output which is also 0’s & 1’s, everything is Binary.

4 COMPUTABILITY 15

Now, say, we have a set

P = set of all python programs

Is the set P countable or uncountable?
Ex. Try to answer

Theorem: P is countable.
Hint: (Use the result of previous exercise)
Ex. Write your proof below

An interesting conclusion from a set of all python programs that being countable.

P ∼ N ⇒ |P | = |N|

R ≁ N ⇒ |R| ̸= |N|
What can you say about size of P & R?

|P | |R|
Can you derive any conclusion from the above relationship?
Ex. Write your conclusion below

Okay ,
The size of R is much bigger than the size of P which is a set of all python programs. Now, a program is
kind of a machine which takes an input and throws out an output.
4 COMPUTABILITY 16

Now, set of all programs corresponds to their outputs so all those numbers are also countable,
but, R are uncountable.

.py .py
outputs
.py .py of P

.py

Figure 1

.py .py
outputs
.py .py of P

.py

x
R

Figure 2: For this real x, there is no program in this universe which can produce x as an output!!

Such x numbers are uncomputable, there is no process, algorithm, finite method which can produce
x, & due |R| > |P|, there are far more uncomputable numbers than computable ones!

Terminology Alert!

Computable Number: A number n is said to be computable if there exists an algorithm which

can produce n as an output.

Uncomputable Number: A number n is said to be uncomputable if there does not exist any
algorithm which can produce n as an output.
4 COMPUTABILITY 17

Try to read the paper by

We compared the size of possible outputs of all python programs which turned out to be way lesser than the
size of reals (R), giving clarity on limits of numbers which can be computed!!
Let’s shift our focus on python programs / processes / algorithms which are essentially func-
tions.

Exercise

Question: Consider the set of all functions from set of naturals (N) to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},

F = { f : N → {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} | f is a function }
Is F countable?
□ Yes □ No
4 COMPUTABILITY 18

Theorem: F is .
(Hint: Use Cantor’s Diagonal Argument).
Ex. write your proof below

This also illuminates the limits of computation even if we have infinite time, space, resources,
the above analysis shows there are numbers and functions which are uncomputable.

We would like end this mind-bending episode on a cliff-hanger,

How to come up with an example of function or python program which is

UNCOMPUTABLE?