PlanetMath: comprehension axiom

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (213)
Orphanage
Unclass'd (1)
Unproven (473)
Corrections (38)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

comprehension axiom

(Definition)

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

$\displaystyle \exists X\forall x(x\in X\leftrightarrow\phi(x))$ for any formula $\displaystyle \phi$ where $\displaystyle X$ does not occur free in $\displaystyle \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:

$\displaystyle \forall Y\exists X\forall x(x\in X\leftrightarrow x\in Y\wedge\phi(x))$ for any formula $\displaystyle \phi$ where $\displaystyle X$ does not occur free in $\displaystyle \phi$

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

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

$\displaystyle \exists X\forall x(x\in X\leftrightarrow\phi(x))$ where $\displaystyle \phi$ is $\displaystyle \Sigma^0_1$ and $\displaystyle X$ does not occur free in $\displaystyle \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:

$\displaystyle \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))$

where $\displaystyle \phi$ and $\displaystyle \psi$ are $\displaystyle \Sigma^0_1$ and $\displaystyle X$ does not occur free in $\displaystyle \phi$ or $\displaystyle \psi$

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

"comprehension axiom" is owned by Henry.

(view preamble)

Other names:

CA, -CA, comprehension, comprehension axiom, axiom of comprehension, separation, separation axiom, axiom of separation, specification, specification axiom, axiom of specification, Aussonderungsaxiom

Log in to rate this entry.
(view current ratings)

Cross-references: collection, set theory, subsets, restricted, second order arithmetic, Russell's paradox, ZF, objects, theories, axiom, formula, states
There are 27 references to this entry.

This is version 6 of comprehension axiom, born on 2002-08-17, modified 2006-08-16.
Object id is 3307, canonical name is ComprehensionAxiom.
Accessed 19609 times total.

Classification:

AMS MSC:

03F35 (Mathematical logic and foundations :: Proof theory and constructive mathematics :: Second- and higher-order arithmetic and fragments)

Pending Errata and Addenda

None.[ View all 2 ]

Discussion

forum policy

No messages.

Interact