Day 41 — Injections, surjections, bijections

Day 41 — Injections, surjections, bijections

Stage IV · concept day
Goal: Define injective, surjective, and bijective functions; link injectivity to pigeonhole; compare finite cardinalities; count injections \(P(n,k)\); characterize invertible functions as bijections.

Why this matters

Encoding without collisions is injectivity; covering all codes is surjectivity; lossless reversible encodings are bijections. Hashing, serialization, primary keys, and array indexing all live in this vocabulary. Counting injections is the “ordered selection without repetition” formula used throughout combinatorics.

Theory

Functions (recall)

A function \(f: A \to B\) assigns to each \(a\in A\) a unique \(f(a)\in B\).
\(A\) is the domain, \(B\) the codomain.
Image \(f(A)=\{f(a):a\in A\}\subseteq B\).
Equality of functions: same domain/codomain and \(\forall a\, f(a)=g(a)\).

Injective (one-to-one)

\(f\) is injective when
\[\forall a_1,a_2\in A,\; f(a_1)=f(a_2) \Rightarrow a_1=a_2,\]
equivalently \(a_1\neq a_2 \Rightarrow f(a_1)\neq f(a_2)\).

Surjective (onto)

\(f\) is surjective when
\[\forall b\in B\, \exists a\in A\, f(a)=b,\]
i.e. \(f(A)=B\).

Bijective

Both injective and surjective. Sets up a one-to-one correspondence between \(A\) and \(B\).

Pigeonhole link

If \(A,B\) finite and \(|A| > |B|\), then no injection \(A\to B\) (pigeons to holes).
If \(|A| < |B|\), no surjection \(A\to B\).
If \(|A|=|B|\) finite, injection \(\Leftrightarrow\) surjection \(\Leftrightarrow\) bijection.

Finite cardinality comparisons

• \(|A| \le |B|\) if there exists an injection \(A\to B\).
  
• \(|A| = |B|\) if there exists a bijection \(A\to B\).
  
• \(|A| \ge |B|\) if there exists a surjection \(A\to B\) (for nonempty, with choice subtleties—finite case fine).

Counting injections

Number of injections from a \(k\)-element set to an \(n\)-element set (\(n\ge k\)):
\[P(n,k) = n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}.\]
Reason: ordered choices without repetition.
If \(k>n\), count is \(0\).

Number of bijections \(A\to A\) for \(|A|=n\): \(n!\) (permutations).

Number of all functions \(A\to B\): \(|B|^{|A|}\).

Number of surjections: inclusion-exclusion (Stage V); \(n!\, S(k,n)\) if \(|A|=k\), \(|B|=n\).

Inverse functions

\(f: A\to B\) has an inverse \(f^{-1}: B\to A\) with \(f^{-1}\circ f = \mathrm{id}_A\) and \(f\circ f^{-1}=\mathrm{id}_B\) iff \(f\) is bijective.
Then \(f^{-1}(b)\) is the unique \(a\) with \(f(a)=b\).

Left/right inverses alone: Day 42.

Proving injectivity/surjectivity

• Injective: assume \(f(a_1)=f(a_2)\); show \(a_1=a_2\) (algebra).
  
• Not injective: find collision \(a_1\neq a_2\), same image.
  
• Surjective: for arbitrary \(b\), construct \(a\) with \(f(a)=b\).
  
• Not surjective: find \(b\) outside the image.

Examples of maps

• \(f:\mathbb{Z}\to\mathbb{Z}\), \(f(n)=2n\): injective not surjective.
  
• \(f:\mathbb{Z}\to\mathbb{Z}\), \(f(n)=\lfloor n/2\rfloor\): surjective not injective.
  
• \(f:\mathbb{R}\to\mathbb{R}\), \(f(x)=x^3\): bijective.
  
• \(f:\mathbb{R}\to\mathbb{R}\), \(f(x)=x^2\): neither.
  
• Inclusion \(A\subseteq B\), \(\iota: A\to B\), \(\iota(a)=a\): injective; surjective iff \(A=B\).

Worked examples

Example 1 — Prove injective

\(f:\mathbb{Z}\to\mathbb{Z}\), \(f(n)=2n\). If \(2a=2b\) then \(a=b\). Not onto: \(1\) not even.

