Day 15 — Bijections, Composition, Countability & Gate IV

Day 15 — Bijections, Composition, Countability & Gate IV

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.

---

Day 42 — Composition & inverse

Stage IV · concept day
Goal: Master function composition \((g\circ f)\); prove associativity; show inverses are unique; use left and right inverses; connect to pipelines and modular software architecture.

Why this matters

Programs are pipelines of functions: parse ∘ validate ∘ handle. Associativity lets you regroup stages; invertibility means undo/rollback; left/right inverses capture “section/retraction” patterns (encode/decode pairs that only work one way). Category-flavored thinking starts here without category theory.

Theory

Composition

For \(f: A\to B\) and \(g: B\to C\), the composition \(g\circ f: A\to C\) is
\[(g\circ f)(a) = g\bigl(f(a)\bigr).\]
Apply \(f\) first, then \(g\). (Read \(\circ\) as “after.”)

Domain/codomain must match: codomain of \(f\) = domain of \(g\) (or \(\subseteq\) with care).

Identity

\(\mathrm{id}_A: A\to A\), \(\mathrm{id}_A(a)=a\).
\(f\circ \mathrm{id}_A = f = \mathrm{id}_B \circ f\) for \(f:A\to B\).

Associativity

\[h\circ (g\circ f) = (h\circ g)\circ f\]
whenever typed. Proof: both send \(a\) to \(h(g(f(a)))\). \(\square\)
So \(h\circ g\circ f\) is unambiguous.

Not commutative

\(g\circ f \neq f\circ g\) in general (often not even both defined).

Inverse (two-sided)

\(f: A\to B\) is invertible if there exists \(f^{-1}: B\to A\) with
\[f^{-1}\circ f = \mathrm{id}_A, \qquad f\circ f^{-1} = \mathrm{id}_B.\]
Then \(f\) is bijective and \(f^{-1}\) is unique (below).

Uniqueness of inverse

If \(g\) and \(h\) both inverses of \(f\), then
\[g = g\circ\mathrm{id}_B = g\circ(f\circ h) = (g\circ f)\circ h = \mathrm{id}_A\circ h = h.\]

Left and right inverses

• Left inverse of \(f: A\to B\): \(\ell: B\to A\) with \(\ell\circ f = \mathrm{id}_A\).
  Exists (for nonempty issues aside) iff \(f\) injective; then \(f\) is a split mono.
  
• Right inverse of \(f\): \(r: B\to A\) with \(f\circ r = \mathrm{id}_B\).
  Exists iff \(f\) surjective (using choice in general); split epi.

If both left and right inverses exist, they coincide and are the two-sided inverse.

Cancellation

If \(f\) injective and \(f\circ g = f\circ h\) then \(g=h\) (left cancel).
If \(f\) surjective and \(g\circ f = h\circ f\) then \(g=h\) (right cancel).

Composition preserves properties

If	Then
\(f,g\) injective	\(g\circ f\) injective
\(f,g\) surjective	\(g\circ f\) surjective
\(f,g\) bijective	\(g\circ f\) bijective, \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\)

Monoid of self-maps

\(\mathrm{Map}(A,A)\) under \(\circ\) is a monoid with unit \(\mathrm{id}_A\). Invertible elements = bijections = symmetric group if finite.

Worked examples

Example 1 — Compute

\(f(x)=x+1\), \(g(x)=2x\) on \(\mathbb{R}\): \((g\circ f)(x)=2(x+1)\), \((f\circ g)(x)=2x+1\).

Example 2 — Associativity numeric

\(f(x)=x+1\), \(g(x)=x^2\), \(h(x)=3x\): both associations give \(3(x+1)^2\).

Example 3 — Inverse linear

\(f(x)=2x+3\), \(f^{-1}(y)=(y-3)/2\). Check both compositions identity.

Example 4 — Inverse order

\((g\circ f)^{-1} = f^{-1}\circ g^{-1}\): undo last first (stack discipline).

Example 5 — Left inverse of injection

\(f:\{1,2\}\to\{a,b,c\}\), \(f(1)=a,f(2)=b\). Left inverse \(\ell(a)=1,\ell(b)=2,\ell(c)=\) anything (say \(1\)).
\(\ell\circ f=\mathrm{id}\) but \(f\circ\ell\neq\mathrm{id}\) (\(c\) issue).

Example 6 — Right inverse of surjection

\(f:\{1,2,3\}\to\{a,b\}\), \(f(1)=f(2)=a\), \(f(3)=b\). Right inverse \(r(a)=1\), \(r(b)=3\).

Example 7 — No left inverse

Non-injective maps cannot have left inverse: \(\ell(f(a_1))=\ell(f(a_2))\) would force \(a_1=a_2\).

Example 8 — Pipeline

\(\mathrm{handle}\circ\mathrm{validate}\circ\mathrm{parse}\): associativity allows \(\mathrm{handle}\circ(\mathrm{validate}\circ\mathrm{parse})\) packaging.

Example 9 — Uniqueness

Two candidate inverses for \(n\mapsto n+1\) on \(\mathbb{Z}\): only \(n\mapsto n-1\).

Example 10 — Permutation composition

Cycles: compose right-to-left as functions.

Example 11 — Identity

Only one identity map on \(A\).

Example 12 — Encode/decode

Base64: decode \(\circ\) encode = id on bytes; encode \(\circ\) decode = id on valid strings—not on all strings (partial inverse).

Example 13 — Cancellation failure

\(f\) constant: \(f\circ g = f\circ h\) always if same codomain patterns—cannot cancel.

Example 14 — Bijective composition inverse formula

Verify \((g\circ f)\circ(f^{-1}\circ g^{-1})=\mathrm{id}\).

Exercises

1. Compute \(g\circ f\) and \(f\circ g\) for \(f(x)=x^2\), \(g(x)=x+2\) on \(\mathbb{R}\).
   
2. Prove associativity in full generality.
   
3. Find inverse of \(f:\mathbb{R}\to\mathbb{R}\), \(f(x)=5-3x\).
   
4. Prove uniqueness of two-sided inverse.
   
5. Prove \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\) when both invertible.
   
6. Prove: \(f\) has a left inverse ⇒ \(f\) injective.
   
7. Prove: \(f\) has a right inverse ⇒ \(f\) surjective.
   
8. Give left inverse for \(n\mapsto 2n\) as \(\mathbb{Z}\to\mathbb{Z}\)? Impossible— not onto wait, it is injective: left inverse from \(\mathbb{Z}\) to \(\mathbb{Z}\)? Left inverse \(\ell:\mathbb{Z}\to\mathbb{Z}\) with \(\ell(2n)=n\)—must define \(\ell\) on odds arbitrarily, e.g. \(\ell(2n)=n\), \(\ell(2n+1)=0\). Check \(\ell(f(n))=\ell(2n)=n\). Yes!
   
