View source for Truncation error

'''General set theory (GST)''' is [[George Boolos]]'s (1998) name for a fragment of the [[axiomatic set theory]] [[Zermelo set theory|Z]]. GST is sufficient for all mathematics not requiring [[infinite set]]s, and is the weakest known set theory whose [[theorem]]s include the [[Peano axioms]].

==Ontology==
The ontology of GST is identical to that of [[ZFC]], and hence is thoroughly canonical. GST features a single [[primitive notion|primitive]] [[ontology|ontological]] notion, that of [[set (mathematics)|set]], and a single ontological assumption, namely that all individuals in the [[universe of discourse]] (hence all [[mathematical object]]s) are sets. There is a single [[primitive notion|primitive]] [[binary relation]], [[element (mathematics)|set membership]]; that set ''a'' is a member of set ''b'' is written ''a''∈''b'' (usually read "''a'' is an [[element (mathematics)|element]] of ''b''").

==Axioms==
The  symbolic axioms below are from Boolos (1998: 196), and govern how sets behave and interact. The natural language versions of the axioms are intended to aid the intuition. The background logic is [[first order logic]] with [[Identity (philosophy)|identity]].
<!-- The symbolic axioms should not be changed without discussion on the talk page. Altering these axioms would constitute original research. However the English descriptions may be changed. The choice of Boolos is open for discussion on the talk page. -->

1) [[Axiom of Extensionality]]: The sets ''x'' and ''y'' are the same set if they have the same members.
:<math>\forall x \forall y [\forall z [z \in x \leftrightarrow z \in y] \rightarrow x = y].</math>
The converse of this axiom follows from the substitution property of equality.