Example 2 — Prove surjective

\(g:\mathbb{Z}\to\mathbb{N}_0\), \(g(n)=|n|\) not injective; not if codomain \(\mathbb{Z}\).
\(h:\mathbb{R}\to\mathbb{R}\), \(h(x)=2x+1\): onto, inverse \((y-1)/2\).

Example 3 — Finite equality

\(|A|=|B|=3\): any injection is bijection—prove by counting image size.

Example 4 — Pigeon

Map \(6\) people to \(5\) birth months: not injective—two share a month.

Example 5 — Count injections

Injections \(\{1,2,3\}\to\{1,\ldots,10\}\): \(P(10,3)=10\cdot9\cdot8=720\).

Example 6 — Permutations

Bijections on \(\{1,2,3\}\): \(6=3!\).

Example 7 — Not injective

\(f(n)=n \bmod 5\) on \(\mathbb{Z}\) to \(\{0,1,2,3,4\}\): surjective, not injective.

Example 8 — Characteristic

\(\chi_A: U\to\{0,1\}\) rarely injective.

Example 9 — Pairing

\(f:\{0,1\}^n \to \mathcal{P}([n])\) bitstring to subset: bijective (Day 36).

Example 10 — Inverse of linear

\(f(x)=ax+b\) on \(\mathbb{R}\), \(a\neq 0\): inverse \((y-b)/a\).

Example 11 — Projection

\(\pi_1: A\times B\to A\): surjective if \(B\neq\emptyset\); injective iff \(|B|\le 1\).

Example 12 — Hash (ideal)

Ideal perfect hash from keys \(K\) to \(\{0,\ldots,|K|-1\}\) is bijective.

Example 13 — Image size

For finite \(A\), \(f:A\to B\) injective \(\Rightarrow |f(A)|=|A|\).

Example 14 — Construct non-surjection

\(f:\{1,2\}\to\{1,2,3\}\), \(f(1)=1,f(2)=2\): injective not surjective.

Exercises

1. Define injective/surjective/bijective formally.
   
2. Prove \(f(n)=2n\) on \(\mathbb{Z}\) injective not surjective.
   
3. Prove \(f(x)=x^3\) on \(\mathbb{R}\) bijective.
   
4. Show \(f(x)=x^2\) on \(\mathbb{R}\) not injective and not surjective.
   
5. Restrict \(x^2\) to \([0,\infty)\to[0,\infty)\)—prove bijective.
   
6. Count injections from a \(4\)-set to a \(7\)-set.
   
7. Count bijections from a \(5\)-set to itself.
   
8. Count all functions from a \(3\)-set to a \(2\)-set.
   
9. Prove: if \(f:A\to B\) and \(g:B\to C\) injective then \(g\circ f\) injective.
   
10. Prove: if \(g\circ f\) injective then \(f\) injective (not necessarily \(g\)).
    
11. Prove: if \(g\circ f\) surjective then \(g\) surjective (not necessarily \(f\)).
    
12. Finite \(|A|=|B|\): injection implies bijection (proof).
    
13. Give surjection \(\mathbb{N}\to\mathbb{Z}\) (construct).
    
14. Is there injection \(\mathbb{R}\to\mathbb{N}\)? (No—preview uncountable.)
    
15. Primary keys: which property of id map from rows to key space?
    
16. Prove number of injections formula \(P(n,k)\).
    
17. Find inverse of \(f:\{a,b,c\}\to\{1,2,3\}\) given as a table you invent that is bijective.
    
18. Show inclusion \(\{1,2\}\hookrightarrow\{1,2,3\}\) not surjective.
    
19. Can a function be inverse to two different functions? Uniqueness Day 42.
    
20. Pigeon: prove if \(f:A\to B\) and \(|A|>|B|\) finite then not injective.
    
21. For \(f:\mathbb{Z}\to\mathbb{Z}\), \(f(n)=n+1\): bijective? Inverse?
    
22. Surjective but not injective example on finite sets of different sizes? Impossible if equal size… use different sizes.
    
23. How many injections \(\{1,2\}\to\{1,2,3\}\) list them.
    
24. Prove \(f(A\times B)\to\) … skip—prove \(|\mathrm{Im}\, f| \le |A|\) always.
    
