$$ P(\underline{1})\ \forall \bigg[k\underbrace{\ge1}\Big(P(k)\rarr P(k+1)\Big)\bigg]\rarr \forall n\ge\underline{1}\ \Big(P(n)\Big) $$

Induction ( as a rule if inference)

${\text{You might say this itself is an infinite number of hypotheses.}}\\]\text{\underline{These} could be replaced with }b$

We can replace the $1’s$ with $b’s$ and still have a true rule of inference.

Let $Q(k)= P(k-b+1)$

then $P(b) \equiv Q(1)$ and we have $\forall k\ge 1\ Q(k) \rarr Q(k+1)$

so $Q(n)$ is true for all $n\ge 1$, thus $P(n)$ is true for all $n\ge b$.

Demystified

How could we show P(6) without induction

$P(1)$

$P(1)\rarr P(2)$

$\therefore P(2)$ by MP

$P(2)$

$P(2)\rarr P(3)$

$\therefore P(3)$ by MP

$P(3)$

$P(3)\rarr P(4)$

$\therefore P(4)$ by MP

$P(4)$

$P(4)\rarr P(5)$

$\therefore P(5)$ by MP

$…$ by universal instantiation

Alternatively,

$P(1)\rarr P(2)$

$P(2)\rarr P(3)$

$\therefore P(1)\rarr P(3)$ by HS

$P(1)\rarr P(3)$

$P(3)\rarr P(4)$

$\therefore P(1)\rarr P(4)$ by HS

$…$

$P(1)\rarr P(6)$

$P(1)$

$\therefore P(6)$

Assignment 5a

Things aren’t always this “easy”

Ex. Suppose

$\forall k\ge 1\ P(k)\rarr P(2k)$

$\forall k\ge 1$ with k odd $P(3k+1)\rarr P(k)$

and $P(4)$ is true.

Is $P(9)$ true?

$P(4)\rarr P(8)\rarr P(16 )\rarr P(5) \rarr P(10) \rarr P(20) \rarr P(40) \rarr P(13) \rarr P(26) \rarr P(52) \rarr P(17) \rarr P(34) \rarr P(11) \rarr P(22) \rarr P(7) \rarr P(14) \rarr P(28) \rarr P(9)$

This pattern is pathological.

Nobody knows if $\exist n\ge 1\ \Big(\neg P(n)\Big)$ (Collatz Conjecture)