Description

Sundry
Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)
1 Countability Proof Practice
(a) A disk is a 2D region of the form {(x,y) ∈ R2 : (x−x0)2 +(y−y0)2 ≤ r2}, for some x0,y0,r ∈ R, r > 0. Say you have a set of disks in R2 such that none of the disks overlap. Is this set always countable, or potentially uncountable?
(Hint: Attempt to relate it to a set that we know is countable, such as Q×Q)
(b) A circle is a subset of the plane of the form {(x,y) ∈ R2 : (x−x0)2 +(y−y0)2 = r2} for some x0,y0,r ∈ R, r > 0. Now say you have a set of circles in R2 such that none of the circles overlap. Is this set always countable, or potentially uncountable?
(Hint: The difference between a circle and a disk is that a disk contains all of the points in its interior, whereas a circle does not.)
(c) Is the set containing all increasing functions f : N → N (i.e., if x ≥ y, then f(x) ≥ f(y)) countable or uncountable? Prove your answer.
(d) Is the set containing all decreasing functions f : N → N (i.e., if x ≥ y, then f(x) ≤ f(y)) countable or uncountable? Prove your answer.
2 Hilbert’s Hotel
You don’t have any summer plans, so you decide to spend a few months working for a magical hotel with a countably infinite number of rooms. The rooms are numbered according to the natural numbers, and all the rooms are currently occupied. Assume that guests don’t mind being moved from their current room to a new one, so long as they can get to the new room in a finite amount of time (i.e. guests can’t be moved into a room infinitely far from their current one).
(a) A new guest arrives at the hotel. All the current rooms are full, but your manager has told you never to turn away a guest. How could you accommodate the new guest by shuffling other guests around? What if you instead had k guest arrive, for some fixed, positive k ∈ Z?
(b) Unfortunately, just after you’ve figured out how to accommodate your first k + 1 guests, a countably infinite number of guests arrives in town on an infinitely long train. The guests on the train are sitting in seats numbered according to the natural numbers. How could you accommodate all the new guests?
(c) Thanks to a (literally) endless stream of positive TripAdvisor reviews, word of the infinite hotel gets around quickly. Soon enough you find out that a countably infinite number of trains have arrived in town. Each is of infinite length, and carries a countably infinite number of passengers. How would you accommodate all the new passengers? 3 Finite and Infinite Graphs
The graph material that we learned in lecture still applies if the set of vertices of a graph is infinite. We thus make a distinction between finite and infinite graphs: a graph G =(V,E) is finite if V and E are both finite. Otherwise, the graph is infnite. As examples, consider the graphs
• G1 =(V =Z, E = {(i, j) ∈ Z×Z| |i− j| = 1})
• G2 =(V =Z, E = {(i, j) ∈ Z×Z| i < j})
• G3 =(V =Z2, E = {((i, j),(k,l)) ∈ Z2 ×Z2| (i = k∧|j−l| = 1)∨(j = l∧|i−k| = 1)})
Observe that G1 is a line of integers, G2 is a complete graph over all integers, and G3 is an grid of integers. Prove whether the following sets of graphs are countable or uncountable
(a) The set of all finite graphs G =(V,E), for V ⊆ N
(b) The set of all infinite graphs over a fixed, countably infinite set of vertices (in other words, they all have the same vertex set).
(c) The set of all graphs over a fixed, countably infinite set of vertices, the degree of each vertex is exactly two. For instance, every vertex in G1 (defined above) has degree 2.
(d) We say that graphs G = (V,E) and G0 = (V0,E0) are isomorphic if the exists some bijection f : V → V0 such that (u,v) ∈ V iff (f(u), f(v)) ∈ V0. Such a bijection f is called a graph isomorphism. Suppose we consider two graphs to be the equivalent if they are isomorphic. The idea is that if we relabel the vertices of a graph, it is still the same graph. Using this definition of “being the same graph”, can you conclude that the set of trees over countably infinite vertices is countable?
(Hint: Begin by showing that for any graph isomorphism f, and any vertex v, f(v) and v have the same degree)