General set theory

From Wikipedia, the free encyclopedia

General set theory (GST) is George Boolos's (1998) name for a three axiom fragment of the canonical axiomatic set theory Z. GST is sufficient for all mathematics not requiring infinite sets, and is the weakest known set theory whose theorems include the Peano axioms.

1 Ontology etc
2 Axioms
3 Discussion
4 Footnotes
5 See also
6 Bibliography
7 External links

[edit] Ontology etc

GST features a single primitive ontological notion, that of set, and a single ontological assumption, namely that all individuals in the universe of discourse (i.e., all mathematical objects) are sets. There is a single primitive binary relation, set membership; that set a is a member of set b is written a∈b (usually read "a is an element of b").

[edit] 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] \rightarrow 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\!$ . The restriction to z is necessary to avoid Russell'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.^[1]

$\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.

[edit] Discussion

GST is the same as the set theory STZ in Burgess.^[2] His theory ST^[3] 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 of Frege's Grundlagen and Grundgesetze, and how they could be modified to eliminate Russell's paradox.

GST is:

A first-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. ^[4]
Immune to the three great antinomies of naïve set theory: Russell's, Burali-Forti's, and Cantor's;
Not 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 Separation, or the background logic must be second-order (as in Boolos 1998: 180);
Interpretable in relation algebra because no part of any GST axiom lies in the scope of more than three quantifiers. This is the necessary and sufficient condition given in Tarski and Givant (1987).

The GST axioms feature only two existentially quantified variables to ZF's minimum of seven.

Separation with φ(x) set to x≠x, plus assuming that the domain is nonempty, assures the existence of the empty set, from which the usual successor 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 in Peano's axioms. More generally, given any model M of ZFC, any collection of hereditarily finite sets in M will satisfy the GST axioms. However, GST cannot prove the existence of even a countable infinite set. And even if GST could do so, it still could not could not prove the existence of a set whose cardinality is that of the continuum, because GST lacks the axiom of power set. Hence GST cannot ground analysis and geometry. More generally, GST cannot serve as a foundation for mathematics.

Nevertheless, the metamathematics of ST and GST are not trivial. ST can interpret Robinson 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 of first-order logic with a single binary predicate letter.^[5]

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 of Gödel. Hence the same is true of GST. Moreover, by Gödel's second theorem, the consistency of GST cannot be proved within GST itself, unless GST is in fact inconsistent.

[edit] Footnotes

^ This axiom is very seldom mentioned in the literature. An exception is Burgess (2005), passim.
^ The Null Set axiom in STZ is redundant. Read on to see why.
^ Called S' in Tarski et al. (1953: 34).
^ Burgess (2005), 2.2, p. 91.
^ Tarski et al. (1953), p. 34.

[edit] See also

[edit] 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, 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.