Sets

A set is a well-defined collection of distinct objects, considered as a single whole. Sets are the foundational language of modern mathematics: nearly every mathematical object — numbers, functions, relations, spaces — is defined in terms of sets. Developed rigorously by Georg Cantor in the 1870s–1880s, set theory underlies all of contemporary mathematics, computer science, logic, and probability.

A set is a collection of distinct objects, called its elements or members, in which order and repetition are irrelevant — only membership matters. Two sets are equal exactly when they contain the same elements. Sets matter because they provide a single, unified language in which all of mathematics can be expressed: integers, geometric points, and even functions are ultimately built from sets. A surprising fact is that there are different sizes of infinity — the set of real numbers is provably "larger" than the set of natural numbers, even though both are infinite, a discovery that shocked mathematicians and remains a cornerstone of the subject.

The Core Insight

A set is determined entirely by what belongs to it — nothing else. There is no notion of "first element," no concept of an element appearing "twice," and no internal structure beyond membership. This radical simplicity is exactly what makes sets powerful: from the single relation " $x$ belongs to $A$ " we can build the entire edifice of mathematics.

Formal Statement

Set and Membership

A set is a collection of distinct objects. If an object $x$ is a member of a set $A$ , we write

x \in A

⟳This is the primitive (undefined) relation of set theory; "

\in

" is read "is an element of."

If $x$ is not a member, we write $x \in / A$ . A set may be specified by listing (roster notation), as in $A = {1, 2, 3}$ , or by a defining property (set-builder notation):

A = {x ∣ P (x)}

⟳Read "the set of all

x

such that

P (x)

is true"; the vertical bar means "such that."

Set Equality — The Axiom of Extensionality

Two sets $A$ and $B$ are equal if and only if they have exactly the same elements:

A = B ⟺ \forall x (x \in A ⟺ x \in B)

⟳Equality depends only on membership — not on how the set is described, ordered, or written.

A consequence: ${1, 2, 2, 3} = {3, 1, 2}$ , since repetition and order do not affect membership.

Subset and Power Set

A

is a subset of

B

, written

A \subseteq B

, if every element of

A

is also an element of

B

A \subseteq B ⟺ \forall x (x \in A ⟹ x \in B)

⟳Universally quantify the implication "member of

A

⟹ member of

B

The power set $P (A)$ is the set of all subsets of $A$ . For a finite set with $n$ elements,

∣ P (A) ∣ = 2^{n}

⟳Each element is either in or out of a subset — two choices per element, multiplied over

n

elements.

Core Operations

For sets $A$ and $B$ within a universe $U$ :

A \cup B = {x ∣ x \in A or x \in B}

⟳The union collects everything in either set; "or" is inclusive.

A \cap B = {x ∣ x \in A and x \in B}

⟳The intersection keeps only the common elements.

A ∖ B = {x ∣ x \in A and x \in / B}

⟳Set difference removes from

A

everything that lies in

B

A^{c} = U ∖ A = {x \in U ∣ x \in / A}

⟳The complement is everything in the universe not in

A

De Morgan's Laws for Sets

For any sets $A, B$ in a universe $U$ :

(A \cup B)^{c} = A^{c} \cap B^{c}, (A \cap B)^{c} = A^{c} \cap ?

(A \cap B)^{c} = A^{c} \cup B^{c}

⟳Negating "in

A

B

" gives "not in

A

and not in

B

"; negating "and" gives "or."

Why It Holds / Derivation

De Morgan's First Law, Equation 10

We show $(A \cup B)^{c} = A^{c} \cap B^{c}$ using the Axiom of Extensionality — i.e. by proving both sets have the same elements.

Step 1. Take any

x \in (A \cup B)^{c}

. By definition of complement,

x \in / A \cup B

. Step 2. By definition of union,

x \in / A \cup B

means it is not the case that (

x \in A

x \in B

). Step 3. By the logical equivalence

\neg (p \lor q) \equiv (\neg p \land \neg q)

, this means

x \in / A

and

x \in / B

. Step 4. Therefore

x \in A^{c}

and

x \in B^{c}

, so

x \in A^{c} \cap B^{c}

. This shows

(A \cup B)^{c} \subseteq A^{c} \cap B^{c}

. Step 5. Every step above is an if and only if, so reading them in reverse gives

