CS 207 Discrete Mathematics – 2012-2013

(1)

CS 207 Discrete Mathematics – 2012-2013

Nutan Limaye

Indian Institute of Technology, Bombay nutan@cse.iitb.ac.in

Mathematical Reasoning and Mathematical Objects Lecture 5: Schroder-Bernstein

Aug 7, 2012

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 1 / 9

(2)

Last time

(3)

Recap

There is a bijection from N×N toN

There is no bijection between Nand set of all subsets of N. Proof by Cantor’s diagonalization. [Cantor, 1891]

(4)

Recap

There is a bijection from N×N toN f(x,y) =

Px+y

i=1 i

+y Why is this a bijection?

(5)

Recap

Px+y

i=1 i

+y= (x+y)(x+y+1)

2 +y

Why is this a bijection?

(6)

Recap

Px+y

i=1 i

+y= (x+y)(x+y+1)

2 +y

Hint: Any point (x,y) such thatx+y =k is mapped to an interval of size k+ 1 which starts at ^k^(k₂⁺¹⁾.

(7)

Recap

Px+y

i=1 i

+y= (x+y)(x+y+1)

2 +y

Hint: Any point (x,y) such thatx+y =k is mapped to an interval of size k+ 1 which starts at ^k^(k₂⁺¹⁾.

Why injective: Ifx+y 6=x⁰+y⁰ then f(x,y)6=f(x⁰,y⁰).

Ifx+y =x⁰+y⁰ and f(x,y) =f(x⁰,y⁰) then y =y⁰. But if x+y =x⁰+y⁰ and y =y⁰ thenx =x⁰

Why surjective: Say∃k∈Nsuch that k has no inverse. But for any k ∈N, there exists n∈Nsuch that ⁿ⁽ⁿ⁺¹⁾₂ ≤k ≤ ^(n+1)(n+2)₂

(8)

Recap

Px+y

i=1 i

+y

There is no bijection between Nand set of all subsets of N.

Proof by Cantor’s diagonalization. [Cantor, 1891]

(9)

Recap

Px+y

i=1 i

+y

(10)

Today

Another property of sets which holds for both finite and infinite sets.

[Schr¨oder-Bernstein Theorem]

An interesting game and an open problem (If time permits).

(11)

Today

Another property of sets which holds for both finite and infinite sets.

[Schr¨oder-Bernstein Theorem]

An interesting game and an open problem (If time permits).

(12)

Schr¨ oder-Bernstein

Theorem

Let A,B be two sets. If there is a injective map g from A to B and another injective map h from B to A then there is a bijection between A,B.

A toy example:

Say g :N→N, g(x) = x+1andh:N→N,h(x) =x+ 1. 0

1 2 3

i i+ 1

0 1 2 3

i i+ 1

0 1 2 3

i i+ 1

0 1 2 3

i i+ 1

(13)

Schr¨ oder-Bernstein

Theorem

A toy example:

Say g :N→N, g(x) = x+1andh:N→N,h(x) =x+ 1.

Why are g,h injective? Are they bijective? 0

1 2 3

i i+ 1

0 1 2 3

i i+ 1

0 1 2 3

i i+ 1

0 1 2 3

i i+ 1

(14)

Schr¨ oder-Bernstein

Theorem

A toy example:

Why are g,h injective? Are they bijective?

0 1 2 3

i i+ 1

0 1 2 3

i i+ 1

0 1 2 3

i i+ 1

0 1 2 3

i i+ 1

(15)

Schr¨ oder-Bernstein

Theorem

A toy example:

0 1 2 3

i i+ 1

0 1 2 3

i i+ 1

0 1 2 3

i i+ 1

0 1 2 3

i i+ 1

(16)

Schr¨ oder-Bernstein

Theorem

A toy example:

0 1 2 3

i i+ 1

0 1 2 3

i i+ 1

0 1 2 3

i i+ 1

0 1 2 3

i i+ 1

(17)

Schr¨ oder-Bernstein

Theorem

There are two types of elements in B. B₀ ={b ∈B | ∃a∈As.t. g(a) =b} B₁ ={b ∈B | ∀a∈As.t. g(a)6=b}

An element b∈B be called h-good if∃β ∈B₁,∃n∈N s.t. b = (g h)ⁿβ We now define another map from Ato B as follows:

f(a) =

h⁻¹(a) ifg(a) is h-good g(a) otherwise

To finish the proof, we will prove the following lemma about f. Lemma

The map f defined above is a

(18)

Schr¨ oder-Bernstein

Theorem

There are two types of elements in B. B0 ={b ∈B | ∃a∈As.t. g(a) =b}

B₁ ={b ∈B |@a∈As.t. g(a) =b}

B₁ ={b ∈B | ∀a∈As.t. g(a)6=b}

f(a) =

(19)

Schr¨ oder-Bernstein

Theorem

There are two types of elements in B. B₀ ={b ∈B | ∃a∈As.t. g(a) =b}

B₁ ={b ∈B | ∀a∈As.t. g(a)6=b}

f(a) =

(20)

Schr¨ oder-Bernstein

Theorem

B₁ ={b ∈B | ∀a∈As.t. g(a)6=b}

An element b∈B be called h-good if∃β ∈B₁,∃n∈N s.t. b = (g h)ⁿβ

We now define another map from Ato B as follows: f(a) =

(21)

Schr¨ oder-Bernstein

Theorem

B₁ ={b ∈B | ∀a∈As.t. g(a)6=b}

An element b∈B be called h-good if∃β ∈B₁,∃n∈N s.t. b = (g h)ⁿβ What is (f g)ⁿ? What does it mean to be h-good?

We now define another map from AtoB as follows: f(a) =

h⁻¹(a) if g(a) is h-good g(a) otherwise To finish the proof, we will prove the following lemma about f. Lemma

(22)

Schr¨ oder-Bernstein

Theorem

B₁ ={b ∈B | ∀a∈As.t. g(a)6=b}

f(a) =

(23)

Schr¨ oder-Bernstein

Lemma

Let B₁={b∈B | ∀a∈A s.t. g(a)6=b}, and f(a) =

h⁻¹(a) if g(a) is h-good g(a) otherwise Then f is injective from A to B

Proof.

Suppose (for the sake of contradiction) a6=a⁰ and f(a) =f(a⁰).

(24)

Schr¨ oder-Bernstein

Lemma

Proof.

Case 1 [g(a),g(a⁰) are h-good:] thenf(a) =h⁻¹(a) =f(a⁰) =h⁻¹(a⁰).

Say h⁻¹(a) =b₀. Then we have,h(b₀) =aandh(b₀) =a⁰, i.e. h is not a well-defined functions. This is a contradiction.

(25)

Schr¨ oder-Bernstein

Lemma

Proof.

Case 2 [g(a),g(a⁰) are not h-good:] thenf(a) =g(a) =f(a⁰) =g(a⁰).

Then we have, g(a) =g(a⁰), i.e. g is not injective. This is a contradiction.

(26)

Schr¨ oder-Bernstein

Lemma

Proof.

Case 3[onlyg(a) is h-good:] We have thatf(a) =f(a⁰).

As g(a) is h-good,f(a) =h⁻¹(a). As g(a⁰) is not h-good,f(a⁰) =g(a⁰).

(27)

Schr¨ oder-Bernstein

Lemma

Proof.

Therefore, h⁻¹(a) =g(a⁰). Call this elementb^∗.

(28)

Schr¨ oder-Bernstein

Lemma

Proof.

As g(a⁰) =b^∗,b^∗∈/ B1. But asg(a) is h-good. Therefore, (hg)⁻ⁱ(b^∗)∈B₁ for somei ∈N.

(29)

Schr¨ oder-Bernstein

Lemma

Proof.

As g(a⁰) =b^∗,b^∗∈/ B1. But asg(a) is h-good. Therefore, (hg)⁻ⁱ(b^∗)∈B1 for somei ∈N.

Assuming g(a⁰) is not h-good, paths walked backwards fromb^∗ lead toB₀. But Assuming g(a) ish-good, paths walked backwards fromb^∗ lead toB1.

(30)

Schr¨ oder-Bernstein

Lemma

Proof.

As g(a⁰) =b^∗,b^∗∈/ B1. But asg(a) is h-good. Therefore, (hg)⁻ⁱ(b^∗)∈B1 for somei ∈N.

Assuming g(a⁰) is not h-good, paths walked backwards fromb^∗ lead toB₀. But Assuming g(a) ish-good, paths walked backwards fromb^∗ lead toB1. Contradiction!

(31)

Schr¨ oder-Bernstein

Lemma

h⁻¹(a) if g(a) is h-good g(a) otherwise Then f is surjective from A to B

(32)

Schr¨ oder-Bernstein

Lemma

h⁻¹(a) if g(a) is h-good g(a) otherwise Then f is surjective from A to B

Proof.

HW

(33)

Subset Take-away Game – David Gale

I am player 1 and you are player 2. We both have been given a setA. In each round, first I choose one subset ofA and then you choose another subset of A. We stick to the following rules:

1 We do not choose the empty set

2 We do not choose the entire setA

3 We do not choose any superset of a set chosen in any earlier round.

First player unable to pick loses the game.

If|A|= 1 then I lose. If |A|= 2 then you will always win. If |A|= 3 then again you can win. What happens when |A|= 4?

(Source – Mathematics for Computer Science, 2012, by Eric Lehman and F Thomson Leighton)

(34)

Subset Take-away Game – David Gale

If|A|= 1 then I lose.

If|A|= 2 then you will always win. If |A|= 3 then again you can win. What happens when |A|= 4?

(35)

Subset Take-away Game – David Gale

If|A|= 1 then I lose. If |A|= 2 then you will always win.

If|A|= 3 then again you can win. What happens when |A|= 4?

(36)

Subset Take-away Game – David Gale

(37)