# 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:

1. Is $x \leq z,$ $y \leq z$ implied from the above two conditions? and Why?
2. Is $f(x,y) \geq x + y$ implied also? and Why?
-
Hint: Induction. – Thomas Andrews Dec 5 '13 at 14:58
Why would one want to use induction in this case? – hejseb Dec 5 '13 at 15:03
You should specify the range of the function $f$, for instance $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, which would rule out some of the couterexamples below. (In other words, if the values of $f$ must be natural numbers too, as it seems based on your thesis) – rewritten Dec 5 '13 at 15:12
@rewritten That is a (quite important) point you're making. Jack, you should unaccept my answer as my counterexample allows for $z$ to not be a natural number. – hejseb Dec 5 '13 at 15:25
@hejseb It's technically the best way to prove 1. and 2., and you can only hide the induction - it isn't true for, say, strictly increasing function on positive rationals. – Thomas Andrews Dec 5 '13 at 15:27

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.

-

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.

-
As stated in the comments, this relies on the (pretty reasonable) assumption that the range of $f$ is $\mathbb{N}$ – Soke Apr 17 '14 at 4:03

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$.

-