Double Induction? (1 Viewer)

Sy123 · Dec 8, 2014

So I was thinking of whether the following inductive statements are logically valid:

Say we have 2 statements, $S_1$ and $S_2$

$\\ $For the base case,$ \ S_1 \ $is true, assuming$ \ S_1 \ $is true for the general case, then if$ \ S_2 \ $is true, then the inductive step for$ \ S_1 \ $is true$$

$\\ $For the base case,$ \ S_2 \ $is true, assuming$ \ S_2 \ $is true for the general case, then if$ \ S_1 \ $is true, the inductive step for$ \ S_2 \ $is true$$

$\\ $Therefore$ \ S_1 \ $and$ \ S_2 \ $are both true for all cases$$

So as you can see, both inductive steps are connected to each other in a sort of circle, does it still count as circularity considering we are only assuming it for an inductive step?

seanieg89 · Dec 16, 2014

Sy123 said:
So I was thinking of whether the following inductive statements are logically valid:

Say we have 2 statements, $S_1$ and $S_2$

$\\ $For the base case,$ \ S_1 \ $is true, assuming$ \ S_1 \ $is true for the general case, then if$ \ S_2 \ $is true, then the inductive step for$ \ S_1 \ $is true$$

$\\ $For the base case,$ \ S_2 \ $is true, assuming$ \ S_2 \ $is true for the general case, then if$ \ S_1 \ $is true, the inductive step for$ \ S_2 \ $is true$$

$\\ $Therefore$ \ S_1 \ $and$ \ S_2 \ $are both true for all cases$$

So as you can see, both inductive steps are connected to each other in a sort of circle, does it still count as circularity considering we are only assuming it for an inductive step?

I should be able to answer this, but the way you have written this is slightly ambiguous/confusing...especially on the quantifier front. Can you rephrase it a little more formally please?

Eg $S_1(n)$ is the statement that statement 1 is true about the number n. The symbols $\land,\lor,\lnot,\forall,\exists,\Rightarrow$ refer to: and, (inclusive) or, not,for all, there exists, implication.

So the classical statement about induction being valid is:

$S(1)\land (\forall n\in\mathbb{N})(S(n)\Rightarrow S(n+1))\Rightarrow (\forall n\in\mathbb{N})S(n).$

Sy123 · Dec 17, 2014

seanieg89 said:
I should be able to answer this, but the way you have written this is slightly ambiguous/confusing...especially on the quantifier front. Can you rephrase it a little more formally please?

Eg $S_1(n)$ is the statement that statement 1 is true about the number n. The symbols $\land,\lor,\lnot,\forall,\exists,\Rightarrow$ refer to: and, (inclusive) or, not,for all, there exists, implication.

So the classical statement about induction being valid is:

$S(1)\land (\forall n\in\mathbb{N})(S(n)\Rightarrow S(n+1))\Rightarrow (\forall n\in\mathbb{N})S(n).$

Right, so I would perhaps characterise what I'm saying like this:

$\\ ( S_1(1) \land (\forall n\in \mathbb{N})((S_1(n) \land S_2(n)) \Rightarrow S_1(n+1)) ) \land (S_2(1) \land (\forall n \in \mathbb{N})((S_2(n) \land S_1(n) )\Rightarrow S_2(n+1)) \Rightarrow (\forall n \in \mathbb{N})(S_1(n) \land S_2(n))$

Making it easier to read:

$P_1: \ S_1(1) \land (\forall n\in \mathbb{N})((S_1(n) \land S_2(n)) \Rightarrow S_1(n+1))$

$P_2: \ S_2(1) \land (\forall n \in \mathbb{N})((S_2(n) \land S_1(n)) \Rightarrow S_2(n+1))$

$\\ P_1 \land P_2 \Rightarrow (\forall n \in \mathbb{N})(S_1(n) \land S_2(n))$

seanieg89 · Dec 17, 2014

Sure, it seems this should be valid. (If we have P1 and P2 then we have both statements for all positive integers.)

If we write $S(n)=S_1(n)\land S_2(n)$ , then this is pretty much the standard induction axiom applied to S.

We have $P_i\land S(n)\Rightarrow S_i(n+1)$ , so

$P_1\land P_2 \land S(n) \Rightarrow S_1(n+1)\land S_2(n+1)=S(n+1).$

Sy123 · Dec 17, 2014

seanieg89 said:
Sure, it seems this should be valid. (If we have P1 and P2 then we have both statements for all positive integers.)

If we write $S(n)=S_1(n)\land S_2(n)$ , then this is pretty much the standard induction axiom applied to S.

We have $P_i\land S(n)\Rightarrow S_i(n+1)$ , so

$P_1\land P_2 \land S(n) \Rightarrow S_1(n+1)\land S_2(n+1)=S(n+1).$

Ah ok thank you!

I asked this because I was trying to solve an induction question like this, and thought if it was logically valid

Double Induction? (1 Viewer)

Sy123

This too shall pass

seanieg89

Well-Known Member

Sy123

This too shall pass

seanieg89

Well-Known Member

Sy123

This too shall pass

Users Who Are Viewing This Thread (Users: 0, Guests: 1)