Cfrgtkky

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 $ain A, bin 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 $ngeq1$. That is, we have isomorphism $varphi_n:{a_1,ldots,a_n}rightarrow {b_1,ldots,b_n}$. Now, pick an $ain Asetminus operatorname{dom}(varphi_n)$ (if this is nonempty, otherwise we are done and we have our desired isomorphism). Next, define
$$X={xinoperatorname{dom}(varphi_n)mid x<_Aa}$$
$$Y={yinoperatorname{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 $bin Bsetminusvarphi(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_ncup (a,b)$.

Then $$varphi:=bigcup_{ninmathbb{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 $bin{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_{ntoinfty} varphi_n=varphi$", does it?

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,bindomvarphi=cup_{ninmathbb{N}}domvarphi_n$ and $a <_A b$, there is $ninmathbb{N}$ such that $a,bindomvarphi_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_nin A_{n-1}$ let $b=varphi_{n-1}(a_n)$; otherwise take $bin Bsetminus B_{n-1}$ so that $b <_B varphi_{n-1}(c) iff a_n <_A c$ holds for all $cin 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_ninimpsi$ we let $a=psi^{-1}(b_n)$, otherwise we take $ain Asetminus A_{n-1}$ so that $a <_A c iff b_n <_B psi(c)$ holds for $cindompsi$; finally, we put $varphi_n=psicup{(a,b_n)}$.