Recap: An Induction Puzzle

CS 207m: Discrete Structures (Minor)

Instructor : S. Akshay

Jan 12, 2018

Lecture 03 – Basic Mathematical Structures

Recap: An Induction Puzzle

An odd number of students stand at mutually distinct distances. At the same time, each student throws a paper rocket at their nearest neighbour, hitting this person. Use mathematical induction, to show that there is at least one survivor, i.e., at least one student who is not hit by a rocket!

I P(n) be the statement that there is a survivor whenever 2n+ 1 students stand at distinct mutual distances and each student throws a rocket at their nearest neighbour. Show that P(n) is true for all positive integersn.

I Base case: n=1.

I Assume for groups of 2k+ 1 students. Now consider a group of 2k+ 3 students.

I Consider the closest pair A-B and divide into two cases based on whether someone threw rocket at them.

2

Recap: An Induction Puzzle

An odd number of students stand at mutually distinct distances. At the same time, each student throws a paper rocket at their nearest neighbour, hitting this person. Use mathematical induction, to show that there is at least one survivor, i.e., at least one student who is not hit by a rocket!

I P(n) be the statement that there is a survivor whenever 2n+ 1 students stand at distinct mutual distances and each student throws a rocket at their nearest neighbour. Show that P(n) is true for all positive integersn.

I Base case: n=1.

I Assume for groups of 2k+ 1 students. Now consider a group of 2k+ 3 students.

I Consider the closest pair A-B and divide into two cases based on whether someone threw rocket at them.

Recap: An Induction Puzzle

An odd number of students stand at mutually distinct distances. At the same time, each student throws a paper rocket at their nearest neighbour, hitting this person. Use mathematical induction, to show that there is at least one survivor, i.e., at least one student who is not hit by a rocket!

I P(n) be the statement that there is a survivor whenever 2n+ 1 students stand at distinct mutual distances and each student throws a rocket at their nearest neighbour. Show that P(n) is true for all positive integersn.

I Base case: n=1.

I Assume for groups of 2k+ 1 students. Now consider a group of 2k+ 3 students.

I Consider the closest pair A-B and divide into two cases based on whether someone threw rocket at them.

2

Recap: An Induction Puzzle

An odd number of students stand at mutually distinct distances. At the same time, each student throws a paper rocket at their nearest neighbour, hitting this person. Use mathematical induction, to show that there is at least one survivor, i.e., at least one student who is not hit by a rocket!

I P(n) be the statement that there is a survivor whenever 2n+ 1 students stand at distinct mutual distances and each student throws a rocket at their nearest neighbour. Show that P(n) is true for all positive integersn.

I Base case: n=1.

I Assume for groups of 2k+ 1 students. Now consider a group of 2k+ 3 students.

I Consider the closest pair A-B and divide into two cases based on whether someone threw rocket at them.

Recap: An Induction Puzzle

An odd number of students stand at mutually distinct distances. At the same time, each student throws a paper rocket at their nearest neighbour, hitting this person. Use mathematical induction, to show that there is at least one survivor, i.e., at least one student who is not hit by a rocket!

I P(n) be the statement that there is a survivor whenever 2n+ 1 students stand at distinct mutual distances and each student throws a rocket at their nearest neighbour. Show that P(n) is true for all positive integersn.

I Base case: n=1.

I Assume for groups of 2k+ 1 students. Now consider a group of 2k+ 3 students.

I Consider the closest pair A-B and divide into two cases based on whether someone threw rocket at them.

2

Recap of last two lectures

Chapter 1: Mathematical reasoning

I Propositions, Predicates, Axioms,

I Theorems and Types of proofs: contradiction, contrapositive, etc.

I Principle of Mathematical Induction

I Well-ordering principle and Strong Induction

Today:- Chapter 2: Basic Mathematical Structures

I Sets

I Functions

Recap of last two lectures

Chapter 1: Mathematical reasoning

I Propositions, Predicates, Axioms,

I Theorems and Types of proofs: contradiction, contrapositive, etc.

I Principle of Mathematical Induction

I Well-ordering principle and Strong Induction

Today:- Chapter 2: Basic Mathematical Structures

I Sets

I Functions

3

Sets

Figure: Georg Cantor (1845-1918); extract

What is a set?

I A set is an unordered collection of objects.

I The objects in a set are called its elements.

Sets

Figure: Georg Cantor (1845-1918); extract

What is a set?

I A set is an unordered collection of objects.

I The objects in a set are called its elements.

4

Sets

Figure: Georg Cantor (1845-1918); extract

What is a set?

I A set is an unordered collection of objects.

I The objects in a set are called its elements.

More formally,

