# A totally ordered set satisfying the induction principle is a well-ordered set

Let $(A,\leq)$ be a totally ordained set satisfying the induction principle, that is,

$\forall T\subseteq A (((\forall a \in A(S_a\subseteq T))\implies a\in T)\implies T=A)$.

Prove $(A,\leq)$ is a well-ordered set.

$(A,\leq)$ is a totally ordained set if $\forall x,y \in A(x\leq y \vee y\leq x)$.

$(A,\leq)$ is a well-ordered set if $\forall B\subseteq A(B\neq \emptyset\implies \exists m\in B \forall x\in B (m\leq x))$.

A totally ordained set satisfies the induction principle if $\forall x\in A (S_x\subseteq T\implies x\in T)\implies T=A$, for all $T\subseteq A$.

I suppose that $B\subseteq A$ has no minimum and $T=A-B$ and I must prove T=A.

• I assume that $S_x=\{y\in A:y<x\}$? – Brian M. Scott Nov 11 '16 at 18:55

HINT: Let $x\in T=A\setminus B$, and suppose that $S_x\subseteq T$; you need to show that $x\in T$. If $x\notin T$, then $x\in B$. Show that in this case $x=\min B$, contradicting the assumption that $B$ has no minimum element.
Alternatively, you can argue without contradiction. Let $B$ be any non-empty subset of $A$, and let $T=A\setminus B$. Then $T\ne A$, so it cannot be true that $S_x\subseteq T$ implies that $x\in T$. Thus, there must be an $x\in A\setminus T=B$ such that $S_x\subseteq T$. Now show that this $x=\min B$.
• I suppose that exists $z\in B$ such that $z\leq x$, since $z\in B$ and $B\subseteq A$, then $z\in A$, so $s\in S_x$ and as $S_x\subseteq T$ then $z\in T$ contradiction because $T=A\setminus B$ and $z\in B$. Then x is minimun element of B. – Carlos M. Nov 16 '16 at 16:23
• @Carlos: You need to assume that $z<x$ (not just $z\le x$) in order to conclude that $z\in S_x$, but otherwise you have it right. – Brian M. Scott Nov 16 '16 at 17:48