Cantor's theorem (order theory)

Question

I will present a proof of Cantor's theorem (order theory), for which I will ask several questions.

Theorem (Cantor): Any $2$ countable linear dense orders with no end points are isomorphic.

Proof. Assume $(A,<_A),(B,<_B)$ satisfy premises. We construct isomorphisms $\varphi_n$ iductively.

First, take any $a\in A, b\in B$ and set $\varphi_1(a)=b$. We have (trivial) isomorphism $\varphi_1:\{a_1\}\rightarrow \{b_1\}$

Now, assume we have constructed isomorphisms up to $n$, for $n\geq1$. That is, we have isomorphism $\varphi_n:\{a_1,\ldots,a_n\}\rightarrow \{b_1,\ldots,b_n\}$. Now, pick an $a\in A\setminus \operatorname{dom}(\varphi_n)$ (if this is nonempty, otherwise we are done and we have our desired isomorphism). Next, define $$X=\{x\in\operatorname{dom}(\varphi_n)\mid x<_Aa\}$$ $$Y=\{y\in\operatorname{dom}(\varphi_n)\mid a<_Ay\}$$ That is, $X$ is the set of all elements below $a$ and $Y$ is the set of all elements above $a$, in some subset $\{a_1,\ldots,a_n\}\subseteq A$. Now, it cannot be the case that $X,Y$ are both empty, because $\operatorname{dom}(\varphi_n)$ is nonempty and the ordering is linear (e.g. $a$ is comparable with atleast one element in $\operatorname{dom}(\varphi_n)$).

Assume now $X$ is empty, then minimum of $\varphi_n(Y)$ exists (because $Y$ is finite), because $<_B$ has no endpoints, there is some $b\in B\setminus\varphi(Y)$ s.t. $b<\min \varphi_n(Y)$.

Simillarly, if $Y$ is empty, then maximum of $\varphi_n(X)$ exists, so take some $b$ s.t. $\max \varphi_n (X)<b$.

If both $X,Y$ are nonempty, by simmilar arguments both $\min \varphi_n(Y)$ and \varphi_n (X). Take some $b$ strictly in between these two (such $b$ exists, because $<_B$ is dense.

Now, set $\varphi_{n+1}=\varphi_n\cup (a,b)$.

Then $$\varphi:=\bigcup_{n\in\mathbb{N}}\varphi_n$$ is our desired isomorphism. Let's also check this really is an isomorphism. It is surely homomorphism, because of the construction, whenever $p<q$ then $\varphi_n(p)<\varphi_n(q)$. Injectivity follows. Surjectivity also holds, because in every step, we added exactly the tuple $(a,b)$ to $\varphi_{n+1}$, so in any $b\in\{b_1,\ldots,b_{n+1}\}$ we find the pre-image in $\{a_1,\ldots,a_{n+1}\}$.

My questions:

1. Is the reasoning for surjectivity clear/valid/rigorous enough?

2. Why can we say that if every "partial function" has a isomorphism property, then the final function $\varphi$ (which is union of all of $\varphi_n$'s) has still all the properties? It surely doesn't make sense to talk about something like "$\lim_{n\to\infty} \varphi_n=\varphi$", does it?

Answer 1

1. No (it looks like a misquoted proof). With the presented construction, one can only conclude that $\varphi$ is an isomorphism of some subsets of $A$ and $B$. See below for a corrected construction. $\newcommand{\dom}{\operatorname{dom}} \newcommand{\im}{\operatorname{im}}$
2. This is easy. Say, if $a,b\in\dom\varphi=\cup_{n\in\mathbb{N}}\dom\varphi_n$ and $a <_A b$, there is $n\in\mathbb{N}$ such that $a,b\in\dom\varphi_n$, therefore $\varphi(a) = \varphi_n(a) <_B \varphi_n(b) = \varphi(b)$.

The proofs I've seen proceed as follows. Let $A=\{a_1,a_2,\ldots\}$ and $B=\{b_1,b_2,\ldots\}$. We build isomorphisms $\varphi_n : A_n \to B_n$, but now such that $\{a_1,\ldots,a_n\}\subseteq A_n$ and $\{b_1,\ldots,b_n\}\subseteq B_n$.

Put $\varphi_1=\{(a_1,b_1)\}$. Suppose $\varphi_{n-1}$ is built. If $a_n\in A_{n-1}$ let $b=\varphi_{n-1}(a_n)$; otherwise take $b\in B\setminus B_{n-1}$ so that $b <_B \varphi_{n-1}(c) \iff a_n <_A c$ holds for all $c\in A_{n-1}$ (with existence justified exactly the way you did).

Now (we are in the middle of a step) let $\psi=\varphi_{n-1}\cup\{(a_n,b)\}$ and, similarly, if $b_n\in\im\psi$ we let $a=\psi^{-1}(b_n)$, otherwise we take $a\in A\setminus A_{n-1}$ so that $a <_A c \iff b_n <_B \psi(c)$ holds for $c\in\dom\psi$; finally, we put $\varphi_n=\psi\cup\{(a,b_n)\}$.