Recap: properties of functions on finite and infinite sets

(1)

CS 207m: Discrete Structures (Minor)

Instructor : S. Akshay

Jan 17, 2018

Lecture 04 – Countable and uncountable sets

(2)

Chapter 2: Basic mathematical structures

Sets and Functions

I Finite and infinite sets, Russell’s paradox, axioms of ZFC.

I Functions, their properties, associativity, inverse.

I Types of functions: surjective, injective and bijective.

I Two sets have the same “size” or cardinality if there is a bijection between them.

Today’s class

I Countable and countably infinite sets.

I A new proof technique.

(3)

Chapter 2: Basic mathematical structures

Sets and Functions

I Finite and infinite sets, Russell’s paradox, axioms of ZFC.

I Functions, their properties, associativity, inverse.

I Types of functions: surjective, injective and bijective.

I Two sets have the same “size” or cardinality if there is a bijection between them.

Today’s class

I Countable and countably infinite sets.

I A new proof technique.

(4)

Recap: properties of functions on finite and infinite sets

Some important properties (H.W.: Prove them!)

I ∃ bij fromA toB and B toC, implies ∃bij from A toC.

I ∃ bij fromA toB, implies ∃bij from B toA.

I ∃ inj fromA toB, implies ∃surj from B toA(&

vice-versa)

I Schr¨oder-Bernstein Theorem: ∃ surjfrom A toB and∃ surj B toA, implies ∃bij from AtoB.

Theorem

LetA be a set andb6∈A. Then Ais infinite iff there is a bijection fromA toA∪ {b}.

Corollary

For any infinite setA, there is a surjection from A toN. Is there also a injection? Are all (infinite) sets bijective toN?

(5)

Recap: properties of functions on finite and infinite sets

vice-versa)

Theorem

Corollary

For any infinite setA, there is a surjection from A toN. Is there also a injection? Are all (infinite) sets bijective toN?

(6)

Recap: properties of functions on finite and infinite sets

vice-versa)

Theorem

Is there also a injection? Are all (infinite) sets bijective toN?

(7)

Recap: properties of functions on finite and infinite sets

vice-versa)

Theorem

Corollary

For any infinite setA, there is a surjection from A toN.

(8)

Comparing infinite sets using functions

Theorem

There is a bijection fromZ toN.

Proof: Hilbert’s hotel argument. But how do you formalize it?

f(x) =

−2x ifx≤0 2x−1 else

Some questions...

I Is there a bijection between N×N toN?

I Is there a bijection between N×N×N toN?

I Is there a bijection from QtoN?

I Is there a bijection from the set of all subsets ofN toN?

I Is there a bijection from RtoN?

(9)

Comparing infinite sets using functions

Theorem

f(x) =

Some questions...

I Is there a bijection between N×N×N toN?

I Is there a bijection from RtoN?

(10)

Comparing infinite sets using functions

Theorem

f(x) =

Some questions...

I Is there a bijection between N×N×NtoN?

(11)

Countable and countably infinite sets

Definition

I For a given set C, if there is a bijection from C toN, then C is calledcountably infinite.

I A set is countableif it is finite or countably infinite.

Examples: even numbers, number of horses,...

By previous corollary (∃ surj from any infinite set to N) Countably infinite sets are the “smallest” infinite sets.

What are the other properties of countable sets?

(12)

Countable and countably infinite sets

Definition

I For a given set C, if there is a bijection from C toN, then C is calledcountably infinite.

I A set is countableif it is finite or countably infinite.

Examples: even numbers, number of horses,...

By previous corollary (∃ surj from any infinite set to N) Countably infinite sets are the “smallest” infinite sets.

What are the other properties of countable sets?

(13)

Some questions...

Are the following sets countable?

That is, is there a bijection from these sets toN?

I the set of all integers Z

I N×N

I N×N×N

I the set of rationals Q

I the set of all (finite and infinite) subsets ofN

I the set of all real numbersR

To show these it suffices to show that

I there is aninjection from these sets to N

I or there is asurjectionfrom N(or any countable set) to these sets.

(14)

Some questions...

I N×N

I N×N×N

I the set of all real numbersR To show these it suffices to show that

(15)

Some questions...

I N×N

I N×N×N

I the set of all real numbersR To show these it suffices to show that

(16)

Union of countable sets is countable

LetA={a₀, . . . ,} be a countably infinite set andB be a set.

Then,isA∪B countable, under the following conditions?

1. B ={b₀}is a singleton 2. B ={b₀, . . . , b_n} is a finite set

3. B ={b₀, . . .} is a countably infinite set

Can we say {a₀, . . . , b₀, . . .} is a countably infinite set?

I But then what is the positionof bi (i.e., natural number corresponding to it)?

I Rather, choose {a₀, b0, a1, b1, . . .}, thenbi is at (2i+ 1)^th position.

I Formally, define a bijection f : (A∪B)→N byf(ai) = 2i and f(b_i) = 2i+ 1

I Are we done? What is missing?

(17)

Union of countable sets is countable

(18)

Union of countable sets is countable

(19)

Union of countable sets is countable

(20)

Union of countable sets is countable

I Formally, define a bijection f : (A∪B)→N byf(ai) = 2i

(21)

Union of countable sets is countable

(22)

Products of countable sets are countable

Theorem: The cartesian product of two countably infinite sets is countably infinite

Proof: LetA, B be countably infinite. Find a way to “number”

the elements inA×B ={(a, b)|a∈A, b∈B}.

I That is, define a bijection from A×B toN.

f(a_i, b_j) =

i+j

X

k=1

k

+j+ 1

Corollaries

I N×N,N×N×N,N×Z×Nare countable.

I The set of (positive) rationals is countable.

