Relations and functions · Definition

Bijective function

set theoryrelations and functions

Before you start you need to know

A bijection pairs the elements of two sets with nothing left over and nothing missing, which is why it is the tool for saying that two sets have the same size.

Definition

Function \(f\colon A\to B\) that is both injective and surjective, so each element of \(B\) corresponds to exactly one element of \(A\).

\[\forall b\in B\;\exists!\,a\in A\,(f(a)=b)\]

Let \(f\colon A\to B\). It is bijective if it is injective (\(f(a)=f(a')\) implies \(a=a'\)) and surjective (for every \(b\in B\) there is \(a\in A\) with \(f(a)=b\)). Equivalently, \(f\) is bijective if and only if there is \(g\colon B\to A\) with \(g\circ f=\mathrm{id}_A\) and \(f\circ g=\mathrm{id}_B\); this \(g\) is unique and is called the inverse of \(f\).

Worked example: \(f\colon\mathbb{R}\to\mathbb{R}\), \(f(x)=2x+1\), is bijective, because for every \(y\in\mathbb{R}\) the equation \(2x+1=y\) has a unique solution, \(x=(y-1)/2\). By contrast \(g\colon\mathbb{R}\to\mathbb{R}\), \(g(x)=x^2\), is not: \(g(1)=g(-1)=1\) breaks injectivity, and \(-1\) has no real preimage, which breaks surjectivity.

Typical mistake: calling a function bijective just because \(A\) and \(B\) have the same number of elements. That equality is necessary for a bijection between finite sets to exist, but it is not sufficient: the specific function must satisfy both properties at once.

Think about it

Why is it not enough for \(A\) and \(B\) to have the same number of elements for \(f\) to be bijective?

Because the specific function must be both injective and surjective; equal size is only necessary.

Exercises 10

  1. Which two properties must \(f\colon A\to B\) satisfy to be bijective?
  2. If \(f\colon A\to B\) is bijective, how many elements of \(A\) have image equal to a given \(b\in B\)?
  3. What does it mean for \(f\colon A\to B\) to be injective?
  4. Which is the definition of surjectivity for \(f\colon A\to B\)?
  5. Let \(f\colon\{1,2,3\}\to\{a,b,c\}\) be injective. What can be concluded?
  6. Is \(f\colon\mathbb{R}\to\mathbb{R}\), \(f(x)=x^3-x\) bijective?
  7. Which of these functions from \(\mathbb{Z}\) to \(\mathbb{Z}\) is bijective?
  8. If \(f\colon A\to B\) is bijective and \(|A|=5\), what is \(|B|\)?
  9. Let \(f\colon\mathbb{R}\to\mathbb{R}\), \(f(x)=x^3+x\). Which statement is correct?
  10. How many bijections are there from a set \(A\) with \(n\) elements to itself?

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.