2
$\begingroup$

I read a proof that went along these lines:

"Let $(X, \le)$ be a woset. Let $E$ be a subset of $X$ such that:

  1. the minimal element of $X$ is a member of $E$
  2. for any $x \in X$, if $\forall_y[y \lt x \rightarrow y \in E]$, then $x \in E$

Then, $E = X.$ Proof:

Suppose that $E \ne X$. Then, let $x$ be the minimal element of $X - E$. Since, it is an element of $X - E$, it can not be an element of $E$. But, any $y \lt x$ would imply $y \in E$, because $x$ is the minimal element of $X - E$, so any element $y$ such that, $y \lt x$ would have to be in $E$. If it wasn't, $x$ wouldn't be the minimal element of $X -E$. Since $y \lt x$ implies $y \in E$, then by the second condition, $x \in E$ and a contradiction arises, so $X = E$."

But, then the claim was made that this being true allows proof by induction on any well founded set. I understand the proof, but I don't see how this theorem and induction are related. Could someone explain?

$\endgroup$
  • $\begingroup$ See here and this post. $\endgroup$ – Mauro ALLEGRANZA Feb 12 '15 at 7:43
  • $\begingroup$ That's strange: I first read this question only a few minutes ago, and I read it several times, but I never saw this comment attached to it until after I posted my answer just now. Is this just a glitch in my poor disordered brain, or does the website sometimes do this? (I'm a newbie, as you may gather.) $\endgroup$ – Calum Gilhooley Feb 12 '15 at 14:36
1
$\begingroup$

Notice that a well-ordered set is precisely a well-founded total ordering, but the proof you quoted makes no use of the total property, so it is valid whenever $X$ is well-founded.

Next, notice that condition 1 is redundant, because it is simply the special case of condition 2 where $x$ is the minimal element of $X$.

(In that case, there simply is no $y \in X$ such that $y < x$, so the antecedent proposition that $y \in E$ for all $y < x$ is vacuously true, therefore the consequence that $x \in E$ is also true.)

Finally, notice that the proof actually works in both directions. Condition 2 can be rewritten:

2' If $x \in X \setminus E$ then there exists $y < x$ such that $y \in X \setminus E$.

Equivalently:

2'' $X \setminus E$ has no minimal element.

So what was proved was the implication:

"If $E$ is any subset of $X$ such that $X \setminus E$ has no minimal element, then $X \setminus E$ is empty."

Since $E$ is an arbitrary subset of $X$, this is equivalent to the implication:

"If $F$ is any subset of $X$ with no minimal element, then $F$ is empty."

Or to put it another way:

"If $F$ is any non-empty subset of $X$, then $F$ has a minimal element."

Of course this is true, by definition, if and only if $X$ is well-founded.

In other words, the proposition that induction on $X$ is a valid method of proof can actually be used as an alternative definition of what it means for the poset $X$ to be well-founded.

$\endgroup$
  • $\begingroup$ See also today's (10 March 2015) blog entry by Tobias Kildetoft. $\endgroup$ – Calum Gilhooley Mar 10 '15 at 20:15

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.