comprehension axiom

The axiom of comprehension (CA) states that every formula defines a set. That is,

$$\exists X\forall x(x\in X\leftrightarrow \varphi (x))\text{for any formula}\varphi \text{where}X\text{does not occur free in}\varphi$$

The specification and separation are sometimes used in place of comprehension, particularly for weakened forms of the axiom (see below).

In theories which make no distinction between objects and sets (such as ZF), this formulation leads to Russell’s paradox, however in stratified theories this is not a problem (for example second order arithmetic includes the axiom of comprehension).

This axiom can be restricted in various ways. One possibility is to restrict it to forming subsets of sets:

$$\forall Y\exists X\forall x(x\in X\leftrightarrow x\in Y\wedge \varphi (x))\text{ for any formula }\varphi \text{ where }X\text{ does not occur free in }\varphi$$

This formulation (used in ZF set theory) is sometimes called the Aussonderungsaxiom.

Another way is to restrict $\varphi$ to some family $F$, giving the axiom F-CA. For instance the axiom ${\mathrm{\Sigma }}_1^0$ -CA is:

$$\exists X\forall x(x\in X\leftrightarrow \varphi (x))\text{ where }\varphi \text{ is }{\mathrm{\Sigma }}_1^0\text{ and }X\text{ does not occur free in }\varphi$$

A third form (usually called separation) uses two formulas, and guarantees only that those satisfying one are included while those satisfying the other are excluded. The unrestricted form is the same as unrestricted collection, but, for instance, ${\mathrm{\Sigma }}_1^0$ separation:

$$\forall x\mathrm{\neg }(\varphi (x)\wedge \psi (x))\to \exists X\forall x((\varphi (x)\to x\in X)\wedge (\psi (x)\to x\notin X))$$

$$\text{ where }\varphi \text{ and }\psi \text{ are }{\mathrm{\Sigma }}_1^0\text{ and }X\text{ does not occur free in }\varphi \text{ or }\psi$$

is weaker than ${\mathrm{\Sigma }}_1^0$ -CA.

Title	comprehension axiom
Canonical name	ComprehensionAxiom
Date of creation	2013-03-22 12:56:54
Last modified on	2013-03-22 12:56:54
Owner	Henry (455)
Last modified by	Henry (455)
Numerical id	10
Author	Henry (455)
Entry type	Definition
Classification	msc 03F35
Synonym	CA
Synonym	-CA
Synonym	comprehension
Synonym	comprehension axiom
Synonym	axiom of comprehension
Synonym	separation
Synonym	separation axiom
Synonym	axiom of separation
Synonym	specification
Synonym	specification axiom
Synonym	axiom of specification
Synonym	Aussonderungsaxiom