Trichotomy of well ordering

683 Views Asked by At

I'm trying to prove trichotomy of well ordering and I have a question concerning the proof of the following fact: If $(A,\triangleleft_A)$ and $(B,\triangleleft_B )$ are two well ordered sets, then the following statements cannot be both true: $$ \textbf{1.} \ \exists a\in A \ \text{s.t.} \ pred(A,a,\triangleleft_A)\cong (B,\triangleleft_B),\\ \textbf{2.} \ \exists b\in B \ \text{s.t.} \ (A,\triangleleft_A) \cong pred(B,b,\triangleleft_B). $$ Likely wrong proof:

Suppose that $\textbf{1}$ and $\textbf{2}$ hold. Let us define the function $$g:pred(B,b,\triangleleft_B)\rightarrow pred(A,a,\triangleleft_A).$$ From $\textbf{1}$, since $\forall b'\in pred(B,b,\triangleleft_B)$, we have $g(b')=a'$ with $a'\in pred(A,a,\triangleleft_A)$, then $g$ is injective. In general it is not surjective because an element of $pred(A,a,\triangleleft_A)$ can be mapped in $B\setminus pred(B,b,\triangleleft_B)$.

But now, if $a''\in pred(A,a,\triangleleft_A)$ is such that $g^{-1}(a'')=b$, can we say that the function $$ h:pred(B,b,\triangleleft_B)\rightarrow pred(A,a'',\triangleleft_A) $$ is surjective and order preserving (taking advantage of the properties of $g$ and of the isomorphism in the hypothesis)? In such a case, since $h$ inherits the injectivity from $g$, it would be an isomorphism and, from $\textbf{2}$ we would get the contradiction: $$ (A,\triangleleft_A) \cong pred(B,b,\triangleleft_B) \cong pred(A,a'',\triangleleft_A), $$ that is, $(A,\triangleleft_A)$ would be isomorphic to an initial segment of itself. I'm not able to prove that $h$ is indeed an isomorphism, maybe because it is not. Could you help me to find the mistake? (I hope this isn't too silly).
Thank you very much

1

There are 1 best solutions below

4
On BEST ANSWER

First of all, it is always a good idea to fix witnesses (even when they are unique!). As (1) and (2) hold, let us fix order-isomorphisms $$\begin{gather} f : ( B , \triangleleft_B ) \to \mathrm{pred} ( A , a , \triangleleft_A ); \\ g : ( A , \triangleleft_A ) \to \mathrm{pred} ( B , b , \triangleleft_B ). \end{gather}$$ Consider the composition $gf : ( B , \triangleleft_B ) \to \mathrm{pred} ( B , b , \triangleleft_B )$. Note that $gf$ is an order-isomorphism between $( B , \triangleleft_B )$ and its range. It is relatively easy to show that the range of $gf$ is an initial segment of $( B , \triangleleft_B )$. Since the range of $gf$ cannot be $B$, there is some $b_0 \in B$ such that $\mathrm{pred} ( B , b_0 , \triangleleft_B )$ is the range of $gf$. It thus follows that $gf$ is an order-isomorphism between $( B , \triangleleft_B )$ and $\mathrm{pred} ( B , b_0 , \triangleleft_B )$, contradicting that no well-ordered set is order-isomorphic to a (proper) initial segment!