- General set theory
General set theory (GST) is
George Boolos 's (1998) name for a three-axiom fragment of the canonicalaxiomatic set theory Z. GST is sufficient for all mathematics not requiringinfinite set s, and is the weakest known set theory whosetheorem s include thePeano axioms .Ontology
GST features a single primitive ontological notion, that of
set , and a single ontological assumption, namely that all individuals in theuniverse of discourse (i.e., all mathematical objects) are sets. There is a single primitivebinary relation , set membership; that set "a" is a member of set "b" is written "a"∈"b" (usually read "a" is an 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.
1)
Axiom of Extensionality : The sets "x" and "y" are the same set if they have the same members.:forall x forall y [forall z [z in x leftrightarrow z in y] ightarrow x = y] .The converse of this axiom follows from the substitution property of equality.2)
Axiom Schema of Specification (or "Separation" or "Restricted Comprehension"): If "z" is a set and phi! 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 phi!. Therestriction to "z" is necessary to avoidRussell's paradox and its variants. More formally, let phi(x)! be any formula in the language of GST in which "x" appears free and "y" is not free. Then all instances of the following schema are axioms::forall z exists y forall x [x in y leftrightarrow ( x in z land phi(x))] .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". [This axiom is very seldom mentioned in the literature. An exception is Burgess (2005), "passim".] :forall z [exist w [z in w] leftrightarrow forall x forall y [z in x or z=y] . "Adjunction", the name of an elementary operation on two sets, is unrelated to the use of the term elsewhere in mathematics, including in category theory.
Discussion
GST is the same as the set theory STZ in Burgess. [The Null Set axiom in STZ is redundant. Read on to see why.] His theory ST [Called S' in Tarski et al. (1953: 34).] is GST with Null Set replacing the
axiom schema of specification . That the letters "ST" also appear in GST is a coincidence. See Burgess (2005), especially the table on p. 223, for a discussion of this and other related weak set theories.Boolos was interested in GST only as a fragment of 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 ofFrege 's "Grundlagen" and "Grundgesetze", and how they could be modified to eliminateRussell's paradox .GST is:
*Afirst-order theory , and the fragment of Z obtained by omitting the axioms Union, Power Set, Infinity, and Choice, then taking a theorem of Z, Adjunction, as an axiom;
*Essentially undecidable. Further discussion of this is given below. [Burgess (2005), 2.2, p. 91.]
*Immune to the three great antinomies ofnaïve set theory : Russell's, Burali-Forti's, and Cantor's;
*Not finitely axiomatizable. Montague (1961) showed thatZFC is not finitely axiomatizable, and his argument carries over to GST. Hence any axiomatization of GST must either include at least oneaxiom schema such as Separation, or the background logic must be second-order (as in Boolos 1998: 180);
*Interpretable inrelation algebra because no part of any GST axiom lies in the scope of more than threequantifier s. This is thenecessary and sufficient condition given in Tarski and Givant (1987).The GST axioms feature only two existentially quantified variables toZF 's minimum of seven.Separation with φ("x") set to "x"≠"x", plus assuming that the
domain is nonempty, assures the existence of theempty set , from which the usualsuccessor ordinal numbers can be built via the axiom of adjunction. Adjuction states that whenever "x" is a set then so is S(x) = x cup {x}. Hence the natural numbers can defined as varnothing, S(varnothing),S(S(varnothing)),ldots, as discussed inPeano's axioms . More generally, given any model "M" of ZFC, any collection ofhereditarily finite set s in "M" will satisfy the GST axioms. However, GST cannot prove the existence of even a countableinfinite set . And even if GST could do so, it still could not could not prove the existence of a set whosecardinality is that of thecontinuum , because GST lacks theaxiom of power set . Hence GST cannot ground analysis andgeometry . More generally, GST cannot serve as a foundation for mathematics.Nevertheless, the
metamathematics of ST and GST are not trivial. ST can interpretRobinson arithmetic , proving its axioms. Hence ST is essentially undecidable. Every consistent theory in which the axioms of ST are provable is therefore also essentially undecidable. This includes GST and every axiomatic set theory worth thinking about, assuming these are consistent. In fact, the undecidability of ST implies the undecidability offirst-order logic with a singlebinary predicate letter. [Tarski et al. (1953), p. 34.]The axioms of ST are GST theorems, and the axioms of
Robinson arithmetic (Q) are ST theorems. Hence GST suffices to interpret Q, and Q is incomplete in the sense ofGödel's incompleteness theorem . Hence the same is true of GST. Moreover, theconsistency of GST cannot be proved within GST itself, unless GST is in fact inconsistent.Footnotes
Bibliography
*
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 , andRaphael 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.
Wikimedia Foundation. 2010.