Set Theory

Definition: The branch of mathematical logic that studies collections of distinct objects, called elements, and the operations that combine and compare them.

How It Works

A set is an unordered collection of distinct elements, {1, 2, 3} and {3, 1, 2} are the same set, and duplicates collapse, {1, 1, 2} = {1, 2}
Union A ∪ B: every element in A, in B, or in both. Intersection A ∩ B: only elements in both A and B. Difference A \ B: elements in A but not in B. Complement A': everything in the universal set not in A
Set membership (x ∈ A) asks whether x is one of A’s elements, subset (A ⊆ B) asks whether every element of A is also in B, a fundamentally different, higher-level question
The Power Set P(A) is the set of all possible subsets of A, including the empty set and A itself, and always has exactly 2^n elements for a set of size n
The Cartesian Product A × B is the set of all ordered pairs (a, b) with a ∈ A and b ∈ B, with |A × B| = |A| × |B|
Two sets are equal if and only if they contain exactly the same elements, proven formally by showing A ⊆ B and B ⊆ A both hold
The empty set ∅ is a subset of every set, including itself, and every set is a subset of itself, both immediate consequences of the subset definition applied vacuously or trivially
Set-builder notation, {x | P(x)}, defines a set as “every x satisfying property P,” the standard way to define sets too large or complex to list element by element
Venn diagrams are the visual counterpart to these operations, overlapping circles make union, intersection, and difference immediately visible, which is why the flowchart-style pipeline below and a Venn diagram describe the same underlying operations from two different angles
De Morgan’s Laws apply to sets exactly as they do to logic: (A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'
Two sets are disjoint if their intersection is empty, A ∩ B = ∅, meaning they share no elements at all

Common Set Notation

Symbol	Meaning	Example
`∈`	Element of	`3 ∈ {1,2,3}`
`∉`	Not an element of	`5 ∉ {1,2,3}`
`⊆`	Subset of (including equal)	`{1,2} ⊆ {1,2,3}`
`⊂`	Proper subset (strictly smaller)	`{1,2} ⊂ {1,2,3}`
`∅`	Empty set	The set with zero elements
`\|A\|`	Cardinality (size) of set A	`\|{1,2,3}\| = 3`

Under the Hood

Each operation is a separate, well-defined pipeline stage taking the same two inputs, A = {1,2,3,4} and B = {3,4,5,6}, and producing a different result. Union collects everything from either set, duplicates (3 and 4, present in both) counted once. Intersection keeps only what’s shared. Difference keeps only what’s exclusively in A, discarding both the shared elements and everything unique to B.

Notice |A ∪ B| = 6 isn’t simply |A| + |B| = 8, because the shared elements {3,4} would be double-counted. The correct relationship is the Inclusion-Exclusion formula: |A ∪ B| = |A| + |B| - |A ∩ B| = 4 + 4 - 2 = 6, matching the diagram exactly. This correction generalizes directly to three or more overlapping sets.

Every set operation shown here is itself defined in terms of set-builder notation and logical connectives: A ∪ B = {x | x ∈ A ∨ x ∈ B}, A ∩ B = {x | x ∈ A ∧ x ∈ B}, and A \ B = {x | x ∈ A ∧ x ∉ B}. This is why Propositional and Predicate Logic and set theory are so tightly linked, every set operation is, underneath, a logical connective applied to membership tests.

Worked Example 1

Given: A = {1,2,3,4}, B = {3,4,5,6}. Compute A ∪ B, A ∩ B, and A \ B.
Step: Union combines all unique elements from both. Intersection keeps only shared elements. Difference keeps A’s elements not present in B.
Answer: A ∪ B = {1,2,3,4,5,6}, A ∩ B = {3,4}, A \ B = {1,2}.

Worked Example 2

Given: Find the power set of A = {x, y, z}.
Step: List every possible subset: the empty set, all singletons, all pairs, and the full set. There should be 2^3 = 8 total.
Answer: P(A) = {∅, {x}, {y}, {z}, {x,y}, {x,z}, {y,z}, {x,y,z}}, exactly 8 subsets.

Worked Example 3

Given: A = {1, 2}, B = {a, b, c}. Compute A × B and verify |A × B| = |A| × |B|.
Step: Pair every element of A with every element of B: (1,a),(1,b),(1,c),(2,a),(2,b),(2,c).
Answer: A × B = {(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)}, 6 pairs total, matching |A| × |B| = 2 × 3 = 6.

Worked Example 4

Given: Verify De Morgan’s Law for sets, (A ∪ B)' = A' ∩ B', using universal set U = {1,2,3,4,5}, A = {1,2,3}, B = {2,3,4}.
Step: A ∪ B = {1,2,3,4}, so (A ∪ B)' = {5}. Separately, A' = {4,5} and B' = {1,5}, so A' ∩ B' = {5}.
Answer: Both sides equal {5}, confirming (A ∪ B)' = A' ∩ B' for this example, consistent with the general law.

Worked Example 5

Given: Determine whether {1,2} ⊆ {1,2,3} and whether 1 ∈ {1,2,3}, and explain why these are different kinds of questions.
Step: {1,2} ⊆ {1,2,3} asks whether every element of {1,2} also appears in {1,2,3}, both 1 and 2 do, so the subset relationship holds. 1 ∈ {1,2,3} asks whether the single element 1 appears in the set, which it does.
Answer: Both statements are true, but ⊆ compares a set to a set, while ∈ compares an element to a set, confusing the two is a common source of errors when nesting sets of sets.

Why It Matters

Underpins relational database theory directly, SQL’s INNER JOIN corresponds to set intersection, UNION to set union, and EXCEPT/MINUS to set difference
Provides the formal basis for programming data structures, Set, Map, and Dictionary types all implement the mathematical definitions of set membership and mapping
Gives precise language for describing valid input domains and edge cases in software specifications, “the input is an element of the empty set” is a precise, checkable way to describe an impossible or unreachable case
Gives every other branch of discrete math its vocabulary, relations, functions, and graphs are all formally defined as specific kinds of sets
Powers query optimization, a database engine reasons about which set operation (intersection versus union versus difference) is cheapest before choosing a query execution plan
Makes deduplication and merging logic precise, combining two data sources into one without duplicate rows is a direct application of set union
Underlies type theory in programming languages, a union type (string | number) and an intersection type both borrow their names and behavior directly from set operations

Common Pitfalls

Confusing element membership (x ∈ A) with subset inclusion ({x} ⊆ A), these are different relationships at different levels, x is an element, {x} is a set containing that element
Computing |A ∪ B| as |A| + |B| without subtracting the overlap |A ∩ B|, double-counting any elements shared between the two sets
Forgetting the empty set ∅ and the full set A itself both count as valid subsets of A when listing a power set, easy to accidentally omit one or both
Mixing up ⊆ (subset, possibly equal) with ⊂ (proper subset, strictly smaller), a distinction that matters in proofs but is often glossed over informally
Assuming the Cartesian product is commutative, A × B and B × A contain the same number of pairs but generally different pairs, (1,a) ≠ (a,1)
Assuming set operations behave like arithmetic operations, union and intersection are commutative and associative like addition and multiplication, but they also distribute over each other in both directions, a property arithmetic addition and multiplication don’t share
Treating A \ B as symmetric like union and intersection, difference is order-dependent, A \ B and B \ A are generally different sets entirely

Comparison

	Union (∪)	Intersection (∩)	Difference (\)	Complement (’)
Keeps	Everything in either set	Only shared elements	Only A’s exclusive elements	Everything outside A
Needs a universal set	No	No	No	Yes
Symmetric (A op B = B op A)	Yes	Yes	No	N/A, single operand
Identity element	`∅` (`A ∪ ∅ = A`)	Universal set `U` (`A ∩ U = A`)	N/A	N/A
SQL equivalent	`UNION`	`INNER JOIN` / `INTERSECT`	`EXCEPT` / `MINUS`	`NOT IN`
Notation	`A ∪ B`	`A ∩ B`	`A − B` or `A \ B`	`A'` or `Aᶜ`

Example

SQL INNER JOIN corresponds to set intersection, matching only rows present in both tables by a shared key, while UNION corresponds to set union, combining rows from both queries and removing duplicates, exactly like the mathematical union operation discards duplicate elements.

Georg Cantor founded set theory in the 1870s and proved, controversially at the time, that infinite sets come in different sizes, the set of real numbers is strictly larger than the set of natural numbers, despite both being infinite, a result that reshaped the foundations of modern mathematics.

Referenced by

Dig deeper

Spot an error in this note?