I often see the statement that weak and strong induction are equivalent. However, while I understand that this is true for the natural numbers, is this true for any well-founded set of objects? As I understand it, a well-founded relation can be a partial order without being a linear order, so we could be dealing with a well-founded set but not a well-ordered set. But then what would the 'successor' of any object be that the principle of weak induction refers to? Can we even meaningfully define a principle of weak induction for well-founded, but not well-ordered, sets? So does the equivalence between weak and strong induction only hold for well-ordered sets?
2 Answers
$\begingroup$
$\endgroup$
4
Actually, weak and strong induction aren't even equivalent for arbitrary well-orderings! Consider the well-ordering $\omega+1$ (so, the natural numbers together with one "infinite" element), and the formula $p(x)=$"$x$ is finite." Then:
$p(0)$ holds;
for every $x\in\omega+1$, if $p(x)$ holds, then $p(x+1)$ holds; but
$p(x)$ does not hold for every $x\in\omega+1$. (Specifically, it fails for the "top" element.)
So the problem isn't the non-totality of the ordering, but rather the existence of limit elements which have no predecessor.
answered Dec 1, 2015 at 21:06
-
$\begingroup$ Ok, so I guess I was right to suspect that weak and strong induction are only equivalent for certain kind of sets, thanks! But was I also right to suspect that in well-founded sets there might be no such thing as a 'successor', and hence no such thing as weak induction at all? $\endgroup$– BramDec 2, 2015 at 0:12
-
$\begingroup$ Well, that's not quite right. Say $a$ is a successor of $b$ (and $b$ is a predecessor of $a$) if $a>b$ and there is no $c$ with $a>c>b$. Successors are not unique, but we can formulate two versions of weak induction for a well-founded partial order $P$, with a least element $0$ and no limit elements. First version: If [$X\subseteq P$, $0\in X$, and for all $x\in P$, if every predecessor of $x$ is in $X$, then $x\in X$], then $X=P$. Second version: If [$X\subseteq P$, $0\in X$, and for all $x\in P$, if some predecessor of $x$ is in $X$, then $x\in X$], then $X=P$. (cont'd) $\endgroup$ Dec 2, 2015 at 1:12
-
$\begingroup$ As it turns out, these two versions are equivalent! (This is a good exercise.) And they hold of precisely those well-founded partial orders with least element, which have no limit elements - that is, for which every nonzero element has at least one predecessor. (Equivalently, these are the well-founded partial orders with least element which do not embed $\omega+1$.) So I think this is in fact the right notion of "weak induction." And this version is indeed equivalent to strong induction, for such partial orders. $\endgroup$ Dec 2, 2015 at 1:14
-
$\begingroup$ Thanks! But can't you have multiple 'smallest' elements in a partial order? And if so, could you include all those elements in the base case? In fact, would you be able to allow for those limit elements to exist as well, but just also include those in the base case? And if we were to do so, wouldn't that prevent the weak induction to go through in your example (since the base case fails for the 'infinite' element)? So with that modification, might weak and strong induction be equivalent after all? $\endgroup$– BramDec 2, 2015 at 14:38
$\begingroup$
$\endgroup$
OK, I did some more research myself on this, and feel I can now answer my own question.
First, we can follow Noah's suggestion and define immediate successor and predecessor as indicated. We can then consider Noah's two versions of weak induction as indicated as well, except that instead of insisting of a single least element $0$, we can allow for multiple minimal elements having no predecessors. Notice that in doing so, any kind of ' top limit element' as described by Noah would indeed have no immediate predecessor ... but would for that very reason be seen as a minimal element.
Thus, we can define weak induction as saying that as long as all those minimal elements have property $P$, and as long as all other elements $x$ have property $P$ if either all (version 1), or some (version 2) of its predecessors have property $P$, then all elements of X have property P.
It is easy to show that these two versions of weak induction hold true as long as X is well-founded. Indeed, in contrast to Noah's claim, these two versions of induction would actually hold for the set as initially described by Noah.
Are they equivalent? Well, they are 'equivalent' in so far as that for any well-founded set, whatever can be proven using one version can be proven with the other version as well.
If X is not well-founded, however, the two versions are no longer equivalent. Consider a set X consisting of elements $a_{1}, a_{2}, a_{3}, ...$ together with $b_{1},b_{2},b_{3},...$, and suppose relation R holds between any $b_{i}$ and $a_{i}$, as well as between any $a_{i+1}$ and $a_{i}$, and nowhere else (in other words, each $a_{i}$ has exactly 2 predecessors: $b_{i}$ and $a_{i+1}$, while any $b_{i}$ has no predecessors at all). R is not well-founded because of the infinite 'descent' of the $a$'s. And it is because of that infinite descent, that the first version of weak induction as defined no longer works, but since each $a_{i}$ has minimal element $b_{i}$ as a predecessor, the second version still works.
This also demonstrates that the second version of induction does not imply well-foundedness: apparently it can also work for non-well-founded relations. So that means that it is not equivalent to strong induction either, which works for all and only well-founded relations.
And the first version is also not equivalent to strong induction in the general case: with $X$ the singleton $a$, and with $R$ a relation that holds between $a$ and $a$, $R$ is clearly not well-founded, but the first version of weak induction holds true, simply because $a$ has no predecessor, and would thus be considered a minimal element after all.
So both versions of weak induction as defined can work for non-well-founded relations. Of course, this does not mean that they always work: keep all the $a$'s from the first example, and throw out all of the $b$'s. Then there are no more any minimal elements, and any version of induction no longer works.
In sum: Yes, we can define a meaningful notion of weak induction that isn't restricted to just well-ordered relations. In fact, we can define two, and interestingly, both versions can hold for non-well founded sets, meaning that they are no longer equivalent to strong induction. And without the restriction of well-foundedness, the two weak versions are not equivalent themselves either.