9. Show \(n\mapsto 2n\) has no right inverse \(\mathbb{Z}\to\mathbb{Z}\).
   
10. Prove if \(f,g\) bijective then \(g\circ f\) bijective.
    
11. Pipeline: three functions on finite sets—count \(|\mathrm{im}(h\circ g\circ f)|\) bounds.
    
12. Is composition commutative on \(\mathrm{Map}(\{1,2\},\{1,2\})\)? Counterexample.
    
13. Prove left cancellation for injective \(f\).
    
14. Show that if \(f\) invertible, left and right inverses equal \(f^{-1}\).
    
15. CS: middleware stack as composition—what is identity middleware?
    
16. For \(f:A\to B\) bijective, prove \(f^{-1}\) bijective.
    
17. Give \(f\) with two different left inverses (non-surjective injection into larger set).
    
18. Monoid: list all elements of \(\mathrm{Map}(\{1\},\{1\})\).
    
19. Prove \(\mathrm{id}_A\) is the only map that is identity for composition on left and right for all \(f\).
    
20. If \(g\circ f = \mathrm{id}_A\), what can you say about inj/surj of \(f\) and \(g\)?
    
21. Same for \(g\circ f=\mathrm{id}\) and \(f\circ g=\mathrm{id}\).
    
22. Functions \(f_i: A_i \to A_{i+1}\)—write \(n\)-fold composition.
    
23. Invert \(f(x)=e^x\) as \(\mathbb{R}\to(0,\infty)\)—codomain matters.
    
24. Explain stack undo: inverse composition order.
    
25. Prove: if \(g\circ f\) is bijective and \(f\) surjective? Actually if \(g\circ f\) bijective then \(f\) injective and \(g\) surjective—prove.

CS connection

• Unix pipes and method chaining ≈ composition.
  
• Undo stacks apply inverses in reverse order.
  
• Serde: serialize/parse as approximate inverses on valid data.
  
• Database migrations up/down as intended inverses (not always).
  
• Middleware wrap = log ∘ auth ∘ route.
  
• Functional programming compose / >>> operators.

Common pitfalls

Pitfall	What to do instead
Applying \(g\) before \(f\) in \(g\circ f\)	\(f\) first
Writing \(f^{-1}\) for preimage relation when not bijective	Use \(f^{-1}(S)\) for sets carefully
Assuming commutative pipelines	Order matters
Left inverse unique	Not always
Forgetting codomain in invertibility	\(e^x: \mathbb{R}\to\mathbb{R}\) not onto

Checkpoint

• Define and compute \(g\circ f\)
  
• Prove associativity
  
• Unique two-sided inverse
  
• Left ⇒ injective; right ⇒ surjective
  
• \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\)
  
• Pipeline example in own words
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — category-lite vocabulary (optional)

• Monomorphism ≈ injective function (in \(\mathbf{Set}\)).
  
• Epimorphism ≈ surjective function.
  
• Isomorphism ≈ bijective function.
  
• Composition is the morphism operation; \(\mathrm{id}\) are identity morphisms.

You do not need category theory; the words sometimes appear in PL theory papers.

Partial functions and inverses

A partial function may have a partial inverse on its image. Serialization often:
\(\mathrm{decode}\circ\mathrm{encode}=\mathrm{id}\) on messages (left inverse of encode / right inverse of decode on valid codes).

Function graphs as relations

\(f:A\to B\) corresponds to \(R_f=\{(a,f(a))\}\subseteq A\times B\) with unique \(b\) for each \(a\).
Composition of functions matches composition of these relations.

More worked examples

Example 15 — Triple pipeline
\(h\circ g\circ f\) with \(f(x)=x+1\), \(g(x)=2x\), \(h(x)=x^2\): expand.

Example 16 — Inverse of product map
If \(f,g\) invertible, \((f\times g)^{-1}=f^{-1}\times g^{-1}\) on product sets.

Example 17 — No inverse
Projection \(\pi_1\) has right inverses (sections) if \(B\neq\emptyset\): pick default \(b_0\), \(r(a)=(a,b_0)\).

Example 18 — Cancellation
\(2x\) injective on \(\mathbb{R}\) so \(2g=2h\Rightarrow g=h\).

Additional exercises

26. Prove right cancellation for surjective \(f\).
    
27. Show a function can have many right inverses.
    
28. If \(g\circ f=\mathrm{id}_A\) and \(f\circ g=\mathrm{id}_B\), prove \(f\) bijective.
    
29. Middleware: write three stages and two legitimate association parenthesizations.
    
30. Prove \(\mathrm{Map}(A,A)\) is not a group under \(\circ\) if \(|A|\ge 2\) (non-bijective maps).

Extended practice workshop

Pipeline calculations

1. \(f(x)=x-3\), \(g(x)=x^2\), \(h(x)=2x\): expand \(h\circ g\circ f\) and \(f\circ g\circ h\).
   
2. Invert \(f(x)=(ax+b)/(cx+d)\) when defined (matrix intuition optional).
   
3. Show \(\mathrm{id}\) is the only function that is a left and right identity for all composable maps on a fixed set family.

Left/right inverse constructions

4. Injection \(f:\{1,2,3\}\to\{a,b,c,d\}\)—write two different left inverses.
   
5. Surjection \(g:\{1,2,3,4\}\to\{x,y\}\)—write two different right inverses.
   
6. Prove no left inverse if not injective—generic argument.
   
7. Prove no right inverse if not surjective—generic argument.

Algebra of invertible maps

8. If \(f,g:A\to A\) invertible, simplify \((f\circ g)^{-1}\circ f\).
   
9. Solve for \(X\) in \(f\circ X = g\) when \(f\) invertible.
   
10. Solve for \(X\) in \(X\circ f = g\) when \(f\) invertible.

CS scenario write-ups (no code)

11. Logging middleware as \(L\circ H\) vs \(H\circ L\)—semantic difference.
    
12. Encode/decode round-trip equations.
    
13. Database migration up/down as intended inverse pair—failure mode when down not inverse.
    
14. Undo stack: sequence of ops \(f_1,\ldots,f_n\); undo applies \(f_n^{-1},\ldots,f_1^{-1}\).

Self-score

Mark each 1–14: cold / notes / failed. Retake failed within 48h.

Associativity diagram (mental)

\[ A \xrightarrow{f} B \xrightarrow{g} C \xrightarrow{h} D \]

