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

  • $\begingroup$ Could you possibly demonstrate with an example? $\endgroup$ – Brian Nov 12 '12 at 11:05
  • $\begingroup$ Yes but one example is not enough to prove all y, and sometimes you can't figure out the image of f(x) $\endgroup$ – Goldname Jan 15 '18 at 18:44

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 No. Solve $3 = 4 - 2x^3$ for $x$ and you get $x=\dfrac{1}{\sqrt[3]{2}} \not \in \mathbb Q$.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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