What Is a Set? The Mathematics Behind Deduplication

The Definition

In mathematics, a set is a collection of distinct objects, called elements or members. The defining property of a set is that each element appears exactly once. There is no concept of multiplicity — an element is either in the set or it is not. The set {A, B, C} and the set {A, A, B, C} are, mathematically, identical — both contain exactly three elements.

This is deduplication in its purest mathematical form. When you remove duplicate lines from a list, you are converting a sequence (where repetitions are meaningful and ordered) into a set (where only membership matters).

Georg Cantor and the Birth of Set Theory (1874)

Set theory as a formal mathematical discipline was created by Georg Cantor, a German mathematician, in the 1870s. Before Cantor, mathematicians worked with collections of objects informally. Cantor's contribution was to make the concept of infinity mathematically rigorous — and to do so, he needed a precise language for talking about collections.

Cantor's 1874 paper introduced the radical idea that there are different sizes of infinity. The set of natural numbers (1, 2, 3, ...) and the set of real numbers (all decimal numbers) are both infinite — but the real numbers are a larger infinity than the natural numbers. Cantor proved this using what is now called the diagonal argument — a technique that later became fundamental in computing theory (Alan Turing used it to prove that some problems cannot be computed).

For our purposes, the important legacy of Cantor is the formalism: sets have clear rules, set membership is binary (in or out), and sets cannot contain duplicates by definition.

Set Operations: The Core Four

Four fundamental operations define how sets relate to each other. These operations map directly to common text and data processing tasks:

Union (A ∪ B)

The union of two sets contains every element that appears in either set — with no duplicates. If Set A = {cat, dog, bird} and Set B = {dog, fish, rabbit}, then A ∪ B = {cat, dog, bird, fish, rabbit}. The "dog" appears only once even though it was in both sets.

In practice: combining two mailing lists and removing duplicates is set union. Combining two keyword lists is set union.

Intersection (A ∩ B)

The intersection contains only elements that appear in both sets. A ∩ B from the example above = {dog} — only "dog" appears in both. In practice: finding which customers appear in both "purchased in the last 30 days" and "opened last email" lists is set intersection.

Difference (A − B)

The difference A − B contains elements that are in A but not in B. From the example: A − B = {cat, bird}. In practice: finding which users are on a suppression list (remove from A anyone who is in B) is set difference.

Symmetric Difference (A △ B)

The symmetric difference contains elements that are in one set but not both — the "exclusive or" of set theory. A △ B = {cat, bird, fish, rabbit}. In practice: finding items that changed between two versions of a list (things added or removed) is symmetric difference.

Sets in Programming Languages

Every major programming language provides a set data structure precisely because the "unique elements only" property is so commonly needed:

• Python: set() — created from any iterable, automatically deduplicates. set(["a", "b", "a", "c"]) produces {'a', 'b', 'c'}.
• JavaScript: Set — new Set(["a", "b", "a", "c"]) produces a Set containing "a", "b", "c". Convert back to array with [...mySet].
• Java: HashSet<T> and TreeSet<T> — the former gives O(1) average lookup, the latter maintains sorted order.
• SQL: DISTINCT keyword in queries returns a set (no duplicate rows) rather than a multiset.

The performance of set operations matters significantly at scale. A naive deduplication algorithm — check each element against all previous elements — runs in O(n²) time. Hash-based sets (which use a hash function to map elements to buckets) achieve O(n) deduplication, making them practical for millions of elements.

Multisets: When Duplicates Have Meaning

A related concept is the multiset (also called a bag) — a collection like a set, but where each element can appear multiple times and the count matters. The multiset {a, a, b, c} is different from {a, b, c} because it records that "a" appears twice.

Multisets are useful for frequency analysis — counting how many times each word appears in a document, or how many times each value appears in a dataset. Python's collections.Counter is a multiset implementation; SQL's GROUP BY with COUNT() produces multiset-style output.

The distinction between set and multiset is the deduplication question in formal terms. When you remove duplicate lines from text, you are converting a multiset (a sequence with possible repetitions) to a set (unique elements only, order optionally preserved or discarded).

Sets in Search and Indexing

Search engines use inverted indices — data structures that map each term to the set of documents that contain it. When you search for two terms, the search engine computes the intersection of their document sets to find documents containing both. Boolean operators (AND, OR, NOT) map directly to set operations (intersection, union, difference).

The mathematical clarity of set theory is what makes information retrieval systems precise and predictable. A search result is the set of documents satisfying the query — no duplicates, well-defined, and computable efficiently with the right data structures.

Remove duplicates from any list →