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$?

  • 1
    $\begingroup$ I rephrased the question. Is this what you are asking? (If not, you can undo the edit by going to an earlier revision.) $\endgroup$ – Andrej Bauer Feb 15 '17 at 15:04
  • $\begingroup$ I might be missing a subtle difference, but it seems to be what I am asking. $\endgroup$ – choeger Feb 15 '17 at 15:06
  • $\begingroup$ In that case, I have the answer. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – 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)$.


| cite | improve this answer | |

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.