Set Theory

Set theory is the language mathematics uses to talk about collections — and it turns out that almost everything else in mathematics can be built from this one idea. When you say "the even numbers," "the solutions to an equation," or "the students who passed," you are describing a set. What makes set theory extraordinary is that this simple notion, pushed to its logical limit by Georg Cantor in the 1870s, forced mathematicians to confront the infinite head-on and discover something shocking: some infinities are genuinely bigger than others.

This page teaches you the working vocabulary of sets — membership, subsets, unions, intersections, complements — and then takes you all the way to Cantor's proof that the real numbers cannot be counted. By the end you will not just know the symbols; you will understand why they matter and how they let us reason precisely about both the finite and the infinite.

Learning Objectives

• Define a set, membership, and the difference between a set and its elements.
• Determine subsets, equality of sets, and construct power sets.
• Perform and interpret unions, intersections, complements, and set differences.
• Read and draw Venn diagrams to model relationships between sets.
• Compute the cardinality of finite sets, including with the inclusion–exclusion principle.
• Distinguish countable from uncountable infinity and follow Cantor's diagonal argument.

Quick Answer

A set is a well-defined collection of distinct objects called elements; we write $x \in A$ to say $x$ belongs to set $A$. Set $A$ is a subset of $B$ (written $A \subseteq B$) if every element of $A$ is also in $B$. The union $A \cup B$ collects everything in either set, the intersection $A \cap B$ keeps only what they share, and the complement $A^c$ contains everything (in the universal set) not in $A$. The cardinality $|A|$ is the number of elements in $A$. For infinite sets, Cantor showed that some — like the integers and rationals — are countable (can be listed), while others — like the real numbers — are uncountable and strictly larger.

Where It Came From

For most of history, mathematicians treated infinity as a process rather than a thing. You could add 1 forever, but "the completed infinite" was considered off-limits — Aristotle called it merely "potential," and Gauss himself protested against using infinity "as something completed." The practical need that broke this taboo came from an unexpected direction: analysis.

In the 1860s and 1870s, Georg Cantor (1845–1918) was studying trigonometric series — questions about when a function's Fourier representation is unique. To pin down the answer, he needed to describe precisely the sets of points where a series could misbehave. This forced him to compare sizes of infinite collections of points, and he needed a rigorous tool to do it. His answer, published beginning in 1874, was to define the size of a set by whether its elements could be paired off one-to-one with another set — a bijection. Two sets have the same size exactly when such a pairing exists.

This innocent-looking definition detonated. Cantor proved that the rational numbers, despite being densely packed, could be paired with the counting numbers — they are the "same size" as $\mathbb{N}$. But the real numbers could not be, no matter how cleverly you tried. There were, provably, different magnitudes of infinity. The reaction was ferocious: Leopold Kronecker attacked Cantor's work as dangerous nonsense and blocked his career; Cantor suffered recurring depression. Yet within a generation his ideas became bedrock. David Hilbert declared, "No one shall expel us from the paradise that Cantor has created." Set theory, later given a rigorous axiomatic foundation by Zermelo and Fraenkel, is now the standard foundation on which the rest of mathematics is built.

Sets, Elements, and How We Describe Them

A set is any collection of distinct objects, considered as a single whole. The objects are its elements or members. We use capital letters for sets and write membership with $\in$:

$A = \{2, 4, 6, 8\}, \qquad 4 \in A, \qquad 5 \notin A.$

Two features are essential. First, order does not matter: $\{1, 2, 3\}$ and $\{3, 1, 2\}$ are the same set. Second, repetition does not matter: $\{1, 1, 2\}$ is just $\{1, 2\}$ — a set records only whether an element is present, not how many times.

There are two common ways to specify a set. Roster notation lists the elements: $B = \{a, e, i, o, u\}$. Set-builder notation states a rule:

$C = \{\, x \mid x \text{ is an integer and } 0 < x < 6 \,\} = \{1, 2, 3, 4, 5\}.$

Read the bar $\mid$ as "such that." A few sets appear so often they get their own names: the empty set $\varnothing = \{\}$ (no elements at all), the natural numbers $\mathbb{N}$, the integers $\mathbb{Z}$, the rationals $\mathbb{Q}$, and the reals $\mathbb{R}$.

Worked example. Let $D = \{\, n^2 \mid n \in \{1, 2, 3, 4\} \,\}$. We compute each element: $1^2 = 1$, $2^2 = 4$, $3^2 = 9$, $4^2 = 16$. So $D = \{1, 4, 9, 16\}$ and $|D| = 4$. Note $3 \notin D$ but $9 \in D$.

