If $(A_1,<_1)$ and $(A_2,<_2)$ are linearly ordered sets and $|A_1|=|A_2|<\aleph_0$. Then $(A_1,<_1)$ and $(A_2,<_2)$ are isomorphic.
My attempt:
Lemma: Every linear ordering on a finite set is a well-ordering.
I will prove this theorem by induction on $n=|A_1|=|A_2|$.
For $n=0$, $A_1=A_2=\emptyset$, then $(A_1,<_1)$ and $(A_2,<_2)$ are clearly isomorphic.
Assume that the theorem is true for $n=k$.
For $n=k+1$, by Lemma, $<_1$ and $<_2$ are well-orderings. Let $a_1,a_2$ be the least elements of $A_1,A_2$ respectively. Then $|A_1-\{a_1\}|=|A_2-\{a_2\}|=n$, so by inductive hypothesis, there is an isomorphism $g$ between $(A_1-\{a_1\},{<_1} \cap (A_1-\{a_1\})^2$ and $(A_2-\{a_2\},{<_2} \cap (A_2-\{a_2\})^2$. We define $f:A_1 \to A_2$ by $$f(a)=g(a) \text{ for all }a\neq a_1 \text{ and }f(a_1)=a_2$$
Now we verify that $f$ is an isomorphism between $(A_1,<_1)$ and $(A_2,<_2)$.
It's clear that $f$ is bijective.
I'm stuck at proving $a <_1 b \iff f(a) <_2 f(b)$ for all $a,b\in A$. Although I find this result is quite intuitive, I'm unable to formalize it. Any help is appreciated!
Update: I added the proof that $f$ is isomorphism.
Now we verify that $f$ is an isomorphism between $(A_1,<_1)$ and $(A_2,<_2)$. It's clear that $f$ is bijective. Let $a,b\in A_1$.
- $a <_1 b \implies f(a) <_2 f(b)$
If $a,b\in A_1-\{a_1\}$, then $g(a) <_2 g(b)$ by the fact that $g$ is an isomorphism. Thus $f(a) <_2 f(b)$.
If one element of $\{a,b\}$ equals to $a_1$, WLOG, we assume $a=a_1$, then $f(a)=f(a_1)=a_2=\min A_2 <_2 f(b)$. Thus $f(a) <_2 f(b)$.
- $f(a) <_2 f(b) \implies a <_1 b$
If $f(a), f(b) \in A_2-\{a_2\}$, then $f(a)=g(a)$ and $f(b)=g(b)$. Thus $f(a) <_2 f(b) \implies g(a) <_2 g(b) \implies a <_1 b$ by the fact that $g$ is an isomorphism.
If one element of $\{f(a),f(b)\}$ equals to $a_2$, WLOG, we assume $f(a)=a_2$, then $a=a_1=\min A_1 <_1 b$. Thus $a <_1 b$.
I don't know how rigorous you want to be or how much set theory you know. Here is one approach:
Suppose $A$ and $B$ are well-ordered sets of equal cardinality. If $A=B=\emptyset$ then $A$ and $B$ are trivally order isomorphic.
Otherwise, let $|A|=|B|=n$ and let $a\in A$ and $b\in B$ be maximal in $A$ and $B$ respectively.
Then, $|A\setminus \left \{ a \right \}|=|B\setminus \left \{ b \right \}|$ so applying the inductive hypothesis, we get an order isomorphism $f:A\setminus \left \{ a \right \}\to |B\setminus \left \{ b \right \}.$
Now $g:A\to B$ defined by
$$ g(x) = \left\{ \begin{array}{ll} f(x) & \quad x <a \\ b& \quad x =a \end{array} \right. $$
is an order isomorphism.
Another way to do this would be to define
$E:A\to n\in \omega$ by $E(a_0)=\emptyset$ where $a_0$ is the least element in $A$ and in general, $E(t)=\left \{ E(x):x<t \right \}.$ Then, $E$ is by construction an order isomorphism from $A$ to $n$, where, of course, $n$ is well-ordered by $\in.$ To finish,observe that the $same$ function works for $B$, so $A$ and $B$ are both order isomorphic to $n$, hence to each other.