Prove that $$|(1,\infty)| = |(-1,1)|$$ by: * using the Cantor-Schröder-Bernstein Theorem, and * (harder) by giving an explicit bijection between the two sets. --- ### CSB Proof #### Scratchwork We need to show that $$|(-1,1)| \le |(1,\infty)|$$ and $$|(1,\infty)| \le |(-1,1)|$$. Recall from the previous demo video that we just need to give an injective function from $$(-1,1)$$ to $$(1,\infty)$$, and an injective function from $$(1,\infty)$$ to $$(-1,1)$$. Remember that the injective function does not need to be surjective. We can, for example, map $$(-1,1)$$ to a subset of $$(1,\infty)$$, as long as we do so in an injective manner. Adding $$2$$ to each element of $$(-1,1)$$ gives an element of $$(1,3) \subseteq (1,\infty)$$. So maybe we can go with $$f : (-1,1) \to (1,\infty)$$ given by $$f(x) = x + 2$$. This is very likely to be injective. What about an injective function from $$(1,\infty)$$ to $$(-1,1)$$? This one's harder. For every $$x \in (1,\infty)$$, $$1/x \in (0,1) \subseteq (-1,1)$$. So we can let $$g : (1,\infty) \to (-1,1)$$ be defined by $$g(x) = 1/x$$. #### Proof To prove $$|(-1,1)| = |(1,\infty)|$$, we will show that $$|(-1,1)| \le |(1,\infty)|$$ and $$|(1,\infty)| \le |(-1,1)|$$. The result then follows from the Cantor-Schröder-Bernstein theorem. First, we will show that $$|(-1,1)| \le |(1,\infty)|$$ by giving an injective function from $$(-1,1)$$ to $$(1,\infty)$$. Let $$f : (-1,1) \to (1,\infty)$$ given by $$f(x) = x + 2$$. We will show that $$f$$ is injective. Let $$x,y \in (-1,1)$$ such that $$f(x) = f(y)$$, i.e, $$x + 2 = y + 2$$, so subtracting $$2$$ from both sides gives $$x = y$$. Similarly, we will show that $$|(1,\infty)| \le |(-1,1)|$$ by giving an injection from $$(1,\infty)$$ to $$(-1,1)$$. Let $$g : (1,\infty) \to (-1,1)$$ be defined by $$g(x) = 1/x$$. Once again, we will show that $$g$$ is injective. Let $$x,y \in (1,\infty)$$ such that $$g(x) = g(y)$$, i.e., $$1/x = 1/y$$. Rearranging gives $$x = y$$. This completes the proof. --- ### Explicit bijection #### Scratchwork This is a major pain. A key insight is to split this up into pieces that are easier to come up with, and then put them together. Recall from Propositions 21 and 22 of the Notes on Sets, Functions, Relations that if $$f : A \to B$$ and $$g : B \to C$$ are bijective, then $$g \circ f : A \to C$$ is also bijective. So for example, in the Notes on Cardinality, we had bijections $$\mathsf{sgn} : \mathbb{Z} \to \mathbb{N}$$, and $$\mathsf{dbl} : \mathbb{N} \to \mathbb{E}$$. Then $$\mathsf{dbl} \circ \mathsf{sgn} : \mathbb{Z} \to \mathbb{E}$$ is bijective. A number of the functions in the Notes on Cardinality can be difficult to come up with on one's own, so it's useful to understand them/memorize them to be able to make modifications to them or put them together in order to build bijective functions (or injective functions to use in CSB). So we already saw this function $$g : (1,\infty) \to (0,1)$$ given by $$g(x) = 1/x$$. We showed that this function is injective, so if we showed that it is also surjective, then $$g$$ is a bijective function between $$(1,\infty)$$ and $$(0,1)$$. So we "just" need to find a bijective function between $$(0,1)$$ and $$(-1,1)$$. One possibility is $$h : (0,1) \to (-1,1)$$ given by $$h(x) = 2x - 1$$. We could, for example, prove separately that $$g$$ and $$h$$ are bijective, and then apply Propositions 21 and 22 of the Notes on Sets, Functions, Relations. Alternatively, we will prove directly that $$h \circ g : (1,\infty) \to (-1,1)$$ is a bijective function. $$h \circ g = 2(1/x) - 1 = \frac{2-x}{x}$$. Scratchwork for surjectiveness: If $$h \circ g(x) = y$$, then $$\frac{2-x}{x} = y$$. Rearranging, $$2-x = xy$$, i.e., $$2 = x + xy = x(1 + y)$$, so isolating $$x$$, we get $$x = \frac{2}{1 + y}$$. Hopefully this choice of $$x$$ is actually in the domain $$(1,\infty)$$. #### Proof Consider the function $$f : (1,\infty) \to (-1,1)$$, given by $$f(x) = \frac{2-x}{x}$$. We will prove that this function is bijective. (Injective:) Let $$x,y \in (1,\infty)$$ so $$f(x) = f(y)$$, i.e., $$\frac{2-x}{x} = \frac{2-y}{y}$$. Cross multiplying gives $$(2-x)y = (2-y)x$$, then expanding gives $$2y - xy = 2x - xy$$. Then adding $$xy$$ to both sides and dividing by $$2$$, we get $$x = y$$. (Surjective:) Let $$y \in (-1,1)$$. We need show that there exists $$x \in (1,\infty)$$ such that $$f(x) = y$$. Consider $$x = \frac{2}{y+1}$$. Since $$y \in (-1,1)$$, $$y + 1 \in (0,2)$$. Then that means that $$\frac{2}{y+1} \in (1,\infty)$$. And $$f(x) = f\left(\frac{2}{y+1}\right) = \frac{2 - \frac{2}{y+1}}{\frac{2}{y+1}} = \left(2 - \frac{2}{y+1}\right)\frac{y+1}{2} = y + 1 - 1 = y.$$ That completes the proof. --- --- --- --- --- --- ---