2) [[axiom schema of specification|Axiom Schema of Specification]] (or ''Separation'' or ''Restricted Comprehension''):  If ''z'' is a set and <math>\phi\!</math> is any property which may be satisfied by all, some, or no elements of ''z'', then there exists a subset ''y'' of ''z'' containing just those elements ''x'' in ''z'' which satisfy the property <math>\phi\!</math>. The [[restriction]] to ''z'' is necessary to avoid [[Russell's paradox]] and its variants. More formally, let <math>\phi(x)\!</math> be any formula in the language of GST in which ''x'' is free and ''y'' is not. Then all instances of the following schema are axioms:
:<math>\forall z \exists y \forall x [x \in y \leftrightarrow ( x \in z \land \phi(x))].</math>
<br>
3) ''Axiom of Adjunction'': If ''x'' and ''y'' are sets, then there exists a set ''w'', the ''adjunction'' of ''x'' and ''y'', whose members are just ''y'' and the members of ''x''.<ref>''Adjunction'' is seldom mentioned in the literature. Exceptions are Burgess (2005) ''passim'', and QIII in Tarski and Givant (1987: 223).</ref>
<!-- :<math> \forall x \forall z \exist y \forall v [v \in y \leftrightarrow (v \in z \or v=x)].</math>-->

:<math>\forall x \forall y \exist w \forall z [ z \in w \leftrightarrow (z \in x \or z=y)].</math>

''Adjunction'' refers to an elementary operation on two sets, and has no bearing on the use of that term elsewhere in mathematics, including in [[adjoint functor|category theory]].

==Discussion==
GST is the fragment of [[Zermelo set theory|Z]] obtained by omitting the axioms [[axiom of union|Union]], [[axiom of power set|Power Set]], [[axiom of infinity|Infinity]], and [[axiom of choice|Choice]], then taking Adjunction, a theorem of Z, as an axiom. The result is a [[first order theory]].

Setting &phi;(''x'') in ''Separation'' to ''x''&ne;''x'', and assuming that the [[Domain of a function|domain]] is nonempty, assures the existence of the [[empty set]]. ''Adjunction'' implies that if ''x'' is a set, then so is <math>S(x) = x \cup \{x\}</math>. Given ''Adjunction'', the usual construction of the [[successor ordinal]]s from the [[empty set]] can proceed, one in which the [[natural number]]s are defined as <math>\varnothing,\,S(\varnothing),\,S(S(\varnothing)),\,\ldots,</math> (see [[Peano's axioms]]). More generally, given any model ''M'' of ZFC, the collection of [[hereditarily finite set]]s in ''M'' will satisfy the GST axioms. Therefore, GST cannot prove the existence of even a countable [[infinite set]], that is, of a set whose cardinality is ℵ<sub>0</sub>. Even if GST did afford a countably infinite set, GST could not prove the existence of a set whose [[cardinality]] is <math>\aleph_1</math>, because GST lacks the [[axiom of power set]]. Hence GST cannot ground [[Mathematical analysis|analysis]] and [[geometry]], and is too weak to serve as a [[foundation of mathematics|foundation for mathematics]].

Boolos was interested in GST only as a fragment of [[Zermelo set theory|Z]] that is just powerful enough to interpret [[Peano arithmetic]]. He never lingered over GST, only mentioning it briefly in several papers discussing the systems of [[Frege]]'s ''[[The Foundations of Arithmetic|Grundlagen]]'' and ''Grundgesetze'', and how they could be modified to eliminate [[Russell's paradox]]. The system '''A&xi;''''[&delta;<sub>0</sub>] in Tarski and Givant (1987: 223) is essentially GST with an [[Peano axioms|axiom schema of induction]] replacing [[axiom schema of specification|Specification]], and with the existence of a [[null set]] explicitly assumed.

GST is called STZ in Burgess (2005), p.&nbsp;223.<ref>The [[axiom of empty set|Null Set]] axiom in STZ is redundant, because the existence of the null set is derivable from the axiom schema of Specification.</ref> Burgess's theory ST<ref>Called S' in Tarski et al. (1953: 34).</ref> is GST with [[axiom of empty set|Null Set]] replacing the [[axiom schema of specification]]. That the letters "ST" also appear in "GST" is a coincidence.

==Metamathematics==
The most remarkable fact about ST (and hence GST), is that these tiny fragments of set theory give rise to such rich metamathematics. While ST is a small fragment of the well-known canonical set theories [[ZFC]] and [[Von Neumann–Bernays–Gödel set theory|NBG]], ST [[interpretability|interprets]] [[Robinson arithmetic]] (Q), so that ST inherits the nontrivial metamathematics of Q. For example, ST is [[decidability (logic)|essentially undecidable]] because Q is, and every consistent theory whose theorems include the ST axioms is also essentially undecidable.<ref>Burgess (2005), 2.2, p. 91.</ref> This includes GST and every axiomatic set theory worth thinking about, assuming these are consistent. In fact, the [[decidability (logic)|undecidability]] of ST implies the undecidability of [[first-order logic]] with a single [[binary predicate]] letter.<ref>Tarski et al. (1953), p. 34.</ref>

Q is also incomplete in the sense of [[Gödel's incompleteness theorem]]. Any axiomatizable theory, such as ST and GST, whose theorems include the Q axioms is likewise incomplete. Moreover, the [[consistency]] of GST cannot be proved within GST itself, unless GST is in fact inconsistent.

GST is:
*Mutually interpretable with [[Peano arithmetic]] (thus it has the same proof-theoretic strength as PA);
*Immune to the three great antinomies of [[naïve set theory]]: [[Russell's paradox|Russell's]], [[Burali-Forti paradox|Burali-Forti's]], and [[Cantor's paradox|Cantor's]];
*Not [[axiom schema|finitely axiomatizable]]. Montague (1961) showed that [[ZFC]] is not finitely axiomatizable, and his argument carries over to GST. Hence any axiomatization of GST must either include at least one [[axiom schema]] such as [[Axiom schema of specification|Separation]];
*Interpretable in [[relation algebra]] because no part of any GST axiom lies in the scope of more than three [[quantifier]]s. This is the [[necessary and sufficient condition]] given in Tarski and Givant (1987).

== Footnotes ==
{{reflist|2}}

==References==
*[[George Boolos]] (1998) ''Logic, Logic, and Logic''. Harvard Univ. Press.
*Burgess, John, 2005. ''Fixing Frege''. Princeton Univ. Press.
*[[Richard Montague]] (1961) "Semantical closure and non-finite axiomatizability" in ''Infinistic Methods''. Warsaw: 45-69.
* [[Alfred Tarski]], [[Andrzej Mostowski]], and [[Raphael Robinson]] (1953) ''Undecidable Theories''. North Holland.
* Tarski, A., and Givant, Steven (1987) ''A Formalization of Set Theory without Variables''. Providence RI: AMS Colloquium Publications, v. 41.

==External links==
* [[Stanford Encyclopedia of Philosophy]]: [http://plato.stanford.edu/entries/set-theory/ Set Theory]—by Thomas Jech.

[[Category:Systems of set theory]]
[[Category:Z notation]]