32 - The Schröder–Bernstein Theorem

!Screenshot 2023-11-29 at 12.42.15 PM.png

!Screenshot 2023-11-29 at 12.42.27 PM.png

HW 32

Ben Finch

E 32.1
Proof.
Let $X, Y, Z$ be sets. Assume that $X \subseteq Y \subseteq Z$ and $| X | = | Z |$ . We know that every element of $X$ is in $Y$ and every element of $Y$ is in $Z$ . Assume by way of contradiction that $| X | \neq | Y |$ . Since $X \subseteq Y$ , $| Y | > | X |$ . However $Y \subseteq Z$ , so every element in $Y$ is in $Z$ . Since $| X | = | Z |$ it follows that $| Y | > | Z |$ . However, since $Y \subseteq Z$ , $| Y | \leq | Z |$ . Herein lies the contradiction. Therefore, $| X | = | Y |$ . $◻$

E 32.2

Proof.
Let $A := [- 5, 16)$ and $B := (0, \infty)$
We proved in a homework problem that $h : (0, \infty) \to (0, 1)$ given by $h (x) = \frac{x}{x + 1}$ is a bijection. Note that $h_{2} : (0, 1) \to [- 5, 16)$ given by the rule $h_{2} (x) = x$ is an injection. Thus $g : h_{1} \circ h_{2}$ is an injection from $B \to A$ .

Deinfe $f : A \to B$ by $f (x) = x + 6$ . Note that this is a function because the rule takes elements of $- [5, 16) \to (0, \infty)$ . Further $f$ is injective because if $a_{1}, a_{2} \in A$ and $f (a_{1}) = f (a_{2})$ then $a_{1} + 6 = a_{2} + 6$ which implies $a_{1} = a_{2}$ . Thus by the Schröder-Bernstein Theorem, $| A | = | B |$ . $◻$

E 32.3

We define the function $f : A \to B$ as follows:

f (x) = {\begin{cases} f_{1 (x)} = x + 17 & if x \in [- 2, - 1] - Q \\ f_{2 (x)} = 4 + \frac{x}{x + 1} & if x \in Q \\ f_{3 (x)} = 3 & if x = \sqrt{2} \end{cases}

For the interval $[- 2, - 1] - Q$ , define $f_{1} (x) = x + 5$ . Let $a_{1}, a_{2} \in [- 2, - 1] - Q$ . Assume $f_{1} (a_{1}) = f_{1} (a_{2})$ . Then $a_{1} + 17 = a_{2} + 17$ . It follows that $a_{1} = a_{2}$ . So $f_{1}$ is injective. The image of $f_{1}$ will be (15, 17) which is in B and separate from the image of $f_{2}$ and $f_{3}$
For the rational numbers, define $f_{2} (x) = 4 + \frac{x}{x + 1}$ . Let $b_{1}, b_{2} \in Q$ . Assume $f_{2} (b_{1}) = f_{2} (b_{2})$ . We find

\begin{aligned} 4 + \frac{b_{1}}{b_{1} + 1} & = 4 + \frac{b_{2}}{b_{2} + 1} \\ \frac{b_{1}}{b_{1} + 1} & = \frac{b_{2}}{b_{2} + 1} \\ b_{2} b_{1} + b_{1} & = b_{2} b_{1} + b_{2} \\ b_{1} & = b_{2} \end{aligned}

So $f_{2}$ is injective. The image of $f_{2}$ will be $(4, 5]$ , which is in B and separate from the image of $f_{1}$ and $f_{3}$ .

For $\sqrt{2}$ , we simply map it to 3, which is obviously injective. It is also separate from the image of $f_{1}, f_{2}$ .

Thus by the pasting together theorem, $f$ is injective.

Now we define the function $g : B \to A$ as follows:

g (x) = {\begin{cases} g_{1} (x) = \frac{1}{6} x - 2.5 & if x \in [3, 6) \\ g_{2} (x) = \frac{1}{4} x - 5.25 & if x \in (15, 17) \end{cases}

For the interval $[- 3, 6)$ define $g_{1} = \frac{1}{6} x - 2.5$ . Let $a_{1}, a_{2} \in [- 3, 6)$ . Assume $g_{1} (a_{1}) = g_{1} (a_{2})$ . We find

\begin{aligned} \frac{1}{6} a_{1} - 2.5 & = \frac{1}{6} a_{2} - 2.5 \\ \frac{1}{6} a_{1} & = \frac{1}{6} a_{2} \\ a_{1} & = a_{2} \end{aligned}

So $g_{1}$ is injective. The image of $g_{1}$ will be $[- 2, 1.5)$ which is in A but separate from the image of $g_{2}$ .

For the interval (15, 17) define $g_{2} (x) = \frac{1}{4} x - 5.25$ . Let $b_{1}, b_{2} \in (15, 17)$ . Assume $g_{2} (b_{1}) = g_{2} (b_{2})$ . We find

\begin{aligned} \frac{1}{4} b_{1} - 5.25 & = \frac{1}{4} b_{2} - 5.25 \\ \frac{1}{4} b_{1} & = \frac{1}{4} b_{2} \\ b_{1} & = b_{2} \end{aligned}

So $g_{2}$ is injective. The image of $g_{2}$ will be $(- 1.5, 2)$ which is in A but separate from the image of $g_{1}$ .

Thus by the pasting together theorem, $g$ is injective.

Since $f$ and $g$ are injective, by the Schröder-Bernstein theorem, $| A | = | B |$ . $◻$

E 32.4
Let $A$ and $B$ be sets. Prove that if there is an injection $f : A \to B$ and a surjection $g : A \to B$ then $| A | = | B |$ .

Proof.
Let $A$ and $B$ be sets. Assume that there is an injection $f : A \to B$ and a surjection $g : A \to B$ .

By a proof in exercise 31.7, since there is a surjection $g : A \to B$ , there exists an injection $h : B \to A$ . Since there is an injection $A \to B$ and an injection $B \to A$ , by the Schröder-Bernstein Theorem $| A | = | B |$ .

E 32.5
Define $j : B_{2} \to A_{2}$ by the rule $j (y) = g (y)$ . To show that $j$ is a bijection, we need to establish three facts:

We first show that $j$ really is a function taking elements of $B_{2}$ to $A_{2}$ . For any $y$ in $B_{2}$ , the genealogy of $y$ is of type 2. The parent of $y$ is $g (y)$ , which must be in $A$ since $g$ is a function from $B$ to $A$ . Moreover, the genealogy of $g (y)$ is also of type 2, thus $g (y)$ is in $A_{2}$ . Hence, $j (y) = g (y)$ is in $A_{2}$ .
Next, we show that $j$ is injective. Let $y_{1}, y_{2} \in B_{2}$ and assume $j (y_{1}) = j (y_{2})$ . This gives us $g (y_{1}) = g (y_{2})$ . Since $g$ is injective (by its given properties), it must be the case that $y_{1} = y_{2}$ . Therefore, $j$ is injective because it maps distinct elements in $B_{2}$ to distinct elements in $A_{2}$ .
Now, we show that $j$ is surjective. For some $x \in A_{2}$ , its genealogy is of type 2, meaning it has a child in $B_{2}$ , say $y$ , such that $g (y) = x$ because $g$ is a function whose domain is all of $B$ and so all elements of $A_{2}$ are images under $g$ . Since $g (y) = x$ and $g (y) = j (y)$ by the definition of $j$ , we have $j (y) = x$ . This shows that every element of $A_{2}$ is an image of some element in $B_{2}$ , hence $j$ is surjective.

Since $j$ is both injective and surjective, we have shown that $j$ is indeed a bijection.

E 32.6
Proof.

Let $x, y \in (0, 1)$ , with decimal expansions $x = 0. x_{1} x_{2} x_{3} \dots$ and $y = 0. y_{1} y_{2} y_{3} \dots$ , where neither decimal expansion ends in repeating 9's.

Assume that $f (x) = f (y)$ . Then the sets ${x_{1}, 10 x_{2}, 100 x_{3}, \dots} - {0}$ and ${y_{1}, 10 y_{2}, 100 y_{3}, \dots} - {0}$ are equal.

Since the sets are equal, the corresponding elements must be equal. In other words, $x_{n} = y_{n}$ for all $n$ . If this were not the case, there would be some least $n$ for which $x_{n} \neq y_{n}$ . Without loss of generality, suppose $x_{n} < y_{n}$ . Then the set derived from $x$ would have a smaller $n$ -th element than the set derived from $y$ , which contradicts our assumption that $f (x) = f (y)$ .

Thus, because all corresponding digits in the decimal expansions of $x$ and $y$ are equal and since neither $x$ nor $y$ has a decimal expansion ending in repeating 9's, it must be the case that $x = y$ .

Therefore $f$ is injective. $◻$