8
$\begingroup$

A function $f : \Bbb Z \times \Bbb Z \rightarrow \Bbb Z$ is defined as $f(u,v) = 3u + 6v.$ Is the function surjective? Prove it.

I had the following proof.

Proof
Pick $x = 2$, then $3u + 6v = 2 \Rightarrow 3(u + 2v) = 2$
Let $y = u + 2v$ $\exists y \in \Bbb Z \times \Bbb Z$.
Thus $3y = 2 \Rightarrow y = \frac{2}{3}$.
This is a contradiction because $\frac{2}{3} \not\in \Bbb Z \times \Bbb Z.$
The function is therefore not surjective.

I am a novice at this whole LaTex thing and relatively new to proofs and these surjective proofs are killing me I can't seem to get anything right. Any help is greatly appreciated.

$\endgroup$
9
  • 3
    $\begingroup$ I think your argument is good, but a little roundabout and not written correctly. You can just note that such an integer $u+2v$ cannot exist. No need to call it $y$. $\endgroup$ Commented May 1, 2024 at 1:22
  • 11
    $\begingroup$ "Let $y=u+2v$ $\exists y\in \mathbb{Z}\times\mathbb{Z}$" is nonsense. You can let $y=u+2v$, but then it is an integer, not an element of $\mathbb{Z}\times\mathbb{Z}$. And having the "$\exists y\in\mathbb{Z}\times\mathbb{Z}$" tacked on at the end gives a formula that is not a well-formed formula. "This is a contradiction because $\frac{2}{3}\notin\mathbb{Z}\times\mathbb{Z}$"... yeah, well, that contradiction is to your false assertion that the integer $y$ was in $\mathbb{Z}\times\mathbb{Z}$, so the only contradiction you found was one you introduced. I would have marked this wrong as well. $\endgroup$ Commented May 1, 2024 at 1:22
  • 9
    $\begingroup$ I get what you tried to do, but what you wrote doesn't work. You are trying to show that $2$ is not in the image. You do so by noting that $f(u,v)$ is a multiple of $3$, which means you would need some pair of integers $(u,v)$ such that $u+2v=\frac{2}{3}$. Which is impossible. But that is, unfortunately, not what you actually wrote. For that matter, it is much easier to note that $f(x,y)$ is always an integer multiple of $3$, so it cannot be equal to $2$, which is not a multiple of $3$. $\endgroup$ Commented May 1, 2024 at 1:24
  • $\begingroup$ Dwelling on 2 obscures the main point too, which is that $f(u,v)$ is always a multiple of 3, so all non-multiples of 3 (i.e. 1,2,4,5,7,8,10,11,...) are missing from the range of $f$. $\endgroup$ Commented May 1, 2024 at 1:51
  • 2
    $\begingroup$ I would say $3 \mid f(u,v)$ for all $u,v \in \mathbb{Z}$. Since $3\not\mid 2$, $f$ cannot be surjective. $\endgroup$ Commented May 1, 2024 at 1:54

4 Answers 4

Reset to default
14
$\begingroup$

You've got the right idea, but the second half is a bit jumbled, mostly because you introduced a lot of unnecessary variables. I'd phrase it this way:

Suppose that there are $u,v\in\mathbb{Z}$ such that $3u+6v=2$. Then $3(u+2v)=2$, so $u+2v=2/3$. This is a contradiction, since $2/3$ is not an integer and the sum of two integers is also an integer.

I'd say that captures the same idea of your proof, but using half the number of variables.

$\endgroup$
7
$\begingroup$

You have the right idea. But you did not write it properly.

Pick $x=2$, then $3u+6v=2$ implies $3(u+2v)=2$.

So far it is fine. But really you plan to show that $2$ is not in the image/range of the function so you should write in the beginning that "Suppose $f$ is surjective. Let $u$ and $v$ be such that $f(u,v)=2$. Then, ...".

Let $y=u+2v$ $\exists y\in\Bbb Z\times\Bbb Z$.

This does not make sense, since $y$ is supposed to be an integer. You should write: "Then, with $y=u+2v\in\Bbb Z$, we have $3y=2$."

So, $y=2/3\notin\Bbb Z$ a contradiction.

Yeah.

With that said, here is a rephrasing of your proof (sticking to your notation and writing as much):

Suppose $f$ is surjective. Then, let $(u,v)\in\Bbb Z\times\Bbb Z$ be such that $f(u,v)=2$. That means $3u+6v=2$, which implies $3(u+2v)=2$ or $u+2v=2/3$. But $u+2v\in\Bbb Z$ - a contradiction. Therefore, $f$ is not surjective.

Hope this helps. :)

$\endgroup$
1
$\begingroup$

You should do it without reference to $2/3$.

The idea is right: suppose $2=f(u,v)$, for some $u,v\in\mathbb{Z}$. Then $$ 2=3u+6v=3(u+2v) $$ but this implies that $3$ divides $2$. Contradiction.

Note that saying that $2/3\notin\mathbb{Z}$ is exactly the same as saying that $3$ doesn't divide $2$, so it's not necessary to go beyond integers.

$\endgroup$
1
$\begingroup$

The image of your map is the ideal $$I:=<3,6>\ \subset \ \mathbb{Z}.$$ Because $6 = 2 \cdot 3$ you have $I=<3>$, the set of integer multiples of $3$. Because $2$ is not an integer multiple of $3$ the map is not surjective.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.