Sets and set operations

Ask a database for all customers who bought in January or February and you get a union. Ask for those who bought in both and you get an intersection. Ask for January buyers who did not return in February and you get a difference. Set theory is not a topic that happens to resemble what your queries do — it is the thing your queries do, formalised in the 1870s by Georg Cantor and given a compact notation that has never needed replacing.

What a set is, and what it forgets

A set is an unordered collection of distinct objects, called its elements or members. Two words there do the work.

Unordered: position carries no information. Distinct: repetition carries none either. So {1, 2, 3}, {3, 1, 2} and {1, 2, 2, 3} are not three sets that happen to be similar — they are the same set, written three ways. Two sets are equal exactly when they have the same members, which is the axiom of extensionality: a set is nothing more than what is in it.

The only primitive relation is membership. Write x ∈ A for “x is an element of A”, and x ∉ A for “x is not”. Everything else is built from that one idea.

Sets are written two ways. Roster notation lists them: {2, 3, 5, 7}. Set-builder notation gives a rule: {x | x is prime and x < 10}, read “the set of all x such that …”. The vertical bar is “such that”, and sometimes a colon is used instead. Builder notation is not just a convenience — an infinite set like {x | x is even} cannot be listed at all.

The empty set

∅ is the set with no elements, and there is only one of it. Its cardinality is zero. It is also where most people’s first mistake lives: ∅ and {∅} are different. The second is a set with one element, and that element happens to be the empty set. An empty box and a box containing an empty box are not the same box.

Subsets

A ⊆ B means every element of A is also in B. Formally: x ∈ A implies x ∈ B, which makes ⊆ a conditional in disguise. Two consequences follow immediately from that reading:

• Every set is a subset of itself. The implication holds trivially.
• ∅ is a subset of every set. With no elements, no counterexample can exist — the same vacuous truth that makes an empty array pass an every() check.

A proper subset is a subset that leaves something out: A ⊂ B when A ⊆ B and A ≠ B. Be a little careful in the wild, because some authors use ⊂ for plain subset; ⊊ is the unambiguous symbol when the distinction matters.

Subsets also give the standard way to prove two sets equal: show A ⊆ B and B ⊆ A. Double inclusion forces equality, and it is the set-theoretic mirror of proving a biconditional in logic.

The operations

Each operation on sets is a logical connective applied to membership.

• Union A ∪ B = {x | x ∈ A ∨ x ∈ B} — in either, or both. Corresponds to or.
• Intersection A ∩ B = {x | x ∈ A ∧ x ∈ B} — in both. Corresponds to and. Sets with empty intersection are disjoint.
• Difference A \ B — in A but not in B. Also written A − B.
• Complement A' = U \ A — everything in the universal set U that is not in A. Corresponds to not, and it is meaningless until you say what the universe is.
• Symmetric difference A Δ B = (A ∪ B) \ (A ∩ B) — in exactly one of them. This is exclusive-or, and it is what a diff between two collections reports.

Because the operations are connectives, the logical laws carry straight across. De Morgan holds: the complement of a union is the intersection of the complements. Distribution holds: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). Draw two or three overlapping circles and the identities become visible rather than memorised — that is the whole purpose of a Venn diagram.

Counting: cardinality and the power set

The cardinality |A| is the number of elements. For finite sets, the inclusion-exclusion principle says |A ∪ B| = |A| + |B| − |A ∩ B|: adding the two counts double-counts the overlap, so you subtract it once. If 12 people know Python, 9 know SQL, and 4 know both, then 17 know at least one, not 21.

The power set P(A) is the set of all subsets of A, including ∅ and A itself. For A = {a, b}, the power set is {∅, {a}, {b}, {a, b}}. If |A| = n then |P(A)| = 2^n, because building a subset means making n independent in-or-out decisions. Each subset is a bitmask — which is exactly how permission flags work.

Finally, the Cartesian product A × B is the set of ordered pairs (a, b). Here order does matter, so it produces a different kind of object; its size is |A| × |B|, and it is precisely what a SQL CROSS JOIN returns.

Where the notation lands in code

Sets are a first-class data structure, and the operations map almost symbol for symbol.

const a = new Set([1, 2, 3]);
const b = new Set([3, 4]);

a.has(3);                          // membership: 3 ∈ A
new Set([...a, ...b]);             // union → 1,2,3,4
[...a].filter(x => b.has(x));      // intersection → 3
[...a].filter(x => !b.has(x));     // difference → 1,2
[...new Set(listWithDupes)];       // deduplicate

SELECT id FROM jan UNION     SELECT id FROM feb;  -- A ∪ B
SELECT id FROM jan INTERSECT SELECT id FROM feb;  -- A ∩ B
SELECT id FROM jan EXCEPT    SELECT id FROM feb;  -- A \ B

Python spells the same operations with operators: a | b, a & b, a - b, a ^ b, plus a <= b for subset. Tag filtering is intersection (“show posts tagged both rust and async”). An inner join is an intersection on key values; deduplication is just building a set.

The one habit worth forming is choosing the structure deliberately. A set answers “is this present?” in roughly constant time and forgets order and duplicates; a list answers “what is at position three?” and remembers both. Storing a ranked top-five in a set silently destroys the ranking. Storing a permission list in an array invites duplicates and slow lookups. Knowing which properties you actually need is the practical payoff of knowing what a set is.