# Can you apply the induction hypothesis to its outcome?

Assume a well-founded relation $<$ over a set $S$ and a property $P$ on $S$ such that:

1. $P$ holds for all minimal elements of $S$.
2. For every $b \in P$ and $a < b$ we have: if $P(a)$ then there exists $c < b$ such that $P(c) \Rightarrow P(b)$.

Question: does it follow that $P(c)$ holds for all $c \in S$?

• I rephrased the question. Is this what you are asking? (If not, you can undo the edit by going to an earlier revision.) – Andrej Bauer Feb 15 '17 at 15:04
• I might be missing a subtle difference, but it seems to be what I am asking. – choeger Feb 15 '17 at 15:06
• In that case, I have the answer. – Andrej Bauer Feb 15 '17 at 15:09

As stated, the reasoning does not make much sense to me.

You claim that, in your specific case, you have

• $a < b \wedge P(a) \Longrightarrow \exists c < b$
• $P(a) \wedge P(b) \Longrightarrow P(b)$

but these properties are trivial tautologies -- they tell nothing about your specific case.

In the first one, if $a < b$, we already know $\exists c<b$. We don't even need $P(a)$.

The second one is an instance of the tautology $p \land q \implies q$.

I'm not sure how these two properties help in the induction proof at all.

• Thank you for pointing that out. The first part was an abuse of the existence quantor. What I meant was, that $c$ is actually an element of the set. The second was just a stupid typo. – choeger Feb 15 '17 at 14:14

The answer is positive.

To show that $P$ holds for all $c \in S$, we need to establish, for all $b \in S$: $$(\forall a < b . P(a)) \Rightarrow P(b).$$ Then we may apply the well-foundedness of $<$ to $P$.

So consider any $b \in S$ and suppose $\forall a < b . P(a)$. We need to show that $P(b)$ holds. There are two cases:

1. There is no $a < b$. In this case $b$ is minimal and so $P(b)$ by the first assumption in the statement of the question.

2. There is some $a < b$. Then we know that $P(a)$ holds. By the second assumption of the statement of the question there is $c < b$ such that $P(c) \Rightarrow P(b)$. However, since $c < b$ we do have $P(c)$ by assumption, and therefore $P(b)$.

QED.