25. CS: why is a lossless compressor that always shortens every file impossible for all files? (Pigeon / injection into shorter bitstrings.)

CS connection

• Databases: primary key injectivity of row→key.
  
• Serialization: bijection with on-wire format when fully reversible.
  
• Hashing: not injective ⇒ collisions (Day 45).
  
• Arrays: index map \(\{0,\ldots,n-1\}\to\) slots bijective.
  
• Encodings UTF-8 as injection from code points to byte sequences (with structure).
  
• Permutation of encrypted blocks = bijections on message space (idealized).

Common pitfalls

Pitfall	What to do instead
Codomain vs image	Surjective means image = codomain
“One-to-one” meaning bijection in casual speech	Say bijective if both
Inverse of non-bijective	Does not exist as full inverse
Forgetting finite hypothesis for inj⇔surj	Need \(|A|=|B|\) finite
Counting functions as injections	\(|B|^{|A|}\) vs \(P\)
Proving surjective by example	Need arbitrary \(b\)

Checkpoint

• Define inj/surj/bij
  
• Prove one of each (yes and no)
  
• State finite size comparison rules
  
• Compute \(P(n,k)\) and \(n!\)
  
• Inverse exists iff bijective
  
• Pigeonhole as no-injection
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — counting table

For finite \(|A|=k\), \(|B|=n\):

Kind	Count
All functions	\(n^k\)
Injections	\(P(n,k)=n!/(n-k)!\) if \(n\ge k\) else \(0\)
Surjections	\(n!\,S(k,n)\) (Stirling 2nd kind)
Bijections	\(n!\) if \(k=n\) else \(0\)

Image cardinality

Always \(|\mathrm{im}\, f| \le \min(|A|,|B|)\).
\(f\) injective \(\Rightarrow |\mathrm{im}\, f|=|A|\).
\(f\) surjective \(\Rightarrow |\mathrm{im}\, f|=|B|\).

Cantor–Bernstein (awareness)

If injections \(A\to B\) and \(B\to A\) exist, then a bijection \(A\leftrightarrow B\) exists. Powerful for infinite cardinals; proof is a bit tricky—awareness only.

Characteristic functions

\(\{0,1\}^A \cong \mathcal{P}(A)\) via \(f \leftrightarrow f^{-1}(\{1\})\). Explains \(|\mathcal{P}(A)|=2^{|A|}\) for finite \(A\).

More worked examples

Example 15 — \(f(n)=n \bmod 4\)
\(\mathbb{Z}\to\{0,1,2,3\}\): surjective not injective.

Example 16 — Pairing
\((x,y)\mapsto 2^x(2y+1)-1\) injection \(\mathbb{N}\times\mathbb{N}\to\mathbb{N}\) (outline).

Example 17 — Inclusion
\(\iota:\mathbb{N}\to\mathbb{Z}\) injective not surjective.

Example 18 — Finite pigeon
No injection \(\{1,\ldots,5\}\to\{1,2,3\}\).

Additional exercises

26. Prove \(f(x)=e^x:\mathbb{R}\to(0,\infty)\) bijective.
    
27. Count surjections \(\{1,2,3\}\to\{a,b\}\) by enumeration.
    
28. Prove if \(f:A\to B\) bijective then \(|A|=|B|\) for finite sets.
    
29. Show \(n\mapsto n^2\) on \(\mathbb{N}\) injective not surjective.
    
30. CS: why must a perfect hash of \(m\) keys use \(\ge m\) slots?

Extended practice workshop

Classify each \(f\) (inj / surj / bij / neither)

1. \(n\mapsto 2n\) on \(\mathbb{Z}\)
   
2. \(n\mapsto n+1\) on \(\mathbb{Z}\)
   
3. \(n\mapsto |n|\) on \(\mathbb{Z}\to\mathbb{N}_0\)
   
4. \(x\mapsto x^2\) on \(\mathbb{R}\)
   
5. \(x\mapsto x^3\) on \(\mathbb{R}\)
   
6. \(x\mapsto e^x\) on \(\mathbb{R}\to(0,\infty)\)
   
7. \(\pi_1:A\times B\to A\) with \(B\) nonempty
   
