Day 46 — Gate IV

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.