How should I go about proving P(x,y) $\forall x,y$ using complete induction? I couldn't find an example for this kind yet. (Some posts in here used normal induction, something like. a) P(0,0), b) for some x, y: $P(x,y) \rightarrow P(x+1,y)$ and c) for some x, y: $P(x,y) \rightarrow P(x,y+1)$. )
In my case, with P(x,y) alone I can not conclude P(x+1,y) or P(x, y+1). Thus, I wish to assume P(u,v) $\forall u,v < x, y$ in order to prove P(x,y).
Would the following scheme valid?
- prove P(0,0)
- prove P(0,y) $\forall y$
- prove P(x,0) $\forall x$
- assume P(u,y) $\forall u < x$ and $\forall y$, prove P(x,y)
- assume P(x,v) $\forall x$ and $\forall v < y$, prove P(x,y)
then conclude from 1-5 that P(x,y) $\forall x,y$.
Thanks
You're overcomplicating this; notice that if we let $Q(x)=\forall y\,P(x,y)$, then proving $Q$ for all $x$ using strong induction is the same as showing that for every natural number $x$, we have that $\forall x' < x[Q(x')]$ implies $Q(x)$ (note that this wraps in the base case, since if $x=0$, the assumption is empty). Written out more fully, what you need to show $\forall x\,Q(x)$ by strong induction is:
This is exactly your step (4) - which encompasses step (2) as the case where $x=0$. In particular, step (4) alone suffices to show that $P(x,y)$ for every $x,y$.
Similarly, step (5) is strong induction applied to $R(y)=\forall x P(x,y)$, and also, by itself, suffices to show $P(x,y)$ for all $x,y$.