Let $(L, \leq)$ be a well-ordered set, and $S\subseteq L$ an arbitrary subset.
If $S$ is closed under the successor function (mapping $x$ to $x+1$) and under least upper bounds, then $S=L$.
(Where $x+1 = \min\{y\in L: x < y\}$ and closed under least upper bounds is defined as: if any $A\subseteq S$ has an upper bound in $L$, then the least upper bound of $A$ belongs to $S$)
Prove that the previous conditions are equivalent to the following three conditions:
$0_L = \min L \in S$
If $x\in S$, then $x+1\in S$
If $\ell$ is a nonzero limit element of $L$ and $\{y\in L: y< \ell\} \subseteq S$, then $\ell \in S$.
(Where a limit element is defined as not being a succesor element, not being able to write it as $z+1$ for any $z\in L$. Or equivalent, $\ell$ is a limit element of $L$ if and only if it is the least upper bound of $\{y\in L: y< \ell\}$)
Proof
I've been able to prove $\Rightarrow$, but I'm kinda stuck on the $\Leftarrow$ part. (i.e. the three conditions imply closed under successor and least upper bounds).
The second condition implies trivial that $S$ is closed under the successor function.
Now choose an $A\subseteq S$ which has an upper bound in $L$. Left to prove: the least upper bound of $A$ belongs to $S$.
Let $\ell $ be the least upper bound of $A$, how can I show that $\ell\in S$?
Ideas
If I could somehow show that $\{y\in L: y< \ell\} \subseteq S$ then I'm done since then:
- If $\ell = 0_L$ then condition one implies $\ell \in S$
- If $\ell = z+1$ for a $z\in L$ then $z\in \{y\in L: y< \ell\}$ which implies $z\in S\Rightarrow \ell = z+1 \in S$
- If now $\ell$ is a limit element (which is not $0_L$), then the third condition implies $\ell \in S$.
However, showing $\{y\in L: y < \ell\} \subseteq S$ seems harder then I thought. We now how $A\subseteq \{y\in L: y< \ell\}$ but there might exists elements not in $A$ which belong in $\{y\in L: y< \ell\}$.
I've been able to show that $\mu := \min (\{y\in L: y<\ell\} \setminus A)$ belongs to $S$, but is that enough?
For the reverse implication we succeed if we can show that the second set of conditions implies $\{y:y<\sup A\}\subset S$ whenever $A\subset S$ and $A$ is bounded above in $L.$
Suppose (by contradiction) that $A\subset S$ and $\neg (\{y:y<\sup A\}\subset S).$ Let $y_0$ be the least member of $ \{y:y<\sup A\}\backslash S.$
If $y_0=0_L$ we have an immediate contradiction because $0_L\in S$ is part of the 2nd conditions.
If $y_0=y_1+1$ then by def'n of $y_0$ we have $y_1\in S ,$ but the 2nd conditions include $y_1\in S\implies y_1+1=y_0\in S.$
If $0\ne y_0\ne y_1+1$ for any $y_1$ then $ y_0=\sup \{y:y<y_0\}.$ And the def'n of $y_0$ implies $\{y:y<y_0\}\subset S.$ But $y_0$ is a non-$0$ limit element of $L,$ and the 2nd conditions require that $\{y:y<y_0\}\subset S\implies y_0\in S.$
Remark: In "Set Theory: An introduction To Independence Proofs" by K.Kunen, he uses pred$_R(x)$ for $\{y:yRx\}$ when $R$ is a binary relation . ("pred" for predecessors). (sometimes varying with pred$_L(x)$ when $R$ is a binary relation on a set or class $L.$)