Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question

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.

share|cite|improve this answer
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.

share|cite|improve this answer

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)$.

share|cite|improve this answer

Your Answer


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.