TEST 2

Question 1

Prove the set of rational numbers is countable.

Answer 1

1/1 2/1 3/1
1/2 2/2 3/2

Every rational number will appear in this list which allows us to set up a one to one correspondence between each rational number and it’s position on the list.

Question 2

Prove the set of real numbers is uncountable.

Answer 2

In this case we write out a set of decimals. If we take the Nth digit of each decimal to make S we can prove that S does not show up in our set of decimals and therefore does not have a one to one correspondence making it uncountable.

Question 3

Infinite buses and infinite hotel rooms

Answer 3

In order to make room for the infinite amount of bus riders we will need to make a second set of infinite rooms. If we ask each guest to move to the room that is double of the room number that they are current and all of the odd rooms will be open for the new guests.

Question 4

Graph with odd vertices cannot have a Euler Circuit.

Answer 4

As one theorem states
d1+d2+....dn
------------- = e
           2
Which equals the number of edges in the graph. This number must be an integer which means the numerator must be an even number. This proves that we cannot have odd vertices if we want to create a Euler circuit.