Proof verification for statement involving three variables

Question

I have a statement $P(x,y,z)$ in natural numbers and I want to prove using mathematical induction and I managed to prove the following steps

1) $P(1,1,1),P(1,2,1)$

2) $P(x,1,z)\land P(x,2,z)\land P(x,3,z)\land \cdots \land P(x,y,z) \implies P(x+1,y,z)$

3) $P(x,y,z) \land P(x -1,y+1,z) \implies P(x,y+1,z)$

4) $P(x,y,z) \land P(x+1,y -1,z) \implies P(x,y,z+1)$

Is my statement proved? My doubt is on step 2 because the premise also includes $y+1$. If $P$ is not proved by above 4 steps, then which steps I need to work on more to prove my statement $P$?

I misspoke. If the statement is of the form "for every natural numbers $x,y,z\ P(x,y,z)$", it suffices to fix $x,y$ and conduct induction on $z$. — AlvinL, Aug 05 '18 at 07:34
But we cant say that statement is proved with out induction on three variables. — hanugm, Aug 05 '18 at 07:38
But $x,y$ are arbitrary and you will have shown via induction the statement holds for any $z$. You may also fix $y,z$ and conduct induction on $x$. — AlvinL, Aug 05 '18 at 07:40
How does $P(1,3,1)$ follow? In your steps there is none that allows induction in $y$. — wonko, Aug 05 '18 at 07:49

AlvinL · Answer 1 · 2018-08-05T07:59:43.593

I assume the statement is of the form $$\forall x\forall y\forall z\,P(x,y,z). $$ Step 2 with some adjustments is essentially what you are after to prove the whole thing. Let $x,z$ be arbitrarily chosen, it suffices to show $$P(x,0,z)\qquad \mbox{and}\qquad \forall y \left (P(x,y,z)\implies P(x,s(y),z)\right ), $$ where $s(y)$ is the successor of $y$. If $0\notin\mathbb N$ then the base case to be proved is $P(x,1,z)$.

This works in general for statements about natural numbers such as $$\forall x_1\forall x_2\ldots \forall x_n\ Q(x_1,x_2,\ldots ,x_n). $$ You fix all but one variable, say $x_1$, and conduct induction on $x_1$. Since the other variables are arbitrarily chosen the statement $Q$ must be true for all possible choices if you prove the inductive step for $x_1$.

Proof verification for statement involving three variables

1 Answers1