Proving two sets $A, B$ are order isomorphic

Question

Let $A, B$ be well ordered sets. If $A$ is order isomorphic to a subset of $B$, and $B$ is order isomorphic to a subset of $A$, prove that $A, B$ are order isomorphic.

I know that two well ordered set is order isomorphic iff there exists a increasing function(i.e. $x<_A y \Rightarrow f(x)<_B f(y)$) from $A$ to $B$ which is bijective. The first thing I thought was the well ordering isomorphic theorem(if $(A, \le_A), (B, \le_B )$ are well orderd, only one of $A \cong B, A \cong B[b] \ \exists!b \in B, \ A[a] \cong B \ \exists!a \in A$) must hold, and the isomorphism is unique.)

Where do I have to start the proof?

Answer 1

SKETCH: Let $B'$ be a subset of $A$ order-isomorphic to $B$. Recursively construct an order-isomorphism from $B'$ onto an initial segment, not necessarily proper, of $A$. If this order-isomorphism is onto $A$, compose it with the order-isomorphism from $B$ into $A$ to get the desired order-isomorphism from $B$ onto $A$. If not, get a contradiction by using the order-isomorphism of $A$ to a subset of $B$ to get an order-isomorphism of $A$ into a proper initial segment of itself, from which you can recursively construct an order-isomorphism of $A$ onto a proper initial segment of itself.

Answer 2

Without recursion.

Let $<$ be a well-order on $A.$ A proper initial segment ($pis$) of $A$ is $pred_<(a)=\{a'\in A:a'<a\}$ for some (any) $a\in A.$ ("pred" for "predecessors"). I will define $a^*=\{a\}\cup pred_<(a).$

Claim: There is no order-isomorphism of $A$ to any subset of any $pis$ of $A.$

Proof. By contradiction, suppose $a\in A$ and $f:A\to C$ is an order-isomorphism with $C\subset pred_<(a).$ Then $f$ maps $a^*$ order-isomorphically to a subset of $pred_<(a).$

So consider $a_0,$ the $<$-least $a\in A$ such that there is an order-isomorphism of $a^*$ to a subset of $pred_<(a),$ and let $f_0$ be an order-isomorphism from $a_0^*$ to a subset of $pred_<(a_0).$

By the minimality of $a_0,$ if $b<a_0$ then $\{f_0(c):c\in b^*\}$ cannot be a subset of $pred_<(b)$ so $\exists c\le b\,(b\le f_0(c)).$ But $c\le b<a_0$ implies $f_0(c)\le f_0(b) .$

So for any $b<a_0$ we have $b\le f_0(b).$

BUT now in the case $b=f_0(a)$ we have $[\,a_0>b\land f(a_0)=b\le f(b)\,],$ so $f$ is not an order-isomorphism, a contradiction.

I think the rest of the Q has been fully addressed in other Answer(s) and Comments.