Mixing
Proof verification for statement involving three variables
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
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$?
proof-verification
asked yesterday
hanugm
789419
 |Â
show 1 more comment
up vote
0
down vote
favorite
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$?
proof-verification
asked yesterday
hanugm
789419
Sorry, its $y$..
– hanugm
yesterday
@AlvinLepik Issue is in step 4?
– hanugm
yesterday
1
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$.
– Alvin Lepik
yesterday
But we cant say that statement is proved with out induction on three variables.
– hanugm
yesterday
1
How does $P(1,3,1)$ follow? In your steps there is none that allows induction in $y$.
– wonko
yesterday
 |Â
show 1 more comment
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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$?
proof-verification
asked yesterday
hanugm
789419
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$?
proof-verification
asked yesterday
hanugm
789419
edited yesterday
asked yesterday
hanugm
789419
asked yesterday
hanugm
789419
asked yesterday
hanugm
789419
789419
Sorry, its $y$..
– hanugm
yesterday
@AlvinLepik Issue is in step 4?
– hanugm
yesterday
1
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$.
– Alvin Lepik
yesterday
But we cant say that statement is proved with out induction on three variables.
– hanugm
yesterday
1
How does $P(1,3,1)$ follow? In your steps there is none that allows induction in $y$.
– wonko
yesterday
 |Â
show 1 more comment
Sorry, its $y$..
– hanugm
yesterday
@AlvinLepik Issue is in step 4?
– hanugm
yesterday
1
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$.
– Alvin Lepik
yesterday
But we cant say that statement is proved with out induction on three variables.
– hanugm
yesterday
1
How does $P(1,3,1)$ follow? In your steps there is none that allows induction in $y$.
– wonko
yesterday
Sorry, its $y$..
– hanugm
yesterday
Sorry, its $y$..
– hanugm
yesterday
@AlvinLepik Issue is in step 4?
– hanugm
yesterday
@AlvinLepik Issue is in step 4?
– hanugm
yesterday
1
1
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$.
– Alvin Lepik
yesterday
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$.
– Alvin Lepik
yesterday
But we cant say that statement is proved with out induction on three variables.
– hanugm
yesterday
But we cant say that statement is proved with out induction on three variables.
– hanugm
yesterday
1
1
How does $P(1,3,1)$ follow? In your steps there is none that allows induction in $y$.
– wonko
yesterday
How does $P(1,3,1)$ follow? In your steps there is none that allows induction in $y$.
– wonko
yesterday
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
1
down vote
I assume the statement is of the form
$$forall xforall yforall 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 mboxandqquad forall y left (P(x,y,z)implies P(x,s(y),z)right ), $$
where $s(y)$ is the successor of $y$. If $0notinmathbb 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_1forall x_2ldots 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$.
answered yesterday
Alvin Lepik
2,025718
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
I assume the statement is of the form
$$forall xforall yforall 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 mboxandqquad forall y left (P(x,y,z)implies P(x,s(y),z)right ), $$
where $s(y)$ is the successor of $y$. If $0notinmathbb 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_1forall x_2ldots 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$.
answered yesterday
Alvin Lepik
2,025718
add a comment |Â
up vote
1
down vote
I assume the statement is of the form
$$forall xforall yforall 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 mboxandqquad forall y left (P(x,y,z)implies P(x,s(y),z)right ), $$
where $s(y)$ is the successor of $y$. If $0notinmathbb 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_1forall x_2ldots 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$.
answered yesterday
Alvin Lepik
2,025718
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I assume the statement is of the form
$$forall xforall yforall 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 mboxandqquad forall y left (P(x,y,z)implies P(x,s(y),z)right ), $$
where $s(y)$ is the successor of $y$. If $0notinmathbb 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_1forall x_2ldots 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$.
answered yesterday
Alvin Lepik
2,025718
I assume the statement is of the form
$$forall xforall yforall 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 mboxandqquad forall y left (P(x,y,z)implies P(x,s(y),z)right ), $$
where $s(y)$ is the successor of $y$. If $0notinmathbb 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_1forall x_2ldots 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$.
answered yesterday
Alvin Lepik
2,025718
edited yesterday
answered yesterday
Alvin Lepik
2,025718
answered yesterday
Alvin Lepik
2,025718
answered yesterday
Alvin Lepik
2,025718
2,025718
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2872707%2fproof-verification-for-statement-involving-three-variables%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sorry, its $y$..
– hanugm
yesterday
@AlvinLepik Issue is in step 4?
– hanugm
yesterday
1
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$.
– Alvin Lepik
yesterday
But we cant say that statement is proved with out induction on three variables.
– hanugm
yesterday
1
How does $P(1,3,1)$ follow? In your steps there is none that allows induction in $y$.
– wonko
yesterday