Hint: Show thatf(a, b) =a/bis a surjection. How does the result follow?

(23)

Products of countable sets are countable

f(a_i, b_j) =

i+j

X

k=1

k

+j+ 1

Corollaries

(24)

Products of countable sets are countable

f(a_i, b_j) =

i+j

X

k=1

k

+j+ 1

Corollaries

(25)

Products of countable sets are countable

f(a_i, b_j) =

i+j

X

k=1

k

+j+ 1

Corollaries

(26)

Products of countable sets are countable

f(a_i, b_j) =

i+j

X

k=1

k

+j+ 1

Corollaries

(27)

Countable sets and functions

I N×N

I N×N×N

I the set of all real numbersR

(28)

Comparing N and set of all subsets of N

Theorem (Cantor, 1891)

There is no bijection betweenNand the set of all subsets ofN.

(29)

Comparing N and set of all subsets of N

I Proving existence just needs one to exhibit a function

I But how do we prove non-existence?

(30)

Comparing N and set of all subsets of N

I Proving existence just needs one to exhibit a function

I But how do we prove non-existence? Try contradiction.

(31)

Comparing N and set of all subsets of N

There is no bijection betweenNand the set of all subsets ofN. Proof by contradiction: Suppose there is such a bijection, sayf. This would imply that eachi∈N maps to some setf(i)⊆N.

0 1 2 3 . . .

f(0) X × × × . . .

f(1) X × X X . . .

f(2) × × × × . . .

f(3) × X × X . . .

(32)

Comparing N and set of all subsets of N

0 1 2 3 . . .

f(0) X/× × × × . . . f(1) X ×/X X X . . . f(2) × × ×/X × . . . f(3) × X × X/× . . .

I Consider the setS ⊆Nobtained by switching the diagonal

(33)

Comparing N and set of all subsets of N

0 1 2 3 . . .

f(0) X/× × × × . . . f(1) X ×/X X X . . . f(2) × × ×/X × . . . f(3) × X × X/× . . .

I Consider the setS ⊆Nobtained by switching the diagonal elements, i.e., S={i∈N|i6∈f(i)}.

I Asf is bij,∃j∈N, f(j) =S.

(34)

Comparing N and set of all subsets of N

0 1 2 3 . . .

f(0) X/× × × × . . . f(1) X ×/X X X . . . f(2) × × ×/X × . . . f(3) × X × X/× . . .

I Consider the setS ⊆Nobtained by switching the diagonal

(35)

Comparing N and set of all subsets of N

Proof by contradiction: Suppose there is such a bijection, sayf. This would imply that eachi∈N maps to some setf(i)⊆N.

0 1 2 3 . . .

f(0) X/× × × × . . . f(1) X ×/X X X . . . f(2) × × ×/X × . . . f(3) × X × X/× . . .

I Consider the setS ⊆Nobtained by switching the diagonal elements, i.e., S={i∈N|i6∈f(i)}.

I Asf is bij,∃j∈N, f(j) =S.

I S andf(j) differ at position j, for anyj.

(36)

Cantor’s diagonalization

Does this proof look familiar??

(37)

Cantor’s diagonalization

Figure:Cantor and Russell

(38)

Cantor’s diagonalization

I S ={i∈N|i6∈f(i)} is like the one from Russell’s paradox.

(39)

Cantor’s diagonalization

I S ={i∈N|i6∈f(i)} is like the one from Russell’s paradox.

I If ∃j∈Nsuch that f(j) =S, then we have a contradiction.

I Ifj∈S, thenj 6∈f(j) =S.

(40)

Cantor’s diagonalization

In fact, using diagonalization Cantor showed that...

I There cannot be a bijection between any set and its power set (i.e., its set of subsets).(H.W)

(41)

Cantor’s diagonalization

I So there is an infinite hierarchy of “larger” infinities...

I There is no bijection fromR toN(H.W). Moreover, there

(42)

Cantor’s diagonalization

I So there is an infinite hierarchy of “larger” infinities...

(43)

One infinity is “strictly” bigger than another!

I But, there is a surjection from set of all subsets ofN toN.

I Thus, the “size” ofP(N) is strictly greater that N! Can there be some set whose “size” is in between the two? Cantor’s Continuum hypothesis

There is no set whose “cardinality” is strictly betweenNand P(N) (i.e., between naturals and reals).

Figure:1st of Hilbert’s 23 problems for the 20th century in 1900.

(44)

One infinity is “strictly” bigger than another!

I Thus, the “size” ofP(N) is strictly greater that N!

Can there be some set whose “size” is in between the two? Cantor’s Continuum hypothesis

(45)

One infinity is “strictly” bigger than another!

Can there be some set whose “size” is in between the two?

Cantor’s Continuum hypothesis

(46)

One infinity is “strictly” bigger than another!

Can there be some set whose “size” is in between the two?

Cantor’s Continuum hypothesis

(47)

What did the world think about these proofs

(in 1890s?)

(a)Kronecker (b)Poincare (c)Theologians

I Kronecker: Only constructive proofs are proofs! “Scientific Charlatan”, “Corruptor of youth”!

I Poincare: Set theory is a “disease” from which mathematics will be cured.

I Christian Theologians: God=Uniqueness of an absolute infinity. So, what is all this different infinities...?!

I Hilbert: No one can expel us from the paradise that Cantor has created for us.

(48)

What did the world think about these proofs

(in 1890s?)

(a)Kronecker (b)Poincare (c)Theologians

I Kronecker: Only constructive proofs are proofs! “Scientific Charlatan”, “Corruptor of youth”!

I Poincare: Set theory is a “disease” from which mathematics will be cured.

I Christian Theologians: God=Uniqueness of an absolute