Problem Sets

Problem 0: Complete the Canvas quiz "PSet 9 - Cardinality".

Problem (4 points): Recall Prof. Glenn's demonstration of mentalism from Tuesday. Demonstrate that your powers are equal to his: there are 94 students in CPSC 202 this semester. Make a true statement of the form "at least X students in CPSC 202 have the same Y". Make sure there are at least 2 choices for Y and make X as large as possible for the possible choices for Y. Explain why your statement must be true. (Play along: avoid trivial claims like "at least 96 students have the same undergraduate institution" and instead make a statement that can be correctly justified with the generalized pigeonhole principle rather than with probability or the fact that all CPSC 202 students attend Yale.)

Problem (8 points): Prove that the union of a countably infinite collection of disjoint non-empty finite sets is countably infinite. (That is, let $X_i$ be a non-empty finite set for each $i \in {\bf N}$ and suppose $X_i \cap X_j = \emptyset$ whenever $i \ne j$. Prove that $\bigcup_{i=0}^{\infty} X_i$ is countably infinite.)

Problem (8 points): Prove that the union of a countably infinite collection of disjoint countably infinite sets is countably infinite. (That is, let $X_i$ be a countably infinite set for each $i \in {\bf N}$ and suppose $X_i \cap X_j = \emptyset$ whenever $i \ne j$. Prove that $\bigcup_{i=0}^{\infty} X_i$ is countably infinite.)

Problem (4 points): Do each of the the previous two statements remain true if we remove the condition that the sets being unioned are disjoint? Explain your answers.

Problem (6 points): Let $X$ be the set of all finite sequences of natural numbers. For any natural number $i$, let $Y_i$ be the set of sequences of natural numbers that either 1) contain exactly $i$ elements, each no greater than $i$, or 2) contain fewer than $i$ elements, the largest of which is $i$ (so, for example, delimiting sequences with square brackets, $Y_0 = \{[]\}$ (the set containing the empty sequence), $Y_1 = \{[0], [1]\}$, $Y_2 = \{[2], [0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]\}$, $[1, 2, 3] \in Y_3$, and $[2, 3, 5] \in Y_5$.)

Prove that $X = \bigcup_{i=0}^\infty Y_i$.
Prove that $X$ is countably infinite.

Problem (6 points): Prove that $\{ X \in {\cal P}({\bf N}) \mid X \text{ is finite}\}$ (the set of finite subsets of natural numbers) is countably infinite.