a set

A set is just a collection of things, with no repeats and no order — like a bag of distinct objects where all that matters is whether something is inside or not. Think of the guest list for a party: the question is never how many times a name appears or in what order it was written, only whether each person is on the list. In the theory of computation almost everything is a set: an alphabet is a set of symbols, a language is a set of strings, and a finite automaton has a set of states.

We write a set by listing its members inside curly braces, for example {a, b, c}, or by describing them with a rule, for example {n : n is an even number}, read as 'the set of all n such that n is even'. The basic question we ask is membership: we write x ∈ S (read 'x is an element of S', the ∈ being the membership symbol) to say x is in the set S, and x ∉ S to say it is not. One special set, the empty set ∅ (written {} or with the symbol ∅), has no members at all; it is not 'nothing', it is a real set that happens to be empty, the way an empty bag is still a bag. We say a set A is a subset of B, written A ⊆ B (the ⊆ being the subset symbol), when every element of A is also in B.

Sets matter because they let us be exactly precise about messy ideas. When we later say 'a deterministic finite automaton accepts the language L', we mean L is a particular set of strings, and the machine's job is to answer the membership question 'is this string in L?' for every possible input. Two sets are equal exactly when they have the same members — so {a, b} and {b, a, a} are the same set, since order and repetition do not count.