Relations and functions · Definition

Injective function

set theoryrelations and functions

Before you start you need to know

An injective function ensures that each output value identifies a single input value.

Definition

Function \(f\colon A\to B\) in which distinct elements of \(A\) have distinct images in \(B\).

\[\forall a_1,a_2\in A\,\bigl(f(a_1)=f(a_2)\Rightarrow a_1=a_2\bigr)\]

Let \(f\colon A\to B\). It is injective if, for any two elements \(a_1,a_2\in A\), \(f(a_1)=f(a_2)\) implies \(a_1=a_2\). Equivalently, \(a_1\ne a_2\) implies \(f(a_1)\ne f(a_2)\). Both formulations are the same condition, and to prove it it is usually enough to start from equal images and solve.

Worked example: \(f\colon\mathbb{R}\to\mathbb{R}\), \(f(x)=2x+1\), is injective. If \(2a+1=2b+1\), subtracting \(1\) and dividing by \(2\) gives \(a=b\). By contrast \(g(x)=x^2\) is not, since \(g(2)=g(-2)=4\) with \(2\ne -2\).

Typical mistake: thinking that injective means every element of \(B\) is reached. That is surjectivity. Injectivity only controls that the values do not repeat, and says nothing about \(B\). So if \(A\) and \(B\) are finite and \(A\) has more elements than \(B\), there can be no injective function.

Think about it

Why can there be no injective function from \(\{1,2,3\}\) to \(\{a,b\}\)?

There are three inputs and only two outputs, so two inputs share an image.

Exercises 10

  1. What does it mean for \(f\colon A\to B\) to be injective?
  2. Which of these functions from \(\mathbb{R}\) to \(\mathbb{R}\) is injective?
  3. What is the logical form of the definition of an injective function?
  4. If \(f\colon A\to B\) is not injective, what holds?
  5. Can there be an injective function \(f\colon\{1,2,3\}\to\{a,b\}\)?
  6. If \(f\) is injective and \(a_1\ne a_2\), what happens to \(f(a_1)\) and \(f(a_2)\)?
  7. Let \(f\colon\mathbb{Z}\to\mathbb{Z}\), \(f(n)=2n\). Is \(f\) injective?
  8. If \(f\colon A\to B\) and \(g\colon B\to C\) are injective, is \(g\circ f\)?
  9. Is every injective function also surjective?
  10. How many injective functions are there from \(\{1,2\}\) to \(\{a,b,c\}\)?

References

  • Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
  • Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.