0
$\begingroup$

I am a little confused by the definitions of these different types of functions:

I think the definition of a surjection is pretty clear in that each element of x is mapped to some value of y.

But I'm a little confused about the difference between an injection and a bijection. An injection maps an element of x to at most one y and a bijection maps an element of x to exactly one y. Does this mean that an injection can have an element of x that does not map to any element of y whereas a bijection always has exactly one mapping?

And then, does this mean that all bijections are injections and all injections and bijections are surjections? Or can a function only be one of the three?

Any help?

$\endgroup$
  • 1
    $\begingroup$ For any function, the element being mapped is an element of the domain. The element it maps to is an element of the range (hence an element of the codomain). So your definition of surjection is not correct. Any function maps an element of the domain to some element of the range. Also, you're muddling sets and elements. You're using the letter $y$ for a set, and the letter $x$ for a value. Very unclear. $\endgroup$ – quasi Jan 11 '18 at 1:48
  • 1
    $\begingroup$ isn't this wikipedia article enough clear ? $\endgroup$ – G Cab Jan 11 '18 at 1:49
  • $\begingroup$ Yes an injection can have an element y that has no x that is mapped to it. A bijection is surjective and injective. So every element of y has an x that is mapped to it, and has only one such x. $\endgroup$ – XRBtoTheMOON Jan 11 '18 at 1:50
2
$\begingroup$

Your usage of of "maps to" is backwards. We're dealing with functions that map from X to Y.

A surjection is a function where each element of Y is mapped to from some (i.e., at least one) element of X.

An injection is a function where each element of Y is mapped to from at most one element of X.

A bijection is a function where each element of Y is mapped to from exactly one element of X. It should be clear that "bijection" is just another word for an injection which is also a surjection.

Thus, a function may be either an injection, a surjection, both (in which case it's a bijection too), or neither.

$\endgroup$
2
$\begingroup$

does this mean that all bijections are injections

All bijections are both injections and surjections.

and all injections and bijections are surjections?

Injections are not necessarily surjections. Bijections are always surjections.

Or can a function only be one of the three?

Let $\mathbb{N}_{0} = \mathbb{N} \cup \{0\}\,$, and take for example the absolute value function $f(x)=|x|\,$:

  • if defined as $f : \mathbb{N}_0 \to \mathbb{N}_0\,$ it is a bijection (and therefore both an injection and a surjection), since it it is indeed the identity function on $\mathbb{N}_0$

  • if defined as $f : \mathbb{N}_0 \to \mathbb{Z}\,$ it is an injection, but not a surjection since for example there is no $x \in \mathbb{N}_0$ such that $f(x)=-1 \in \mathbb{Z}$

  • if defined as $f : \mathbb{Z} \to \mathbb{N}_0\,$ it is a surjection, but not an injection since for example $-1 \ne 1$ but $f(-1)=f(1)=1$

$\endgroup$
1
$\begingroup$

Addition to the answers above, there is one more way to distinguish them when the sets are countable (I specify this according to the tag discrete):

Let $A$,$B$ are countable sets and $f: A \to B$ is a function. Then,

  • If $f$ is injection, we must have $|A| \le |B|$ (necessary condition).

  • If $f$ is surjection, we must have $|A| \ge |B|$ (necessary condition).

  • If $f$ is bijection, we must have $|A| = |B|$ (necessary condition).

Sufficient conditions are derived from the definitions:

  • $f$ is an injection if and only if for every $b \in B$, there is at most one corresponding element $a \in A$ with $f(a) = b$ (means that there may be elements in $B$ that are not matched with an element in $A$).

  • $f$ is a surjection if and only if for every $b \in B$, there is at least one corresponding element $a \in A$ with $f(a) = b$ (means that there may be elements in $B$ that are matched with more than one element in $A$).

  • $f$ is a bijection if and only if $f$ is an injection and a surjection, that is, for every $b \in B$, there is exactly one corresponding element $a \in A$ with $f(a) = b$ (means that for every $a \in A$, value of $f(a)$ is unique).

$\endgroup$

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.