Chapter 3Elementary Discrete Math

Injectivity, Surjectivity, Bijectivity

Three flavors of function with a name

Concept

Three properties every function can have (or not):

- Injective (one-to-one): distinct inputs give distinct outputs.

∀x1,x2.f(x1)=f(x2)⇒x1=x2\forall x_1, x_2. f(x_1) = f(x_2) \Rightarrow x_1 = x_2

- Surjective (onto): every element of the codomain is hit.

∀y∈Y.∃x∈X.f(x)=y\forall y \in Y. \exists x \in X. f(x) = y

- Bijective: both injective AND surjective.
Equivalent to: ff has an inverse f−1f^{-1}.

Cardinality: if a bijection f:A→Bf: A \to B exists, AA and BB have the same
cardinality (#A=#B\#A = \#B).

Animation — injective surjective
Transcript — click a line to jump6 cues
  1. 0.0sFunctions: injective, surjective, bijective
  2. 1.5sDomain A on the left, codomain B on the right
  3. 4.5sArrows map a₁, a₂, a₃ to distinct b's — injective
  4. 7.5sNew arrows: a₁ and a₂ both map to b₁ — not injective
  5. 10.5sSurjective map: every b is hit, but two a's share one b
  6. 13.5sBijective: every a maps to a unique b, every b hit exactly once
Practice — score 100% to advance
Multiple choice
Q1
What does injective mean?
Q2
Is f(n)=2nf(n) = 2n on N\mathbb{N} surjective onto N\mathbb{N}?
Q3
Is f(n)=n+1f(n) = n + 1 on Z\mathbb{Z} bijective?
Q4
If f:A→Bf: A \to B is bijective, then #A=#B\#A = \#B?
Q5
What's the contrapositive of injectivity?
Q6
Composition of two injective functions is…
Loading…