Either path \(A\to D\) is \(h\circ g\circ f\). Parentheses only change evaluation association, not the function.

Quick reference identities

\[ \begin{align*} (h\circ g)\circ f &= h\circ(g\circ f),\\ f\circ\mathrm{id} &= \mathrm{id}\circ f = f,\\ (g\circ f)^{-1} &= f^{-1}\circ g^{-1} \quad\text{(when invertible)},\\ \ell\circ f=\mathrm{id} &\Rightarrow f\text{ injective},\\ f\circ r=\mathrm{id} &\Rightarrow f\text{ surjective}. \end{align*} \]

Checkpoint recap (composition day)

• Compute two non-commuting compositions
  
• Prove associativity in one line of pointwise reasoning
  
• Produce a left inverse for a concrete injection
  
• State uniqueness of two-sided inverse
  
• Explain undo-stack reverse order

Synthesis

Composition is the algebra of pipelines: \((g\circ f)(x)=g(f(x))\), apply \(f\) first. Associativity is free (pointwise); commutativity is rare. Two-sided inverses undo perfectly; left/right inverses capture one-sided encode/decode. Undo stacks reverse order because \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\).

Algebra card

\[ \begin{align*} (h\circ g)\circ f &= h\circ(g\circ f),\\ f\circ\mathrm{id} &= \mathrm{id}\circ f = f,\\ (g\circ f)^{-1} &= f^{-1}\circ g^{-1} \quad\text{(both bijective)},\\ \exists \ell:\; \ell\circ f=\mathrm{id} &\Rightarrow f\text{ injective},\\ \exists r:\; f\circ r=\mathrm{id} &\Rightarrow f\text{ surjective}. \end{align*} \]

More worked examples

Example — Non-commute.
\(f(x)=x+1\), \(g(x)=2x\): \((g\circ f)(x)=2x+2\), \((f\circ g)(x)=2x+1\).

Example — Left inverse of injection.
\(f:\mathbb{N}\to\mathbb{Z}\), \(f(n)=n\). Left inverse \(r:\mathbb{Z}\to\mathbb{N}\) can send negatives to \(0\) and nonnegatives to themselves: \(r\circ f=\mathrm{id}_{\mathbb{N}}\), but \(f\circ r\neq\mathrm{id}_{\mathbb{Z}}\).

Example — Right inverse of surjection.
\(f:\mathbb{Z}\to\mathbb{N}_0\), \(f(n)=|n|\). Choose \(r(k)=k\); then \(f\circ r=\mathrm{id}\) on \(\mathbb{N}_0\). Not injective, so no two-sided inverse.

Example — Unique two-sided inverse.
If \(g\circ f=\mathrm{id}_A\) and \(f\circ g=\mathrm{id}_B\) and also \(h\) is another two-sided inverse, then \(g=g\circ\mathrm{id}_B=g\circ(f\circ h)=(g\circ f)\circ h=h\).

Example — Pipeline invertibility.
Parse then validate: even if each stage has a right inverse “locally,” the composite needs matching domains; failure of validate is not undone by unparse alone.

Extra exercises (synthesis)

31. Compute \(g\circ f\) and \(f\circ g\) for \(f(x)=x^2\), \(g(x)=x+1\) on \(\mathbb{R}\).
    
32. Prove associativity pointwise in three lines.
    
33. Show \(f(n)=2n\) on \(\mathbb{Z}\) has a left inverse \(\mathbb{Z}\to\mathbb{Z}\) (define one) but no right inverse.
    
34. Prove: if \(f\) has a two-sided inverse, then \(f\) is bijective.
    
35. Prove: if \(f\) is bijective, the inverse is unique.
    
36. CS: serialization \(S\) and deserialization \(D\) with \(D\circ S=\mathrm{id}\) (left inverse of \(S\))—what does that guarantee about \(S\)? About \(D\)?

Inverse existence summary

Situation	Inverse type
\(f\) injective, \(A\neq\emptyset\) issues aside	left inverse exists (AC for general sets; constructive for finite/nice \(f\))
\(f\) surjective	right inverse (same caveat)
\(f\) bijective	unique two-sided inverse
Finite \(|A|=|B|\)	inj ⇒ bij ⇒ inverse

Next: infinite sizes—when do bijections with \(\mathbb{N}\) exist, and when does diagonalization forbid them?

Tomorrow

Day 43 — Countability. Countable unions; \(\mathbb{Z},\mathbb{Q}\) countable sketches; Cantor diagonal \((0,1)\) uncountable; continuum awareness; \(|\mathcal{P}(\mathbb{N})| > |\mathbb{N}|\).

---

Day 43 — Countability

Stage IV · concept day
Goal: Define countable sets; show \(\mathbb{Z}\) and \(\mathbb{Q}\) are countable (sketches); prove \((0,1)\) uncountable by Cantor diagonal; know continuum awareness; prove \(|\mathcal{P}(\mathbb{N})| > |\mathbb{N}|\).

Why this matters

“Countable” means listable in a sequence (possibly infinite). Computers enumerate \(\mathbb{N}\), finite strings, and programs—all countable. Real numbers and arbitrary function spaces are vastly larger: you cannot list all reals or all subsets of \(\mathbb{N}\). Diagonalization is the ancestor of undecidability and many impossibility proofs in CS theory.

Theory

Finite and infinite

\(A\) is finite if \(A=\emptyset\) or \(|A|=n\) for some \(n\in\mathbb{N}\) (bijection with \(\{1,\ldots,n\}\)).
Otherwise infinite.

Countably infinite and countable

\(A\) is countably infinite if there is a bijection \(\mathbb{N}\to A\) (or \(\mathbb{N}^+\to A\)).
\(A\) is countable if finite or countably infinite.
Equivalently: there exists an injection \(A\to\mathbb{N}\), or a surjection \(\mathbb{N}\to A\) (for nonempty \(A\)).

Enumerable: list \(a_0,a_1,a_2,\ldots\) possibly with repeats (surjection from \(\mathbb{N}\)).

Basic countable sets

• \(\mathbb{N}\), \(\mathbb{Z}\) (list \(0,1,-1,2,-2,\ldots\)).
  
• \(\mathbb{N}\times\mathbb{N}\) (diagonal enumeration).
  
• Finite products of countable sets.
  
• Finite strings \(\Sigma^*\) over finite \(\Sigma\) (union by length).
  
• \(\mathbb{Q}\) (list fractions in lowest terms by height \(|p|+|q|\)).

Theorems (tools)

1. Subset of countable is countable.
   
2. Image of countable under a function is countable.
   
3. Countable union of countable sets is countable.
   Sketch: arrange in a grid; diagonal walk; or map \(\bigcup_n A_n\) via pairs \((n,k)\) indexing \(A_n\).
   