Subsets, Equality, and Power Sets

Set $A$ is a subset of $B$, written $A \subseteq B$, when every element of $A$ is also an element of $B$. If additionally $A \neq B$ (so $B$ has something $A$ lacks), we call $A$ a proper subset and write $A \subset B$. Two sets are equal precisely when each is a subset of the other: $A = B$ means $A \subseteq B$ and $B \subseteq A$. This "prove it both ways" strategy is how set equalities are actually established in higher mathematics.

A subtle but important fact: the empty set is a subset of every set, and every set is a subset of itself. Why is $\varnothing \subseteq A$ always true? Because the statement "every element of $\varnothing$ is in $A$" cannot be violated — there is no element to serve as a counterexample.

The power set $\mathcal{P}(A)$ is the set of all subsets of $A$. If $A$ has $n$ elements, then $\mathcal{P}(A)$ has exactly $2^n$ elements, because building a subset means making an independent yes/no choice for each of the $n$ elements.

Worked example. Let $A = \{a, b, c\}$, so $n = 3$ and we expect $2^3 = 8$ subsets:

$\mathcal{P}(A) = \{\, \varnothing,\ \{a\},\ \{b\},\ \{c\},\ \{a,b\},\ \{a,c\},\ \{b,c\},\ \{a,b,c\} \,\}.$

Counting confirms 8 subsets. Notice both $\varnothing$ and $A$ itself appear — a common thing to forget.

Operations: Union, Intersection, Complement, Difference

Most of set theory's power comes from combining sets. Fix a universal set $U$ containing everything under discussion.

• Union $A \cup B = \{\, x \mid x \in A \text{ or } x \in B \,\}$ — everything in at least one set (the "or" is inclusive).
• Intersection $A \cap B = \{\, x \mid x \in A \text{ and } x \in B \,\}$ — only the shared elements.
• Complement $A^c = \{\, x \mid x \in U \text{ and } x \notin A \,\}$ — everything outside $A$.
• Difference $A \setminus B = \{\, x \mid x \in A \text{ and } x \notin B \,\}$ — in $A$ but not $B$.

Two sets with no elements in common ($A \cap B = \varnothing$) are called disjoint.

Worked example. Let $U = \{1,2,3,4,5,6,7,8,9,10\}$, $A = \{1,2,3,4,5\}$, and $B = \{4,5,6,7\}$.

$A \cup B = \{1,2,3,4,5,6,7\}, \qquad A \cap B = \{4,5\}.$ $A \setminus B = \{1,2,3\}, \qquad B \setminus A = \{6,7\}.$ $A^c = \{6,7,8,9,10\}, \qquad (A \cup B)^c = \{8,9,10\}.$

A cornerstone identity, De Morgan's laws, connects complements to the other operations:

$(A \cup B)^c = A^c \cap B^c, \qquad (A \cap B)^c = A^c \cup B^c.$

Check the first with our numbers: $(A \cup B)^c = \{8,9,10\}$, while $A^c \cap B^c = \{6,7,8,9,10\} \cap \{1,2,3,8,9,10\} = \{8,9,10\}$. They match.

Venn Diagrams and Cardinality

A Venn diagram draws each set as a circle inside a rectangle (the universal set); overlaps show intersections. They turn abstract logic into geometry and are the fastest way to reason about two or three sets. Picture two overlapping circles $A$ and $B$: the lens where they cross is $A \cap B$, the region covered by either circle is $A \cup B$, and everything in the rectangle outside both circles is $(A \cup B)^c$.

For finite sets, cardinality is just the element count. But when sets overlap, you cannot simply add sizes — you would count the overlap twice. The inclusion–exclusion principle fixes this:

$|A \cup B| = |A| + |B| - |A \cap B|.$

Worked example. In a class of 30 students, 18 study French, 15 study Spanish, and 7 study both. How many study at least one language, and how many study neither?

At least one: $|F \cup S| = |F| + |S| - |F \cap S| = 18 + 15 - 7 = 26$.

Neither: these are the students outside $F \cup S$, so $30 - 26 = 4$ students. If we had naively added $18 + 15 = 33$, we would have exceeded the class size — a clear signal that the 7 double-counted students must be subtracted.

Countable versus Uncountable Infinity

