Proving One to One: f(x,y) = (x+y, 2x-3y) is a One-to-One Function

[scorpius1782]

Homework Statement

I'm having a lot of problems with this class of thinking I understand something then getting a grade back that proves otherwise. I'd like someone to check my proof of this:

Claim: $f:\mathbb{N}^2 \rightarrow \mathbb{N}^2 by f(x,y) = (x+y, 2x-3y)$ is one to one.

Homework Equations

The Attempt at a Solution

Using the definition of one to one: $f:A\rightarrow B$ is one-to-one, i.e. $\forall x,y \in A, f(x) = f(y) \rightarrow x = y$

Proof: Let x, y, w, z $\in \mathbb{Z}$

I'll take the two elements (that is x+y and 2x-3y) separately in order to prove one to one.

In order for $f(x,y)=g(w,z)$ then $x+y=w+z$ therefore x=w or x=z and y=w or y=z. So it is clear that by itself this part of the function is not one to one.



Now for $2x-3y$ we have $f(x,y)=g(w,z)$. Then $2x-3y=2w-3z$. However here we do not have the possibility for x to equal w or z and y cannot equal w or z. It must be one or the other as $2x-3y\neq2y-3x$ and $2w-3z\neq2z-3w$. Except if, and only if, $x=y=w=z=0$. But this fits in the definition of one to one, regardless.



Finally, from the above constraints $w=x$ and $y=z$. Therefore $x, y, w, z \in \mathbb{Z}, f(x,y)=f(w,z) \implies (x,y)=(w,z)$

 

[hilbert2]

Why don't you just form the pair of linear equations

$x+y=x'+y'$
$2x-3y=2x'-3y'$

and solve it to find that $(x,y)=(x',y')$?

I recommend you also try to próve that the function is a surjection, ie. for any pair of numbers $(x,y)\in\mathbb{N}\times\mathbb{N}$ there exists a pair of numbers $(a,b)\in\mathbb{N}\times\mathbb{N}$ such that $f(a,b)=(x,y)$. That's a good exercise.

 

[scorpius1782]

Why don't you just form the pair of linear equations

$x+y=x'+y'$
$2x-3y=2x'-3y'$

and solve it to find that $(x,y)=(x',y')$?

Not sure what you mean. Can you point me towards an example with another set of equations? I always have a hard time understanding without some sort of an example. And to me, with things like this, it looks like setting up those two equations like that requires that $(x,y)=(x',y')$ since they've been defined that way.

And, is my proof correct, if inefficient? To make sure I understand it conceptually.

 

[gopher_p]

In order for $f(x,y)=g(w,z)$ then $x+y=w+z$ therefore x=w or x=z and y=w or y=z. So it is clear that by itself this part of the function is not one to one.

Take $x=y=1$ and $w=0$, $z=2$. Then $x+y=w+z=2$, but $x\neq w$ and $x\neq z$. So clearly that part of the function is decidedly not 1-1. In fact, it is $\omega$-1, where $\omega$ is the cardinality of the natural numbers. So there are a lot of counterexamples to your claim.

Also, what is $g$?

Now for $2x-3y$ we have $f(x,y)=g(w,z)$. Then $2x-3y=2w-3z$. However here we do not have the possibility for x to equal w or z and y cannot equal w or z. It must be one or the other as $2x-3y\neq2y-3x$ and $2w-3z\neq2z-3w$. Except if, and only if, $x=y=w=z=0$. But this fits in the definition of one to one, regardless.

Again, very much not 1-1. I'll let you find your own counterexamples.

Finally, from the above constraints $w=x$ and $y=z$. Therefore $x, y, w, z \in \mathbb{Z}, f(x,y)=f(w,z) \implies (x,y)=(w,z)$

OK. For just a minute, forget about your problem for a second. Seriously, try to put it out of your mind.

Ready? Ok. Answer the following completely unrelated*, pre-calc level** question;