4. Finite product of countable is countable.

\(\mathbb{Z}\) countable (sketch)

Define \(f:\mathbb{N}\to\mathbb{Z}\) by \(f(0)=0\), \(f(2k-1)=k\), \(f(2k)=-k\) for \(k\ge 1\). Bijective.

\(\mathbb{Q}\) countable (sketch)

Every rational \(p/q\) in lowest terms, \(q>0\). Enumerate by stages \(n=|p|+q\); each stage finite; countable union of finite sets. Discard duplicates. Hence injection \(\mathbb{Q}\to\mathbb{N}\) exists (or surjection from \(\mathbb{N}\)).

\(\mathbb{N}\times\mathbb{N}\) countable

Cantor pairing: list \((0,0),(0,1),(1,0),(0,2),(1,1),(2,0),\ldots\) by diagonals \(i+j=\mathrm{const}\).
Pairing function \(\pi(k,m)=\frac{(k+m)(k+m+1)}{2}+m\) (one common form)—bijection \(\mathbb{N}\times\mathbb{N}\to\mathbb{N}\).

Uncountable: Cantor diagonal on \((0,1)\)

Theorem. \((0,1)\) is uncountable.

Proof. Suppose for contradiction \((0,1)\) is countable: list all elements as infinite decimals
\(x_1 = 0.d_{11}d_{12}d_{13}\ldots\),
\(x_2 = 0.d_{21}d_{22}d_{23}\ldots\),
…
Define \(y = 0.e_1 e_2 e_3\ldots\) with \(e_n = 4\) if \(d_{nn}\neq 4\), and \(e_n=5\) if \(d_{nn}=4\) (avoid \(0\) and \(9\) to dodge dual representations).
Then \(y\in(0,1)\) but \(y\neq x_n\) for all \(n\) (differs in \(n\)-th place). Contradiction. \(\square\)

Hence \(\mathbb{R}\) uncountable (contains \((0,1)\)).

Continuum awareness

\(|\mathbb{R}| = 2^{\aleph_0} = \mathfrak{c}\) (continuum) under standard identification with \(\mathcal{P}(\mathbb{N})\) equinumerosity flavor (\(|\mathbb{R}|=|\mathcal{P}(\mathbb{N})|\)).
Continuum hypothesis (CH): no cardinality strictly between \(\mathbb{N}\) and \(\mathbb{R}\)—independent of standard ZFC (awareness only).

Power set strictly larger (Cantor)

Theorem. For any set \(A\), there is no surjection \(A\to\mathcal{P}(A)\). In particular \(|\mathcal{P}(A)| > |A|\) when infinite (and for finite already \(2^n > n\) for \(n\ge 0\) with care at \(0\)).

Proof (diagonal). Suppose \(f: A\to\mathcal{P}(A)\). Let
\[D = \{ a\in A : a \notin f(a) \}.\]
If \(D=f(a_0)\), then \(a_0\in D \Leftrightarrow a_0\notin f(a_0)=D\), contradiction. So \(f\) not surjective. \(\square\)

Thus \(|\mathcal{P}(\mathbb{N})| > |\mathbb{N}|\): uncountably many subsets of \(\mathbb{N}\); uncountably many languages over \(\{0,1\}\); uncountably many functions \(\mathbb{N}\to\{0,1\}\).

Countable vs computable (awareness)

There are countably many programs (finite strings) but uncountably many languages/subsets of \(\mathbb{N}\)—most languages are not decidable / not even recognizable. Diagonalization appears again in undecidability proofs.

Worked examples

Example 1 — List \(\mathbb{Z}\)

\(0,1,-1,2,-2,3,-3,\ldots\)

Example 2 — Finite product

\(\mathbb{Z}^3\) countable: \((\mathbb{Z}\times\mathbb{Z})\times\mathbb{Z}\).

Example 3 — \(\Sigma^*\)

Binary strings: \(\varepsilon,0,1,00,01,10,11,\ldots\) by length then lex.

Example 4 — Union

\(\bigcup_{n=1}^\infty \{n\}\times\mathbb{Z}\) countable.

Example 5 — Diagonal y

If list starts \(0.1000\ldots\), \(0.1222\ldots\), … construct \(y\) differing on diagonal.

Example 6 — \(\mathcal{P}(\mathbb{N})\) injection from \(\mathbb{N}\)

\(n\mapsto \{n\}\) shows \(|\mathbb{N}| \le |\mathcal{P}(\mathbb{N})|\); Cantor shows not equal.

Example 7 — Functions \(\mathbb{N}\to\{0,1\}\)

Identified with characteristic sequences / subsets: uncountable.

Example 8 — Algebraic reals countable

Countable union over degrees of finite root sets of integer polynomials—countable. Hence transcendentals exist (reals uncountable).

Example 9 — Intervals

Any nonempty open interval equinumerous with \(\mathbb{R}\) (awareness: tan bijection).

Example 10 — No listing of all reals

Any purported list misses the diagonal real.

Example 11 — Countable union of finite

All finite subsets of \(\mathbb{N}\) is countable (union over size \(k\) of \(\binom{\mathbb{N}}{k}\) countable).
But \(\mathcal{P}(\mathbb{N})\) also has infinite subsets—uncountable.

Example 12 — Hilbert hotel

Full countable hotel can still accommodate one more: shift \(n\mapsto n+1\). Awareness anecdote for infinite bijections.

Example 13 — Surjection \(\mathbb{N}\to\mathbb{Q}^+\)

Enumerate; repeats OK.

Example 14 — Injection \(\mathbb{N}\to\mathbb{R}\)

\(n\mapsto n\); reals larger.

Exercises

1. Define countable and countably infinite.
   
2. Give an explicit bijection \(\mathbb{N}\to\mathbb{Z}\).
   
3. Explain diagonal enumeration of \(\mathbb{N}\times\mathbb{N}\).
   
4. Prove: subset of countable set is countable.
   
5. Prove: countable union of countable sets is countable (grid argument).
   
6. Sketch countability of \(\mathbb{Q}\).
   
7. Prove \((0,1)\) uncountable by diagonal (write carefully).
   
8. Conclude \(\mathbb{R}\) uncountable.
   
9. Prove no surjection \(A\to\mathcal{P}(A)\) for any \(A\).
   
10. Show the set of all infinite binary sequences is uncountable.
    
11. Show finite subsets of \(\mathbb{N}\) form a countable set.
    
12. Show \(\mathbb{Q}^n\) countable.
    
13. True/false: union of uncountably many countable sets is countable.
    
14. Show algebraic numbers are countable (outline).
    