LetP be a property. Any collection of objects that are defined by (or satisfy)P is a set, i.e.,S ={x|P(x)}.

Some simple boring stuff about sets

Examples and properties

I We have already seen examples: Z,N,R, set of all horses,...

I Let A, B be two sets. Recall the usual definitions:

I EqualityA=B, SubsetA⊆B,

I Cartesian productA×B={(a, b)|a∈A, b∈B}

I UnionA∪B={x|a∈Aorb∈B}

I IntersectionA∩B ={x|a∈Aandb∈B}

I Empty setφ,

I Power set ofA=P(A)= set of all subsets ofA.

I IfU is the universe, then the complement ofA, A¯=A^c ={x∈U |x6∈A}.

So, what is the difference between{∅}and ∅?

5

Some simple boring stuff about sets

Examples and properties

I We have already seen examples: Z,N,R, set of all horses,...

I Let A, B be two sets. Recall the usual definitions:

I EqualityA=B, SubsetA⊆B,

I Cartesian productA×B={(a, b)|a∈A, b∈B}

I UnionA∪B={x|a∈Aorb∈B}

I IntersectionA∩B ={x|a∈Aandb∈B}

I Empty setφ,

I Power set ofA=P(A)= set of all subsets ofA.

I IfU is the universe, then the complement ofA, A¯=A^c ={x∈U |x6∈A}.

So, what is the difference between{∅}and ∅?

Not so simple...

A barber is a man in town who only shaves those who don’t shave themselves.

Barber’s paradox: Does the barber shave himself?

6

Not so simple...

A barber is a man in town who only shaves those who don’t shave themselves.

Barber’s paradox: Does the barber shave himself?

Russell’s paradox LetS={X|X 6∈X}

Then ifS ∈S, thenS 6∈S and if S6∈S, thenS∈S!

Not so simple...

A barber is a man in town who only shaves those who don’t shave themselves.

Barber’s paradox: Does the barber shave himself?

Russell’s paradox LetS={X|X 6∈X}

Then ifS ∈S, thenS 6∈S and if S6∈S, thenS∈S!

How do you resolve this?

Figure:Bertrand Russell (1872-1970)

6

Not so simple...

A barber is a man in town who only shaves those who don’t shave themselves.

Barber’s paradox: Does the barber shave himself?

Russell’s paradox LetS={X|X 6∈X}

Then ifS ∈S, thenS 6∈S and if S6∈S, thenS∈S!

Axiomatic approach to set theory (ZFC!)

Start with a few objectsdefined. Then for a set Aand a propertyP,S ={x∈A|P(x)} is a set.

Not so simple...

A barber is a man in town who only shaves those who don’t shave themselves.

Barber’s paradox: Does the barber shave himself?

Russell’s paradox LetS={X|X 6∈X}

Then ifS ∈S, thenS 6∈S and if S6∈S, thenS∈S!

Axiomatic approach to set theory (ZFC!)

Start with a few objectsdefined. Then for a set Aand a propertyP,S ={x∈A|P(x)} is a set.

Why does this definition get rid of Russell’s paradox?

6

Not so simple...

A barber is a man in town who only shaves those who don’t shave themselves.

Barber’s paradox: Does the barber shave himself?

Russell’s paradox LetS={X|X 6∈X}

Then ifS ∈S, thenS 6∈S and if S6∈S, thenS∈S!

Axiomatic approach to set theory (ZFC!)

Start with a few objectsdefined. Then for a set Aand a propertyP,S ={x∈A|P(x)} is a set.

LetP(x) =x6∈x. let Abe a set and S={x∈A|x6∈x}.

I I

Not so simple...

A barber is a man in town who only shaves those who don’t shave themselves.

Barber’s paradox: Does the barber shave himself?

Russell’s paradox LetS={X|X 6∈X}

Then ifS ∈S, thenS 6∈S and if S6∈S, thenS∈S!

Axiomatic approach to set theory (ZFC!)

Start with a few objectsdefined. Then for a set Aand a propertyP,S ={x∈A|P(x)} is a set.

LetP(x) =x6∈x. let Abe a set and S={x∈A|x6∈x}.

I if (S∈S): from the definition ofS,S∈A andS 6∈S, which is a contradiction.

I

6

Not so simple...

A barber is a man in town who only shaves those who don’t shave themselves.

Barber’s paradox: Does the barber shave himself?

Russell’s paradox LetS={X|X 6∈X}

Then ifS ∈S, thenS 6∈S and if S6∈S, thenS∈S!

Axiomatic approach to set theory (ZFC!)

Start with a few objectsdefined. Then for a set Aand a propertyP,S ={x∈A|P(x)} is a set.

LetP(x) =x6∈x. let Abe a set and S={x∈A|x6∈x}.

