Sets: Basics, Extensionality, and Russell's Paradox

What is a Set?

A set is an unordered collection of distinct objects. The objects in a set are called its elements or members.

Membership

We write $x \in A$ to mean ”$x$ is an element of $A$” and $x \notin A$ to mean ”$x$ is not an element of $A$”.

Examples

• $\{1, 2, 3\}$: the set containing 1, 2, and 3
• $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$: the set of natural numbers
• $\emptyset$ or $\{\}$: the empty set
• $\{x \in \mathbb{Z} : x^2 < 10\} = \{-3, -2, -1, 0, 1, 2, 3\}$

Extensionality

The Axiom of Extensionality

Two sets are equal if and only if they contain exactly the same elements:

$A = B \iff \forall x. (x \in A \Leftrightarrow x \in B)$

Consequences

• Order does not matter: $\{1, 2, 3\} = \{3, 2, 1\}$
• Repetition does not matter: $\{1, 1, 2, 2\} = \{1, 2\}$
• A set is determined entirely by its membership

Proof Strategy

To prove $A = B$: show that every element of $A$ is in $B$, and every element of $B$ is in $A$.

Subsets and Supersets

Definitions

• $A \subseteq B$ ($A$ is a subset of $B$): every element of $A$ is in $B$ $A \subseteq B \iff \forall x \in A. x \in B$

• $A \subsetneq B$ ($A$ is a proper subset of $B$): $A \subseteq B$ and $A \neq B$

• $A \supseteq B$ ($A$ is a superset of $B$): $B \subseteq A$

Properties

• Reflexivity: $A \subseteq A$
• Antisymmetry: $A \subseteq B \land B \subseteq A \Rightarrow A = B$
• Transitivity: $A \subseteq B \land B \subseteq C \Rightarrow A \subseteq C$

The Empty Set

The empty set $\emptyset$ is the unique set with no elements.

$\forall x. x \notin \emptyset$

Properties

• $\emptyset \subseteq A$ for any set $A$ (vacuously true)
• $|\emptyset| = 0$

Separation (Restricted Comprehension)

Naive Comprehension (Problematic)

The naive comprehension principle would allow: for any property $P$, form $\{x : P(x)\}$.

Russell’s Paradox

Consider the “set” $R = \{x : x \notin x\}$.

Is $R \in R$?

• If $R \in R$: then $R$ satisfies the defining property, so $R \notin R$. Contradiction.
• If $R \notin R$: then $R$ satisfies the defining property, so $R \in R$. Contradiction.

This is a genuine paradox, showing naive comprehension is inconsistent.

Separation Schema

Given a set $A$ and a property $P$, we can form:

$\{x \in A : P(x)\}$

This is restricted comprehension or separation: we can only form subsets of existing sets.

Set Operations

Union

$A \cup B = \{x : x \in A \lor x \in B\}$

Intersection

$A \cap B = \{x : x \in A \land x \in B\}$

Set Difference

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

Complement (Relative to a Universe $U$)

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

Laws of Set Algebra

Identity Laws

$A \cup \emptyset = A$ $A \cap U = A$

Domination Laws

$A \cup U = U$ $A \cap \emptyset = \emptyset$

Idempotent Laws

$A \cup A = A$ $A \cap A = A$

De Morgan’s Laws

$(A \cup B)^c = A^c \cap B^c$ $(A \cap B)^c = A^c \cup B^c$

Distributive Laws

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

---

Summary

• Sets are collections determined entirely by membership (extensionality)
• $A \subseteq B$ means every element of $A$ is in $B$
• Russell’s paradox shows naive comprehension is inconsistent
• Use separation: $\{x \in A : P(x)\}$ for safe set construction
• Sets form a Boolean algebra under $\cup$, $\cap$, complement