Naive Set Theory

Naive set theory is the original, intuitive approach to the mathematics of collections — the idea that any clearly defined property determines a set of objects satisfying that property. Developed by Georg Cantor in the 1870s, it provided the first rigorous language for talking about infinity, functions, and mathematical structures in a unified way. Yet this very generality harbors contradictions, most famously Russell’s paradox, which revealed that unrestricted set formation leads to logical inconsistency and spurred the development of the axiomatic set theories explored later in this branch.

Sets, Elements, and Membership

The concept of a set is among the most fundamental in all of mathematics. In his 1895 Beiträge zur Begründung der transfiniten Mengenlehre, Georg Cantor defined a set as “a gathering together into a whole of definite, distinct objects of our perception or our thought.” Those objects are called the elements or members of the set. The relationship between an element and a set is called membership, and it is written with the symbol $\in$: if $x$ is a member of the set $A$, we write $x \in A$, and if $x$ is not a member, we write $x \notin A$. Membership is the only primitive relation in set theory — everything else is built from it.

There are two standard ways to specify which elements belong to a set. Roster notation (also called enumeration) simply lists the elements inside curly braces:

$A = \{1, 2, 3, 4, 5\}$

This works well for small or finite sets, but it becomes impractical — or impossible — for large or infinite collections. The more powerful alternative is set-builder notation, which defines a set by a property that its members must satisfy:

$B = \{x : x \text{ is a prime number}\}$

The colon (or vertical bar) is read “such that,” so $B$ is “the set of all $x$ such that $x$ is a prime number.” Set-builder notation is where the real expressive power lies, and also where the danger lurks — as we shall see shortly.

Two special sets deserve immediate mention. The empty set, denoted $\emptyset$ or $\{\}$, is the set with no elements at all. It is unique: there is only one set with no members, a fact that follows from the extensionality principle discussed in the next section. At the other extreme, naive set theory entertains the notion of a universal set $U$, the set of all objects under discussion in a given context. Venn diagrams, the overlapping-circle illustrations introduced by John Venn in 1880, typically depict sets as regions inside a rectangle representing $U$. While Venn diagrams are invaluable as an intuitive aid, they should be treated as illustrations rather than proofs — the visual metaphor can mislead when sets have complex or infinite structure.

Cantor’s original vision — that every well-defined property determines a set — is sometimes called the unrestricted comprehension principle: for any property $P(x)$, there exists a set $\{x : P(x)\}$. This principle is wonderfully intuitive and, for most everyday mathematical purposes, entirely safe. But in 1901, Bertrand Russell demonstrated that it is logically self-contradictory. Consider the property “does not contain itself,” and form the set

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

Now ask: is $R$ a member of itself? If $R \in R$, then by the defining property, $R \notin R$ — a contradiction. If $R \notin R$, then $R$ satisfies the defining property, so $R \in R$ — again a contradiction. This is Russell’s paradox, and it shows that unrestricted comprehension is inconsistent. The paradox is not an exotic curiosity; it strikes at the very foundation of the system. Cantor himself had encountered related difficulties, including the paradox of the “set of all sets” (if such a set $V$ exists, its power set $\mathcal{P}(V)$ must be both a subset of $V$ and strictly larger than $V$ — a contradiction by Cantor’s own theorem). These paradoxes are precisely what motivated the development of axiomatic set theories such as Zermelo-Fraenkel set theory (ZFC), which replace unrestricted comprehension with carefully controlled axioms that avoid self-referential constructions while preserving the vast majority of useful set-theoretic reasoning.

Despite its logical flaws, naive set theory remains the working language of most mathematicians. The intuition it provides is indispensable, and its constructions are sound whenever we restrict attention to sets built from well-understood starting materials — which is exactly what the axioms of ZFC formalize, as explored in Axiomatic Set Theory (ZFC).

Subsets, Power Sets, and Equality

Given two sets $A$ and $B$, we say that $A$ is a subset of $B$, written $A \subseteq B$, if every element of $A$ is also an element of $B$:

$A \subseteq B \;\;\text{if and only if}\;\; \text{for every } x,\; x \in A \implies x \in B.$

If $A \subseteq B$ and $A \neq B$ — that is, $B$ contains at least one element not in $A$ — we say $A$ is a proper subset of $B$ and write $A \subset B$ (though some authors use $A \subsetneq B$ to avoid ambiguity). The empty set is a subset of every set: since $\emptyset$ has no elements, the condition “every element of $\emptyset$ is in $B$” is vacuously true for any $B$. Every set is also a subset of itself, so the subset relation is reflexive.

The concept of set equality rests on the axiom of extensionality, one of the most important principles in all of set theory. It states that two sets are equal if and only if they have exactly the same elements:

$A = B \;\;\text{if and only if}\;\; \text{for every } x,\; x \in A \iff x \in B.$

