Exercise 1.5.11

Question

[Schröder-Bernstein Theorem]
  Assume there exists a 1-1 function $f: X ightarrow Y$ and another 1-1 function $g: Y ightarrow X .$ Follow the steps to show that there exists a 1-1, onto function $h: X ightarrow Y$ and hence $X \sim Y$.
  The strategy is to partition $X$ and $Y$ into components
  $$
  X=A \cup A^{\prime} \quad 	ext { and } \quad Y=B \cup B^{\prime}
  $$
  with $A \cap A^{\prime}=\emptyset$ and $B \cap B^{\prime}=\emptyset$, in such a way that $f$ maps $A$ onto $B$, and $g$ maps $B^{\prime}$ onto $A^{\prime}$.

\begin{enumerate}[label=(\alph*)] 
  \item Explain how achieving this would lead to a proof that $X \sim Y$.
  \item Set $A_{1}=X \setminus g(Y)=\{x \in X: x 
otin g(Y)\}$ (what happens if $\left.A_{1}=\emptyset ?ight)$ and inductively define a sequence of sets by letting $A_{n+1}=g\left(f\left(A_{n}ight)ight)$. Show that $\left\{A_{n}: n \in \mathbf{N}ight\}$ is a pairwise disjoint collection of subsets of $X$, while $\left\{f\left(A_{n}ight): n \in \mathbf{N}ight\}$ is a similar collection in $Y$.
  \item Let $A=\bigcup_{n=1}^{\infty} A_{n}$ and $B=\bigcup_{n=1}^{\infty} f\left(A_{n}ight)$. Show that $f$ maps $A$ onto $B$.
  \item Let $A^{\prime}=X \setminus A$ and $B^{\prime}=Y \setminus B$. Show $g$ maps $B^{\prime}$ onto $A^{\prime}$.
   \end{enumerate}

Ulisse Mini · Accepted Answer

\begin{enumerate}[label=(\alph*)] 
  \item $f : A 	o B$ and $g : B' 	o A'$ are bijective, therefore we can define
    $$h(x) = \begin{cases}f(x) & 	ext{ if } x \in A \ g^{-1}(x) & 	ext{ if } x \in A' \end{cases}$$
    which is bijective.
  \item If $A_1 = \emptyset$ then $g : Y 	o X$ is 1-1 and onto so we are done.
    So assume $A_1 
e \emptyset$, to show $\{A_n\}$ is pairwise disjoint, first consider how $A_1 \cap A_k = \emptyset$
    since $A_1 = X\setminus g(Y)$ and $g(f(A_1)) \subseteq g(Y)$. Define $h(x) = g(f(x))$

Since $h$ is injective we have $h(A \cap B) = h(A) \cap h(B)$ for all $A,B$ in $X$. (Proof left as an exercise to the reader.)
    Using this we can prove pairwise disjointness, let $j > k$ and use the iterated function notation $h^2 = h\circ h$ and note that $h^k$ is injective.
    $$
    A_{j+1} \cap A_{k+1} = h^{k}(A_{j-k}) \cap h^{k}(A_1) = h^k(A_{j-k} \cap A_1) = h^k(\emptyset) = \emptyset
    $$
    % TODO: Figure out the intuition behind this ^^, how does someone come up with this argument?!?
    % TODO: Draw image / add diagram (Tikz hard, maybe png from tablet)
    % TODO: Remove custom notation, explain in words
    And since $f$ is injective $f(A_j) \cap f(A_k) = f(A_j\cap A_k) = f(\emptyset) = \emptyset$.
  \item $f(A) = B$ because $f\left(\bigcup_{n=1}^\infty A_night) = \bigcup_{n=1}^\infty f(A_n)$ thus $f : A 	o B$ is onto. ($B$ was basically defined as the range of $f$)
  \item We show inclusion both ways by deriving contradictions. Key facts we use: (i) $A_1 \cap g(Y) = \emptyset$ (ii) $g(B) = \bigcup_{n=2}^\infty A_n = A\setminus A_1 = A\cap g(Y)$
    \begin{enumerate}[label=(oman*)] 
    \item $g(B') \subseteq A'$. SFC that $g(b') \in A$. Because $A_1\cap g(Y)=\emptyset$, $g(b) 
otin A_1$ meaning $g(b') \in \bigcup_{n=2}^\infty A_n = g(B)$, meaning $\exists b \in B$ with $g(b') = g(b)$ and $b' 
e b$, contradicting $g$ being 1-1.
    \item $A' \subseteq g(B')$. SFC $\exists a' \in A'$ with $a' 
otin g(B')$. Because $A' \subseteq g(Y)$ we have $a' \in g(B)$ (since $a' 
otin g(B')$) and $g(B) \subseteq A$ contradicting $a' \in A'$ (we can't have $a' \in A'$ and $a' \in A$.)
      % TODO: Rewrite pointless, only set ops ^ (if its clearer)
     \end{enumerate}
   \end{enumerate}

Exercise 1.5.11

Answers

Comments

Exercise 1.5.11

Answers

Comments

Add answer