Proof Practical Class, Week 23

Question One §

Question §

Prove that the following sets have the same cardinality by producing explicitly a bijection between the sets and describing this bijection…

1. … by a formula for $|(-\infty ,0]|=|[3,+\infty )$;
2. … by representing the set on the right as a sequence: $|\mathbb{N}|=|\{a,b,c\}\cup \mathbb{N}|$;
3. … by any method: $|\{a,b\}\times \mathbb{Z}|=|\mathbb{Z}|$;
4. … by using a sequence of points: $|[0,1]|=|(0,1)|$;
5. … geometrically: $|(0,1)|=|(0,\infty )|$.

Hint for 1.5: for example, first construct a bijection of $(0,1)$ onto a quarter circle (without endpoints), and then a bijection of the quarter circle onto $(0,\infty )$ similarly to the stereographic projection in the lectures.

Solution §

…

Question Two §

Question §

A theorem in the lectures says that if $f:B\to A$ is an injective mapping and $A$ is countable, then $B$ is also countable.

Use this theorem to prove that $|\mathbb{N}\times \mathbb{N}\times \mathbb{N}|={\aleph }_0$.

Hint: one method is to use product of powers of three fixed primes as images of triples of positive integers.

Solution §

…

Question Three §

Question §

Let $S$ be the set of all sequences of the form $(a_1,a_2,a_3,\dots )$, where every $a_i$ is either $A$ or $B$. Use Cantor’s “diagonal method” to prove that the set $S$ is not countable.

Solution §

…

Question Four §

Question §

Recall that $\{0,1\}\times \{0,1\}\times \{0,1\}$ consists of triples of $1$s and $0$s, and $\mathcal{P}(\{a,b,c\})$ is the set of all subsets of $\{a,b,c\}$. Consider the following mapping, in which a subset $X\subset \{a,b,c\}$ is mapped to a string of length $3$ consisting of $0$s and $1$s depending on which of the elements $a,b,c$ belong to $X$ (with $1$ indicating yes and $0$ indicating no).

$$f:\mathcal{P}(\{a,b,c\})\to \{0,1\}\times \{0,1\}\times \{0,1\}$$

Write the images $f(\varnothing )$, $f(\{a,c\})$, $f(\{b\})$. Is $f$ a bijection?

Solution §

…

Question Five §

Question §

A theorem in the lectures says that if $f:B\to A$ is an injective mapping and $A$ is countable, then $B$ is also countable.

Use this theorem to show that any set consisting of pairwise disjoint intervals of the real line (each of $\text{length}>0$) is countable.

Hint: use the fact that $|\mathbb{Q}|={\aleph }_0$.

Solution §

…