15. Why does dual decimal \(0.1999\ldots=0.2000\ldots\) matter for diagonal proofs? How did we avoid it?
    
16. Prove \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|\) using injection + Cantor.
    
17. CS: countability of all Python programs (finite text).
    
18. CS: uncountability of all functions \(\mathbb{N}\to\mathbb{N}\).
    
19. Give a countably infinite proper subset of \(\mathbb{Q}\).
    
20. Is \((0,1)\cup(2,3)\) countable?
    
21. Pairing: compute \(\pi(2,3)\) for the displayed formula if you use it.
    
22. Show there are countably many polynomials with rational coefficients.
    
23. Explain Hilbert hotel check-in of one guest.
    
24. Prove: if \(A\) infinite countable and \(a\in A\), then \(A\setminus\{a\}\) still countably infinite.
    
25. One paragraph: how diagonalization foreshadows undecidability.

CS connection

• Programs countable; behaviors often uncountable ⇒ noncomputable functions exist.
  
• Languages: \(|\mathcal{P}(\Sigma^*)|=|\mathcal{P}(\mathbb{N})|\) uncountable; only countably many TMs.
  
• Floating point is finite (hence countable)—not \(\mathbb{R}\).
  
• Databases store finite subsets; theory still uses \(\mathbb{Q},\mathbb{Z}\).
  
• Hashing infinite domains cannot be injective into finite tables.
  
• Diagonal arguments in proof of undecidability of halting (later courses).

Common pitfalls

Pitfall	What to do instead
“Infinite = countable”	\(\mathbb{R}\) counterexample
Diagonal with \(0/9\) ambiguity	Avoid those digits
Assuming \(\mathbb{Q}\) uncountable because dense	Density ≠ cardinality
Confusing finite strings vs infinite sequences	\(\Sigma^*\) countable; \(\Sigma^{\mathbb{N}}\) not
Claiming all subsets of \(\mathbb{N}\) finite	Infinite subsets exist
Bijection required for “list”	Surjection enough for countability

Checkpoint

• Define countable
  
• Sketch \(\mathbb{Z}\), \(\mathbb{N}\times\mathbb{N}\), \(\mathbb{Q}\) countable
  
• Full diagonal proof for \((0,1)\)
  
• Cantor power set theorem
  
• Continuum / CH awareness one sentence
  
• CS link: more languages than programs
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — hierarchy of sizes (awareness)

\[ |\mathbb{N}| = \aleph_0 < 2^{\aleph_0} = |\mathbb{R}| = |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots \]

Each power set strictly increases cardinality (Cantor’s theorem iterated).
No “largest” infinite set in this hierarchy.

Computability link (one page in a course)

• Programs ⊆ finite strings ⊆ countable.
  
• Each program decides at most one language (subset of \(\Sigma^*\)).
  
• Only countably many decidable languages.
  
• Uncountably many languages ⇒ almost all undecidable.

Diagonalization in the halting problem is a computable cousin of Cantor’s argument.

Careful with “listing”

A listing \(a_0,a_1,\ldots\) may have duplicates (surjection \(\mathbb{N}\to A\)) and still prove countability. Bijection is cleaner when you can write one.

More worked examples

Example 15 — \(\mathbb{N}^{<\omega}\)
Finite sequences of naturals: countable union over length of \(\mathbb{N}^k\), each countable.

Example 16 — \(\mathbb{R}\times\mathbb{R}\)
\(|\mathbb{R}\times\mathbb{R}|=|\mathbb{R}|\) (interleave decimals awareness)—continuum squared is continuum.

Example 17 — Missing diagonal
Any list of reals in \((0,1)\) misses at least the constructed \(y\).

Example 18 — Finite \(\Rightarrow\) countable
\(\{1,2,3\}\) injects into \(\mathbb{N}\).

Additional exercises

26. Prove \(\mathbb{Z}\times\mathbb{Z}\) countable two ways (product; zigzag).
    
27. Show the set of polynomials with integer coefficients is countable.
    
28. Prove \((0,1)\) and \((0,1)\times(0,1)\) equinumerous (outline).
    
29. Why does “\(\mathbb{Q}\) dense” not imply “\(\mathbb{Q}\) uncountable”?
    
30. Write the diagonal set \(D\) for a supposed enumeration of all subsets of \(\mathbb{N}\).

Extended practice workshop

Prove countable

1. \(\mathbb{N}\)
   
2. \(\mathbb{Z}\) (explicit bijection)
   
3. \(\mathbb{N}\times\mathbb{N}\) (diagonal)
   
4. \(\mathbb{Q}\) (outline by height)
   
5. \(\Sigma^*\) for \(\Sigma=\{0,1\}\)
   
6. Finite subsets of \(\mathbb{N}\)
   
7. \(\mathbb{Z}[x]\) polynomials with integer coeffs (outline)

Prove uncountable

8. \((0,1)\) diagonal full write-up
   
9. \(\mathbb{R}\)
   
10. \(\{0,1\}^{\mathbb{N}}\) infinite binary sequences
    
11. \(\mathcal{P}(\mathbb{N})\) via Cantor theorem
    
12. Functions \(\mathbb{N}\to\mathbb{N}\)

Tools

13. Subset of countable is countable.
    
14. Countable union of countable is countable.
    
15. Image of countable is countable.
    
16. No surjection \(A\to\mathcal{P}(A)\).

CS links

17. Programs countable.
    
18. Languages uncountable.
    
19. Therefore noncomputable languages exist—one paragraph.
    
20. Floating-point sets are finite—not \(\mathbb{R}\).

Careful points

21. Avoid \(0.999=1.000\) in diagonal—how?
    
22. Listing may have duplicates—still OK for countability.
    
23. Density of \(\mathbb{Q}\) ≠ uncountability.

Cardinality postcard

\[|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| = |\mathbb{R}| < |\mathcal{P}(\mathbb{R})| < \cdots\]
(CH: nothing between \(|\mathbb{N}|\) and \(|\mathbb{R}|\)?—independent.)

Synthesis

Countability is bijection-with-\(\mathbb{N}\) thinking (or injection into \(\mathbb{N}\)). Countable sets are listable—possibly with repeats. Uncountable sets are not: Cantor’s diagonal and \(|\mathcal{P}(A)|>|A|\) are the standard hammers. CS punchline: there are countably many programs and uncountably many languages/functions on \(\mathbb{N}\), so most behaviors are noncomputable.

Hierarchy (working picture)

