Linear ordering isomorphic to an initial segment

Question

Question: Suppose $\left( L, \prec \right)$ is a linear ordering such that for every $X \subseteq L, \left( X, \prec \right)$ is isomorphic to an initial segment of $\left( L, \prec \right)$. Show that $\left( L, \prec \right)$ is a well ordering.

This is what i have gotten so far.

In order to show that $\left( L, \prec \right)$ well ordering I need to show that $\left( L, \prec \right)$ is a linear ordering and every non empty subset of $X$ has a $\prec-$ least member.

Since $\left( X, \prec \right) \cong \left( L, \prec \right)$ there is a bijective function $f:X \to L$ such that for any $x, y \in X$, if $x \prec y$ than $f(x)\prec f(y)$.

Since $f$ sends $x \in X$ to $f(x) \in L$, there is a subset $W=\{v \in L : f(v) \prec v \}$ which is non-empty.

This is what I have gotten and I am stuck after this. Also, is my set $W$ wrong? Help is much appreciated.

Answer 1

We don't have an isomorphism $f:(X,\prec) \, \to\, (L,\prec)$, only an order-preserving embedding such that the range of $f$ is an initial segment of $L$.

Now it's very easy: if we show that $L$ has a smallest element, then every initial segment of $L$ will have a smallest element, thus by the embedding being order-preserving, $X$ will have a smallest element, too.

To show that $L$ has minimum, simply take any singleton $X:=\{a\}$ with $a\in L$. By the hypothesis, $X$ is isomorphic to an initial segment of $L$, thus $f(a)$, the correspondent of $a$, must be minimal.

Answer 2

First suppose (L, ≺) is a well-ordering. Fix A ⊆ L. We’ll construct an isomorphism from (A, ≺) to an initial segment of (L, ≺).

Define f ={ (x,a) ∈ L×A: (pred(L,≺,x),≺) ∼= (pred(A,≺,a),≺)} (i) f is a function: Clearly, f is a relation. To see that it is a function, fix (x, a), (x, b) ∈ f and we’ll show that a = b. Towards a contradiction suppose a $neq$ b. Without loss of generality suppose a ≺ b. Since (x, a) and (x, b) are both in f , we get

(pred(L, ≺, x), ≺) ∼= (pred(A, ≺, a), ≺) and (pred(L, ≺, x), ≺) ∼= (pred(A, ≺, b), ≺).

Hence (pred(A, ≺, a), ≺) ∼= (pred(A, ≺, b), ≺). But this means that (pred(A, ≺, b), ≺) is a well-ordering that is isomorphic to a proper initial segment of itself. Contradiction. So f is a function.

(ii) f is injective: The proof is similar to (i) above. (iii) dom(f ) is an initial segment of (L, ≺): Suppose x ∈ dom(f ) and y ≺ x. We need to show that y ∈ dom(L). Let f(x) = a. Fix an isomorphism h : (pred(L, ≺, x), ≺) → (pred(A, ≺, a), ≺). Note that y ∈ dom(h). Let h(y) = b. It is clear that h pred(L, ≺, y) is an isomorphism from (pred(L, ≺, y), ≺) to (pred(A, ≺, b), ≺). Hence (y, b) ∈ f and so y ∈ dom(f). (iv) range(f) is an initial segment of (A,≺): The proof is similar to (iii) above. (v) f is an isomorphism from (dom(f ), ≺) to (range(f ), ≺):

Suppose x ≺ y are in dom(f). Put a = f(x) and b = f(y). Using the definition of f, it follows that (pred(L, ≺, x), ≺) ∼= (pred(A, ≺, a), ≺) and (pred(L, ≺, y), ≺) ∼= (pred(A, ≺, b), ≺). As x ≺ y, it follows that (pred(A, ≺, a), ≺) is isomorphic to an initial segment of (pred(A, ≺, b), ≺). Since no well-ordering can be isomorphic to a proper initial-segment of itself, it follows that a ≺ b. So f is an isomorphism from (dom(f),≺) to (range(f),≺). (vi) range(f) = A: Suppose not. Let a = min(A \ range(f )). Since range(f) is an initial segment of (A, ≺), it follows that range(f ) = pred(A, ≺, a). We claim that dom(f) = L. For suppose not and let x = min(L \ dom(f)).

Then dom(f) = pred(L, ≺, x). But this implies that (a, b) ∈ f using (i)-(v) above which is a contradiction. So dom(f) = L. Hence a ∈ dom(f). Now observe that f(a) ≺ a (since range(f ) = pred(A, ≺, a)) and iteratively applying f , we get a ≻ f(a) ≻ f(f(a)) ≻ . . . .

But this means that (L, ≺) has an infinite ≺-descending sequence which is impossible by part (a). (i)-(vi) implies that (A,≺) is isomorphic (via f−1) to an initial segment of (L,≺) (namely dom(f)).

Next, we show the converse. Suppose for every A ⊆ L, (A, ≺) is isomorphic to an initial segment of (L, ≺). We’ll show that (L, ≺) must be well-ordering. We can assume that L ̸= ∅. Let a ∈ L. Then ({a}, ≺) is isomorphic to an initial segment f (L, ≺). This implies that L has a ≺-least element, say x. Now let A ⊆ L be nonempty and fix an isomorphism f : (A, ≺) → (W, ≺) where W is an initial segment of (L,≺).

Note that x ∈ W. Put a = f−1(x). Then a is the ≺-least element of A. It follows that (L, ≺) is a well-ordering.