Set Theory: The Foundation of Mathematics

Most students meet sets early on as lists inside curly brackets and Venn diagrams with overlapping circles. It can feel like a gentle warm-up topic, but set theory is far more than that. Numbers, functions, geometry and probability can all be built out of sets, and the study of sets led to some of the most astonishing discoveries in the history of mathematics, including the fact that some infinities are bigger than others.

What Is a Set?

A set is a well-defined collection of distinct objects, called its elements. "Well-defined" means that for any object we can decide whether it belongs. We write \( x \in A \) to mean "\( x \) is an element of \( A \)".

Sets can be described by listing, such as \( A = \{2, 4, 6, 8\} \), or by a rule, such as

$$ A = \{x : x \text{ is an even number and } 0 < x < 10\} $$

Order and repetition do not matter: \( \{1, 2, 3\} \), \( \{3, 1, 2\} \) and \( \{1, 1, 2, 3\} \) are the same set. The empty set \( \varnothing \) has no elements at all, and \( A \subseteq B \) means every element of \( A \) is also in \( B \).

The Basic Operations

• Union \( A \cup B \): elements in \( A \) or \( B \) (or both).
• Intersection \( A \cap B \): elements in both \( A \) and \( B \).
• Difference \( A \setminus B \): elements in \( A \) but not in \( B \).
• Complement \( A' \): elements of the universal set not in \( A \).
• Cartesian product \( A \times B \): all ordered pairs \( (a, b) \) with \( a \in A \), \( b \in B \).

These operations obey laws much like arithmetic. De Morgan's laws are especially useful:

$$ (A \cup B)' = A' \cap B', \qquad (A \cap B)' = A' \cup B' $$

Worked Example 1: Operations and the Power Set

Let \( A = \{1, 2, 3, 4\} \) and \( B = \{3, 4, 5\} \).

• \( A \cup B = \{1, 2, 3, 4, 5\} \)
• \( A \cap B = \{3, 4\} \)
• \( A \setminus B = \{1, 2\} \)
• \( B \setminus A = \{5\} \)
• \( A \times B \) contains \( 4 \times 3 = 12 \) ordered pairs, for example \( (1, 3) \) and \( (4, 5) \).

The power set of a set is the set of all its subsets. For \( C = \{a, b, c\} \):

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

There are 8 subsets. In general, a set with \( n \) elements has \( 2^n \) subsets, because each element is either in or out of a subset: two choices, made \( n \) times. Here \( 2^3 = 8 \), as we counted.

Worked Example 2: Inclusion-Exclusion

In a college of 120 students, 70 study Mathematics, 50 study Physics and 30 study both. How many study neither?

Let \( M \) and \( P \) be the two sets. The inclusion-exclusion principle says

$$ n(M \cup P) = n(M) + n(P) - n(M \cap P) $$

We subtract the overlap because those 30 students were counted twice. So

$$ n(M \cup P) = 70 + 50 - 30 = 90 $$

and the number studying neither subject is

$$ 120 - 90 = 30 $$

A Venn diagram confirms it: 40 Mathematics only, 20 Physics only, 30 both and 30 outside, totalling 120.

Cantor and the Sizes of Infinity

Set theory as a serious subject was created by the German mathematician Georg Cantor, mainly between about 1874 and 1897. Cantor asked a deceptively simple question: when do two infinite sets have the same size?

His answer: when their elements can be paired off one-to-one with nothing left over. This leads to surprises. The even numbers can be paired with all the natural numbers via \( n \leftrightarrow 2n \), so there are "as many" even numbers as natural numbers, even though evens seem to be only half of them. Sets that can be paired with the natural numbers are called countable. Cantor showed that even the rational numbers are countable, by listing fractions in a zig-zag pattern through a grid.

Then came the shock. In 1891 Cantor published his diagonal argument, proving the real numbers are not countable. Suppose someone claims to have a complete list of all real numbers between 0 and 1:

• 0.51820...
• 0.33914...
• 0.27005...
• 0.91048...

Build a new number by changing the \( n \)th digit of the \( n \)th number, say by adding 1 (and turning 9 into 0). From the bold digits 5, 3, 0, 4 we get 0.6415... This number differs from every number on the list in at least one digit, so the list was not complete after all. Therefore the real numbers form a strictly larger infinity than the natural numbers.

Cantor also proved that the power set of any set is always bigger than the set itself, so there is an endless ladder of ever larger infinities. Many contemporaries, including Leopold Kronecker, attacked his ideas, but David Hilbert later declared that "no one shall expel us from the paradise that Cantor has created."

Russell's Paradox and the Axioms

Early set theory allowed any describable collection to be a set. Around 1901, Bertrand Russell found the flaw. Consider the set of all sets that do not contain themselves:

$$ R = \{x : x \notin x\} $$

Is \( R \) a member of itself? If it is, then by definition it is not. If it is not, then by definition it is. Either answer is a contradiction.

To repair the foundations, Ernst Zermelo proposed axioms in 1908, later refined by Abraham Fraenkel and others. The resulting system, ZFC (Zermelo-Fraenkel set theory with the Axiom of Choice), carefully controls how new sets may be formed, so paradoxical collections like \( R \) are simply not allowed to be sets. Almost all of modern mathematics can be written within ZFC.

Building Numbers from Nothing

How can sets be the foundation of mathematics? John von Neumann showed how to build the natural numbers using only the empty set:

$$ 0 = \varnothing, \quad 1 = \{\varnothing\}, \quad 2 = \{\varnothing, \{\varnothing\}\}, \quad 3 = \{0, 1, 2\} $$

Each number is the set of all smaller numbers, so the number \( n \) has exactly \( n \) elements. From the naturals we can build integers, rationals and real numbers, and functions are defined as special sets of ordered pairs. Everything rests on sets.

Did You Know?

• The continuum hypothesis asks whether any infinity lies strictly between the naturals and the reals. Gödel (1940) and Paul Cohen (1963) showed it can be neither proved nor disproved from ZFC.
• The \( \in \) symbol comes from the Greek letter epsilon and was introduced by Giuseppe Peano in 1889.
• John Venn introduced his famous diagrams in 1880, although similar diagrams had been used earlier by Leonhard Euler.

Key Takeaways

• A set is a well-defined collection of distinct objects; union, intersection, difference and complement combine sets.
• A set with \( n \) elements has \( 2^n \) subsets, and inclusion-exclusion counts overlapping groups correctly.
• Cantor proved that infinite sets come in different sizes, with the reals larger than the naturals.
• Russell's paradox forced mathematicians to adopt careful axioms, leading to ZFC.
• Numbers, functions and nearly all of mathematics can be constructed from sets.

Struggling with set theory proofs or Venn diagram problems? Amathify's experts and PhD scholars offer step-by-step solutions via WhatsApp or the Ask a Question form.