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.

  • 1
    $\begingroup$ I assume that $S_x=\{y\in A:y<x\}$? $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – Carlos M. Nov 16 '16 at 16:23
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Nov 16 '16 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.