## You are here

Homecomprehension axiom

## Primary tabs

# comprehension axiom

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

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

The names 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\phi(x))\text{ % for any formula }\phi\text{ where }X\text{ does not occur free in }\phi$ |

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

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

$\exists X\forall x(x\in X\leftrightarrow\phi(x))\text{ where }\phi\text{ is }% \Sigma^{0}_{1}\text{ and }X\text{ does not occur free in }\phi$ |

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, $\Sigma^{0}_{1}$ separation:

$\forall x\neg(\phi(x)\wedge\psi(x))\rightarrow\exists X\forall x((\phi(x)% \rightarrow x\in X)\wedge(\psi(x)\rightarrow x\notin X))$ |

$\text{ where }\phi\text{ and }\psi\text{ are }\Sigma^{0}_{1}\text{ and }X\text% { does not occur free in }\phi\text{ or }\psi$ |

is weaker than $\Sigma^{0}_{1}$ -CA.

## Mathematics Subject Classification

03F35*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new correction: examples and OEIS sequences by fizzie

Oct 13

new correction: Define Galois correspondence by porton

Oct 7

new correction: Closure properties on languages: DCFL not closed under reversal by babou

new correction: DCFLs are not closed under reversal by petey

new question: Lorenz system by David Bankom

Oct 2

new correction: Many corrections by Smarandache

Sep 28

new question: how to contest an entry? by zorba

new question: simple question by parag

Sep 26

new question: Latent variable by adam_reith