I if (S∈S): from the definition ofS,S∈A andS 6∈S, which is a contradiction.

I if (S6∈S): from the definition, eitherS 6∈A orS ∈S. But we have assumed that S 6∈S. Hence,S 6∈A. No

contradiction!

Is the fun done? How do we compare sets?

I For two finite sets, this is easy, just count the number of elements and compare them!

I But what about two infinite sets?

I Example: {set of all even natural numbers}vs NvsQvs R

I Turns out we need functions... but first...

7

Is the fun done? How do we compare sets?

I For two finite sets, this is easy, just count the number of elements and compare them!

I But what about two infinite sets?

I Example: {set of all even natural numbers}vs NvsQvs R

I Turns out we need functions... but first...

Is the fun done? How do we compare sets?

I For two finite sets, this is easy, just count the number of elements and compare them!

I But what about two infinite sets?

I Example: {set of all even natural numbers}vs NvsQvs R

I Turns out we need functions... but first...

7

Hilbert’s hotel

I Suppose there is a hotel with infinitely many rooms.

I And suppose they are all full (like in IIT guest house).

1. Can you accomodate 1 or finitely many more guests, by shifting around the existing guests?

2. What if infinitely many more guests arrive?

3. What if infinitely many more trains with infinitely many more guests arrive? (H.W)

Hilbert’s hotel

I Suppose there is a hotel with infinitely many rooms.

I And suppose they are all full (like in IIT guest house).

1. Can you accomodate 1 or finitely many more guests, by shifting around the existing guests?

2. What if infinitely many more guests arrive?

3. What if infinitely many more trains with infinitely many more guests arrive? (H.W)

8

Hilbert’s hotel

I Suppose there is a hotel with infinitely many rooms.

I And suppose they are all full (like in IIT guest house).

1. Can you accomodate 1 or finitely many more guests, by shifting around the existing guests?

2. What if infinitely many more guests arrive?

3. What if infinitely many more trains with infinitely many more guests arrive? (H.W)

Hilbert’s hotel

I Suppose there is a hotel with infinitely many rooms.

I And suppose they are all full (like in IIT guest house).

1. Can you accomodate 1 or finitely many more guests, by shifting around the existing guests?

2. What if infinitely many more guests arrive?

3. What if infinitely many more trains with infinitely many more guests arrive? (H.W)

8

Functions

What you did above was to define functions...

Definition

LetA,B be two sets. Afunctionf from A toB is an

assignment of exactly one element ofB to each element ofA.

Functions

What you did above was to define functions...

Definition

LetA,B be two sets. Afunctionf from A toB is an

assignment of exactly one element ofB to each element ofA.

i.e., f :A→B is a subsetR ofA×B such that (i) ∀a∈A,∃b∈B such that (a, b)∈R, and (ii) if (a, b)∈R and (a, c)∈R, thenb=c.

9

Functions

What you did above was to define functions...

Definition

LetA,B be two sets. Afunctionf from A toB is an

assignment of exactly one element ofB to each element ofA.

i.e., f :A→B is a subsetR ofA×B such that (i) ∀a∈A,∃b∈B such that (a, b)∈R, and (ii) if (a, b)∈R and (a, c)∈R, thenb=c.

I We writef(a) =b and call btheimageof a.

I Range(f)={b∈B| ∃a∈A s.t. f(a) =b},Domain(f)=A

Functions

What you did above was to define functions...

Definition

LetA,B be two sets. Afunctionf from A toB is an

assignment of exactly one element ofB to each element ofA.

i.e., f :A→B is a subsetR ofA×B such that (i) ∀a∈A,∃b∈B such that (a, b)∈R, and (ii) if (a, b)∈R and (a, c)∈R, thenb=c.

Composition of functions

I If g:A→B and f :B →C, thenf ◦g:A→C is defined by f◦g(x) =f(g(x)).

I Defined only if Range(g)⊆Domain(f).

I Example: if f(x) =x²,g(x) =x−x³ with f, g:R→R, what is f◦g(x), g◦f(x)?

9

Functions

What you did above was to define functions...

Definition

LetA,B be two sets. Afunctionf from A toB is an

assignment of exactly one element ofB to each element ofA.

i.e., f :A→B is a subsetR ofA×B such that (i) ∀a∈A,∃b∈B such that (a, b)∈R, and (ii) if (a, b)∈R and (a, c)∈R, thenb=c.

Composition of functions is associative

I If h:A→B and g:B →C and f :C →D, then f ◦(g◦h) = (f◦g)◦h.

Check it! (H.W.)

Functions

What you did above was to define functions...

Definition

LetA,B be two sets. Afunctionf from A toB is an