Here is where set theory becomes revolutionary. How do you compare the sizes of infinite sets when you can never finish counting? Cantor's answer: two sets have the same size if their elements can be matched in a perfect one-to-one pairing (a bijection), with none left over on either side.

A set is countably infinite if it can be paired with the natural numbers $\mathbb{N} = \{1, 2, 3, \dots\}$ — that is, if you can arrange its elements in an infinite list. Surprisingly many sets pass this test. The integers do: list them $0, 1, -1, 2, -2, 3, -3, \dots$, hitting each exactly once. Even the rationals do, by walking through a grid of fractions diagonally and skipping duplicates. The size of any such set is the smallest infinite cardinal, written $\aleph_0$ ("aleph-null").

The stunning result is that the real numbers are not countable. Cantor proved it with his diagonal argument. Suppose, for contradiction, that we could list all real numbers between 0 and 1 as $r_1, r_2, r_3, \dots$, each written as an infinite decimal:

$r_1 = 0.\mathbf{3}14159\ldots,\quad r_2 = 0.2\mathbf{7}1828\ldots,\quad r_3 = 0.14\mathbf{1}42\ldots,\ \dots$

Now build a new number $d = 0.d_1 d_2 d_3 \ldots$ by a simple rule: make $d_1$ differ from the first digit of $r_1$, $d_2$ differ from the second digit of $r_2$, $d_3$ from the third digit of $r_3$, and so on down the diagonal (say, if the digit is 5 make it 6, otherwise make it 5). By construction $d$ differs from every number on the list in at least one decimal place, so $d$ is a real number between 0 and 1 that is not on the list. This contradicts the assumption that the list was complete. No list can contain all the reals — $\mathbb{R}$ is uncountable, strictly larger than $\mathbb{N}$.

This means there is a genuine hierarchy of infinities. Cantor even proved a general theorem: for any set $A$, its power set $\mathcal{P}(A)$ is strictly larger than $A$. Apply it repeatedly and you get an endless tower of ever-larger infinite sizes.

Real-World Applications

• Databases and SQL. Query operations are literally set operations: UNION, INTERSECT, and EXCEPT (difference) combine result sets, and a JOIN filters by an intersection condition.
• Search and filtering. Every faceted search ("red AND size-10 AND in-stock") evaluates intersections and unions of product sets; Boolean web search does the same.
• Probability. Events are subsets of a sample space. The addition rule $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ is inclusion–exclusion in disguise.
• Digital circuits and logic. Boolean algebra — the basis of computer hardware — is set algebra: AND is intersection, OR is union, NOT is complement, and De Morgan's laws are used constantly to simplify gates.
• Computability theory. Cantor's countable/uncountable distinction underlies the proof that some problems are undecidable: there are uncountably many possible functions but only countably many programs, so most functions cannot be computed.

Common Mistakes

Mistake 1: Confusing $\in$ with $\subseteq$. Students write $\{1\} \in \{1, 2, 3\}$ when they mean $\{1\} \subseteq \{1, 2, 3\}$. Why it's wrong: $\in$ relates an element to a set, while $\subseteq$ relates a set to a set. The element $1$ is in the set, so $1 \in \{1,2,3\}$; the set $\{1\}$ is a subset, so $\{1\} \subseteq \{1,2,3\}$. Correction: ask "is this thing an element, or a whole collection?" before choosing the symbol.

Mistake 2: Forgetting to subtract the overlap. When counting $|A \cup B|$, students add $|A| + |B|$ and overcount shared members. Why it's wrong: elements in both sets get tallied twice. Correction: always apply $|A \cup B| = |A| + |B| - |A \cap B|$, and sanity-check that your total never exceeds the universal set.

Mistake 3: Assuming all infinities are equal. Many believe "infinity is infinity," so $\mathbb{N}$ and $\mathbb{R}$ must be the same size. Why it's wrong: Cantor's diagonal argument proves no bijection exists between them. Correction: infinite size is defined by bijection; some infinite sets (integers, rationals) share the size $\aleph_0$, but the reals are strictly larger.

Comparison and Connections

The operations are easy to confuse because their symbols look similar. This table pins down the distinctions:

Concept	Symbol	Meaning	Result type
Membership	$x \in A$	$x$ is an element of $A$	true/false
Subset	$A \subseteq B$	every element of $A$ is in $B$	true/false
Union	$A \cup B$	in $A$ or $B$	a set
Intersection	$A \cap B$	in $A$ and $B$	a set
Complement	$A^c$	in $U$ but not $A$	a set
Difference	$A \setminus B$	in $A$ but not $B$	a set

