Math 135: Solutions to Homework Set #9

1 (page 161, # 26) Suppose that every member of ${\mathcal A}$ has cardinality at most $\kappa$, then ${\rm card}\bigcup {\mathcal A}\leq ({\rm card}{\mathcal A}) \cdot \kappa$.

Proof. Define $Y := \{ \langle a, x \rangle : x \in a \in {\mathcal A}\}$. Then by definition of the union, the function $f:Y \to \bigcup A$ defined by $\langle a, x \rangle \mapsto x$ is surjective. Hence, ${\mathcal A}\preceq Y$. It suffices to show that $Y \preceq {\mathcal A}\times \kappa$. Let $R := \{ \langle a, f \rangle \in A \times (\bigcup A \times \kappa) : f$    is an injective function with domain $a$    and range contained in $\kappa \}$. By hypothesis, every $a \in {\mathcal A}$ has cardinality at most $\kappa$ so that there is some injective $f:a \hookrightarrow \kappa$. That is, ${\rm dom}R = {\mathcal A}$. By the axiom of choice there is a function $F \subseteq R$ with ${\rm dom}F = {\rm dom}R = {\mathcal A}$.

Define $G: Y \to {\mathcal A}\times \kappa$ by $\langle a, x \rangle \mapsto \langle a, F(a)(x) \rangle$. If $y = \langle a, x \rangle$ and $y' = \langle a', x' \rangle$ are two elements of $Y$ with $G(y) = G(y')$, then $a = a'$ and $F(a)(x) = F(a')(x') = F(a)(x')$. As $F(a)$ is injective, we have $x = x'$ as well, so that $y = y'$. Thus, $G$ is injective showing that $Y \preceq {\mathcal A}\times \kappa$.

Therefore, ${\rm card}\bigcup {\mathcal A}\leq ({\rm card}{\mathcal A}) \cdot \kappa$. $\qedsymbol$

