Difference between revisions of "Positive set theory"
Line 1: | Line 1: | ||
''Positive set theory'' is the name of a certain group of axiomatic set theories originally created as an example of a (nonstandard) set theories in which the axiom of foundation fails (e.g. there exists $x$ such that $x\in x$). <cite>FortiHinnion89:ConsitencyProblemPositiveComp</cite> Those theories are based on a weakening of the (inconsistent) ''comprehension axiom'' of [[naive set theory]] (which asserts that every formula $\phi(x)$ defines a set that contains all $x$ such that $\phi(x)$) by restraining the formulas used to a smaller class of formulas called ''positive'' formulas. | ''Positive set theory'' is the name of a certain group of axiomatic set theories originally created as an example of a (nonstandard) set theories in which the axiom of foundation fails (e.g. there exists $x$ such that $x\in x$). <cite>FortiHinnion89:ConsitencyProblemPositiveComp</cite> Those theories are based on a weakening of the (inconsistent) ''comprehension axiom'' of [[naive set theory]] (which asserts that every formula $\phi(x)$ defines a set that contains all $x$ such that $\phi(x)$) by restraining the formulas used to a smaller class of formulas called ''positive'' formulas. | ||
− | While most positive set theories are weaker than [[ZFC]] (and usually mutually interpretable with [[:wikipedia:second-order arithmetic|second-order arithmetic]]), one of them, | + | While most positive set theories are weaker than [[ZFC|$\text{ZFC}$]] (and usually mutually interpretable with [[:wikipedia:second-order arithmetic|second-order arithmetic]]), one of them, $\text{GPK}^+_\infty$ turns out to be very powerful, being mutually interpretable with [[Morse-Kelley set theory]] plus an axiom asserting that the class of all [[ordinal|ordinals]] is [[weakly compact]]. <cite>Esser96:InterpretationZFCandMKinPositiveTheory</cite> |
== Positive formulas == | == Positive formulas == | ||
Line 12: | Line 12: | ||
A formula is then a ''GPF formula'' (generalized positive formula) if it is a BPF formula or if it is of the form $\forall x(\theta(x)\Rightarrow\varphi)$ with $\theta(x)$ a GPF formula with exactly one free variable $x$ and no parameter and $\varphi$ is a GPF formula (possibly with parameters). <cite>Esser96:GPKAFA</cite> | A formula is then a ''GPF formula'' (generalized positive formula) if it is a BPF formula or if it is of the form $\forall x(\theta(x)\Rightarrow\varphi)$ with $\theta(x)$ a GPF formula with exactly one free variable $x$ and no parameter and $\varphi$ is a GPF formula (possibly with parameters). <cite>Esser96:GPKAFA</cite> | ||
− | == GPK positive set theories == | + | == $\text{GPK}$ positive set theories == |
− | The positive set theory GPK consists of the following axioms: | + | The positive set theory $\text{GPK}$ consists of the following axioms: |
* '''Empty set''': $\exists x\forall y(y\not\in x)$. | * '''Empty set''': $\exists x\forall y(y\not\in x)$. | ||
* '''Extensionality''': $\forall x\forall y(x=y\Leftrightarrow\forall z(z\in x\Leftrightarrow z\in y))$. | * '''Extensionality''': $\forall x\forall y(x=y\Leftrightarrow\forall z(z\in x\Leftrightarrow z\in y))$. | ||
* '''GPF comprehension''': the universal closure of $\exists x\forall y(y\in x\Leftrightarrow\varphi)$ for every GPF formula $\varphi$ (with parameters) in which $x$ does not occur. | * '''GPF comprehension''': the universal closure of $\exists x\forall y(y\in x\Leftrightarrow\varphi)$ for every GPF formula $\varphi$ (with parameters) in which $x$ does not occur. | ||
− | The empty set axiom is necessary, as without it the theory would hold in the trivial model which has only one element satisfying $x=\{x\}$. Note that, while GPK do proves the existence of a set such that $x\in x$, Olivier Esser proved that it refutes the [[:wikipedia:anti-foundation axiom|anti-foundation axiom]] (AFA). <cite>Esser96:GPKAFA</cite> | + | The empty set axiom is necessary, as without it the theory would hold in the trivial model which has only one element satisfying $x=\{x\}$. Note that, while $\text{GPK}$ do proves the existence of a set such that $x\in x$, Olivier Esser proved that it refutes the [[:wikipedia:anti-foundation axiom|anti-foundation axiom]] (AFA). <cite>Esser96:GPKAFA</cite> |
− | The theory | + | The theory $\text{GPK}^+$ is obtained by adding the following axiom: |
* '''Closure''': the universal closure of $\exists x(\forall z(\varphi(z)\Rightarrow z\in x)\land\forall y(\forall w(\varphi(z)\Rightarrow z\in y)\Rightarrow y\subset x))$ for every formula $\varphi(z)$ (not necessarily BPF or GPF) with a free variable $z$ (and possibly parameters) such that $x$ does not occur in $\varphi$. | * '''Closure''': the universal closure of $\exists x(\forall z(\varphi(z)\Rightarrow z\in x)\land\forall y(\forall w(\varphi(z)\Rightarrow z\in y)\Rightarrow y\subset x))$ for every formula $\varphi(z)$ (not necessarily BPF or GPF) with a free variable $z$ (and possibly parameters) such that $x$ does not occur in $\varphi$. | ||
This axiom scheme asserts that for any (possibly proper) class $C=\{x|\varphi(x)\}$ there is a smallest set $X$ containing $C$, i.e. $C\subset X$ and for all sets $Y$ such that $C\subset Y$, one has $X\subset Y$. <cite>Esser99:ConsistencyPositiveTheory</cite> | This axiom scheme asserts that for any (possibly proper) class $C=\{x|\varphi(x)\}$ there is a smallest set $X$ containing $C$, i.e. $C\subset X$ and for all sets $Y$ such that $C\subset Y$, one has $X\subset Y$. <cite>Esser99:ConsistencyPositiveTheory</cite> | ||
− | Note that replacing GPF comprehension in | + | Note that replacing GPF comprehension in $\text{GPK}^+$ by BPF comprehension does not make the theory any weaker: BPF comprehension plus Closure implies GPF comprehension. |
− | Both GPK and | + | Both $\text{GPK}$ and $\text{GPK}^+$ are consistent relative to $\text{ZFC}$, in fact mutually interpretable with second-order arithmetic. However a much stronger theory, '''$\text{GPK}^+_\infty$''', is obtained by adding the following axiom: |
* '''Infinity''': the von Neumann ordinal $\omega$ is a set. | * '''Infinity''': the von Neumann ordinal $\omega$ is a set. | ||
− | By "von Neumann ordinal" we mean the usual definition of ordinals as well-ordered-by-inclusion sets containing all the smaller ordinals. Here $\omega$ is the set of all finite ordinals (the natural numbers). The point of this axiom is not implying the existence of an infinite set; the ''class'' $\omega$ exists, so it has a set closure which is certainely infinite. This set closure happens to satisfy the usual axiom of infinity of ZFC (i.e. it contains 0 and the successor of all its members) but in | + | By "von Neumann ordinal" we mean the usual definition of ordinals as well-ordered-by-inclusion sets containing all the smaller ordinals. Here $\omega$ is the set of all finite ordinals (the natural numbers). The point of this axiom is not implying the existence of an infinite set; the ''class'' $\omega$ exists, so it has a set closure which is certainely infinite. This set closure happens to satisfy the usual axiom of infinity of $\text{ZFC}$ (i.e. it contains 0 and the successor of all its members) but in $\text{GPK}^+$ this is not enough to deduce that $\omega$ itself is a set (an improper class). |
− | Olivier Esser showed that | + | Olivier Esser showed that $\text{GPK}^+_\infty$ can not only interpret $\text{ZFC}$ (and prove it consistent), but is in fact mutually interpretable with a ''much'' stronger set theory, namely, Morse-Kelley set theory with an axiom asserting that the (proper) class of all ordinals is [[weakly compact]]. This theory is powerful enough to prove, for instance, that there exists a proper class of [[Mahlo|hyper-Mahlo]] cardinals. <cite>Esser96:InterpretationZFCandMKinPositiveTheory</cite> |
== As a topological set theory == | == As a topological set theory == | ||
''To be expanded.'' | ''To be expanded.'' | ||
− | == The axiom of choice and GPK set theories == | + | == The axiom of choice and $\text{GPK}$ set theories == |
''To be expanded. <cite>Esser2000:InconsistencyACwithGPK</cite><cite>FortiHinnion89:ConsitencyProblemPositiveComp</cite>'' | ''To be expanded. <cite>Esser2000:InconsistencyACwithGPK</cite><cite>FortiHinnion89:ConsitencyProblemPositiveComp</cite>'' | ||
== Other positive set theories and the inconsistency of the axiom of extensionality == | == Other positive set theories and the inconsistency of the axiom of extensionality == |
Revision as of 14:24, 11 November 2017
Positive set theory is the name of a certain group of axiomatic set theories originally created as an example of a (nonstandard) set theories in which the axiom of foundation fails (e.g. there exists $x$ such that $x\in x$). [1] Those theories are based on a weakening of the (inconsistent) comprehension axiom of naive set theory (which asserts that every formula $\phi(x)$ defines a set that contains all $x$ such that $\phi(x)$) by restraining the formulas used to a smaller class of formulas called positive formulas.
While most positive set theories are weaker than $\text{ZFC}$ (and usually mutually interpretable with second-order arithmetic), one of them, $\text{GPK}^+_\infty$ turns out to be very powerful, being mutually interpretable with Morse-Kelley set theory plus an axiom asserting that the class of all ordinals is weakly compact. [2]
Contents
Positive formulas
In the first-order language $\{=,\in\}$, we define a BPF formula (bounded positive formula) the following way [2]: For every variable $x$, $y$ and BPF formulas $\varphi$, $\psi$,
- $x=y$ and $x\in y$ are BPF.
- $\varphi\land\psi$, $\varphi\lor\psi$, $\exists x\varphi$ and $(\forall x\in y)\varphi$ are BPF.
A formula is then a GPF formula (generalized positive formula) if it is a BPF formula or if it is of the form $\forall x(\theta(x)\Rightarrow\varphi)$ with $\theta(x)$ a GPF formula with exactly one free variable $x$ and no parameter and $\varphi$ is a GPF formula (possibly with parameters). [3]
$\text{GPK}$ positive set theories
The positive set theory $\text{GPK}$ consists of the following axioms:
- Empty set: $\exists x\forall y(y\not\in x)$.
- Extensionality: $\forall x\forall y(x=y\Leftrightarrow\forall z(z\in x\Leftrightarrow z\in y))$.
- GPF comprehension: the universal closure of $\exists x\forall y(y\in x\Leftrightarrow\varphi)$ for every GPF formula $\varphi$ (with parameters) in which $x$ does not occur.
The empty set axiom is necessary, as without it the theory would hold in the trivial model which has only one element satisfying $x=\{x\}$. Note that, while $\text{GPK}$ do proves the existence of a set such that $x\in x$, Olivier Esser proved that it refutes the anti-foundation axiom (AFA). [3]
The theory $\text{GPK}^+$ is obtained by adding the following axiom:
- Closure: the universal closure of $\exists x(\forall z(\varphi(z)\Rightarrow z\in x)\land\forall y(\forall w(\varphi(z)\Rightarrow z\in y)\Rightarrow y\subset x))$ for every formula $\varphi(z)$ (not necessarily BPF or GPF) with a free variable $z$ (and possibly parameters) such that $x$ does not occur in $\varphi$.
This axiom scheme asserts that for any (possibly proper) class $C=\{x|\varphi(x)\}$ there is a smallest set $X$ containing $C$, i.e. $C\subset X$ and for all sets $Y$ such that $C\subset Y$, one has $X\subset Y$. [4]
Note that replacing GPF comprehension in $\text{GPK}^+$ by BPF comprehension does not make the theory any weaker: BPF comprehension plus Closure implies GPF comprehension.
Both $\text{GPK}$ and $\text{GPK}^+$ are consistent relative to $\text{ZFC}$, in fact mutually interpretable with second-order arithmetic. However a much stronger theory, $\text{GPK}^+_\infty$, is obtained by adding the following axiom:
- Infinity: the von Neumann ordinal $\omega$ is a set.
By "von Neumann ordinal" we mean the usual definition of ordinals as well-ordered-by-inclusion sets containing all the smaller ordinals. Here $\omega$ is the set of all finite ordinals (the natural numbers). The point of this axiom is not implying the existence of an infinite set; the class $\omega$ exists, so it has a set closure which is certainely infinite. This set closure happens to satisfy the usual axiom of infinity of $\text{ZFC}$ (i.e. it contains 0 and the successor of all its members) but in $\text{GPK}^+$ this is not enough to deduce that $\omega$ itself is a set (an improper class).
Olivier Esser showed that $\text{GPK}^+_\infty$ can not only interpret $\text{ZFC}$ (and prove it consistent), but is in fact mutually interpretable with a much stronger set theory, namely, Morse-Kelley set theory with an axiom asserting that the (proper) class of all ordinals is weakly compact. This theory is powerful enough to prove, for instance, that there exists a proper class of hyper-Mahlo cardinals. [2]
As a topological set theory
To be expanded.
The axiom of choice and $\text{GPK}$ set theories
Other positive set theories and the inconsistency of the axiom of extensionality
To be expanded. [6]
References
- Forti, M and Hinnion, R. The Consistency Problem for Positive Comprehension Principles. J Symbolic Logic 54(4):1401--1418, 1989. bibtex
- Esser, Olivier. An Interpretation of the Zermelo-Fraenkel Set Theory and the Kelley-Morse Set Theory in a Positive Theory. Mathematical Logic Quarterly 43:369--377, 1997. www DOI bibtex
- Esser, Olivier. Inconsistency of GPK+AFA. Mathematical Logic Quarterly 42:104--108, 1996. www DOI bibtex
- Esser, Olivier. On the Consistency of a Positive Theory. Mathematical Logic Quarterly 45:105--116, 1999. www DOI bibtex
- Esser, Olivier. Inconsistency of the Axiom of Choice with the Positive Theory $GPK^+_\infty$. Journal of Symbolic Logic 65(4):1911--1916, Dec., 2000. www DOI bibtex
- Esser, Olivier. On the axiom of extensionality in the positive set theory. Mathematical Logic Quarterly 19:97--100, 2003. www DOI bibtex
This article is a stub. Please help us to improve Cantor's Attic by adding information.