assignment of exactly one element ofB to each element ofA.

i.e., f :A→B is a subsetR ofA×B such that (i) ∀a∈A,∃b∈B such that (a, b)∈R, and (ii) if (a, b)∈R and (a, c)∈R, thenb=c.

Inverse of a function

I If f :A→B is a ??? function, then f⁻¹:B →A defined by f⁻¹(b) =aiff(a) =b, is called its inverse.

9

Comparing (finite and infinite) sets

I Surjective or onto: f :A→B is surjective if ∀y∈B,

∃x∈Asuch that f(x) =y.

I Injective or 1-1: f :A→B is injective if ∀x, y∈A, if f(x) =f(y), thenx=y.

I Bijective or 1-1 correspondence: A function is bijective if it is surjective and injective.

Comparing (finite and infinite) sets

I Surjective or onto: f :A→B is surjective if ∀y∈B,

∃x∈Asuch that f(x) =y.

I Injective or 1-1: f :A→B is injective if ∀x, y∈A, if f(x) =f(y), thenx=y.

I Bijective or 1-1 correspondence: A function is bijective if it is surjective and injective.

Iff is a bijection, then its inverse function exists and f◦f⁻¹ =f⁻¹◦f = id

10

Comparing (finite and infinite) sets

I Surjective or onto: f :A→B is surjective if ∀y∈B,

∃x∈Asuch that f(x) =y.

I Injective or 1-1: f :A→B is injective if ∀x, y∈A, if f(x) =f(y), thenx=y.

I Bijective or 1-1 correspondence: A function is bijective if it is surjective and injective.

1. f :Z→Zsuch that f(x) =x². 2. f :R^≥0 →R^≥0 such that f(x) =x².

Comparing (finite and infinite) sets

I Surjective or onto: f :A→B is surjective if ∀y∈B,

∃x∈Asuch that f(x) =y. – IfA, B finite,|A| ≥ |B|

I Injective or 1-1: f :A→B is injective if ∀x, y∈A, if f(x) =f(y), thenx=y. – IfA, B finite,|A| ≤ |B|

I Bijective or 1-1 correspondence: A function is bijective if it is surjective and injective. – IfA, B finite,|A|=|B|

1. f :Z→Zsuch that f(x) =x². 2. f :R^≥0 →R^≥0 such that f(x) =x².

10

Properties of finite and infinite sets

Relative notion of “size” using bijections

Thus, we say that two finite/infinite sets have the same “size” if there is a bijection between them.

I For finite sets, this is a property that can be shown.

I For infinite sets, it is a definition!

Properties of finite and infinite sets

Similarities between finite and infinite sets

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

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

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

11

Properties of finite and infinite sets

Similarities between finite and infinite sets

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

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

I (Schr¨oder-Bernstein Theorem:) ∃surj from A toB and ∃ surj B toA, implies ∃bij from AtoB. (H.W: Read this!)

Properties of finite and infinite sets

Similarities between finite and infinite sets

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

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

I (Schr¨oder-Bernstein Theorem:) ∃surj from A toB and ∃ surj B toA, implies ∃bij from AtoB. (H.W: Read this!)

Differences between finite and infinite sets

I For finite sets, if A is a set andb6∈A, then |A| 6=|A∪ {b}|.

11

Properties of finite and infinite sets

Similarities between finite and infinite sets

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

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

I (Schr¨oder-Bernstein Theorem:) ∃surj from A toB and ∃ surj B toA, implies ∃bij from AtoB. (H.W: Read this!)

Differences between finite and infinite sets

I For finite sets, if A is a set andb6∈A, then |A| 6=|A∪ {b}|.

I What about infinite sets?

Properties of finite and infinite sets

Similarities between finite and infinite sets

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

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

I (Schr¨oder-Bernstein Theorem:) ∃surj from A toB and ∃ surj B toA, implies ∃bij from AtoB. (H.W: Read this!)

Differences between finite and infinite sets

I For finite sets, if A is a set andb6∈A, then |A| 6=|A∪ {b}|.

I What about infinite sets?

Theorem

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

11

Properties of finite and infinite sets

Similarities between finite and infinite sets

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

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

I (Schr¨oder-Bernstein Theorem:) ∃surj from A toB and ∃ surj B toA, implies ∃bij from AtoB. (H.W: Read this!)

Differences between finite and infinite sets

I For finite sets, if A is a set andb6∈A, then |A| 6=|A∪ {b}|.

I What about infinite sets?

Theorem

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

Proof: essentially Hilbert’s hotel but be careful...

Comparing infinite sets using functions

Some questions...

I Is there a bijection between N×N toN?

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

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?

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

Countably infinite sets are the “smallest” infinite sets.