Set theory connects outward everywhere. Logic mirrors it exactly: "and/or/not" correspond to intersection/union/complement, which is why De Morgan's laws appear in both. Probability builds events as sets. Functions and relations are defined as special sets of ordered pairs. And the countable/uncountable divide is the seed of both cardinal arithmetic and the theory of computability.

Practice Questions

Recall

List all subsets of $\{x, y\}$. How many should there be?

Answer: There are $2^2 = 4$ subsets: $\varnothing$, $\{x\}$, $\{y\}$, $\{x, y\}$.

Understanding

Let $A = \{1,2,3,4,6\}$ and $B = \{2,4,5,6,8\}$. Find $A \cap B$, $A \cup B$, and $A \setminus B$.

Answer: $A \cap B = \{2,4,6\}$; $A \cup B = \{1,2,3,4,5,6,8\}$; $A \setminus B = \{1,3\}$.

Application

In a survey of 50 people, 30 like tea, 25 like coffee, and 10 like both. How many like neither?

Guidance: Those liking at least one drink: $30 + 25 - 10 = 45$. Neither: $50 - 45 = 5$ people.

Analysis

Explain why the set of rational numbers is countable but the set of real numbers is not. What single argument distinguishes them?

Guidance: Rationals can be arranged in a systematic list (walk a grid of numerators/denominators diagonally, skipping repeats), giving a bijection with $\mathbb{N}$. For the reals, Cantor's diagonal argument constructs a number differing from every entry of any proposed list, proving no such list is complete — hence $\mathbb{R}$ is uncountable and strictly larger.

FAQ

Is the empty set really a subset of every set? Yes. The definition "every element of $\varnothing$ is in $A$" holds vacuously — there is no element of $\varnothing$ that could fail the condition, so the statement is true for every $A$.

What's the difference between $\{\varnothing\}$ and $\varnothing$? $\varnothing$ is the empty set — it has no elements, so $|\varnothing| = 0$. But $\{\varnothing\}$ is a set containing one thing (the empty set), so $|\{\varnothing\}| = 1$. They are not equal.

Why does order and repetition not matter in a set? A set records only membership — whether something belongs. If you need order or repeated entries, you want a different object: an ordered tuple (like $(1,2)$) or a multiset. Sets deliberately strip those features away.

How can the rationals be "the same size" as the integers when there are infinitely many fractions between any two integers? Density and size are different questions. Size, for Cantor, means "can they be paired one-to-one?" — and yes, the rationals can be listed in a sequence, so they pair perfectly with the integers despite being densely packed.

Did mathematicians accept Cantor's ideas right away? No. Kronecker and others attacked them fiercely as meaningless, and Cantor faced real professional and personal hardship. Acceptance came within a generation, and Hilbert later called Cantor's work a "paradise" mathematics would never leave.

Is there an infinity between $\aleph_0$ (the integers) and the size of the reals? This is the famous Continuum Hypothesis. Gödel and Cohen proved it can be neither proved nor disproved from the standard ZFC axioms — it is genuinely independent of them.

Quick Revision

• Set: collection of distinct elements; $x \in A$ means membership; order and repeats don't matter.
• Subset: $A \subseteq B$ if every element of $A$ is in $B$; $\varnothing$ is a subset of everything.
• Power set: all subsets of $A$; a set of $n$ elements has $2^n$ subsets.
• Operations: $A \cup B$ (or), $A \cap B$ (and), $A^c$ (not), $A \setminus B$ (in $A$ not $B$).
• De Morgan: $(A \cup B)^c = A^c \cap B^c$ and $(A \cap B)^c = A^c \cup B^c$.
• Inclusion–exclusion: $|A \cup B| = |A| + |B| - |A \cap B|$.
• Countable: can be listed / paired with $\mathbb{N}$ (integers, rationals; size $\aleph_0$).
• Uncountable: cannot be listed (reals); proven by Cantor's diagonal argument.

Related Topics

Prerequisites

• Discrete Mathematics overview

Related Topics

• Logic and Boolean algebra (and/or/not mirror intersection/union/complement)
• Probability — events as subsets of a sample space (see Statistics and Probability)

Next Topics

• Relations and functions (defined as sets of ordered pairs)
• Combinatorics and counting (builds on cardinality and inclusion–exclusion)