Sets, Relations, and Functions You Will Need

Why a Math Toolkit Comes First

In the previous rung you met the raw materials of this whole subject: an alphabet Σ (Sigma, just a finite set of symbols), strings built from it, and a language as a set of strings. Notice that almost every one of those words is the word set. A set is simply a collection of distinct things with no particular order — like the set of letters {a, b}, or the set of all strings over that alphabet. Before we can build machines that recognize languages, we need to be comfortable handling the sets, relations, and functions those machines are secretly made of.

Think of this guide as packing your backpack before a hike. None of these ideas is hard on its own, but later you will run a deterministic finite automaton whose whole definition is a function from (state, symbol) pairs to states; you will prove two strings are 'the same as far as a machine can tell' using an equivalence relation; and you will discover, with a single dazzling argument, that some languages cannot be recognized by any machine at all. Every one of those moments leans on exactly the tools below.

Sets, Their Operations, and Cartesian Products

You combine sets with a few everyday operations. The union A ∪ B gathers everything in either set; the intersection A ∩ B keeps only what is in both; the difference A − B keeps what is in A but not B; and the complement is everything (within some agreed universe) that is not in A. These are not abstract decorations: later, the fact that regular languages are closed under union and complement is exactly what lets you build one machine out of two, so getting the operations into your fingers now pays off directly.

Two more set ideas show up constantly. The power set of A is the set of all subsets of A; if A has n elements, its power set has 2^n elements — remember that number, because it is exactly why turning an n-state nondeterministic automaton into a deterministic one can produce up to 2^n states. The other is the Cartesian product A × B: the set of all ordered pairs (a, b) with a from A and b from B. A transition like delta(q, a) = p is really just reading off a value for the pair (q, a) drawn from States × Σ, so the Cartesian product is the natural home of every transition you will ever write.

Relations: The Equivalence Relation You Cannot Skip

A relation on a set A is nothing more than a chosen subset of A × A — a list of which pairs count as 'related'. The relation 'x is less than y' on numbers, or 'string x is a prefix of string y', are everyday examples. Most relations have no special structure, but one special kind, the equivalence relation, is worth a whole guide on its own because it captures the idea of 'same in some respect'. A relation ~ is an equivalence relation when it is reflexive (every x ~ x), symmetric (if x ~ y then y ~ x), and transitive (if x ~ y and y ~ z then x ~ z).

Here is the magic. Any equivalence relation on A automatically chops A into non-overlapping clumps called equivalence classes — each clump holds exactly the elements that are equivalent to one another, and together the clumps cover all of A with no overlaps. This clean carving-up is called a partition. Think of sorting a pile of socks 'by color': every sock lands in exactly one color-pile, no sock is in two piles, and no pile is empty. The color-piles are the equivalence classes; 'same color' is the equivalence relation.

Why care so much? Because the deepest theorem about regular languages — the Myhill–Nerode theorem you will meet a few rungs up — works by declaring two strings equivalent when no continuation can ever tell them apart, then counting the resulting classes. Each class becomes one state of the smallest possible machine. The equivalence class is, quite literally, the seed of a state, so the time you spend on this idea now is repaid many times over.

Functions, Graphs, and Trees

A function f from A to B assigns to each input in A exactly one output in B — no input is left dangling, and none gets two answers. The transition function of a deterministic automaton is precisely this: feed it a (state, symbol) pair and it hands back exactly one next state, delta(q, a) = p. That 'exactly one' is the whole meaning of deterministic. Three adjectives sharpen the picture: a function is injective (one-to-one) if different inputs never collide on the same output; surjective (onto) if every possible output is actually hit; and bijective if it is both, which means inputs and outputs pair off perfectly. We will lean hard on bijections soon, because a bijection is the gold standard for saying two sets are 'the same size'.

The pictures you will draw are mostly graphs and trees. A graph is a set of nodes joined by edges; a state diagram of an automaton is exactly a graph whose nodes are states and whose labeled arrows are transitions. A tree is a special graph with a single root and no cycles, so every node has exactly one path back to the root. Parse trees — the diagrams showing how a grammar generates a string — are trees in this precise sense, and so are the branching computations of a nondeterministic machine, where each branch is one 'guess'. Recognizing these two shapes will make later diagrams feel familiar rather than foreign.

States = {even, odd}        (count of a's so far, mod 2)
start = even,  accept = {even}

    delta | a     | b
    ------+-------+------
    even  | odd   | even
    odd   | even  | odd

run on "abba":  even --a--> odd --b--> odd --b--> odd --a--> even   ACCEPT

Countable vs Uncountable — and Why Some Languages Are Unreachable

Now the idea that makes the whole subject possible. Two sets have the same size if there is a bijection between them — a perfect pairing with no leftovers on either side. A set is countable if you can pair it up with the counting numbers 1, 2, 3, … so that every element eventually gets a number. Strikingly, the set of all strings over any alphabet is countable: list them shortest first, breaking ties alphabetically, and every string appears at some finite position. The set of all programs (or all automata) is countable for the same reason — each is just a finite string of symbols.

But how many languages are there? A language is a set of strings — a subset of the countable set of all strings — so the collection of all languages is the power set of a countable set. Georg Cantor showed by his famous diagonalization argument that this power set is uncountable: strictly bigger than the counting numbers, so no list can ever contain all of them. Here is the punchline, lining up two facts you already have: there are only countably many machines, but uncountably many languages. A smaller set cannot be paired one-for-one with a strictly larger set, so most languages have no machine. Some languages simply cannot be recognized by any computer — not because we are not clever enough, but because there is literally nothing left to assign to them.

1. Suppose, for contradiction, that you could list all languages over Σ as L1, L2, L3, … with the strings themselves also listed as s1, s2, s3, …
2. Build a brand-new language D by a rule that disagrees with the list on the diagonal: put string si into D exactly when si is NOT in Li.
3. Now D cannot equal any Lk on the list — it was deliberately built to differ from Lk on the single string sk (membership of sk is flipped).
4. So D is a real language that the list missed: the list was not complete after all, and no list can be. The languages are uncountable, hence beyond the reach of the countably many machines.

Be careful what this does and does not say. It does not name a specific unrecognizable language, and it does not mean computers are weak — it is a pure counting fact about sizes. The exact same diagonalization, aimed at machines instead of an arbitrary list, is what later proves the halting problem undecidable. Mastering the small move now means that famous result will feel less like a magic trick and more like an old friend.