SET 10 · Beyond the Slides (GATE extras)
Not in the Neso Chapter 3 deck
These topics appear in GATE (especially as NAT questions) but aren’t covered in the slides.
1. Inclusion–exclusion
Two sets
Three sets
General: add singles, subtract pairs, add triples, subtract quadruples, …
Memory — "add, subtract, add …" (alternate signs by group size)
Derived counts (3 sets, write etc.)
| Quantity | Formula |
|---|---|
| None of them | |
| Only A | |
| Exactly two | |
| Exactly one | |
| At least two |
Count integers 1–100 divisible by 2 or 3 or 5
⌊100/2⌋ + ⌊100/3⌋ + ⌊100/5⌋ − ⌊100/6⌋ − ⌊100/10⌋ − ⌊100/15⌋ + ⌊100/30⌋ = 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74 Not divisible by any of them: 100 − 74 = 26.
Fill a 3-set Venn diagram from the centre outward
Put in the middle first, then “pairs only” = , then “only A”, etc. Starting from the outside double-counts.
2. Counting formulas (|A| = n, |B| = m)
| Quantity | Count |
|---|---|
| Subsets of A | |
| Proper subsets | |
| Non-empty proper subsets | |
| Subsets of size k | |
| Subsets containing a fixed element x | |
| Subsets of even size (n ≥ 1) | |
| (= number of relations A → B) | |
| Ordered pairs (X, Y) of subsets with X ⊆ Y ⊆ A | |
| Ordered pairs of disjoint subsets of A |
The "choices per element" trick
For “how many ways to pick subsets with condition …”, ask what each element can do independently. X ⊆ Y ⊆ A: each element is in neither, in Y only, or in both ⇒ 3 choices ⇒ .
3. Power set facts
| Statement | True? |
|---|---|
| ✅ always | |
| ❌ only ⊇ holds: | |
| ✅ | |
| ✅ |
Counter-example for union: A = {1}, B = {2}. Then {1, 2} ∈ P(A ∪ B) but not in P(A) ∪ P(B).
4. Cartesian product with operations
- — not equal in general
5. Disjoint sets & partitions
- Disjoint: . Then .
- Partition of A: non-empty, pairwise disjoint subsets whose union is A. (Partitions ↔ equivalence relations, in the next chapter.)
6. Countable vs uncountable (TOC crossover)
- Countable: finite, or can be listed as a sequence (one-to-one with ℕ).
- Countably infinite: ℕ, ℤ, ℚ, even numbers, primes, the set of all finite strings over a finite alphabet (Σ*), the set of all programs / Turing machines.
- Uncountable: ℝ, any interval like (0, 1), P(ℕ), the set of all functions ℕ → {0, 1}, the set of all languages over Σ ().
- Cantor’s theorem: for every set A — even infinite ones. No set is as big as its power set.
- Countable ∪ countable = countable. A subset of a countable set is countable.
Why there exist undecidable languages
Programs are countable (finite strings), but languages over Σ are uncountable (). So most languages have no program deciding them.
7. Russell’s paradox (why “well-defined” matters)
— the set of all sets that don’t contain themselves. Is ? Either answer contradicts itself ⇒ “the set of all sets” isn’t a valid set. This is why modern set theory restricts how sets are built.
Prev ← SET 09 Symmetric Difference · Next → SET 11 GATE PYQs