Sets

1. What does it mean for a machine to accept an input?
   Stuck? Peek at 0.1.1 What “computation” means

   • Machine: reads a finite input symbol by symbol, changes mode, ends with yes (accept) / no (reject) — or may never end.
   • Decision problem: a question whose answer is yes or no for every input.
   • Machines differ by memory: finite modes → pile of plates → endless notebook → beyond all machines.
   • Finite memory works iff the fact you must carry stays bounded (even/odd, remainder, “seen x?”). Unbounded counts/comparisons break it.

   Read lesson 0.1.1

2. Why can’t a fixed-mode machine check whether an input has equally many a’s and b’s?
   Stuck? Peek at 0.1.1 What “computation” means

   • Machine: reads a finite input symbol by symbol, changes mode, ends with yes (accept) / no (reject) — or may never end.
   • Decision problem: a question whose answer is yes or no for every input.
   • Machines differ by memory: finite modes → pile of plates → endless notebook → beyond all machines.
   • Finite memory works iff the fact you must carry stays bounded (even/odd, remainder, “seen x?”). Unbounded counts/comparisons break it.

   Read lesson 0.1.1

3. What is a decision problem?
   Stuck? Peek at 0.1.1 What “computation” means

   • Machine: reads a finite input symbol by symbol, changes mode, ends with yes (accept) / no (reject) — or may never end.
   • Decision problem: a question whose answer is yes or no for every input.
   • Machines differ by memory: finite modes → pile of plates → endless notebook → beyond all machines.
   • Finite memory works iff the fact you must carry stays bounded (even/odd, remainder, “seen x?”). Unbounded counts/comparisons break it.

   Read lesson 0.1.1

A spam filter keeps a list of blocked email addresses. Your phone keeps a list of contacts. A machine that “says yes” keeps — in effect — a collection of all the inputs it says yes to. Before we can talk about all inputs a machine accepts, we need the language of collections. That language is sets, and every later definition in TOC is written in it.

A set has 3 elements, say {red, green, blue}. How many different sub-collections can you pick from it — counting “pick nothing” and “pick everything”?

Prediction check

Answer: 8. For each of the 3 elements you decide independently “in” or “out”: 2 × 2 × 2 = 2³ = 8. The list: {}, {red}, {green}, {blue}, {red,green}, {red,blue}, {green,blue}, {red,green,blue}. This 2ⁿ count will come back many times (for example, when a machine with n modes is converted into a machine whose modes are groups of the old modes).

Set and membership

• Write elements in braces: A = {1, 2, 3}.
• Order doesn’t matter: {1,2,3} = {3,1,2}.
• Repeats don’t count: {1,1,2} = {1,2}.
• Membership: x ∈ A means “x is an element of A”; x ∉ A means it isn’t. 2 ∈ {1,2,3}, 5 ∉ {1,2,3}.
• Set-builder form: {x | x is even and 0 ≤ x ≤ 6} = {0, 2, 4, 6}. Read “|” as “such that”.

The empty set

The set with no elements is the empty set, written ∅ or {}. Careful: {∅} is not empty — it is a set containing one element, and that element happens to be the empty set. Think of an empty box (∅) versus a box containing an empty box ({∅}).

Subset

• {1,2} ⊆ {1,2,3}. Also {1,2,3} ⊆ {1,2,3} (every set is a subset of itself).
• ∅ ⊆ every set (there is nothing in ∅ that could fail to be in B).
• Proper subset A ⊂ B: A ⊆ B and A ≠ B. {1,2} ⊂ {1,2,3}, but {1,2,3} is not a proper subset of itself.
• Equality: A = B exactly when A ⊆ B and B ⊆ A. This “prove both directions” idea is how you prove two sets equal.

Union, intersection, difference

• Union A ∪ B = everything in A or B (or both).
• Intersection A ∩ B = everything in both.
• Difference A − B (also written A \ B) = in A but not in B.

With A = {1,2,3,4}, B = {3,4,5}: A ∪ B = {1,2,3,4,5}; A ∩ B = {3,4}; A − B = {1,2}; B − A = {5}. Note A − B ≠ B − A in general.

Two sets are disjoint if A ∩ B = ∅.

Universe and complement

Usually all sets in a discussion live inside one big set, the universe U. The complement of A, written A̅ (or Aᶜ, or A′), is U − A: everything in the universe that is not in A.

If U = {1,…,6} and A = {2,4,6}, then A̅ = {1,3,5}. Complement always depends on the universe — this matters a lot later, when “the universe” will be all possible inputs.

De Morgan’s laws: (A ∪ B)̅ = A̅ ∩ B̅ and (A ∩ B)̅ = A̅ ∪ B̅. Also A − B = A ∩ B̅. Memorize this last one: it turns difference into intersection + complement.

