General set theory

General set theory (GST) is George Boolos's (1998) name for a fragment of the 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.

Ontology

The ontology of GST is identical to that of ZFC, and hence is thoroughly canonical. GST features a single primitive ontological notion, that of set, and a single ontological assumption, namely that all individuals in the universe of discourse (hence 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").

Axioms

The symbolic axioms below are from Boolos (1998: 196), and govern how sets behave and interact. As with Z, the background logic for GST is first order logic with identity. Indeed, GST is the fragment of Z obtained by omitting the axioms Union, Power Set, Elementary Sets (essentially Pairing) and Infinity and then taking a theorem of Z, Adjunction, as an axiom. 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 may occur freely and y does not. 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 x\forall y\exists w\forall z[z\in w\leftrightarrow (z\in x\lor z=y)].

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

Discussion

Metamathematics

Note that Specification is an axiom schema. The theory given by these axioms is 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. With its simple axioms, GST is also immune to the three great antinomies of naïve set theory: Russell's, Burali-Forti's, and Cantor's.

GST is 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).

Peano arithmetic

Setting φ(x) in Separation to x≠x, and assuming that the domain is nonempty, assures the existence of the empty set. Adjunction implies that if x is a set, then so is $S(x)=x\cup \{x\}$ . Given Adjunction, the usual construction of the successor ordinals from the empty set can proceed, one in which the natural numbers are defined as $\varnothing ,\,S(\varnothing ),\,S(S(\varnothing )),\,\ldots ,$ . See Peano's axioms. GST is mutually interpretable with Peano arithmetic (thus it has the same proof-theoretic strength as PA).

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 NBG, ST interprets Robinson arithmetic (Q), so that ST inherits the nontrivial metamathematics of Q. For example, ST is essentially undecidable because Q is, and every consistent theory whose theorems include the ST axioms is also essentially undecidable.[2] 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.[3]

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.

Infinite sets

Given any model M of ZFC, the collection of hereditarily finite sets 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 ℵ₀. Even if GST did afford a countably infinite set, GST could not prove the existence of a set whose cardinality is $\aleph _{1}$ , because GST lacks the axiom of power set. Hence GST cannot ground analysis and geometry, and is too weak to serve as a foundation for mathematics.

History

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. The system Aξ'[δ₀] in Tarski and Givant (1987: 223) is essentially GST with an axiom schema of induction replacing Specification, and with the existence of an empty set explicitly assumed.

GST is called STZ in Burgess (2005), p. 223.[4] Burgess's theory ST[5] is GST with Empty Set replacing the axiom schema of specification. That the letters "ST" also appear in "GST" is a coincidence.

Footnotes

Adjunction is seldom mentioned in the literature. Exceptions are Burgess (2005) passim, and QIII in Tarski and Givant (1987: 223).
Burgess (2005), 2.2, p. 91.
Tarski et al. (1953), p. 34.
The Empty Set axiom in STZ is redundant, because the existence of the empty set is derivable from the axiom schema of Specification.
Called S' in Tarski et al. (1953: 34).

References

George Boolos (1999) 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: Set Theory—by Thomas Jech.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Adjunction is seldom mentioned in the literature. Exceptions are Burgess (2005) passim, and QIII in Tarski and Givant (1987: 223).

[2] Burgess (2005), 2.2, p. 91.

[3] Tarski et al. (1953), p. 34.

[4] The Empty Set axiom in STZ is redundant, because the existence of the empty set is derivable from the axiom schema of Specification.

[5] Called S' in Tarski et al. (1953: 34).

Set theory
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement De Morgan's laws Disjoint union Intersection Power set Set difference Symmetric difference Union
Concepts Methods	Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Transfinite induction Venn diagram
Set types	Countable Empty Finite (hereditarily) Fuzzy Infinite (Dedekind-infinite) Recursive Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Abraham Fraenkel Bertrand Russell Ernst Zermelo Georg Cantor John von Neumann Kurt Gödel Paul Bernays Paul Cohen Richard Dedekind Thomas Jech Thoralf Skolem Willard Quine

Mathematical logic
General	Formal language Formation rule Formal proof Formal semantics Well-formed formula Set Element Class Classical logic Axiom Rule of inference Relation Theorem Logical consequence Type theory Symbol Syntax Theory
Systems	Formal system Deductive system Axiomatic system Hilbert style systems Natural deduction Sequent calculus
Traditional logic	Proposition Inference Argument Validity Syllogism Square of opposition Venn diagram
Propositional calculus and Boolean logic	Boolean functions Propositional calculus Propositional formula Logical connectives Truth tables Many-valued logic
Predicate logic	First-order Quantifiers Predicate Second-order Monadic predicate calculus
Naive set theory	Set Empty set Element Enumeration Extensionality Finite set Infinite set Subset Power set Countable set Uncountable set Recursive set Domain Codomain Image Map Function Relation Ordered pair
Set theory	Foundations of mathematics Zermelo–Fraenkel set theory Axiom of choice General set theory Kripke–Platek set theory Von Neumann–Bernays–Gödel set theory Morse–Kelley set theory Tarski–Grothendieck set theory
Model theory	Model Interpretation Non-standard model Finite model theory Truth value Validity
Proof theory	Formal proof Deductive system Formal system Theorem Logical consequence Rule of inference Syntax
Computability theory	Recursion Recursive set Recursively enumerable set Decision problem Church–Turing thesis Computable function Primitive recursive function