3
$\begingroup$

Let $S(n_1,n_2,n_3)$ be the statement to prove in natural numbers;

If I prove the following three

  1. $S(1,1,1)$ is true

  2. $\forall n_1n_2 S(n_1,n_2,n_3) \implies S(n_1,n_2,n_3+1)$

  3. $\forall n_1n_3 S(n_1,n_2,n_3) \implies S(n_1,n_2+1,n_3)$

Now, Is it sufficient or we have to prove for $n_1$ also?

$\endgroup$
3
$\begingroup$

Yes, you need one for $n_1$ as well. As it stands, you don't even have any way of knowing whether $S(2,1,1)$ is true from those assumptions.

$\endgroup$
  • $\begingroup$ For example, if $S(n_1, n_2, n_3)$ is the proposition $n_1 = 1$ then the conditions hold... $\endgroup$ – Daniel Schepler Aug 2 '18 at 23:16
1
$\begingroup$

You have to prove it for $n_1$ as well. Consider the statement: $$ S(n_1,n_2,n_3) \leftrightarrow (n_1 < 2) \land (n_2 = n_2) \land (n_3 = n_3) $$ We have that $S(1,1,1)$ is true. For $n_1 > 1$, the statement is false, so the implications are all true; for $n_1=1$, the statement is true regardless of $n_2$ and $n_3$, so the implications are still true.

Note: I'm not sure if this is sufficient to prove $S(n_1,n_2,n_3)$ for every $n_1,n_2,n_3$. We'd have to prove it formally.

$\endgroup$

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.