2
$\begingroup$

I often see two variations in how the principle of strong induction is stated:

First Variation: $\Big(B\!\subseteq\!\mathbb{N}\wedge1\!\in\!B\wedge\big(\forall x[x\!\leq\!k\rightarrow x\!\in\!B]\rightarrow k\!+\!1\!\in\!B\big)\Big)\longrightarrow B\!=\!\mathbb{N}$

Second Variation: $\Big(B\!\subseteq\!\mathbb{N}\wedge\big(\forall x[x\!<\!k\rightarrow x\!\in\!B]\rightarrow k\!\in\!B\big)\Big)\longrightarrow B\!=\!\mathbb{N}$

Are these logically equivalent (superficially, it seems that they are, but I am having difficulty proving that they are). And is one variation preferred over the other, or does it basically depend on the specific problem at hand?

For context, I am assuming only the following axioms and definitions:

Peano Axioms:

  • (P1) $\ \exists x[x\!=\!1]$;

  • (P2) $\ $there exists an unary ("successor") function $S$ on $\mathbb{N}$ (i.e., $x\!\in\!\mathbb{N}\rightarrow S(x)\!\in\!\mathbb{N}$);

  • (P3) $\ \forall x[S(x)\!\neq\!1]$;

  • (P4) $\ \forall x\forall y[S(x)\!=\!S(y)\rightarrow x\!=\!y]$

  • (P5) $\ $Principle of Mathematical Induction

Addition

  • (A1) $\forall x[S(x)=x+1]$

  • (A2) $\forall x\forall y[x+S(y)=S(x\!+\!y)]$

Order Relation

  • (O1) $\ x\!<\!y\leftrightarrow\exists z[x\!+\!z\!=\!y]$

  • (O2) $\ x\!\leq\!y\leftrightarrow[x\!=\!y\vee x\!<\!y]$

$\endgroup$
  • $\begingroup$ What is P1 supposed to be saying? $\endgroup$ – Derek Elkins Mar 12 '18 at 3:40
  • $\begingroup$ @DerekElkins: (P1) merely states that the signature for this particular logic includes a special constant symbol "1" (which here semantically is interpreted to represent the natural number one; but of course could equally have been "0" representing the natural number zero). $\endgroup$ – Stephen K. Mar 12 '18 at 12:48
  • 1
    $\begingroup$ For the formula $\exists x.x=1$ to be well-formed already presumes there's the constant $1$. In a logical context, the constant, function, and predicate symbols are specified in a signature before the axioms as that determines what the well-formed formulas are. In a more set-theoretic context, you'd probably write the first axiom as $1\in\mathbb N$. $\exists x.x=1$ is a logical tautology that asserts nothing. $\endgroup$ – Derek Elkins Mar 12 '18 at 18:01
  • $\begingroup$ Yes. Clearly (P1), and indeed (P2) as well, are not formal statements to be given the weight of "formal axioms." I never said they were. Most formulations of the Peano axioms only list (P3)-(P5) as the axioms, since (P1) and (P2) are inherent in the logical system itself. I am only listing them here for context (as many textbooks do as well). Thank you though for the comment. $\endgroup$ – Stephen K. Mar 12 '18 at 19:28
2
$\begingroup$

You need to quantify the $k$, so you get:

$$\Big(B\!\subseteq\!\mathbb{N}\wedge1\!\in\!B\wedge\forall k\big(\forall x[x\!\leq\!k\rightarrow x\!\in\!B]\rightarrow k\!+\!1\!\in\!B\big)\Big)\longrightarrow B\!=\!\mathbb{N}$$

and

$$\Big(B\!\subseteq\!\mathbb{N}\wedge\forall k\big(\forall x[x\!<\!k\rightarrow x\!\in\!B]\rightarrow k\!\in\!B\big)\Big)\longrightarrow B\!=\!\mathbb{N}$$

But if you do so, they are arithmetically equivalent. Using the other axioms, you should be able to derive the one from the other. Here is the general strategy:

First, you can use weak induction to prove that:

$$\forall x (x \not =1 \rightarrow \exists y \ x = y+1)$$

And you can also use weak induction to show things like:

$$\forall x \ x+1 \not =x$$

And:

$$\forall x \ \neg x <x$$

And:

$$\forall x \forall y (x \le y \leftrightarrow x < y+1)$$

and:

$$\forall x \ \neg x <1$$

And:

$$\forall x \ 1 \le x$$

Now let's derive version 2 from version 1.

So we assume $$\forall k (\forall x (x<k \rightarrow x \in B) \rightarrow k \in B)) \tag{1}$$

And we need to show that:

$$1 \in B \land \forall k (\forall x (x \le k \rightarrow x \in B) \rightarrow k+1 \in B)\tag{2}$$

To show $1 \in B$, simply instantiate $(1)$ with $1$: then, since nothing is smaller than $1$, that makes the antecedent true, and hence we get $1 \in B$

For the other part, assume that for some arbitrary $k$:

$$\forall x (x \le k \rightarrow x \in B)$$

Instantiate $(1)$ with $k+1$:

$$\forall x (x < k+1 \rightarrow x \in B) \rightarrow k+1 \in B$$

And since $x <k+1 \leftrightarrow x \le k$, you thus get $k+1 \in B$ as desired.

Deriving version 1 from version 2:

So now we assume $(2)$, and try to prove $(1)$

Ok, so for some arbitrary $k$ assume

$$\forall x (x < k \rightarrow x \in B)$$

Where want to show $k \in B$

Well, if $k=1$, we're done, since we have $1 \in B$ from $(2)$

If $k \not =1$, then $k = m+1$ for some $m$. But since $x < m+1 \leftrightarrow x \le m$, we thus have

$$\forall x (x \le m \rightarrow x \in B)$$

and thus we get $m+1 \in B$ from $(2)$, i.e. $k \in B$ as desired.

Personally I prefer working with the second; it's simpler and looks less like weak induction. But often times you'll end up having to prove the $n=1$ 'base case' separately anyway.

$\endgroup$
  • $\begingroup$ Why does it need to be stated with quantification over $k$? (Isn't that inherent (or even given) based on the inference rule of generalization?). Also, I'm afraid as my original question made clear, it's precisely the derivation of each variation from the other based on the axioms that I was having difficulty with; so any help/hints would be greatly appreciated. $\endgroup$ – Stephen K. Mar 13 '18 at 0:19
  • 1
    $\begingroup$ @StephenK. you need the universal quantifier where it is ... since the whole statement is a conditional, and since the quantifier is in the antecedent, taking it out would actually result in an existential, not a universal. Also, let me give you some hints for deriving them from wach other ... $\endgroup$ – Bram28 Mar 13 '18 at 0:54
  • $\begingroup$ @StephenK. "Isn't that inherent (or even given) based on the inference rule of generalization?" I suppose that you mean that there is a hidden universal quantifier binding $k$. In that case, the principle is saying that it is sufficient to prove an induction step for one value of $k$ in order to obtain that every natural number belongs to $B$. For example, use the second variation with $k$ being $1$. Then if $1\in B$, then $B=\mathbb{N}$. You can easily think of $B$ leading to absurd. $\endgroup$ – beroal Mar 14 '18 at 21:51

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.