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.


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 ω .


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 .


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