MathB.in - Share Mathematics with LaTeX and Markdown

Prove that TFAE, \(\forall x\):

(1) \(x\) finite i.e. \(x =_c n,\) some \(n \in \omega\) 
(2) \(\exists! n \in \omega\) so that \(x =_c n\) 
(3) \(x <_c \omega\).

\((2) \Rightarrow (1)\) and \((1) \Rightarrow (3)\) are immediate; it remains to show \((1) \Rightarrow (2)\) and \((3) \Rightarrow (1)\). Suppose towards a contradiction \((1) \not \Rightarrow (2)\) i.e. \[(\exists n \in \omega)[x =_c n] \land (\exists m \in \omega)[(m \not = n) \land (x =_c m)],\] which implies by composition of isomorphisms that \(n =_c m\); WLOG \(n <_\omega m \Rightarrow n \in m.\) But by transitivity we can embed \(n\) in \(m\), so \(m\) contains something the size of \(n\) along with \(n\) itself, contradicting \(n =_c m.\)

Suppose now that \(x <_c \omega.\) By definition there exists an embedding \(x \overset{f}{\hookrightarrow} \omega;\) consider \[\sup_{\omega} (\operatorname{Image}(f)) := \inf_\omega \{(w \in \omega)[(\forall x \in \operatorname{Image}(f))[w \geq x]]\}.\] Now, if \(\sup_\omega (\operatorname{Image}(f))\) is finite, we’re done, since \(x =_c \operatorname{Image}(f) \subseteq \sup_\omega (\operatorname{Image}(f))\) and we can induct downwards/use the pigeonhole principle on the expression \[(x =_c 0) \lor (x =_c 1) \lor … \lor (x =_c\sup_\omega(\operatorname{Image}(f)).\] But we see immediately that \(\sup_\omega (\operatorname{Image}(f)\) has to be finite, because if it were infinite we could induce an embedding \(\omega \overset{g}{\hookrightarrow} x\) by \[n \mapsto f^{-1}(\inf_\omega \{(w \in \operatorname{Image}(f))[w \geq_\omega \operatorname{max}_\omega (n, g(n - 1))]\})\] where we put \(g(-1) = 0\) and where \(f^{-1}\) is the inverse mapping from the image of the injection \(f\) to its domain.

Wed, 23 Apr 2014 05:40 GMT