A^{c} \cap B^{c} \subseteq (A \cup B)^{c}

. Step 6. Mutual inclusion plus Extensionality (Equation 3) gives equality.

■

Power Set Size, Equation 5

Step 1. Let

A = {a_{1}, a_{2}, \dots, a_{n}}

. A subset

S \subseteq A

is fully determined by deciding, for each element

a_{i}

, whether

a_{i} \in S

. Step 2. Each of these

n

decisions has exactly 2 outcomes (in or out), and they are made independently. Step 3. By the multiplication principle of counting, the total number of distinct subsets is

n factors 2 \times 2 \times \dots \times 2 = 2^{n} .

Step 4. Hence

∣ P (A) ∣ = 2^{n}

■

Georg Cantor | 1845–1918

Georg Cantor, a German mathematician, single-handedly created set theory in a series of papers beginning in 1874. His most revolutionary contribution was the rigorous treatment of infinite sets and the discovery, via his famous diagonal argument, that infinities come in different sizes — the real numbers cannot be put in one-to-one correspondence with the natural numbers. His ideas were fiercely resisted by contemporaries such as Leopold Kronecker, who called them "humbug." Cantor suffered from depression, partly aggravated by this hostility, yet his work was ultimately embraced; David Hilbert declared, "No one shall expel us from the paradise that Cantor has created."

Building Intuition

Think of a set as a bag with a strict doorman. The doorman only ever answers one question: "Is this thing inside?" — yes or no. He does not care which item arrived first (no order), and he never lets the same item enter twice (no duplicates). Two bags are "the same bag" precisely when the doorman would give identical answers for every possible item.

Venn diagrams make operations concrete: overlapping circles represent two sets, the overlap is $A \cap B$ , the whole shaded region is $A \cup B$ , and the region outside both circles (inside the rectangle) is $(A \cup B)^{c}$ . The empty set $\emptyset$ is the bag the doorman always says "no" to — and there is only one such bag, which is why we say "the" empty set.

Venn diagram of two sets within a universe $U$, showing union, intersection, and complement regions

Worked Examples

Power Set and Operations

Given:

A = {1, 2, 3}

and

B = {2, 3, 4}

, with universe

U = {1, 2, 3, 4, 5}

. Step 1 — Union (Eq. 6): combine all members:

A \cup B = {1, 2, 3, 4} .

Step 2 — Intersection (Eq. 7): keep common members:

A \cap B = {2, 3} .

Step 3 — Difference (Eq. 8): members of

A

not in

B

A ∖ B = {1} .

Step 4 — Complement (Eq. 9): members of

U

not in

A

A^{c} = {4, 5} .

Step 5 — Power set size (Eq. 5): since

∣ A ∣ = 3

∣ P (A) ∣ = 2^{3} = 8.

Boxed answers:

A \cup B = {1, 2, 3, 4}, A \cap B = {2, 3}, A ∖ B = {1}, ∣ P (A) ∣ = 8

Verifying De Morgan's Law Numerically

Given:

U = {1, 2, 3, 4, 5, 6}

A = {1, 2, 3}

B = {3, 4}

. Verify Equation 11:

(A \cap B)^{c} = A^{c} \cup B^{c}

. Step 1 — Left side.

A \cap B = {3}

, so

(A \cap B)^{c} = U ∖ {3} = {1, 2, 4, 5, 6} .

Step 2 — Right side, complements.

A^{c} = {4, 5, 6}

and

B^{c} = {1, 2, 5, 6}

. Step 3 — Right side, union.

A^{c} \cup B^{c} = {1, 2, 4, 5, 6} .

Step 4 — Compare. Both sides equal

{1, 2, 4, 5, 6}

. Boxed answer:

(A \cap B)^{c} = A^{c} \cup B^{c} = {1, 2, 4, 5, 6} ✓

Common Misconceptions

An element is not the same as the singleton set containing it. The number

2

and the set

{2}

are different objects:

2 \in {2}

, but

2 \neq = {2}

. Likewise,

\emptyset

(the empty set, containing nothing) differs from

{\emptyset}

(a set containing one element, namely the empty set) — so

∣\emptyset∣ = 0

but

∣ {\emptyset} ∣ = 1

. Do not confuse $\subseteq$ with $\in$ . "

{1} \subseteq {1, 2}

" is true (subset), but "