2 (page 161, # 27)

(a)

Let $A$ be a collection of circular disks in the plane, no two of which intersect. Show that $A$ is countable.

Proof. As ${\mathbb{Q}}^2$ is dense in ${\mathbb{R}}^2$, if $D$ is any disk in the plane, then we must have $D \cap {\mathbb{Q}}^2 \neq {\varnothing}$. Let $R := \bigcup \{ D \cap {\mathbb{Q}}^2 \vert D \in A \}$. For $x \in R$, by definition, there is some $D \in A$ with $x \in D$. As the disks in $A$ are disjoint, there can be at most one such $D$. Define $G: R \to A$ by $G := \{ \langle x, D \rangle \in {\mathbb{Q}}^2 \times A \vert x \in D \}$. The above remark shows that $R$ is a surjective function. Hence, we may find some injective $f:A \hookrightarrow R$ with $G \circ f = {\rm id}_A$. As $R \subseteq {\mathbb{Q}}^2$, we have $\vert R\vert \leq \aleph_0$. Hence, $\vert A\vert \leq \vert\aleph_0\vert$. $\qedsymbol$

(b)

Let $B$ be a collection of circles in the plane, no two of which intersect. Need $B$ be countable?

No. For $r$ a positive real number, let $S_r := \{ (x,y) \in {\mathbb{R}}^2: x^2 + y^2 = r \}$. Then $S_r$ is a circle and for $r \neq s$ we have $S_r \cap S_s = {\varnothing}$. Set $C := \{ S_r \vert r \in {\mathbb{R}}, r > 0 \}$.

(c)

Let $C$ be a collection of figure eights in the plane, no two of which intersect. Need $C$ be countable?

Yes. Recall that we defined a figure eight to be a set of the form $X \cup Y$ where $X$ and $Y$ are circles whose bounded disks meet at exactly one point. For each pair of positive rational numbers $p$ and $q$ with $p \leq q$, we define $C_{p,q}$ to be the set of figure eights in $C$ whose smaller circle has radius $r$ with $p \leq r$ and whose large circle has radius $R$ with $q \leq R < q + p$. Note that $C = \bigcup_{p \leq q} C_{p,q}$ is a countable union of the sets $C_{p,q}$. If we show that each $C_{p,q}$ is countable, then we know that $C$ itself is. Note that if $F, E \in C_{p,q}$ are two distinct figure eights with the specified conditions on their radii, then not only are $F$ and $E$ disjoint, but the disks that they bound are also disjoint as if $F$ were a subset of the union of the disks bounded by $F$, we would need the sum of the radii of the circles of $F$ to be less than the radius of the larger circle of $E$, but this sum is at least $p + q$. Thus, exactly as in part (a) we may define an injective function $f:C_{p,q} \to {\mathbb{Q}}^2$ showing that $C_{p,q}$ is countable.

3 (page 161, # 28) Find a set ${\mathcal A}$ of open intervals in ${\mathbb{R}}$ such that every rational number belongs to one of those intervals but $\bigcup {\mathcal A}\neq {\mathbb{R}}$.

Let ${\mathcal A}= \{(\sqrt{2} + n, \sqrt{2} + n + 1) : n \in {\mathbb{Z}}\}$.

4 (page 161, # 29) Let $A$ be a set of positive real numbers. Assume that there is a bound $b$ such that the sum of any finite subset of $A$ is less than $b$. Show that $A$ is countable.

Proof. For each positive integer $n$ define $A_n := A \cap (\frac{1}{n},\infty)$. I claim that for each $n$, the set $A_n$ is finite. Suppose this fails for some $n$. Let $k \in \omega$ be a natural number for which $k > n b$. If $A_n$ were infinite, then we could find $a_1, \ldots, a_k \in A$ distinct. We have $b \geq \sum_{i=1}^k a_i > \sum_{i=1}^k \frac{1}{n} = \frac{k}{n} > \frac{nb}{n} = b$.With this contradiction, we see that $A_n$ is finite. Thus, $A = \bigcup_{n = 1}^\infty A_n$ being a countable union of at most countable sets is itself at most countable. $\qedsymbol$

5 (page 161, # 30) Assume that $A$ is a set with at least two elements. Show that ${\rm Sq}(A) \preceq {^\omega}A$.

Proof. By definition of ${\rm Sq}(A)$, we have ${\rm Sq}(A) = \bigcup_{n \in \omega} {^n}A$.

We break the argument into two cases at this point.

If $A$ is finite, then each of the sets ${^n}A$ is also finite and, thus, at most countable. Therefore, ${\rm Sq}(A)$ is also at most countable. However, as $2 \preceq A$, we see that ${\rm Sq}(A) \preceq \omega \prec {^\omega}2 \preceq {^\omega}A$.

If $A$ is infinite, then $A \approx A \cup \{ * \} =: A'$ where $* \notin A$. Let $g:A' \to A$ be a bijection and let $G:{^\omega} A' \to {^\omega}A$ be the induced bijection given by $\sigma \mapsto g \circ \sigma$.

Define a function $F:{\rm Sq}(A) \to {^\omega}A'$ by

$$F(\sigma)(n) = \begin{cases}\sigma(n) & \text{ if } n \in {\rm dom}\sigma \\ * & \text{ otherwise } \end{cases}$$

Then $F$ is injective as if $F(\sigma) = F(\tau)$ we see that ${\rm dom}(\sigma) = F(\sigma)^{-1} [[A]] = F(\tau)^{-1} [[A]] {\rm dom}(\tau)$ and that we have $\sigma = F(\sigma) \upharpoonright {\rm dom}(\sigma) = F(\tau) \upharpoonright {\rm dom}(\sigma) = F(\tau) \upharpoonright {\rm dom}(\tau) = \tau$.

Composing $F$ with $G$, we see that ${\rm Sq}(A) \preceq {^\omega}A$. $\qedsymbol$

6 (page 165, # 32) Let ${\mathcal F}A$ be the collection of all finite subsets of $A$. Show that if $A$ is infinite, then $A \approx {\mathcal F}A$.

Proof. We claim that for $n \in \omega$ and $n > 0$ we have $A \approx {^n}A$. We prove this by induction on $n$. For $n = 1$, there is an obvious bijection between $A$ and ${^1}A$ given by $a \mapsto [0 \mapsto a]$. Assuming the result for $n$, we compute

$${ ^{n^+} }A = {^{n \cup \{ n \} }}A$$

$$\approx {^n A} \times {^{\{n\}}}A$$

$$\approx {^n} A \times A$$

$$\approx A \times A$$

$$\approx A$$

Thus, by problem 26 of page 161, we have that $\vert{\rm Sq}(A)\vert \leq \aleph_0 \cdot \vert A\vert = \vert A\vert$. However, as ${^1}A \subseteq {\rm Sq}(A)$, we certainly have $\vert A\vert \leq \vert{\rm Sq}(A)\vert$. Therefore, $A \approx {\rm Sq}(A)$.

Now, define a function ${\rm Sq}(A) \to {\mathcal F}A$ by $\sigma \mapsto {\rm rng}\sigma$. By definition of a finite set, this function is surjective. Thus, $\vert{\mathcal F}A\vert \leq \vert{\rm Sq}(A)\vert = \vert A\vert$. Again, as every singleton in $A$ is a finite set, we have $\vert A\vert \leq \vert{\mathcal F}A\vert$. Therefore, $A \approx {\mathcal F}A$. $\qedsymbol$

7 (page 165, # 35) Find a collection ${\mathcal A}$ of $2^{\aleph_0}$ sets of natural numbers such that any two distinct members of ${\mathcal A}$ have finite intersection.

Proof. We prove a claim.

Claim: Let $K$ be any infinite set with ${\rm card}K = \kappa$. Let ${\mathcal I}K := \{ X \in {\mathcal P}K \ \vert \ \vert X\vert \geq \aleph_0 \}$. Then $\vert{\mathcal I}K\vert = 2^\kappa$.

Proof of claim: We may write ${\mathcal P}K$ as the disjoint union of ${\mathcal I}K$ and ${\mathcal F}K$. By the result of the previous problem, we have ${\rm card}{\mathcal F}A = \kappa$. Letting $\lambda := {\rm card}{\mathcal I}K$, We compute

$$2^\kappa = {\rm card}{\mathcal P}K$$

$$= {\rm card}({\mathcal F}K \cup {\mathcal I}K)$$

$$= {\rm card}({\mathcal F}K) + {\rm card}({\mathcal I}K)$$

$$= \kappa + \lambda$$

$$= \max \{ \kappa, \lambda \}$$

$$= \lambda \kappa < 2^\kappa$$

$\maltese$

By Euclid's theorem, the set $P$ of prime numbers is a countably infinite set. Hence, the set ${\mathcal I}P$ of infinite sets of primes has cardinality $2^{\aleph_0}$.

For each $X \in {\mathcal I}P$ define $A_X := \{ \prod_{p \leq n, p \in X} p \ \vert \ n \in \omega \} \subseteq \omega \}$. This association defined a function $F: {\mathcal I}P \to {\mathcal P}\omega$. Let ${\mathcal A}:= {\rm rng}F$.

Note that for any $X \in {\mathcal I}P$ the set $A_X$ is infinite as $X$ is infinite so that there are elements of $A_X$ with arbitrarily many prime divisors.

If $X \neq Y$ are two distinct elements of ${\mathcal I}P$, then there is some prime which belongs to one set but not the other. Without loss of generality, we may assume $p \in X \setminus Y$. Let $A_X' := \{ \prod_{\ell \leq n, \ell \in X} \ell \ \vert \ n < p \}$ and $A_X'' := A_X \setminus A_X'$. Note that if $y \in A_Y$, then $p$ does not divide $y$ while $p$ divides every element of $A_X''$. Thus, $A_X \cap A_Y$ is contained in $A_X' \cap A_Y \subseteq A_X' \subseteq \{ m \in \omega : m < p! \}$ which is a finite set. Hence, $A_X \cap A_Y$ is finite. As $A_X$ is infinite, this implies in particular that $A_X \neq A_Y$. Thus, the map $F:{\mathcal I}P \to {\mathcal A}$ is a bijection so that ${\mathcal A}$ has cardinality $2^{\aleph_0}$ and is almost disjoint. $\qedsymbol$

8 Show that for any infinite cardinal $\kappa$, we have $\kappa! = 2^\kappa$.

Proof. Let $K$ be any set with ${\rm card}K = \kappa$. Let ${\rm Sym}(K) := \{ \sigma: K \to K \vert \sigma$    a bijection $\}$. Then by definition, we have $\kappa ! = {\rm card}{\rm Sym}(K)$.

As every permutation is a function from $K$ to $K$ (and in particular a relation with field $K$), we have ${\rm Sym}(K) \subseteq {\mathcal P}(K \times K)$ so that $\kappa! \leq 2^{\kappa \cdot \kappa} = 2^\kappa$.

For the other inequality, define a function $F: {\rm Sym}(K) \to {\mathcal P}K$ by $\sigma \mapsto \{ x \in K \vert \sigma(x) = x \}$. Let $A := {\rm rng}F$. To compute the cardinality of $A$ we need a claim.

Claim: Let $X$ be any set with ${\rm card}X \geq 2$. Then there is a permutation $\pi:X \to X$ having no fixed points.

Proof of claim: If $X$ is finite, then $X \approx n$ for some $n \in \omega$ with $n > 2$. Let $f:n \to X$ be a bijection. Define $\sigma:n \to n$ by $\sigma(i) = i^+$ if $i < n-1$ and $\sigma(n-1) = 0$. Define $\pi:X \to X$ by $\pi = f \circ \pi \circ f^{-1}$.

If $X$ is infinite of cardinality $\lambda$, then as $\lambda = \lambda \times \lambda$, we can find a bijection $g:X \to X \times 2$. Define $\sigma: X \times 2 \to X \times 2$ by $\langle x, i \rangle \to \langle x, 1 - i \rangle$. Let $\pi := g^{-1} \circ \sigma \circ g$. $\maltese$

From the claim it follows that $B = \{ X \in {\mathcal P}K \ \vert \ {\rm card}(K \setminus X) \neq 1 \}$. For if $X = K$, then $X = F({\rm id}_K)$ and if $K \setminus X =: Y$ has more than one element, then we can find (by the claim) a permutation $\pi:Y \to Y$ having no fixed points so that if $\sigma = \pi \cup {\rm id}_X$ we have $F(\sigma) = X$. Finally, if $K \setminus X = \{ a \}$ is a singleton, then $X$ cannot be in the image of $F$ as any permutation which fixes $X$ must fix its complement setwise, and in the case of a singleton, being fixed setwise is the same as being fixed pointwise.

There is an obvious bijection between $K$ and the set of subsets of $K$ whose complements are singletons given by $a \mapsto K \setminus \{ a \}$. Hence, $\vert{\mathcal P}K \setminus B\vert = \kappa$. As in the proof the claim in problem 7, we conclude that $\vert B\vert = 2^\kappa$. As $F:{\rm Sym}(K) \to B$ is surjective, we conclude that $\kappa ! \geq 2^\kappa$.

Combining this with the other inequality, we conclude that $\kappa! = 2^\kappa$. $\qedsymbol$