Axiom schema of replacement

related topics
{math, number, function}

In set theory, the axiom schema of replacement is a schema of axioms in Zermelo-Fraenkel set theory (ZFC) that asserts that the image of any set under any definable mapping is also a set. It is necessary for the construction of certain infinite sets in ZFC.

The axiom schema is motivated by the idea that whether a class is a set depends only on the cardinality of the class, not on the rank of its elements. Thus, if one class is "small enough" to be a set, and there is a bijection from that class to a second class, the axiom states that the second class is also a set. However, because ZFC only speaks of sets, not proper classes, the schema is stated only for definable bijections, which are identified with their defining formulas.

Contents

Statement

Suppose P is a definable binary relation (which may be a proper class) such that for every set x there is a unique set y such that P(x,y) holds. There is a corresponding definable function FP, where FP(X) = Y if and only if P(X,Y); F will also be a proper class if P is. Consider the (possibly proper) class B defined such for every set y, y is in B if and only if there is an x in A with FP(x) = y. B is called the image of A under FP, and denoted FP(A) or (using set-builder notation) {FP(x) : xA}.

The axiom schema of replacement states that if F is a definable class function, as above, and A is any set, then the image F(A) is also a set. This can be seen as a principle of smallness: the axiom states that if A is small enough to be a set, then F(A) is also small enough to be a set. It is implied by the stronger axiom of limitation of size.

Because it is impossible to quantify over definable functions in first-order logic, one instance of the schema is included for each formula φ in the language of set theory with free variables among w1, ... , wn, A, x, y; but B is not free in φ. In the formal language of set theory, the axiom schema is:

Axiom schema of collection

The axiom schema of collection is closely related to and frequently confused with the axiom schema of replacement. While replacement says that the image itself is a set, collection merely says that a superclass of the image is a set. In other words, the resulting set, B, is not required to be minimal.

Full article ▸

related documents
Heine–Borel theorem
Euclidean algorithm
Glossary of topology
Pushdown automaton
Factorization
Linear independence
Binary relation
Presentation of a group
Type theory
Abstract interpretation
E (mathematical constant)
Random variable
Probability density function
Algebraic structure
Linear combination
Ideal class group
Homology (mathematics)
IEEE 754-1985
Elliptic curve
Sequence
Goldbach's conjecture
Gaussian quadrature
Dijkstra's algorithm
Natural transformation
Breadth-first search
Chaitin's constant
Fuzzy logic
Wiener process
Euler characteristic
Absolute convergence