{1} \in {1, 2}

" is false, since the element

{1}

is not one of the members

1

2

Order and Repetition Do Not Create New Sets

One might think ${1, 2, 3}$ , ${3, 2, 1}$ , and ${1, 1, 2, 3, 3}$ are three different sets. By the Axiom of Extensionality (Equation 3), they are all the same set, because every $x$ is a member of one iff it is a member of the others. If you need order to matter, you need an ordered tuple $(1, 2, 3)$ , not a set; if you need repetition to matter, you need a multiset — neither of which is a set.

Naïve Comprehension Fails — Russell's Paradox

It is tempting to believe any property defines a set. Consider $R = {x ∣ x \in / x}$ , "the set of all sets that are not members of themselves." Ask: is $R \in R$ ? If $R \in R$ , then by its own definition $R \in / R$ — contradiction. If $R \in / R$ , then $R$ satisfies the defining property, so $R \in R$ — contradiction. No such set can exist. This is Russell's Paradox, and it shows unrestricted set-building is logically inconsistent, motivating the careful axioms of modern set theory.

Connections

Sets are the connective tissue of mathematics. A Function is formally a special set of ordered pairs (a relation with at most one output per input). The number systems — the Natural Numbers, integers, rationals, and Real Numbers — are all constructed as sets. Logic mirrors set operations exactly: "and"/"or"/"not" correspond to intersection/union/complement, which is why De Morgan's Laws appear in both. Probability defines events as subsets of a sample space, so $P (A \cup B)$ and $P (A \cap B)$ inherit the set algebra directly. Cardinality generalizes "counting" to compare sizes of infinite sets.

Real-World Applications

Relational databases (SQL): Queries are literally set operations — UNION, INTERSECT, EXCEPT correspond to $\cup$ , $\cap$ , $∖$ on tables of rows.
Search engines & information retrieval: A keyword search returns the intersection of document sets; Boolean search ("cats AND NOT dogs") is set algebra.
Digital logic & circuit design: Bitmasks and boolean gates implement set membership; an $n$ -bit integer encodes a subset of an $n$ -element universe, mirroring Equation 5.
Probability & statistics: Risk, insurance, and machine-learning models treat events as sets and use the inclusion–exclusion principle.
Type systems in programming: Languages like Python, Java, and Rust provide native set data structures with $\cup$ , $\cap$ , and difference for deduplication and fast membership tests.
Cryptography & error-correcting codes: Finite fields and codes are built on carefully structured sets and their subsets.
Genetics & bioinformatics: Gene-set enrichment analysis intersects sets of genes to find shared biological functions.

Historical Development

c. 350 BCE — Aristotle studies syllogistic logic, an informal precursor to class/membership reasoning.
1847 — George Boole publishes The Mathematical Analysis of Logic, algebraizing logical classes (Boolean algebra).
1874 — Georg Cantor's paper on countability launches set theory; he proves the algebraic numbers are countable but the reals are not.
1881–1883 — John Venn introduces the diagrams that bear his name for visualizing set relations.
1891 — Cantor publishes the diagonal argument, cleanly proving $∣ R ∣ > ∣ N ∣$ .
1901 — Bertrand Russell discovers Russell's Paradox, exposing the inconsistency of naïve set theory.
1908 — Ernst Zermelo proposes the first axiom system to avoid paradoxes; refined with Abraham Fraenkel into ZFC (1922).
1931 — Kurt Gödel's Incompleteness Theorems show no consistent axiom system (including ZFC) can prove all true statements about sets.
1963 — Paul Cohen proves the Continuum Hypothesis is independent of ZFC, completing work begun by Gödel (1940).

Subtleties & Limits

The Continuum Hypothesis (CH) asks whether there exists a set whose size is strictly between that of the natural numbers $∣ N ∣$ and that of the real numbers $∣ R ∣$ . Cantor conjectured "no," but the question turned out to be undecidable: Gödel (1940) showed CH cannot be disproved from the standard ZFC axioms, and Cohen (1963) showed it cannot be proved either. CH is therefore independent of ZFC — both it and its negation can be consistently added. This raises a profound philosophical puzzle: are there genuine mathematical truths beyond what any axiom system can capture, and how do we choose which set-theoretic universe to inhabit? Active research in large cardinals and forcing continues to probe these foundations.