Jaysen Tsao
Discrete Mathematics for Computer Science

Zermelo-Fraenkel Set Theory

Limitations of Naive Set Theory

Theorem 17: Russell’s Paradox

The “set” 𝑅={𝑥|𝑥𝑥} is not well-defined.

Natural Numbers as Sets

Definition 66: Von Neumann Numerals

The von Neumann numeral 𝑁𝑘 for a natural number 𝑘 is defined as the set of all von Neumann numerals less than 𝑘, or if 𝑘=0. Formally:

𝑁𝑘={ if 𝑘=0{𝑁0,𝑁1,,𝑁𝑘1} otherwise

Definition 67: Successor Function

The successor function, denoted succ, is defined as follows:

succ(𝑥)=𝑥{𝑥}.

Theorem 18: Validity of Successor Function

Let 𝑁𝑘 be the von Neumann numeral for any 𝑘. Then:

succ(𝑁𝑘)=𝑁𝑘+1.

Zermelo-Fraenkel Axioms

Definition 68: Zermelo-Fraenkel Axioms

  1. Extensionality. Two sets are equal if and only if they have the same elements:

    𝑥𝑦[𝑧(𝑧𝑥𝑧𝑦)𝑥=𝑦].
  2. Regularity.