🧺 Set Theory — GATE Hub
What this folder is
GATE-focused notes for Discrete Mathematics → Chapter 3: Set Theory, built from the Neso Academy slides (86 pages) and extended with the topics GATE asks that the slides skip: inclusion–exclusion, counting formulas, countability. Prerequisite: 08 Logical Equivalences. Every set identity is a logic law in disguise (∪ = ∨, ∩ = ∧, ’ = ¬).
Slide typo corrected
In the Domination Law proof, part (b) is titled “A ∪ ϕ = ϕ” but proves A ∩ ϕ = ϕ (the correct law). See SET 08 Set Identities.
🗺️ Map of Content
| # | Note | What’s inside | Priority |
|---|---|---|---|
| 01 | SET 01 Basics and Representation | Well-defined, distinct, ∈ / ∉, list / predicate / ellipsis form | ⭐ |
| 02 | SET 02 Subsets and Equality | ⊆, ⊂, =, their properties | ⭐⭐ |
| 03 | SET 03 Membership vs Inclusion | ∈ vs ⊆ — the box analogy, nested-set traps | ⭐⭐⭐ |
| 04 | SET 04 Universal Null Singleton | U, ϕ, {ϕ}, “ϕ is a subset of every set” | ⭐⭐⭐ |
| 05 | SET 05 Power Set and Cardinality | P(A), 2ⁿ, power sets of nested sets | ⭐⭐⭐ |
| 06 | SET 06 Cartesian Product | Ordered pairs, A×B, |A×B| = mn, A×B×C vs (A×B)×C | ⭐⭐ |
| 07 | SET 07 Set Operations | ∪, ∩, −, complement, Venn diagrams, region method | ⭐⭐⭐ |
| 08 | SET 08 Set Identities | All 10 laws with logic-style proofs | ⭐⭐⭐ |
| 09 | SET 09 Symmetric Difference | A ⊕ B, its two forms, identities | ⭐⭐ |
| 10 | SET 10 Beyond the Slides | Inclusion–exclusion, counting formulas, countability | ⭐⭐⭐ |
| 11 | SET 11 GATE PYQs | All 8 PYQs from the slides, solved with shortcuts | ⭐⭐⭐ |
| 12 | SET 12 Practice Problems | 30 new problems (Easy → GATE 2-mark), hidden answers | ⭐⭐⭐ |
| 13 | SET 13 Flashcards | Spaced Repetition deck | ⭐⭐ |
| 14 | SET 14 Memory Tricks and Traps | Mnemonics + every edge case GATE uses | ⭐⭐⭐ |
| 15 | SET 15 Cheat Sheet | One-page revision sheet | ⭐⭐⭐ |
🔗 Concept Flow
graph LR L[Propositional Logic] --> O A[Sets & elements] --> B[Subset / equality] A --> C[∈ vs ⊆] B --> D[ϕ, U, singleton] D --> E[Power set] A --> F[Cartesian product] A --> O[Operations ∪ ∩ − '] O --> I[Identities] O --> S[Symmetric difference] I --> X[Inclusion–exclusion] F --> R[Relations — next chapter]
🎯 How GATE tests this chapter
Question patterns that keep repeating
- ∈ vs ⊆ with nested sets (“ϕ ∈ 2ᴬ? {5,{6}} ⊆ 2ᴬ?“) → SET 03 Membership vs Inclusion, SET 05 Power Set and Cardinality (GATE 2015).
- Counting — |P(A)|, |A×B|, proper subsets, subsets of size k → SET 05 Power Set and Cardinality, SET 10 Beyond the Slides (GATE 1995, 2015).
- Simplify / compare set expressions — X = Y? X ⊂ Y? → rewrite with ∩ and ’, or use the region method (SET 07 Set Operations) (GATE 1996, 2005, 2006, 2008).
- Inclusion–exclusion word problems (NAT) → SET 10 Beyond the Slides.
Formats: MCQ (negative marking), MSQ (all correct options needed), NAT.
📅 Suggested study plan (4 sessions)
- Day 1 — SET 01 Basics and Representation, SET 02 Subsets and Equality, SET 03 Membership vs Inclusion, SET 04 Universal Null Singleton
- Day 2 — SET 05 Power Set and Cardinality, SET 06 Cartesian Product, SET 07 Set Operations
- Day 3 — SET 08 Set Identities, SET 09 Symmetric Difference, SET 10 Beyond the Slides
- Day 4 — SET 11 GATE PYQs (timed) → SET 12 Practice Problems → SET 14 Memory Tricks and Traps
- Ongoing — SET 13 Flashcards daily; SET 15 Cheat Sheet weekly
✅ Mastery checklist
- I never confuse ∈ (is an element) with ⊆ (every element is inside)
- I can say instantly whether ϕ ∈ X and whether ϕ ⊆ X
- I can list P(A) for sets containing sets, like {ϕ, {ϕ}}
- I know |P(A)| = 2ⁿ, |A×B| = mn, proper subsets = 2ⁿ − 1
- I can simplify any set expression with A − B = A ∩ B’ + logic laws
- I can compare two 3-set expressions with the region method in under 2 minutes
- I can do 2- and 3-set inclusion–exclusion
- I’ve solved all 8 PYQs and scored ≥ 80% on the practice set
📝 Mistake log
Track every question you get wrong
Date Question / Source My mistake Correct idea Linked note
Previous chapter ← First Order Logic · Next chapter → Relations