Equivalently, $A = B$ if and only if $A \subseteq B$ and $B \subseteq A$. This “double containment” argument is the standard technique for proving two sets are equal: show that each is a subset of the other. Extensionality also tells us that a set is determined entirely by its members, not by how it is described. The sets $\{1, 2, 3\}$, $\{3, 1, 2\}$, and $\{x : x \text{ is a positive integer less than } 4\}$ are all the same set, because they contain exactly the same elements. Order and repetition in roster notation do not matter.

The power set of a set $A$, denoted $\mathcal{P}(A)$, is the set of all subsets of $A$:

$\mathcal{P}(A) = \{S : S \subseteq A\}.$

For a concrete example, if $A = \{1, 2\}$, then $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$. The power set always includes both $\emptyset$ (which is a subset of every set) and $A$ itself. For a finite set with $n$ elements, the power set has exactly $2^n$ elements:

$|\mathcal{P}(A)| = 2^{|A|}$

The reason is combinatorial: each element of $A$ is either included or excluded from a given subset, giving two independent choices per element. This formula also explains the common notation $2^A$ for the power set.

The power set construction is far more than a bookkeeping device — it is the engine behind some of the deepest results in set theory. Cantor’s theorem, which we will encounter in Functions and Cardinality, states that for any set $A$ (finite or infinite), there is no surjection from $A$ onto $\mathcal{P}(A)$. In other words, the power set is always strictly larger than the original set. For finite sets, this is the obvious fact that $2^n > n$. For infinite sets, it is a profound result: it means there is no single “largest” infinity, but rather an endless hierarchy of ever-larger infinite cardinalities. This hierarchy, discovered by Cantor, was one of the most revolutionary ideas in the history of mathematics and remains at the heart of modern set theory.

Set Operations and Algebraic Laws

Just as arithmetic provides operations for combining numbers, set theory provides operations for combining sets. The union of two sets $A$ and $B$ is the set of all elements belonging to at least one of them:

$A \cup B = \{x : x \in A \text{ or } x \in B\}.$

The intersection of $A$ and $B$ is the set of elements belonging to both:

$A \cap B = \{x : x \in A \text{ and } x \in B\}.$

When $A \cap B = \emptyset$ — the two sets share no elements — we say $A$ and $B$ are disjoint. The complement of a set $A$ relative to a universal set $U$ is the set of all elements in $U$ that are not in $A$:

$A^c = \{x \in U : x \notin A\}.$

More generally, the relative complement (or set difference) of $B$ in $A$ is defined without reference to a universal set:

$A \setminus B = \{x : x \in A \text{ and } x \notin B\}.$

Finally, the symmetric difference of $A$ and $B$ collects those elements belonging to exactly one of the two sets:

$A \mathbin{\triangle} B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B).$

These operations obey a rich collection of algebraic laws that mirror — and historically inspired — the laws of Boolean algebra from propositional logic. The parallel is not accidental: union corresponds to disjunction ($\lor$), intersection to conjunction ($\land$), and complementation to negation ($\neg$). The key identities are summarized below.

Law	Identity
Commutativity	$A \cup B = B \cup A$ and $A \cap B = B \cap A$
Associativity	$(A \cup B) \cup C = A \cup (B \cup C)$ and likewise for $\cap$
Distributivity	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ and dually
Idempotence	$A \cup A = A$ and $A \cap A = A$
Identity	$A \cup \emptyset = A$ and $A \cap U = A$
Annihilation	$A \cup U = U$ and $A \cap \emptyset = \emptyset$
Complement	$A \cup A^c = U$ and $A \cap A^c = \emptyset$
Double complement	$(A^c)^c = A$
De Morgan’s laws	$(A \cup B)^c = A^c \cap B^c$ and $(A \cap B)^c = A^c \cup B^c$

De Morgan’s laws for sets, named after Augustus De Morgan who stated the logical versions in the 1840s, are particularly important. They express a fundamental duality: complementing a union yields the intersection of the complements, and vice versa. These laws generalize to arbitrary (even infinite) unions and intersections:

$\left(\bigcup_{i \in I} A_i\right)^c = \bigcap_{i \in I} A_i^c \qquad \text{and} \qquad \left(\bigcap_{i \in I} A_i\right)^c = \bigcup_{i \in I} A_i^c.$

The algebraic structure formed by a collection of sets under $\cup$, $\cap$, and complementation (with $\emptyset$ and $U$ as identity elements) is a Boolean algebra — the very same structure that Boole’s propositional calculus gives rise to. This correspondence between logic and set theory is one of the most elegant features of the foundations of mathematics: the algebra of truth values and the algebra of collections are two manifestations of the same abstract structure. The connection runs even deeper through Stone’s representation theorem, which shows that every Boolean algebra is isomorphic to a field of sets — a topic explored further in the Lattices and Boolean Algebras section of axiomatic set theory.