Set	Countable?	Why (sketch)
\(\mathbb{N}\)	yes	identity
\(\mathbb{Z}\)	yes	\(0,1,-1,2,-2,\ldots\)
\(\mathbb{N}\times\mathbb{N}\)	yes	diagonal / Cantor pairing
\(\mathbb{Q}\)	yes	enumerate reduced fractions
\(\Sigma^*\) finite strings	yes	length then lex
\((0,1)\), \(\mathbb{R}\)	no	diagonal
\(\{0,1\}^{\mathbb{N}}\)	no	diagonal / \(\sim\mathcal{P}(\mathbb{N})\)
\(\mathcal{P}(\mathbb{N})\)	no	Cantor theorem

More worked examples

Example — \(\mathbb{Z}\) bijection.
\(f:\mathbb{N}\to\mathbb{Z}\), \(f(0)=0\), \(f(2k-1)=k\), \(f(2k)=-k\) for \(k\ge 1\). Check bijective.

Example — Countable union of countable sets is countable.
List each \(A_i=\{a_{i0},a_{i1},\ldots\}\); zigzag over the grid \((i,j)\) same as \(\mathbb{N}\times\mathbb{N}\). (Careful: needs countable choice in full generality—awareness only.)

Example — Diagonal on \((0,1)\).
Given supposed list \(0.d_{n1}d_{n2}\ldots\), define \(e_n=4\) if \(d_{nn}\neq 4\), else \(e_n=5\) (avoid \(0/9\) terminal issues). Then \(0.e_1e_2\ldots\) differs from every listed expansion.

Example — Cantor theorem.
No surjection \(f:A\to\mathcal{P}(A)\): diagonal set \(D=\{a\in A: a\notin f(a)\}\) cannot be \(f(a_0)\) for any \(a_0\).

Example — Programs vs languages.
Fix finite alphabet; programs \(\subseteq\Sigma^*\) countable. Languages \(\mathcal{P}(\Sigma^*)\) uncountable. Hence some languages have no decider.

Extra exercises (synthesis)

31. Give an explicit injection \(\mathbb{N}\times\mathbb{N}\to\mathbb{N}\) (e.g. \(2^a(2b+1)-1\)).
    
32. Prove any subset of a countable set is countable (finite or countably infinite).
    
33. Prove the set of finite subsets of \(\mathbb{N}\) is countable.
    
34. Prove functions \(\mathbb{N}\to\{0,1\}\) are uncountable.
    
35. Show \((0,1)\) and \((0,2)\) equinumerous via an explicit bijection.
    
36. Explain why density of \(\mathbb{Q}\) in \(\mathbb{R}\) does not make \(\mathbb{Q}\) uncountable.

Proof-tool checklist

Goal	Tool
Show countable	Exhibit injection into \(\mathbb{N}\) or bijection with \(\mathbb{N}\) / known countable
Show uncountable	Diagonal, or reduce from \(\mathcal{P}(\mathbb{N})\) / \((0,1)\)
Compare sizes	Injection both ways (Cantor–Bernstein) awareness
CS noncomputability	Countable programs, uncountable problems

Floating-point sets are finite—do not confuse machine scalars with \(\mathbb{R}\). Continuum hypothesis is optional culture, not a drill target.

Tomorrow

Day 44 — Types/sets analogy. Types as sets of values; sum/product types; option/maybe; predicates as subsets; specs vs implementation—no coding labs.

---

Day 46 — Gate IV

Stage IV · gate day
Goal: Closed-book mixed review of sets, products, relations, orders, functions, countability, types analogy, and pigeonhole (Days 35–45). Diagnose weak spots before Stage V counting.

Why this matters

Stage V (combinatorics) and Stage VI (graphs) assume fluency with \(\in\), \(\subseteq\), relations, and functions. Gate IV is the last structural checkpoint before counting arguments multiply. If double inclusion, equivalence classes, or inj/surj are shaky, repair now.

What this gate covers

Block	Days	Skills
Sets	35	\(\in\), \(\subseteq\), \(=\), \(\emptyset\), double inclusion
Set ops & power set	36	\(\cup\cap\setminus\), De Morgan, \(|\mathcal{P}|=2^n\)
Products	37	\(A\times B\), counting, \(\sqcup\) vs \(\times\)
Relations	38	Properties; closures; composition
Equivalence	39	Partitions ↔︎ classes; \(\mathbb{Z}/n\mathbb{Z}\)
Posets	40	Hasse; chains; topo order lite
Functions	41–42	Inj/surj/bij; composition; inverses
Countability	43	Countable vs not; diagonal; \(\mathcal{P}(\mathbb{N})\)
Types analogy	44	Product/sum/option; spec vs type
Pigeonhole	45	Basic + generalized; collisions

How to use this page

1. Closed book first pass (timebox \(90\)–\(120\) minutes).
   
2. Mark ✅ / ⚠ / ❌.
   
3. Repair ❌/⚠ from notes; retest cold within \(48\) hours.
   
4. Proceed to Day 47 only when retest is solid on failed items.

Important

No programming labs. Proofs and constructions by hand.

Theory — rapid self-check sheet

Reproduce from memory:

1. Definition of \(A\subseteq B\) and double-inclusion criterion for \(A=B\).
   
2. De Morgan for sets; \(A\setminus B = A\cap B^c\).
   
3. \(|\mathcal{P}(S)|=2^{|S|}\) (one proof idea).
   
4. \(|A\times B|=|A||B|\); relation \(R\subseteq A\times B\).
   
5. Reflexive / symmetric / transitive / antisymmetric.
   
6. Equivalence ⇔ partition.
   
7. Partial order; Hasse covers.
   
8. Injective / surjective / bijective; inverse iff bijective.
   
9. \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\).
   
10. Cantor diagonal one-sentence idea; \(|\mathcal{P}(\mathbb{N})|>|\mathbb{N}|\).
    
11. PHP basic + \(\lceil n/k\rceil\).
    
12. Option \(\cong A+1\); product vs sum types.

Worked examples (gate warm-ups)

A. Prove \(\emptyset\subseteq A\).

B. List \(\mathcal{P}(\{0,1\})\).

C. Compute \(\{1,2\}\times\{a,b\}\).

D. Is \(\{(1,1),(2,2),(1,2)\}\) reflexive on \(\{1,2\}\)? Symmetric?

E. Classes of \(\equiv\pmod 3\).

F. \(f(n)=2n\) on \(\mathbb{Z}\): inj? surj?

G. \((g\circ f)\) for \(f(x)=x+1\), \(g(x)=x^2\).

H. Why is \((0,1)\) uncountable (outline)?

I. \(10\) pigeons \(3\) holes: min max load.

J. Type of Option(Bool) value count.

Gate exam (closed book)

Part I — Sets & operations

1. Prove by double inclusion: \(A\cap B = B\cap A\).
   
