2
$\begingroup$

Proving the injectivity of a function starts with lines similar to the following:

Assume that $f(x_{1}) = f(x_{2})$. If $x_{1} = x_{2}$, then $f$ is an injection.

Checking for the surjectivity of a function requires solving for the inverse and so on. Is there a similar way to prove the surjectivity of a function using a process similar to the one above?

$\endgroup$
3
$\begingroup$

Define $f : X \to Y$. Assume $y \in Y$. If you can show there exists at least one $x \in X$ such that $f(x) = y$, then you can show that $f$ is surjective.

Alternatively, say you define a function $g : Y \to X$. If you can show that $(f \circ g)(y) = y$ for all $y \in Y$, then $g$ is a right inverse to $f$, and thus surjective.

Alternatively, let $f^{-1}(B)$ denote the preimage of $B$, i.e. it is not an inverse, but rather

$$f^{-1}(B) = \{ x \in X \mid f(x) \in B \}$$

Then if for all $B \subseteq Y$ we have $f(f^{-1}(B)) =B$, then $f$ is surjective. Similarly, for all $B,C$ such that $B\subsetneq C \subseteq Y$, $f$ is surjective if $f^{-1}(B) \subsetneq f^{-1}(C)$.

All four of these are equivalent to surjectivity for a function $f$. Though, in my opinion, the first two are the main ones of utility.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So you mean to say that $f^{-1}(x)$ can be defined as a function, but not exactly the inverse of $f$? $\endgroup$ – your friendly neighbor Oct 1 at 16:02
  • 1
    $\begingroup$ $f^{-1}(x)$ can mean the preimage of $x$ under $f$. It is not necessarily a function, however, but rather it is a set, as I have described. Essentially, $f^{-1}(x)$ is the set of all points in $X$ that map to $x$. (I agree, the notation is somewhat confusing, but it is the conventional way to notate it.) $\endgroup$ – Eevee Trainer Oct 1 at 16:03
  • 1
    $\begingroup$ @kevs924 the preimage $f^{-1}(x)$ is suggestive of an inverse but it is a set, not a function. For a simple example consider the function $f: \mathbb{R} \rightarrow \mathbb{R}$ given by $f(x)=x^2$. The preimage of $4$ is $f^{-1}(4)=\{2,-2\}$ and of $-1$ is $f^{-1}(-1)=\emptyset$. Technically this should be written $f^{-1}(\{4\})$ but it is a common abuse of notation to leave off the braces for singletons. $\endgroup$ – CyclotomicField Oct 1 at 16:09
  • $\begingroup$ Can I ask, how do you read it if it is not the inverse to avoid confusion? $\endgroup$ – your friendly neighbor Oct 2 at 6:34
  • $\begingroup$ Do you mean reading it aloud? If it were $f^{-1}(B)$, I would say "the preimage of $B$ (under $f$)." $\endgroup$ – Eevee Trainer Oct 2 at 6:53
4
$\begingroup$

A function $f: X \to Y$ is surjective if and only if

for each $y \in Y$ there is a $x \in X$, such that $f(x) = y$.

Let's consider an example. Let $f: \mathbb R \to \mathbb R$ be defined as $$f(x) = 2x + 1 \; .$$ We want to show that $f$ is surjective. So let $y \in \mathbb R$ be arbitrary. We need to find a $x \in \mathbb R$, such that $f(x) = y$. So the equation $$2x + 1 = y$$ must hold for this to be true. Solving this equation for $x$ gives $$ x = \frac{y-1}{2} \; . $$ Now we are done: For $y \in \mathbb R$ we choose $$ x = \frac{y-1}{2} \; , $$ then $$ f(x) = f\left(\frac{y-1}{2}\right) = 2 \cdot \frac{y-1}{2} + 1 = y - 1 + 1 = y \; . $$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Another way for proving surjectivity or onto is by $\forall b \in B \space \exists a \in A [f(a) = b]$

So an example would be $f(x) = 2x+1$ where $f: \mathbb R \rightarrow \mathbb R$. $$\text{Let $b$ be an arbitrary number in the codomain.} \\ \text{Let $a = \frac{b-1}{2}$} \\ f(a) = 2a +1 \\ f(a) = 2 (\frac{b-1}{2}) +1 \\ f(a) = b-1+1 \\ f(a) = b \\ \text{Since $b$ is arbitrary we can say this function is surjective.}$$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Remember that a function always needs an explicit domain and codomain. Your proof fails for $\text{codomain f}=\mathbb{R}$ and $\text{domain f}=\mathbb{R}\setminus \{0\}$ $\endgroup$ – André Armatowski Oct 1 at 16:08
  • $\begingroup$ Added! Thank you! New to proof writing. $\endgroup$ – E__ Oct 1 at 16:46

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.