Ordered Pairs and Relations

The sets we have discussed so far are unordered — the set $\{a, b\}$ is the same as $\{b, a\}$. But much of mathematics depends on order: coordinates in the plane, the input-output behavior of functions, and the structure of relations all require us to distinguish $(a, b)$ from $(b, a)$. The challenge is to define the notion of an ordered pair purely in terms of sets, so that the entire apparatus of set theory can be brought to bear.

The standard solution, due to Kazimierz Kuratowski in 1921, defines the ordered pair $(a, b)$ as:

$(a, b) = \{\{a\}, \{a, b\}\}.$

This encoding looks peculiar, but it has the one property that matters: $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$. The proof is a short exercise in extensionality — one verifies by case analysis that equality of the outer sets forces equality of the components. Other definitions of ordered pair have been proposed (notably by Norbert Wiener in 1914), but Kuratowski’s is the one adopted as standard because of its simplicity.

With ordered pairs in hand, we define the Cartesian product of two sets $A$ and $B$ as the set of all ordered pairs whose first component comes from $A$ and whose second comes from $B$:

$A \times B = \{(a, b) : a \in A \text{ and } b \in B\}.$

The name honors Rene Descartes, whose coordinate geometry identified points in the plane with pairs of real numbers — the plane being $\mathbb{R} \times \mathbb{R} = \mathbb{R}^2$. For finite sets, $|A \times B| = |A| \cdot |B|$, which is why the operation is called a “product.” The construction extends to $n$-tuples: $A_1 \times A_2 \times \cdots \times A_n$ is the set of all ordered $n$-tuples $(a_1, a_2, \ldots, a_n)$ with each $a_i \in A_i$.

A relation from $A$ to $B$ is any subset $R \subseteq A \times B$. When $(a, b) \in R$, we say that $a$ is related to $b$ by $R$, often written $a \mathrel{R} b$. The domain of $R$ is the set of all first components, $\text{dom}(R) = \{a \in A : (a, b) \in R \text{ for some } b\}$, and the range (or image) is the set of all second components, $\text{ran}(R) = \{b \in B : (a, b) \in R \text{ for some } a\}$. A relation on a single set $A$ — that is, a subset of $A \times A$ — is where the most interesting structural properties emerge.

Three properties of a relation $R$ on $A$ are especially important. $R$ is reflexive if $a \mathrel{R} a$ for every $a \in A$ — every element is related to itself. $R$ is symmetric if $a \mathrel{R} b$ implies $b \mathrel{R} a$ — the relation goes both ways. $R$ is transitive if $a \mathrel{R} b$ and $b \mathrel{R} c$ together imply $a \mathrel{R} c$ — the relation can be chained. A relation that is reflexive, symmetric, and transitive is called an equivalence relation, and equivalence relations are ubiquitous in mathematics. Equality itself is the simplest example, but the concept extends to congruence modulo $n$ in number theory, similarity of geometric figures, isomorphism of algebraic structures, and countless other settings.

Every equivalence relation $\sim$ on a set $A$ partitions $A$ into disjoint equivalence classes: for each element $a \in A$, its equivalence class is $[a] = \{x \in A : x \sim a\}$, and the collection of all equivalence classes forms a partition of $A$ — a family of nonempty, pairwise disjoint subsets whose union is all of $A$. Conversely, every partition of $A$ determines an equivalence relation (declare two elements equivalent if they belong to the same block). This bijection between equivalence relations and partitions is one of the most useful structural results in naive set theory.

When a relation is reflexive and transitive but replaces symmetry with antisymmetry — the condition that $a \mathrel{R} b$ and $b \mathrel{R} a$ together imply $a = b$ — the result is a partial order. Partial orders formalize the idea of ranking or hierarchy: the subset relation $\subseteq$ on the power set of any set is a partial order, as is the divisibility relation on positive integers. If, in addition, every two elements are comparable (for any $a, b$, either $a \mathrel{R} b$ or $b \mathrel{R} a$), the partial order is a total order (or linear order) — the usual ordering $\leq$ on the real numbers is the prototypical example.

Finally, a function from $A$ to $B$ is a special kind of relation: it is a subset $f \subseteq A \times B$ such that for every $a \in A$, there is exactly one $b \in B$ with $(a, b) \in f$. This definition — a function as a set of ordered pairs satisfying a uniqueness condition — is one of the great conceptual achievements of the set-theoretic approach to mathematics. It frees the notion of function from any dependence on formulas, rules, or algorithms, and allows us to reason about functions with the full power of set theory. The deep study of functions, their properties, and their role in comparing the sizes of infinite sets is the subject of Functions and Cardinality.