What does "$f(x,y)$ is strictly increasing in each argument" imply? Say we have a function $f(x,y)$. below are what we know about $f(x,y)$ 


*

*strictly increasing in each argument. 

*$x$ and $y$ are natural numbers only, i.e., $0, 1, 2, ...$


Now we have a fixed number $z$ which is also a natural number and we want to find out all values of $x$ and $y$ which satisfy $f(x,y)=z$.

My question:


*

*Is $x \leq z,$ $y \leq z$ implied from the above two conditions? and Why?

*Is $f(x,y) \geq x + y$ implied also? and Why?

 A: Okay, I don't think the previous two answers are correct. You can prove this. Lets restate facts:
$$
x, y, z \in \mathbb{N} \\
f(x, y) = z \\
x < k \Rightarrow f(x, y) < f(k, y) \\ 
y < k \Rightarrow f(x, y) < f(x, k)
$$
With these four facts we can prove the second part by induction:
For $x = y = 0$:
$$
\begin{aligned}
x + y & \le f(x, y) \\
\therefore 0 & \le f(0, 0) & \text{by substitution} \\
\forall z \in \mathbb{N} ~~~ f(x, y) = z & \Longrightarrow f(x, y) \ge 0 & \text{because the natural numbers are from zero up}\\
\therefore 0 & \le f(0, 0)
\end{aligned}
$$
So with the zero case proven we can now try the induction step. We need to prove that if $x + y \le f(x, y)$ then it is true that $(x + 1) + y \le f(x + 1, y)$:
Lets work on the initial step first:
$$
\begin{aligned}
x + y & \le f(x, y) & \text{given} \\
x + 1 + y & \le f(x, y) + 1 & \text{add one to both sides}
\end{aligned}
$$
And now lets work on what we need to prove:
$$
\begin{aligned}
f(x, y) & < f(x + 1, y) & \text{by the increasing property of the first argument} \\
\therefore f(x, y) + 1 & \le f(x + 1, y) & \text{adding one to the left makes it possibly equal because this is the set of natural numbers} \\
\therefore (x + y) + 1 & \le f(x + 1, y) & \text{by substitution of the induction assumption}
\end{aligned}
$$
And that is it, we have proven that it is true for the first argument of f and hopefully you can see that it will be true for the second argument of f by symmetry.
I decided to prove this myself once I saw it given as true in Chapter 3 of Pearls of Functional Algorithm Design.
A: Partial answer: Strictly increasing in each argument means 
$$f(x,y) < f(z,y) \text{ for } x < z$$ and
$$f(x,y) < f(x,z) \text{ for } y < z.$$
Therefore you cannot imply that $x \leq z, y \leq z$ from the above. 
For 2., this is neither true.
A: None of these are implied. Take for example $$
  f(x,y) = x + y - 1 \text{.}
$$
Then for $x=y=0$, $f(x,y) = -1 < x,y$ and $f(x,y) = -1 < 0 = x+y$.
