Sets are the basic language of almost all of discrete mathematics: relations, functions, graphs and probability are all defined in terms of them. For anyone who works with data they are also an everyday tool, because comparing two lists and finding the elements they share or lack is exactly a set operation.
What a set is
A set is a collection of distinct objects, called elements, in which neither order nor repetition matters. {1, 2, 3}, {3, 1, 2} and {1, 1, 2, 3} are the same set.
A set can be described in two ways:
- by listing: A = {red, green, blue};
- by property: B = {x ∈ ℤ | 0 < x < 10 and x is even} = {2, 4, 6, 8}.
The symbol ∈ denotes membership: 4 ∈ B, while 5 ∉ B. The set with no elements is the empty set, ∅. The number of elements of a finite set is its cardinality, written |A|: here |A| = 3.
Inclusion and equality
A is a subset of B (A ⊆ B) if every element of A also belongs to B. Two sets are equal if and only if A ⊆ B and B ⊆ A: this is precisely the standard method for proving that two sets coincide, showing the two inclusions separately.
Some useful facts:
- ∅ is a subset of every set (it has no elements that could violate the condition).
- Every set is a subset of itself.
- If A ⊆ B and B ≠ A, A is a proper subset of B, written A ⊂ B.
Do not confuse ∈ with ⊆: 1 ∈ {1, 2}, but {1} ⊆ {1, 2}. And {1} ∈ {{1}, 2}, but {1} is not a subset of {{1}, 2}, because the element 1 does not appear in the latter.
The basic operations
Let A and B be subsets of a universe U.
| Operation | Symbol | Elements | Logical counterpart |
|---|---|---|---|
| Union | A ∪ B | in A or in B | ∨ |
| Intersection | A ∩ B | in A and in B | ∧ |
| Difference | A ∖ B | in A but not in B | p ∧ ¬q |
| Symmetric difference | A △ B | in exactly one of them | ⊕ (XOR) |
| Complement | Aᶜ | in U but not in A | ¬ |
The last column is no coincidence. Every set operation corresponds to a logical connective applied to the membership condition: x ∈ A ∩ B if and only if x ∈ A ∧ x ∈ B. That is why every law of propositional logic has a set-theoretic counterpart. De Morgan's laws, for instance, become:
- (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
- (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ
Two sets are called disjoint if A ∩ B = ∅.
Venn diagrams
A Venn diagram represents each set as a closed region inside a rectangle that stands for the universe. With two sets there are four regions: only A, only B, both A and B, neither. With three sets there are eight, one for each combination of "inside" and "outside".
Diagrams help you sense that an equality holds, but they do not prove it in general: the proof uses inclusions or algebraic laws. Beyond three or four sets they become hard to read.
A practical example
Suppose we have the list of accounts registered on a system and the list of accounts that have logged in during the last 90 days. In Python:
registered = {"anna", "bruno", "carla", "dario", "elena"}
active = {"anna", "carla", "elena", "fabio"}
registered & active # {'anna', 'carla', 'elena'} regular logins
registered - active # {'bruno', 'dario'} dormant accounts
active - registered # {'fabio'} anomaly to check
registered ^ active # {'bruno', 'dario', 'fabio'} all discrepancies
The two differences mean very different things. Dormant accounts are candidates for deactivation; a login from an unregistered account is an inconsistency that, in a security analysis, needs explaining. Comparing sets this way is one of the simplest and most useful checks I know when verifying that two data sources agree.
Python sets are implemented with hash tables, so checking membership takes constant time on average. Searching for an element in a list, by contrast, means scanning it. On long lists the difference is huge.
Algebraic properties
Union and intersection are commutative and associative, and each distributes over the other:
- A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
- A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
The absorption laws also hold, A ∪ (A ∩ B) = A and A ∩ (A ∪ B) = A, along with a useful identity for differences: A ∖ B = A ∩ Bᶜ.
In short
- A set ignores order and repetition; ∈ denotes membership, ⊆ inclusion.
- To prove A = B, show both inclusions A ⊆ B and B ⊆ A.
- Union, intersection, difference and complement correspond to ∨, ∧, ∧¬ and ¬.
- The laws of logic, De Morgan's included, hold identically for sets.
- In data work, intersections and differences reveal shared, missing and anomalous elements.
