Induction principle on well ordered set

Question

I'm new and very grateful this site exists. If I do something wrong, feel free to tell me.

I have to prove the following:

Let $S$ be a subset of a well ordered set $L$ with the conditions:

a) $0_L \in S$

b) If $x \in S$ then $x+1 \in S$

c) If $l$ is a nonzero limit element of $L$ and $L_{<x} \subseteq S$, then $l\in S$

Prove that $L=S$.

I think I have to take an element of L randomly and prove it is in S. If it is $0_L$, we are done. Suppose it is $x+1$ for a certain $x$ in L. Then it is enough that x is in L by (b), but how to show x is in L?

Maybe splitting the case it is a limit element or a succesor of a certain y in L?

Can someone explain me please? I'm looking at this for days...

Edit: My definition of a limit element is an element that is not a successor of some other element.

Answer 1

It seems like you haven't yet used the fact that $L$ is well-ordered in your solution attempt! That's the reason why you're stuck.

I would set up the proof like this.

Suppose, for contradiction, that $S$ is not the whole of $L$. Then $L \setminus S$ is a non-empty subset of $L$. Since $L$ is well-ordered, all non-empty subsets of $L$ contain a minimal element. In particular, the subset $L \setminus S$ contains a minimal element $m$.

To phrase this another way, if $S$ is not the whole of $L$, then there must exists an element $m \in L$ such that:

• $m \notin S$.
• If $x < m$, then $x \in S$.

Now your task is to derive a contradiction from this.

I suggest you consider three cases separately.

• Case 1: $m = 0_L$.
• Case 2: $m$ is a successor element, i.e. there exists an $x \in L$ such that $m = x + 1$.
• Case 3: $m$ is a non-zero limit element, i.e. $m \neq 0_L$, and $m \neq x + 1 $ for all $x \in L$.

You need to: (i) convince yourself that these three cases cover all the possibilities, and (ii) derive a contradiction in each of these three cases.