Set theory basics

The formula

x ∈ A — the element x belongs to set A. Everything else is built on this one relation.

A ⊆ B — every element of A is also in B; A is a subset of B. Note it does not say B has anything extra.

A ∪ B = { x : x ∈ A or x ∈ B } — the union: everything in either set, counted once.

A ∩ B = { x : x ∈ A and x ∈ B } — the intersection: only what both sets share.

A′ = { x ∈ U : x ∉ A } — the complement: everything in the agreed universe U that is not in A. No universe, no complement.

A \ B = { x : x ∈ A and x ∉ B } — set difference: what A has that B doesn't. This is the "what did we miss" operator.

|A ∪ B| = |A| + |B| − |A ∩ B| — inclusion–exclusion: add the counts, then subtract the overlap you double-counted.

|P(A)| = 2^n — a set of n elements has 2^n subsets (its power set), counting the empty set and the whole set.

(A ∪ B)′ = A′ ∩ B′ and (A ∩ B)′ = A′ ∪ B′ — De Morgan's laws: complement swaps union with intersection. "Not (A or B)" means "not A and not B."

Where you meet it

The verification cross-reference matrix. Your spec is a set R of requirements. Each test procedure covers a subset. Coverage is the union of those subsets; the open items the review board asks about are R \ (T₁ ∪ T₂ ∪ … ∪ Tₖ). If two procedures both claim requirement 3.2.1.4, the intersection is why your coverage count doesn't equal the sum of the per-test counts.
Querying test data. Every SQL WHERE clause carves a subset out of a table; UNION, INTERSECT, and EXCEPT are the set operations by their own names, and an inner join is an intersection on key values. When a data-review script "loses" rows, the first question is which set operation dropped them.
Probability event spaces. Fault-tree and reliability math starts by defining the sample space U and treating failure events as subsets. P(A ∪ B) = P(A) + P(B) − P(A ∩ B) is inclusion–exclusion wearing a probability hat. Adding two failure probabilities without subtracting the joint term overstates risk — sometimes past 100%.
ICD and pin-list diffs. Rev C of an interface control document defines a set of signals; Rev D defines another. C \ D is what got deleted, D \ C is what got added, C ∩ D is what better still match. Half the value of a good diff tool is that it computes these three sets without arguing.

How it works

A set has two properties that trip people up on day one: it is unordered, and it has no duplicates. {5, 3, 3, 1} and {1, 3, 5} are the same set. That is exactly why sets model requirement coverage well (a requirement is covered or it isn't — covering it twice adds nothing) and why they model a test log badly (the log's order and repeats carry information; that's a sequence, not a set).

Inclusion–exclusion is the workhorse, and the classic mistake is skipping it. Suppose 412 requirements exist, thermal-vac testing covers 305 and vibration testing covers 214, with 131 verified by both. Coverage is 305 + 214 − 131 = 388, leaving 24 uncovered — not the "519 covered" a naive sum implies. The same error shows up when someone adds defect rates, market shares, or duty-cycle percentages that overlap. If the total comes out over 100%, the overlap term went missing.

Complements are only defined against a universe, and an unstated universe is a silent spec change. "All signals not on connector J1" means something different depending on whether U is the signals on that box or the signals on the whole vehicle. De Morgan's laws matter in the same practical way: the requirement "the unit shall not enter mode X or mode Y" forbids both modes ((X ∪ Y)′ = X′ ∩ Y′), and a surprising number of test procedures verify only one.

The power set is where set theory turns into a scheduling problem. n independent boolean options give 2^n configurations: 10 options is 1,024, 20 options is 1,048,576. That number is the honest answer to "why don't we just test every combination," and it is why combinatorial methods like pairwise testing exist — you cover the interactions that matter without enumerating the full power set.

Two notational potholes. First, ∈ versus ⊆: 3 is an element of {1, 3, 5}, but {3} — the set containing 3 — is a subset of it. Requirements databases confuse these constantly when a "requirement" is really a group. Second, the empty set ∅ is a subset of every set (there is no element in it to violate the condition), and ∅ is not the same object as {∅}, which is a one-element set. That distinction is pedantic right up until a script treats "no results" and "one empty result" identically.

Venn diagrams are the visualization, and they have a hard limit: three overlapping circles show all 8 regions of three sets, but no arrangement of four circles produces all 16 regions — four-set diagrams need ellipses or worse. Past three sets, trust the algebra, not the picture.

History

The pieces arrived out of order. Leonhard Euler was drawing overlapping closed curves to illustrate logical relationships in his 1768 Letters to a German Princess ^[3]^[4], a century before anyone had a theory of sets to illustrate. George Boole supplied the algebra in 1854 with An Investigation of the Laws of Thought, reducing logic to symbol manipulation ^[7]^[8] — though the clean union–intersection–complement algebra now called Boolean was polished by his successors over the following decades ^[8].

Set theory proper begins with Georg Cantor. His 1874 paper proved that the real numbers cannot be listed against the integers — some infinities are strictly bigger than others — and that result is generally taken as the founding of set theory as a mathematical subject ^[1]^[2]. In 1880, John Venn published the diagram scheme that fixed a defect in Euler's circles, developing it fully in his 1881 Symbolic Logic ^[3]^[4].

Then the foundation cracked. In 1901 Bertrand Russell considered the set of all sets that are not members of themselves — which is a member of itself exactly when it isn't — and in June 1902 mailed the paradox to Gottlob Frege as Frege's life's work on logical foundations was going to press ^[5]^[6]. Ernst Zermelo had noticed essentially the same contradiction independently around the same period ^[5]^[6]. Zermelo's repair, published in 1908, was to axiomatize which collections count as sets, restricting the unrestricted "any property defines a set" principle ^[5]^[6]; his axioms grew into the ZFC system that quietly underwrites the everyday set operations engineers use without incident.

The engineering takeaway from the paradox era is modest and useful: naive set-building works fine as long as you define your universe first and build subsets of it. Every trouble case in the history books came from sets defined with no universe at all.

Related tools

/tools/adc-resolution — the 2^N code count of an N-bit converter is the same counting rule as the power set: each bit doubles the set of possibilities.
/tools/resistor-e-series — the E-series are standardized finite sets of component values; picking the nearest standard part is a membership test.

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →