Propositional Functions with Well-Ordering/Strong Induction
I'm having trouble with this problem:
$P(k)$ is a propositional function in the natural numbers $\mathbb{N}$. $P(1)$ is true. Further, $\forall j,k \in\mathbb{Z}(\, [P(j) \land P(k)] \implies P(j+k)\,).$ For what elements of $\mathbb{N}$ is P(k) necessarily true?
My Thought Process:
- Well-ordering says that every non empty set of non-negative integers has a least element and that here is 1 based on domain.
- We don't have a given value for j, though we do for k. Here is where my reasoning is breaking down. To me, I think that using the k value and the formula without j being explicitly stated means that the conditions are true for any value j+k. But I'm not certain. I'd think there would need to be a 'next rung' to climb the induction ladder to say that. If that is not the case, I'd think that it would only be strong enough to say the only element that is true is when k=1.
@DanielWainfleet showed in the comments above that this is true for all k in the propositional function. He did this by contradiction
If $\neg$P(k) for some k$\in$$\Bbb Z$$^+$ then there exists k$^∗$, the least k$\in$$\Bbb Z$$^+$ such that $\neg$P(k). Then k$^*$$\gt$1 because P(1), so $\,$ k$^*$$\gt$(k$^*$-1) $\in$$\Bbb Z$. So, P(k$ ^ *$-1) by the def'n of k$^∗$. But then [P(k$^*$-1)$\land$P(1)]$\implies$P((k$^*$-1)+1)$\Longleftrightarrow$P(k$^∗$) contrary to $\neg$P(k$^∗$).