What it the solution set in $\mathbb{R}^2$ to the system of equations
<br /> \left\{<br /> \begin{array}{l}<br /> x+y=a\\<br /> 2x-3y=b<br /> \end{array}<br /> \right.<br />
where $a,b\in\mathbb{R}$ are fixed?

Did you answer that question? Ok, now think about your problem again.

* Of course it's related.
**(1) While the problem might be stated using more "advanced" language and in slightly more generality than a standard pre-calc problem, it really is a pre-calc problem. (2) I say that for your benefit so that you (a) don't think that it's harder than it really is and (b) have a frame of reference for how to potentially approach it.

 

[scorpius1782]

Did you answer that question? Ok, now think about your problem again.

I think I have it solved unless my algebra is as terrible as my understanding of proofs. But, it isn't taking me anywhere in terms of understanding how to use it to prove 1 to 1. When I look at this I only see that x and y depend on a or b (or vice versa).

Note:
Telling me this is a pre-calc problem doesn't hurt my feelings. I'm bad at this, like really bad. I'm prepared to be talked to like I don't get it, that's why I'm here. Proofs, even simple ones, are hard for me to understand and ten times harder for me to do on my own. I've gotten all A's until, what I thought was my last math class, linear algebra where I got a B. I can do math... but I just don't get proofs at all.

 

[gopher_p]

I think I have it solved unless my algebra is as terrible as my understanding of proofs. But, it isn't taking me anywhere in terms of understanding how to use it to prove 1 to 1. When I look at this I only see that x and y depend on a or b (or vice versa).

Alright. So the fact that you got x and y to depend on a and b means that there is a unique solution to that particular system. So when a and b are real numbers, there is exactly one pair (x,y) of real numbers satisfying x+y=a and 2x-3y=b.

If we restrict a and b to being integers and (x,y) to being a pair of natural numbers, it's possible that there are no solutions. But could there ever be more than one solution to the system?

Now, given f(x,y)=(a,b)=f(w,z). Both (x,y) and (w,z) are solutions to the system of equations that we've been talking about, right? Now can you see how to use this idea to show that f is 1-1?

Note:
Telling me this is a pre-calc problem doesn't hurt my feelings. I'm bad at this, like really bad. I'm prepared to be talked to like I don't get it, that's why I'm here. Proofs, even simple ones, are hard for me to understand and ten times harder for me to do on my own. I've gotten all A's until, what I thought was my last math class, linear algebra where I got a B. I can do math... but I just don't get proofs at all.

Proofs are generally much easier to understand than they are to create, even for the "pros". I would think that it would be very hard to formulate your own proofs if you're having difficulty following the ones that have been provided to you. I would encourage you to work on understanding proofs that have been given to you; focus on understanding why each statement follows from previous statements/assumptions of the claim/definitions rather than trying to figure out how someone came up with the proof.

I find that a lot of times, especially in the "first class in proofs" type of problems, the inspiration for how to go about proving things comes when you write down explicitly what you're assuming, sometimes in multiple different ways. In this case, when you write down f(x,y)=f(w,z), nothing comes up. Then you write down x+y=w+z and 2x-3y=2w-3z, and that also isn't very helpful (unless you make some bad assumptions)*. But when you write down f(x,y)=(a,b)=f(w,z) and then rewrite that, x+y=a, 2x-3y=b and w+z=a, 2w-3z=b, then you maybe start to see that you have a system of linear equations. And you think "I know precalc, and I know linear algebra. I know some things about solutions to linear systems." And that gives you some inspiration towards how to deal with the proof.

Now, given that you know some linear algebra, can you see that the f that you have been given is linear? What is the kernel of f? What do you know about linear functions with trivial kernels?

*There is a way to use this, but it's not quite as intuitive (imo) as the approach that I am suggesting; recognize that x+y=w+z and 2x-3y=2w-3z is equivalent to (x-w)+(y-z)=0 and 2(x-w)-3(y-z)=0, and so (x-w,y-z) is a (the) solution to the system X+Y=0 and 2X-3Y=0. It's certainly faster and more elegant. But it's harder to come up with, I think.

 

[pasmith]

Homework Statement

I'm having a lot of problems with this class of thinking I understand something then getting a grade back that proves otherwise. I'd like someone to check my proof of this:

Claim: $f:\mathbb{N}^2 \rightarrow \mathbb{N}^2 by f(x,y) = (x+y, 2x-3y)$ is one to one.

The function f as defined is not \mathbb{N}^2 \to \mathbb{N}^2, since (1,1) \in \mathbb{N}^2 but f(1,1) = (2, -1) \notin \mathbb{N}^2.

Recall that \mathbb{N} is the positive integers; depending on who you ask it might also include zero (zero being the cardinality of the empty set) but it certainly doesn't include -1. Either you have copied the problem incorrectly or whoever wrote the problem has made an error.

Sensible codomains for f are \mathbb{Z}^2 or \mathbb{N} \times \mathbb{Z}.

 

[scorpius1782]

The function f as defined is not \mathbb{N}^2 \to \mathbb{N}^2, since (1,1) \in \mathbb{N}^2 but f(1,1) = (2, -1) \notin \mathbb{N}^2.

Recall that \mathbb{N} is the positive integers; depending on who you ask it might also include zero (zero being the cardinality of the empty set) but it certainly doesn't include -1. Either you have copied the problem incorrectly or whoever wrote the problem has made an error.

Sensible codomains for f are \mathbb{Z}^2 or \mathbb{N} \times \mathbb{Z}.

This was recently fixed. So natural numbers to integers now. I'll be working on this again tonight.