Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question
    
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

3 Answers 3

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.

share|improve this answer

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.

share|improve this answer
1  
As stated in the comments, this relies on the (pretty reasonable) assumption that the range of $f$ is $\mathbb{N}$ –  Soke Apr 17 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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.