2. Prove \((A\cup B)^c = A^c \cap B^c\).
   
3. Prove \(A\subseteq B \Leftrightarrow A\cup B = B\).
   
4. True/false with reason: \(\mathcal{P}(A\cup B)=\mathcal{P}(A)\cup\mathcal{P}(B)\).
   
5. If \(|\mathcal{P}(S)|=64\), find \(|S|\).
   
6. Prove \(|\mathcal{P}(S)|=2^n\) by induction or bitstrings (\(|S|=n\)).
   
7. Distinguish \(\emptyset\), \(\{\emptyset\}\), \(\{\{\emptyset\}\}\).
   
8. Prove \(A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C)\).

Part II — Products, relations, orders

9. Prove \(A\times\emptyset=\emptyset\).
   
10. Is \((A\times B)\cup(C\times D)=(A\cup C)\times(B\cup D)\)? Prove or counterexample.
    
11. Check REF/SYM/TRANS/ANTI for \(\mid\) on \(\mathbb{Z}^+\).
    
12. Transitive closure of \(\{(1,2),(2,3),(3,1)\}\) on \(\{1,2,3\}\).
    
13. Compose \(R=\{(a,b)\}\), \(S=\{(b,c)\}\).
    
14. Prove: equivalence classes are equal or disjoint.
    
15. Addition table sketch for \(\mathbb{Z}/4\mathbb{Z}\).
    
16. Draw Hasse diagram for \((\{1,2,3,6\},\mid)\).
    
17. Find a chain of length \(3\) and an antichain of size \(2\) in \(\mathcal{P}(\{1,2\})\).
    
18. Give two topological orders for tasks \(A\to C\), \(B\to C\).

Part III — Functions & composition

19. Prove \(f:\mathbb{R}\to\mathbb{R}\), \(f(x)=2x+1\) is bijective; give inverse.
    
20. Count injections from a \(3\)-set to a \(6\)-set.
    
21. Count all functions from a \(4\)-set to a \(3\)-set.
    
22. Prove: if \(g\circ f\) injective then \(f\) injective.
    
23. Prove: if \(f\) has a left inverse then \(f\) injective.
    
24. Compute \((g\circ f)^{-1}\) in terms of inverses when both bijective.
    
25. Finite \(|A|=|B|\): show injection \(A\to B\) is bijection.
    
26. Projection \(\pi_1: A\times B\to A\)—when surjective? when injective?

Part IV — Countability, types, pigeonhole

27. Give a bijection sketch \(\mathbb{N}\leftrightarrow\mathbb{Z}\).
    
28. Why is \(\mathbb{Q}\) countable (outline)?
    
29. Write a full diagonal argument that \((0,1)\) is uncountable.
    
30. Prove there is no surjection \(A\to\mathcal{P}(A)\).
    
31. Countable vs uncountable: \(\Sigma^*\) vs infinite binary sequences.
    
32. Interpret Result[T,E] as a sum type; count if \(|T|=2\), \(|E|=3\).
    
33. Why type List[int]→List[int] does not ensure sorting correctness.
    
34. PHP: \(100\) keys \(7\) buckets—some bucket has at least how many keys?
    
35. Prove among any \(9\) integers two differ by a multiple of \(8\).
    
36. Birthday: distinguish \(23\) vs \(366\).
    
37. Prefix sums: any \(n\) integers have consecutive block sum \(\equiv 0\pmod n\) (proof).
    
38. Erdős–Szekeres: state the theorem.
    
39. Product vs sum: “name and age” vs “cat or dog id.”
    
40. Portfolio: three Stage IV skills to drill this week.

Scoring guide (self)

Score band	Meaning	Action
≥ 34/40 solid	Stage IV ready	Proceed to Day 47
26–33	Patch holes	Retake failed items cold in 48h
≤ 25	Rebuild	Revisit weak day clusters; retake gate

Optional deep extras

41. Prove well-definedness of multiplication in \(\mathbb{Z}/n\mathbb{Z}\).
    
42. Structural induction: \(\mathrm{len}(xs{+\!\!+}ys)=\mathrm{len}(xs)+\mathrm{len}(ys)\).
    
43. Show \(|\mathbb{R}|=|(0,1)|\) via an explicit bijection sketch.
    
44. Dilworth / width of a small poset you invent.
    
45. Full proof: every finite nonempty poset has a maximal element.

CS connection (gate lens)

• Schemas = products; joins filter products; relations are tables.
  
• Hash collisions = PHP; encodings = injections.
  
• Types = sets with constructors; options and results = sums.
  
• Topo sort = linear extension of dependency poset.
  
• Stage V will count the structures you can now name.

Common pitfalls (gate day)

Pitfall	What to do instead
One inclusion for set equality	Both directions
Properties of relations by vibe	Check definitions on pairs
Inverse without bijective	Prove both inj and surj
Diagonal with \(0.999=1.000\) mess	Avoid \(0\) and \(9\) digits
Birthday certainty at \(23\)	Certainty is \(n_{\mathrm{holes}}+1\)
Open book pass 1	Close it

Checkpoint

• Self-check sheet from memory
  
• Warm-ups A–J cold
  
• Gate exam scored
  
• Retest plan for failures
  
• Ready/not-ready for Stage V

Two takeaways from Stage IV:

1. …
   
2. …

Extended drill set

Drill A — Sets

41. Prove \(A\subseteq B \Leftrightarrow A\cap B=A\) both directions.
    
42. Compute \(\mathcal{P}(\{a,b,c\})\) size and three distinct elements.
    
43. Prove De Morgan for three sets \((A\cup B\cup C)^c=A^c\cap B^c\cap C^c\).
    
44. Indicator: express \(1_{A\setminus B}\) in terms of \(1_A,1_B\).

Drill B — Relations & orders

45. Matrix of \(\le\) on \(\{1,2,3,4\}\).
    
46. Symmetric closure then transitive closure of \(\{(1,2),(2,3)\}\).
    
47. Is “differ by even integer” an equivalence on \(\mathbb{Z}\)? Classes?
    
48. Hasse diagram for divisors of \(12\).
    
49. Two linear extensions of a poset with relations \(a\le c\), \(b\le c\), \(a\le d\).

Drill C — Functions

50. Prove \(f(x)=x/(1+|x|)\) maps \(\mathbb{R}\) bijectively to \((-1,1)\) (outline).
    
51. \(P(8,3)\) and \(8^3\)—interpret.
    
52. Left inverse for \(n\mapsto(n,0):\mathbb{Z}\to\mathbb{Z}^2\).
    
53. Show \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\) on a concrete bijection pair.

