## Zermelo-Fraenkel Set Theory

### Axioms of ZF

Extensionality:
xy[∀z(zxzy) → x=y]

This axiom asserts that when sets x and y have the same members, they are the same set.

The next axiom asserts the existence of the empty set:

Null Set:
x¬∃y(yx)

Since it is provable from this axiom and the previous axiom that there is a unique such set, we may introduce the notation ‘∅’ to denote it.

The next axiom asserts that if given any set x and y, there exists a pair set of x and y, i.e., a set which has only x and y as members:

Pairs:
xyzw(wzw=xw=y)

Since it is provable that there is a unique pair set for each given x and y, we introduce the notation ‘{x,y}’ to denote it.

The next axiom asserts that for any given set x, there is a set y which has as members all of the members of all of the members of x:

Unions:
xyz[zy ≡ ∃w(wx & zw)]

Since it is provable that there is a unique ‘union’ of any set x, we introduce the notation ‘∪x’ to denote it.

The next axiom asserts that for any set x, there is a set y which contains as members all those sets whose members are also elements of x, i.e., y contains all of the subsets of x:

Power Set:
xyz[zy ≡ ∀w(wzwx)]

Since every set provably has a unique ‘power set’, we introduce the notation ‘℘(x)’ to denote it. Note also that we may define the notion x is a subset of y (‘xy’) as: ∀z(zx → zy). Then we may simplify the statement of the Power Set Axiom as follows:

xyz[zyzx)

The next axiom asserts the existence of an infinite set, i.e., a set with an infinite number of members:

Infinity:
x[∅∈x  &  ∀y(yx → ∪{y,{y}}∈x)]

We may think of this as follows. Let us define the union of x and y (‘xy’) as the union of the pair set of x and y, i.e., as ∪{x,y}. Then the Axiom of Infinity asserts that there is a set x which contains ∅ as a member and which is such that whenever a set y is a member of x, then y∪{y} is a member of x. Consequently, this axiom guarantees the existence of a set of the following form:

{∅,   {∅},   {∅, {∅}},   {∅, {∅}, {∅, {∅}}},   … }

Notice that the second element, {∅}, is in this set because (1) the fact that ∅ is in the set implies that ∅ ∪ {∅} is in the set and (2) ∅ ∪ {∅} just is {∅}. Similarly, the third element, {∅, {∅}}, is in this set because (1) the fact that {∅} is in the set implies that {∅} ∪ {{∅}} is in the set and (2) {∅} ∪ {{∅}} just is {∅, {∅}}. And so forth.

The next axiom asserts that every set is ‘well-founded’:

Regularity:
x[x≠∅ → ∃y(yx & ∀z(zx → ¬(zy)))]

A member y of a set x with this property is called a ‘minimal’ element. This axiom rules out the existence of circular chains of sets (e.g., such as xy & yz & and zx) as well as infinitely descending chains of sets (such as … x3 ∈ x2 ∈ x1 ∈ x0).

The final axiom of ZF is the Replacement Schema. Suppose that φ(x,y,û) is a formula with x and y free, and let û represent the variables u1,…,uk, which may or may not be free in φ. Furthermore, let φx,y,û[s,r,û] be the result of substituting s and r for x and y, respectively, in φ(x,y,û). Then every instance of the following schema is an axiom:

Replacement Schema:
u1…∀uk[∀x∃!yφ(x,y,û) →
∀wvr(rv ≡ ∃s(sw & φx,y,û[s,r,û]))]

In other words, if we know that φ is a functional formula (which relates each set x to a unique set y), then if we are given a set w, we can form a new set v as follows: collect all of the sets to which the members of w are uniquely related by φ.

Note that the Replacement Schema can take you ‘out of’ the set w when forming the set v. The elements of v need not be elements of w. By contrast, the well-known Separation Schema of Zermelo yields new sets consisting only of those elements of a given set w which satisfy a certain condition ψ. That is, suppose that ψ(x,û) has x free and may or may not have u1,…,uk free. And let ψx,û[r,û] be the result of substituting r for x in ψ(x,û). Then the Separation Schema asserts:

Separation Schema:
u1…∀uk[∀wvr(rvrw & ψx,û[r,û])]

In other words, if given a formula ψ and a set w, there exists a set v which has as members precisely the members of w which satisfy the formula ψ.