Functions, relations and equivalence classes

1. If |A| = 5, what is |P(A)|?
   Stuck? Peek at 0.2.1 Sets

   • x ∈ A (element) vs X ⊆ A (subset). ∅ ⊆ every set. A = B ⇔ A ⊆ B and B ⊆ A.
   • A ∪ B, A ∩ B, A − B = A ∩ B̅, A̅ = U − A. De Morgan: (A∪B)̅ = A̅∩B̅, (A∩B)̅ = A̅∪B̅.
   • |A ∪ B| = |A| + |B| − |A ∩ B|. |A × B| = |A|·|B|. |P(A)| = 2^|A|.
   • |∅| = 0, |{∅}| = 1, P(∅) = {∅}.

   Read lesson 0.2.1

2. Is {a} an element of {a, b}? Is it a subset?
   Stuck? Peek at 0.2.1 Sets

   • x ∈ A (element) vs X ⊆ A (subset). ∅ ⊆ every set. A = B ⇔ A ⊆ B and B ⊆ A.
   • A ∪ B, A ∩ B, A − B = A ∩ B̅, A̅ = U − A. De Morgan: (A∪B)̅ = A̅∩B̅, (A∩B)̅ = A̅∪B̅.
   • |A ∪ B| = |A| + |B| − |A ∩ B|. |A × B| = |A|·|B|. |P(A)| = 2^|A|.
   • |∅| = 0, |{∅}| = 1, P(∅) = {∅}.

   Read lesson 0.2.1

3. How many modes does a machine need to check “length is even”?
   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 vending machine has a rule book: “If you are waiting for money and someone inserts ₹10, move to ‘ready to dispense’.” Every rule takes a (situation, action) pair and gives exactly one next situation. That is a function.

Later, we’ll want to shrink machines by merging modes that “behave the same”. Deciding which things “behave the same” — and grouping them — is exactly what an equivalence relation does. GATE asks about both, and minimizing machines (a top-scoring topic) is built entirely on equivalence classes.

Consider all whole numbers 0, 1, 2, 3, … and call two numbers “alike” if they leave the same remainder when divided by 3. Into how many groups do all the infinitely many numbers fall?

Prediction check

Answer: 3 groups — remainder 0 {0,3,6,…}, remainder 1 {1,4,7,…}, remainder 2 {2,5,8,…}. Infinitely many things, but only finitely many groups. This is exactly how a finite-memory machine can handle infinitely many inputs: it groups them into finitely many classes.

Relations

Example: A = {1,2,3}, “less than” on A is {(1,2), (1,3), (2,3)}. A relation on A means a subset of A × A. Since |A × A| = n², the number of relations on an n-element set is 2^(n²).

Functions

• “Every” — no element of A is left without an output.
• “Exactly one” — no element of A has two outputs.

The number of functions from A to B is |B|^|A| (each of the |A| inputs independently picks one of |B| outputs).

A partial function may leave some inputs without an output. Remember this: a machine whose rule book has a missing entry is like a partial function, and we will learn how to “complete” it.

Functions of two inputs

A function can take a pair as input: f : A × B → C. Example: δ(mode, symbol) = next mode, where δ (Greek “delta”) is just a name. With 3 modes and 2 symbols the domain has 3 × 2 = 6 pairs, so the rule book has 6 entries.

One-to-one, onto, bijection

• One-to-one (injective): different inputs give different outputs.
• Onto (surjective): every element of B is hit by some input.
• Bijection: both. A bijection pairs A and B perfectly, so finite A and B have equal size.

Properties of a relation on A

• Reflexive: a R a for every a.
• Symmetric: a R b ⇒ b R a.
• Transitive: a R b and b R c ⇒ a R c.

“Less than” is transitive but not reflexive or symmetric. “Has the same birthday as” is all three.

Equivalence relations and classes

The equivalence class of a, written [a], is the set of everything equivalent to a. Key facts:

• Every element is in exactly one class. Classes never partly overlap: two classes are either identical or disjoint.
• So the classes partition the set: they cut it into non-overlapping pieces that cover everything.
• The number of classes is called the index of the relation. “Same remainder mod 3” has index 3.

Conversely, any partition defines an equivalence relation (“in the same piece”).

Refinement

Relation R₁ refines R₂ if every class of R₁ sits inside a class of R₂ — R₁ cuts more finely. “Same remainder mod 6” refines “same remainder mod 3”: class {0,6,12,…} ⊆ {0,3,6,9,…}. A finer relation has at least as many classes. Machine minimization is exactly “find the coarsest grouping that still works”.

Putting it together

• A function gives every input exactly one output; there are |B|^|A| of them. A missing output makes it partial.
• An equivalence relation (reflexive + symmetric + transitive) cuts a set into non-overlapping classes; their number is the index.
• Finer relation = more, smaller classes. Shrinking machines (Chapter 1.3) is finding the coarsest grouping that still works.

"same remainder mod 3" on {0,1,2,...,11}

 class [0]          class [1]          class [2]
 ┌───────────┐      ┌───────────┐      ┌───────────┐
 │ 0 3 6 9   │      │ 1 4 7 10  │      │ 2 5 8 11  │
 └───────────┘      └───────────┘      └───────────┘
 pieces don't overlap · together they cover everything · index = 3

 function check:   A={p,q}  B={0,1}
   f = {(p,0),(q,1)}         ✓ function (each input one output)
   g = {(p,0),(p,1),(q,1)}   ✗ p has two outputs
   h = {(p,0)}               ✗ q has none (only a partial function)
   number of functions A→B = |B|^|A| = 2² = 4

We can now state rules (functions) and group things that behave alike (equivalence classes). Next we need to prove things about machines — for example, “no finite-memory machine can check balanced brackets”. That needs proof techniques.

1. NAT

   How many functions are there from {a,b,c,d} to {0,1}?

   Write your answer before opening the key.

2. MCQ

   Which relation on the integers is an equivalence relation?

   1. x R y iff x ≤ y
   2. x R y iff x − y is divisible by 4
   3. x R y iff |x − y| = 1
   4. x R y iff x < y
3. MSQ

   An equivalence relation on a 10-element set has exactly 3 classes. Which must be true?

   1. The classes are pairwise disjoint
   2. Every element is in some class
   3. Each class has at least one element
   4. All classes have the same size
4. NAT

   How many relations are there on a 3-element set?

   Write your answer before opening the key.

5. MCQ

   Relation R₁ = “same remainder mod 8” and R₂ = “same remainder mod 4” on integers. Which is true?

   1. R₂ refines R₁
   2. R₁ refines R₂
   3. Neither refines the other
   4. They are the same relation

• relation
• function f : A → B, domain, codomain
• partial function
• function of two inputs (e.g. δ(mode, symbol))
• one-to-one, onto, bijection
• reflexive, symmetric, transitive
• equivalence relation
• equivalence class [a]
• partition
• index (number of classes)
• refinement

1. Number of functions from A to B?
   Reveal answer

   |B|^|A|
2. Three properties of an equivalence relation?
   Reveal answer

   Reflexive, symmetric, transitive.
3. What do equivalence classes form?
   Reveal answer

   A partition: disjoint, non-empty pieces covering the whole set.
4. What is the index of an equivalence relation?
   Reveal answer

   The number of its equivalence classes.
5. Number of relations on an n-element set?
   Reveal answer

   2^(n²)