Drill D — Countability & PHP

54. Diagonal proof write-up in \(\le 12\) lines.
    
55. Why \(|\mathcal{P}(\mathbb{N})|\neq\aleph_0\).
    
56. Generalized PHP numerical: \(200\) into \(9\).
    
57. Subarray sum divisible by \(7\)—state theorem for \(n=7\).
    
58. Type count: Option(Bool×Bool).

Drill E — Mixed synthesis

59. Relation “same image under \(f\)” is always an equivalence—prove.
    
60. Connect PHP to non-injectivity of \(f:A\to B\) when \(|A|>|B|\).

Repair plan template

Failed #	Day to revisit	Drill minutes	Retest

Sample outlines (check after attempt)

Power set induction: partition subsets of \(T\) by membership of a fixed \(a\).

Diagonal: list \(x_n\), build \(y\) differing at position \(n\), avoid \(0/9\).

Prime factor strong induction: composite splits into smaller factors.

\(\sqrt{2}\) not needed here—Stage III—but double inclusion is Stage IV staple.

Stage IV exit criteria

Cold readiness:

• Double inclusion equality proof.
  
• \(|\mathcal{P}(S)|=2^n\) argument.
  
• Test relation properties; name equivalence vs partial order.
  
• Inj/surj proofs; \(P(n,k)\).
  
• One composition/inverse identity.
  
• Diagonal uncountability sketch.
  
• PHP basic + generalized numerical application.
  
• Product vs sum types in one sentence each.

Bridge to Stage V

Counting answers “how many?” using:

• Product/sum rules (Day 47)
  
• Bijections to known sets (Day 41 skills)
  
• Inclusion-exclusion, binomial, etc.

Your Stage IV vocabulary is the ontology; Stage V is enumeration over it.

Timed mock (50 minutes)

#	Task	Min
M1	Double inclusion: \(A\cup B=B\cup A\)	4
M2	\(\|\mathcal{P}(\{1,2,3,4\})\|\) with justification	3
M3	List \(A\times B\) for \(\|A\|=2,\|B\|=2\)	3
M4	Properties of \(\mid\) on \(\mathbb{Z}^+\)	5
M5	Classes of \(\equiv\pmod 5\)	4
M6	Hasse of \((\{1,2,4\},\mid)\)	4
M7	Inj/surj of \(n\mapsto n+1\) on \(\mathbb{Z}\)	4
M8	\(P(6,2)\) and meaning	3
M9	\((g\circ f)^{-1}\) formula	3
M10	Diagonal uncountability outline	6
M11	PHP: \(25\) into \(4\) holes min max	3
M12	Option as sum type one sentence	2
M13	Composition \(S\circ R\) for small \(R,S\)	4
M14	Prove no surjection \(\mathbb{N}\to\mathcal{P}(\mathbb{N})\) outline	5

Pass bar: \(\ge 11/14\) solid.

Reflection prompts

• Set equality with only one inclusion?
  
• Relation properties guessed not checked?
  
• Diagonal digits \(0/9\) issue handled?
  
• PHP ceiling computed correctly?

Second-pass protocol

Same as Gate III: notes only for ❌ → next-day cold retest → log times.

Stage IV → V teaser

Counting will ask:

• How many injective functions? (you know \(P(n,k)\))
  
• How many subsets? (\(2^n\))
  
• How many paths / trees / colorings? (graphs later)

Bijections are the cleanest counting proofs: show a set equinumerous to a known counted set.

Closing checklist for the volume so far

• Stages I–II arithmetic/algebra still fluent
  
• Stage III logic/proof methods fluent
  
• Stage IV sets/relations/functions fluent
  
• Ready to count without double-counting (Stage V)

Synthesis — Stage IV portfolio

Gate IV compresses Days 35–45. The ontology is: sets → operations → products → relations → equivalences / orders → functions → size (finite & countable) → types analogy → PHP. Counting (Stage V) enumerates over this ontology.

Skill clusters (what “ready” means)

Cluster	Cold ability
Sets	Double inclusion; \(\emptyset\subseteq A\); \(\in\) vs \(\subseteq\)
Ops / power	De Morgan; \(\|\mathcal{P}(S)\|=2^{\|S\|}\)
Products	\(\|A\times B\|\); relation as subset of product
Relations	REF/SYM/TRANS/ANTI; closures; composition
Equivalence	Classes partition; \(\mathbb{Z}/n\mathbb{Z}\); well-definedness
Posets	Hasse; maximal vs maximum; topo sort idea
Functions	Inj/surj/bij; \(P(n,k)\); inverse iff bijective
Composition	Associativity; \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\)
Countability	\(\mathbb{Z},\mathbb{Q}\) countable; diagonal; \(\mathcal{P}(\mathbb{N})\)
PHP	Basic + \(\lceil n/k\rceil\); name pigeons/holes

Method / tool drill (one line each)

1. Prove \(A\cap B=B\cap A\) →
   
2. \(\|\mathcal{P}(S)\|=16\) ⇒ \(\|S\|\) →
   
3. Number of relations on a \(3\)-set →
   
4. Prove classes equal or disjoint →
   
5. \(f(n)=2n\) on \(\mathbb{Z}\): inj? surj? →
   
6. Why no injection \(\{1,\ldots,5\}\to\{1,2,3\}\) →
   
7. Outline: \((0,1)\) uncountable →
   
8. \(100\) pigeons, \(7\) holes: min max load →

Mini repair log (post-score)

Item #	Failure mode	Day to reread	Retest
	one-sided set equality	35
	power set identity false claim	36
	product union counterexample	37
	property mis-test	38
	ill-defined on classes	39
	maximal/maximum swap	40
	infinite inj≠bij forgotten	41
	inverse order wrong	42
	diagonal \(0/9\) care	43
	PHP holes undefined	45

More mixed warm-ups (second pass)

W1. Prove \(A\subseteq B\Leftrightarrow A\cup B=B\).
W2. Transitive closure of \(\{(1,2),(2,3)\}\) on \(\{1,2,3\}\).
W3. Kernel of \(f(n)=n\bmod 3\)—list classes.
W4. Compose \(f(x)=x+1\), \(g(x)=x^2\); is \(g\circ f=f\circ g\)?
W5. PHP: force \(\ge 3\) in some of \(5\) holes—how many pigeons?

Exit criteria (restate)

Enter Stage V when, cold, you can: double-include a set identity; test relation properties on a small example; classify inj/surj; outline diagonal uncountability; apply generalized PHP with named pigeons and holes. Retest beats calendar progress.

Tomorrow

Day 47 — Product & sum rules (counting). Stage V begins: systematic enumeration without double-counting.