8. inclusion \(\{1,2\}\hookrightarrow\{1,2,3\}\)

Counting

9. \(P(10,4)\)
   
10. \(7!\)
    
11. \(3^5\) vs \(P(3,5)\)
    
12. List all injections \(\{1,2\}\to\{a,b,c\}\)
    
13. Number of bijections on a \(4\)-set

Proofs

14. If \(g\circ f\) injective then \(f\) injective.
    
15. If \(g\circ f\) surjective then \(g\) surjective.
    
16. Finite equal size: inj ⇒ bij.
    
17. Inverse exists ⇒ bijective (both directions outline).
    
18. PHP: \(|A|>|B|\) ⇒ no injection \(A\to B\).

CS

19. Primary keys as injective maps.
    
20. Perfect hash as bijection to slots.
    
21. Why universal lossless shortening is impossible.
    
22. Serialization round-trip as inverse pair (preview Day 42).

Decision tree

Same image ⇒ same preimage? → injective
Every codomain hit? → surjective
Both? → bijective → inverse exists

Synthesis

Injective / surjective / bijective are the quality grades of a function \(f:A\to B\). Injection: no collisions (left-cancellable; invertible on its image). Surjection: full coverage of the codomain. Bijection: perfect matching—\(|A|=|B|\) when finite, and a two-sided inverse exists. Pigeonhole is the obstruction: \(|A|>|B|\) forbids injections \(A\to B\).

Definition card (memorize both forms)

Property	\(\forall\)-form	Useful contrapositive / rephrase
Injective	\(f(a)=f(a')\Rightarrow a=a'\)	\(a\neq a'\Rightarrow f(a)\neq f(a')\)
Surjective	\(\forall b\exists a\, f(a)=b\)	Every fiber nonempty
Bijective	inj + surj	Inverse function exists

More worked examples

Example — \(n\mapsto 2n\) on \(\mathbb{Z}\).
Injective: \(2a=2a'\Rightarrow a=a'\). Not surjective: odd numbers missed. On \(\mathbb{R}\), \(x\mapsto 2x\) is bijective.

Example — \(n\mapsto n+1\) on \(\mathbb{Z}\).
Bijective; inverse \(n\mapsto n-1\). On \(\mathbb{N}=\{0,1,\ldots\}\), injective not surjective (\(0\) not hit).

Example — Projection \(\pi_1:A\times B\to A\).
Surjective if \(B\neq\emptyset\) (fix \(b_0\)). Not injective if \(|B|>1\).

Example — Counting injections.
Injections \(\{1,\ldots,k\}\to\{1,\ldots,n\}\): \(P(n,k)=n(n-1)\cdots(n-k+1)\) for \(k\le n\), else \(0\). Bijections on an \(n\)-set: \(n!\).

Example — Finite equal size.
If \(|A|=|B|<\infty\), then injective \(\Leftrightarrow\) surjective \(\Leftrightarrow\) bijective. Proof uses counting of image size. Fails for infinite sets (\(n\mapsto 2n\) on \(\mathbb{N}\)).

Extra exercises (synthesis)

31. Classify \(x\mapsto x^2\) on \(\mathbb{R}\), on \([0,\infty)\), on \(\mathbb{Z}\).
    
32. Prove: if \(g\circ f\) injective then \(f\) injective.
    
33. Prove: if \(g\circ f\) surjective then \(g\) surjective.
    
34. Give \(f,g\) with \(g\circ f\) injective but \(g\) not injective.
    
35. Count surjections \(\{1,2,3\}\to\{a,b\}\) by inclusion or enumeration.
    
36. CS: why a lossless compressor mapping all \(n\)-bit strings to \((n-1)\)-bit strings is impossible (injection into smaller set).

Size comparison toolkit (finite)

Observation	Conclusion
Injection \(A\to B\)	\(|A|\le|B|\)
Surjection \(A\to B\)	\(|A|\ge|B|\)
Bijection	\(|A|=|B|\)
\(|A|>|B|\)	no injection \(A\to B\) (PHP)

Tomorrow composes these maps and studies inverses formally—left vs right vs two-sided.

Tomorrow

Day 42 — Composition & inverse. \(g\circ f\); associativity; unique inverse; left/right inverses; function pipelines in CS.