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.)

QuantityFormula
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)

QuantityCount
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

StatementTrue?
✅ 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