# Proving Functions are Surjective

Prove the following are surjective, or disprove with a counter-example:

1. $f\colon \mathbb{Q} \to \mathbb{Q}$, $f(x) = 1 + 2x$.
2. $f\colon \mathbb{Z} \to \mathbb{N}\cup\{0\}$, $f(x) = |1 - x|$.
3. $f\colon \mathbb{Q} \to \mathbb{Q}$, $f(x) = 4 - 2x^3$.
4. $f\colon \mathbb{Z}^2 \to \mathbb{Z}$, $f(x, y) = x + y$.

Please show me the most effective method to lay out such proofs.

These come from a manual on Set Theory, which I am trying to reach to myself. Please be understanding!

-

I consider this to be homework, so I will just give some hints. Still, I don't have the permission yet to comment, so I write this as an answer. I will not be offended if anybody turns this into a comment or something.

On topic: Surjective means that every element in the codomain is "hit" by the function, i.e. given a function $f:X\rightarrow Y$ the image $\mathrm{im}(X)$ of f equals the codomain set $Y$.

To proof that a function is surjective, take an arbitrary element $y\in Y$ and show that there is an element $x\in X$ so that $f(x)=y$. I suggest that you consider the equation $f(x)=y$ with arbitrary $y\in Y$, solve for $x$ and check whether or not $x\in X$.

As an expample, take $f(x)=x^2$, $f:X\rightarrow Y$, $X=Y=\mathbb R$. Now consider $y\in Y$: It is $y=x^2 \Leftrightarrow \pm\sqrt{y}=x$. The right-hand-side is a valid expression and $x$ can be calculated from $y$ if and only if $y\geq 0$. So within the given sets, the function is not surjective.

-
Could you possibly demonstrate with an example? – Brian Nov 12 '12 at 11:05

1) $f\colon \mathbb{Q} \to \mathbb{Q}$, $f(x) = 1 + 2x$.

For $f$ to be surjective it must be the case that every $y \in \mathbb Q$ can be written as $y = f(x)$ for some $x$, but $x = \frac{y - 1}{2}$ does. So $y$ is surjective.

2) $f\colon \mathbb{Z} \to \mathbb{N}\cup\{0\}$, $f(x) = |1 - x|$.

let $y \in \mathbb{N}\cup\{0\}$ then $1-y \in \mathbb Z$ and $y = f(1-y)$ so $f$ is surjective.

3) $f\colon \mathbb{Q} \to \mathbb{Q}$, $f(x) = 4 - 2x^3$.

This is the most interesting one, because of the cube I don't expect it to be surjective. Note that $2-f(x)/2 = x^3$ so if $f(x)$ really is surjective then take any rational $q$ and $2-q/2$ is a cube! Obviously this is false so $f$ is proved not surjective. For a concrete example take any $q$ such that $2-q/2$ is not a cube say $q = 2$ then there's no $x$ such that $q=f(x)$.

4) $f\colon \mathbb{Z}^2 \to \mathbb{Z}$, $f(x, y) = x + y$.

This is easily surjective because $f(x,0)$ is the identity function, which is surjective.

-

1 Yes, solve $2x + 1 = y$ for x.

2 Yes. Compute $f(n+1)$ for any $n \in \mathbb N \cup \{0\}$.

3 Yes. Solve $y = 4 - 2x^3$ for x.

4 Yes. Compute $f(x, 0)$.

-