[Beginner → Intermediate] — The vocabulary for describing structure, and the mathematical object a relational database is named after.

Sets

An unordered collection of distinct elements. No duplicates, no order.

That’s exactly a HashSet — the language feature is the mathematical object.

Set-builder notation, which you also already use:

“The set of integers such that is positive and even.” Compare:

{x for x in ints if x > 0 and x % 2 == 0}

Python’s set comprehension is set-builder notation with ASCII. The syntax was borrowed deliberately.

The standard sets: naturals, integers, rationals, reals, the empty set.

Operations

OperationNotationSQL / code
UnionUNION
IntersectionINTERSECT
DifferenceEXCEPT
ComplementNOT IN
Cartesian productCROSS JOIN
Power setall subsets

Cardinality is the number of elements.

Two facts worth carrying:

The power set of an -element set has elements — because each element is independently in or out, one binary choice each. This is why brute-forcing “try every subset” is exponential and why subset problems are hard. → Complexity Classes

Set operations obey the same algebra as logic — union is , intersection is , complement is . De Morgan’s laws hold verbatim:

That’s not a coincidence: both are Boolean algebras. → Logic

Infinite sets and countability

A genuinely surprising corner, and it matters for decidability.

Two sets have the same size if a bijection exists between them. That definition is uncontroversial for finite sets and produces strange results for infinite ones.

Countably infinite — same size as . The integers are countable (list them ), and so are the rationals, despite being dense.

The reals are not. Cantor’s diagonal argument: suppose you could list every real in . Construct a new number whose th digit differs from the th digit of the th number on your list. It differs from every entry, so it wasn’t on the list. Contradiction.

Why a programmer should care. Programs are countable — each is a finite string, and finite strings over a finite alphabet are countable. Functions from to are uncountable.

So there are strictly more problems than programs. Most functions are not computable, and not because we haven’t found the algorithm — no algorithm exists. That’s a counting argument, and it’s the cleanest way to see why undecidability isn’t surprising.

Relations

A relation between and is a subset of — a set of ordered pairs.

That’s the whole definition, and it’s more general than it sounds. “Less than” on integers is the set of pairs with . “Is a parent of” is a set of pairs of people.

A database table is a relation. Rows are tuples, the table is a subset of the product of its column domains. This is literally where “relational database” comes from — Codd’s 1970 paper. SELECT is projection, WHERE is selection, JOIN is a restricted product. → Databases

Properties

For a relation on a set :

PropertyMeansExample
Reflexive for all ,
Symmetric, “is a sibling of”
Antisymmetric,
Transitive, ,

These aren’t trivia — two combinations define the two most important kinds of structure.

Equivalence relations

Reflexive + symmetric + transitive. Equality, “same remainder mod ”, “same connected component”.

An equivalence relation partitions its set into disjoint equivalence classes covering everything. Partition and equivalence relation are two views of the same thing.

Where it shows up: hashing (buckets are classes under “same hash”), modular arithmetic ( is the set of classes), union-find (maintaining classes under merging), type unification, and the Myhill–Nerode theorem, where states of a minimal automaton are equivalence classes.

And the equals() contract in Java or Eq in Rust is exactly these three axioms. Violating transitivity — easy to do with a “fuzzy” comparison — breaks hash sets in ways that look like memory corruption.

Partial orders

Reflexive + antisymmetric + transitive. , , divisibility, “depends on”.

“Partial” because some elements are incomparable. Under , and have no relationship. In a total order, everything is comparable.

Where it matters:

  • Dependency graphs. A build’s task order is a partial order, and topological sort extends it to a total order — that’s exactly what topological sorting is
  • Version constraints, semver ranges
  • Happens-before in distributed systems — the canonical partial order. Concurrent events are simply incomparable, and Lamport’s whole point is that physical time forces a false total order onto a genuinely partial one
  • Lattices — partial orders where every pair has a least upper bound. The basis of CRDTs and of dataflow analysis in compilers

Closures

The transitive closure of adds every pair reachable by a chain. Given “directly depends on”, the transitive closure is “depends on, however indirectly”.

Computed by Floyd–Warshall or repeated traversal, and it’s what you want for full dependency resolution or reachability. → Graphs

Functions

A function is a relation where every element of maps to exactly one element of .

“Exactly one” is the whole content. A relation may pair 5 with three things; a function may not. This is why a function is deterministic — same input, same output — and why an impure function isn’t a function in this sense.

Domain , codomain , range the subset actually hit.

Injective, surjective, bijective

MeansConsequence
Injective (one-to-one)distinct inputs → distinct outputsno collisions
Surjective (onto)every element of is hitrange = codomain
Bijectivebothinvertible

Only bijections have inverses. That’s why:

  • Encryption must be bijective — otherwise decryption is ambiguous → Symmetric Encryption
  • Hash functions are deliberately not injective — a fixed output size mapping arbitrary inputs must collide, by pigeonhole. Collisions are mathematically guaranteed; a good hash just makes them hard to find on purpose → Hashing
  • Lossless compression cannot shrink every input. It’s a bijection between the same two countable sets, so if some strings get shorter, others must get longer. This is a proof, not an engineering limitation — every “compresses any file by 50%” claim is provably false

Composition is associative — which is why function pipelines compose freely, and the observation that a monoid of endofunctions underlies a lot of functional programming.

Where this pays off

Databases — the relational model, normalisation (functional dependencies are literally functions between attribute sets), and set operations as query operators.

Type systems — a type is a set of values, and a function type is a set of functions. Subtyping is . → Type Systems

Collections — Set, Map, and the equals/hashCode contract as equivalence-relation axioms.

Graphs — a graph is a set of vertices plus a relation on them. → Graph Theory

Distributed systems — partial orders, lattices, and CRDT merge as a least-upper-bound operation.


↑ Back to Discrete Mathematics