Set Theory for Computing

AA surprising amount of computer science is set theory wearing a domain-specific costume. A type is a set of values a variable is permitted to hold; a database table is a set of rows; a graph's edges are a set of pairs; a regular expression describes a set of strings. Treating "set" as the common vocabulary underneath all four, rather than four unrelated ideas, is what set theory actually buys a working programmer — not a proof discipline for its own sake, but a small, precise notation that several very different-looking structures turn out to share. Halmos's classic treatment remains the standard, approachable route into the notation this page uses¹.

Basic Notation and Operations

AA set is an unordered collection with no duplicates — {1, 2, 3} and {3, 1, 2, 1} name exactly the same set. Everything else is built from a handful of operations on sets like this:

Notation	Reads as	Example
x ∈ S	x is a member of S	3 ∈ {1, 2, 3} is true
A ⊆ B	A is a subset of B — every member of A is also in B	{1, 2} ⊆ {1, 2, 3}
A ∪ B	union — everything in A or B or both	{1, 2} ∪ {2, 3} = {1, 2, 3}
A ∩ B	intersection — only what's in both	{1, 2} ∩ {2, 3} = {2}
A \ B	difference — what's in A but not B	{1, 2} \ {2, 3} = {1}
∅	the empty set — the unique set with no members	{1, 2} ∩ {3, 4} = ∅
|S|	cardinality — how many members S has	|{1, 2, 3}| = 3

None of this is exotic — it's the same handful of operations most languages expose directly as a set type (Python's set, Java's HashSet) with |, &, and - standing in for ∪, ∩, and \. What set theory adds beyond the library type is a precise way to describe a set without listing its members one at a time.

Set-Builder Notation

xX | P(x)} names the set of every x for which some condition P(x) holds — read the vertical bar as "such that." {x | x ∈ ℕ ∧ x < 5} is exactly {0, 1, 2, 3, 4}, described by a rule rather than a listing. That rule, P(x), is itself a small piece of logic — a predicate, true or false depending on x — and reasoning carefully about what predicates can say, and how to combine and quantify them, is its own subject: Predicate Logic picks up exactly here.

Relations and Functions as Sets

TheThe Cartesian product A × B is the set of every ordered pair (a, b) with a ∈ A and b ∈ B — for A = {1, 2} and B = {x, y}, A × B = {(1,x), (1,y), (2,x), (2,y)}. A relation between A and B is nothing more than a subset of A × B — some, not necessarily all, of the possible pairings — and a function f: A → B is a relation with two further restrictions: every a ∈ A appears in exactly one pair (total and single-valued), so looking up f(a) always gives one definite answer rather than none or several. This is the same set already covered from a different angle: a graph's edge set is literally a relation on its vertex set — a directed graph's edges are exactly a subset of V × V, no more and no less, and everything that page says about BFS, DFS, and traversal is really a statement about walking a particular relation.

Set Theory in the Relational Model

TheThe naming is not a coincidence: the relational model takes its name directly from "relation" in the set-theoretic sense above — a table is, in the strict theory, a set of tuples (no duplicate rows), and SQL's UNION, INTERSECT, and EXCEPT are exactly the ∪, ∩, and \ operations from the table above, applied to two tables with matching columns instead of two sets of numbers. A WHERE clause is set-builder notation with the serial numbers filed off: SELECT * FROM loans WHERE due_date < today is {row ∈ loans | due_date(row) < today}, a subset of the loans table carved out by a predicate — the same shape as the set-builder notation above, just spelled in SQL instead of mathematical notation. A JOIN goes a step further and is a filtered Cartesian product: conceptually, pair every row of one table with every row of another (loans × members, in the companion page's own example), then keep only the pairs a predicate accepts — usually loans.member_id = members.member_id — which is exactly the "subset of A × B" definition of a relation given above, applied at the row level instead of the value level.

Infinite Sets and Countability

NotNot every infinite set is the same size. The set of natural numbers ℕ and the set of even numbers are both infinite, yet there's a perfect one-to-one pairing between them (n ↔ 2n), so by the only definition of "same size" that makes sense for infinite sets, they're equal in size — countably infinite. Cantor's diagonal argument shows the set of all real numbers is not like this: no matter how a list of reals is arranged, a new real can always be constructed that differs from every entry on the list at at least one digit, proving no such pairing with ℕ can exist, and that the reals are a strictly larger kind of infinite — uncountable. This isn't a curiosity confined to pure mathematics: the same diagonal argument, applied to programs instead of numbers, is the core proof technique behind the halting problem's undecidability, and countability is exactly why a language with infinitely many possible programs can still enumerate them all (each has a finite text representation, so the set of programs is only countably infinite) while claiming to decide a property of every real-valued function cannot even get started (there are uncountably many of those).

References