$\forall x \in X: (y < x \implies y \in E) \implies x \in E$

34 Views Asked by At

Let $(X, \leq)$ be well-ordered and non-empty.

If $E \subseteq X$ satisfies

(i) $\min E \in X$

(ii) $\forall x \in X: ((y < x \implies y \in E) \implies x \in E)$

Then $E=X$.

Proof: Assume $E \neq X$. Then we can put $x:= \min X \setminus E$. If $y < x$, then $y \notin X\setminus E$, i.e. $y \in E$. By (ii) $x \in E$, a contradiction. Thus $E= X$.$\quad \square$

Note now that in this proof $(i)$ was not used. But $(ii)$ vacuously holds if $E=\emptyset$, while the theorem fails if $E=\emptyset$. Where does the proof implicitely use $(i)$ then? Why is $(i)$ important?

1

There are 1 best solutions below

1
On BEST ANSWER

Property (i) is superfluous, it follows from (ii). In fact (i) does not really make sense for $E = \emptyset$ and if $E \neq \emptyset$ then it is immediate from the fact that $E \subseteq X$. Property (ii) already guarantees $E \neq \emptyset$.

To see this, let $x = \min X$. Then we vacuously have for all $y < x$ that $y \in E$. So we must have $x \in E$.