1
$\begingroup$

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.
$\endgroup$
9
  • $\begingroup$ It is better style to use $\land$ (LaTex \land ) than ^ for "and". $\endgroup$
    – DanielWainfleet
    Commented Dec 5, 2021 at 21:19
  • $\begingroup$ Got it, edited -- thanks @DanielWainfleet $\endgroup$
    – Elemonti
    Commented Dec 5, 2021 at 21:24
  • 1
    $\begingroup$ 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^*>1$ because $P(1),$ so $k^*>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)\iff P(k^*)$ contrary to $ \neg P(k^*).$ $\endgroup$
    – DanielWainfleet
    Commented Dec 5, 2021 at 21:32
  • $\begingroup$ My edit was for style. Removed extra dollars so that $\forall j,k...$ et cetera would all be in one line. BTW you can use \Bbb for \mathbb, and you don't need braces {} around a single keystroke, e.g. \Bbb N. And you can use \, and \; and \quad to add space. $\endgroup$
    – DanielWainfleet
    Commented Dec 5, 2021 at 21:44
  • $\begingroup$ You're saying that you can also use the well-ordering principle to say there is a least P(k) which makes the propositional function false. You then use that value to show how the combined statement evaluates to true, but that is contrary to what you found proceeding that. So from that, you cannot say that any value $\textbf{necessarily true}$ other than P(1). Unless I misinterpret what you're saying there. $\endgroup$
    – Elemonti
    Commented Dec 5, 2021 at 21:52

1 Answer 1

Reset to default
1
$\begingroup$

@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$^∗$).

$\endgroup$
1
  • $\begingroup$ +1. And to get to up-vote my own words. :) $\endgroup$
    – DanielWainfleet
    Commented Dec 6, 2021 at 3:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .