06 Set Theory and Russels Paradox

Lecture from: 07.10.2024 | Video: Videos ETHZ

Set Theory

Set theory is the mathematical study of collections, called sets, and their relationships.

Basic Definitions

• Set: A well-defined collection of distinct objects called elements. Formally, a set $S$ is denoted by curly braces: $\{e_1,e_2,...,e_n\}$ where each $e_i$ is an element of $S$.
• Element: An individual object contained within a set. The symbol $\in$ indicates membership in a set. For example, if $A=\{1,2,3\}$, then $2\in A$ but $4\notin A$.
• Empty Set: A set containing no elements, denoted by $\varnothing$ or {}.

Set Operations

• Union ($\cup$): The union of two sets $A$ and $B$, denoted $A\cup B$, is the set containing all elements that are in either $A$, $B$, or both.
• Intersection ($\cap$): The intersection of two sets $A$ and $B$, denoted $A\cap B$, is the set containing all elements common to both $A$ and $B$.
• Difference (- or \): The difference of two sets $A$ and $B$, denoted $AB$, is the set containing all elements that are in $A$ but not in $B$.
• Subset ($\subseteq$): Set $A$ is a subset of set $B$ (denoted $A\subseteq B$) if every element of $A$ is also an element of $B$.

Union & Intersection:

Difference:

Subset:

Russell’s Paradox

Imagine a special set called “R” that contains all sets that don’t contain themselves as members. Sounds straightforward, right?

Now, here’s the mind-bending part: Does “R” contain itself?

• If “R” does contain itself, then it breaks its own rule – it shouldn’t include sets that contain themselves!
• If “R” doesn’t contain itself, well, that means it should be in the set because it fits the description of a set that doesn’t contain itself.

This paradox can be represented mathematically:

Let $R=\{A|A\notin A\}$

where the notation $\{A|...\}$ denotes the set comprehension, meaning “the set of all $A$ such that…“.

Contradiction: We have a contradiction! If $R\in R$, then by definition $R\notin R$. Conversely, if $R\notin R$, then it should belong to $R$ according to its own definition.

This paradox demonstrates the danger of defining sets without strict rules. Mathematicians needed a more rigorous foundation for set theory to avoid such contradictions.

The Foundation: Axiomatic Set Theory and Constructing Natural Numbers

Early, “naive” set theory operated on the intuitive idea that any property could be used to define a set. This principle, known as unrestricted comprehension, led directly to contradictions like Russell’s Paradox. The paradox arises when considering the set $R=\{x\mid x\notin x\}$. The existence of such a set is logically impossible. Similarly, the concept of a Universal Set, $U$, a set containing all possible sets, also leads to this paradox.

Zermelo’s axiomatic set theory (which forms the basis of the modern standard, ZFC) resolved these issues not by using a universal set, but by rejecting its existence. Instead of allowing any property to form a set, ZFC provides a list of axioms that carefully control how sets can be built. This provides a clear, consistent foundation and avoids the paradoxes of naive set theory.

Within this axiomatic framework, we begin with fundamental building blocks and rules for construction:

• The Empty Set: The axioms guarantee the existence of a set with no elements, denoted $\varnothing$. It serves as the ultimate starting point for all constructions.

• Natural Numbers: Using the empty set and axioms like the Axiom of Pairing and the Axiom of Union, we can define the natural numbers recursively (this is the standard von Neumann construction):

  • 0 = $\varnothing$
  • 1 = $\{0\}=\{\varnothing \}$
  • 2 = $\{0,1\}=\{\varnothing ,\{\varnothing \}\}$
  • 3 = $\{0,1,2\}=\{\varnothing ,\{\varnothing \},\{\varnothing ,\{\varnothing \}\}\}$
  • … and so on.

Each natural number is defined as the set of all preceding natural numbers. This construction is rigorously controlled by the axioms. Russell’s Paradox is avoided because the axioms, particularly the Axiom of Specification (or Separation), do not permit the formation of a “set of all sets” or other paradoxical collections. You can only form subsets of already existing sets, which prevents the system from contradicting itself.

Zermelo’s approach provides a solid foundation for set theory, avoiding the pitfalls of Russell’s Paradox and enabling the construction of complex mathematical structures with precise definitions.

If we were delving deeper into traditional mathematics, we’d naturally progress to defining operations like addition and multiplication for these sets representing natural numbers. However, in computer science, our focus is more practical. We’re less concerned with the abstract theoretical underpinnings and more interested in how these concepts can be used to build and understand real-world systems.

Continue here: 07 Equality, Ordered Pairs, Cartesian Product, Power Set and Relationships