Cardinality and counting

The cardinality |A| is the number of elements. |{a,b,c}| = 3, |∅| = 0, |{∅}| = 1.

Inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|. (You subtract the overlap because you counted it twice.)

Sets can also be infinite, like the set of all natural numbers ℕ = {0, 1, 2, …}.

Power set

P({1,2}) = {∅, {1}, {2}, {1,2}} — four elements. P(∅) = {∅}, which has 1 element (2⁰ = 1), not 0.

Ordered pairs and the Cartesian product

Sometimes order matters. An ordered pair (x, y) has a first and second entry: (1,2) ≠ (2,1). The Cartesian product A × B is the set of all pairs (a, b) with a ∈ A and b ∈ B.

{p,q} × {0,1} = {(p,0), (p,1), (q,0), (q,1)}. In general |A × B| = |A| · |B|. We will use this to describe a machine’s rules: “in mode p, reading symbol 0, go to …” is a rule for the pair (p, 0).

Putting it together

• ∈ is about one element, ⊆ about a whole set; ∅ ⊆ every set; ∅ ≠ {∅}.
• Union, intersection, difference and complement are just shaded regions; A − B = A ∩ B̅ and De Morgan swaps ∪ and ∩ under complement.
• |P(A)| = 2^|A| (a switch per element), |A × B| = |A|·|B|, |A ∪ B| = |A| + |B| − |A ∩ B|.

U = {1,2,3,4,5,6}      A = {1,2,3,4}      B = {3,4,5}
 ┌──────────────────────────────────────────────┐ U
 │     ┌───────────────┐                        │
 │     │ A    1  2  ┌──┼──────────┐             │
 │     │            │ 3│ 4        │             │
 │     │            │  │   A∩B    │  5    B     │
 │     └────────────┼──┘          │             │
 │                  └─────────────┘        6    │  ← 6 is in neither
 └──────────────────────────────────────────────┘
 A∪B = {1,2,3,4,5}   A∩B = {3,4}   A−B = {1,2}   B−A = {5}
 Ā = {5,6}           B̄ = {1,2,6}   (A∪B)̄ = {6} = Ā ∩ B̄ ✓ De Morgan

Power set of {a,b,c} by the “in/out” switches:

a b c   subset          a b c   subset
0 0 0   ∅               1 0 0   {a}
0 0 1   {c}             1 0 1   {a,c}
0 1 0   {b}             1 1 0   {a,b}
0 1 1   {b,c}           1 1 1   {a,b,c}      → 2³ = 8 subsets

Sets let us name “all the inputs a machine accepts” as one object. Next we need a way to describe rules: “given this mode and this symbol, go to that mode”. That is what a function is, and grouping modes that “behave the same” needs equivalence relations.

1. MCQ

   Which statement is FALSE?

   1. ∅ ⊆ {1,2}
   2. ∅ ∈ {∅, 1}
   3. |{∅}| = 0
   4. {1} ⊆ {1,2}
2. NAT

   If |A| = 4, how many subsets of A contain at least one element?

   Write your answer before opening the key.

3. MSQ

   Let U = {1,…,8}, A = {1,2,3,4}, B = {3,4,5,6}. Which are correct?

   1. A − B = {1,2}
   2. A̅ ∩ B̅ = {7,8}
   3. A ∩ B̅ = {1,2}
   4. |A ∪ B| = 8
4. NAT

   If |A| = 3 and |B| = 2, what is |P(A × B)|?

   Write your answer before opening the key.

5. MCQ

   Which is equal to A − B for every A, B inside universe U?

   1. A ∪ B̅
   2. A ∩ B̅
   3. A̅ ∩ B
   4. (A ∩ B)̅

• set, element, ∈, ∉
• empty set ∅
• subset ⊆, proper subset ⊂
• union ∪, intersection ∩, difference −
• universe U, complement A̅
• De Morgan’s laws
• cardinality |A|
• power set P(A) = 2^A
• ordered pair, Cartesian product A × B
• finite / infinite set
• disjoint sets

1. |P(A)| when |A| = n?
   Reveal answer

   2ⁿ
2. ∅ vs {∅} — cardinalities?
   Reveal answer

   |∅| = 0, |{∅}| = 1
3. Write A − B using ∩ and complement.
   Reveal answer

   A ∩ B̅
4. De Morgan’s laws for sets
   Reveal answer

   (A∪B)̅ = A̅ ∩ B̅ and (A∩B)̅ = A̅ ∪ B̅
5. |A ∪ B| = ?
   Reveal answer

   |A| + |B| − |A ∩ B|
6. |A × B| = ?
   Reveal answer

   |A| · |B|

• Nested power sets: compute from the inside out. |P(P(P(∅)))| = 2^(2^(2^0)) = 2^(2^1) = 2² = 4.