# The axiom scheme of replacement

## 1. The axiom scheme of replacement

We saw that there are two kinds of functions in axiomatic set theory: class functions and set functions. A class function is a rule, defined by a first order formula. A set function is a function which is a set of pairs. The axiom scheme of replacement relates these two notions.

Axiom Scheme of Replacement: for any first order $ϕ ( x , y , a _ )$, if $∀ x ∃ y ϕ ( x , y , a _ )$ and $b$ is a set then ${ ⟨ u , v ⟩ : u ∈ b ∧ ϕ ( u , v , a _ ) }$ is a set.

This is a new general principle building sets, and another instance of Frege's comprehension axiom. It was added by Fraenkel after Zermelo proposed his earlier set of axioms. (Zermelo endorsed the addition - he said that he had overlooked it originally.)

## 2. Transitive sets and transitive closure

As an application, we look at the idea of transitive sets.

Definition.

A set $x$ is transitive if for all $u , v$ if $u ∈ v$ and $v ∈ x$ then $u ∈ x$.

To find examples of transitive sets we apply the recursion theorem on $ω$.

Definition.

We define $TC ( x , n )$ by $TC ( x , 0 ) = x$ and $TC ( x , n +1 ) = ⋃ TC ( x , n )$.

Using replacement, $t = { TC ( x , n ) : n ∈ ω }$ is a set. We let $TC ( x )$ be the set $⋃ t$ and call this the transitive closure of $x$.

Theorem.

(a) The transitive closure of $x$ is transitive. (b) If $y ⊇ x$ and $y$ is transitive then $y ⊇ TC ( x )$.

Proof.

Exercise.