General set theory

From Wikipedia, the free encyclopedia

General set theory (hereinafter abbreviated GST) is the name George Boolos (1998) employed for a three axiom fragment of the canonical axiomatic set theory ZF.

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

[edit] Ontology etc

GST consists of 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"). GST is a first-order theory; hence the background logic is first-order logic.

[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 be more intuitive.

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 Separation (or Restricted Comprehension): If z is a set and $\phi\!$ is any property which may be satisfied by some or all 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. Then:

$\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 whose members are just y and the members of x.

$\forall x \forall y \exist w \forall z [z \in w \Leftrightarrow (z \in x \or z=y)]$

Adjunction is a binary operation combining sets. w above is said to be the adjunction of the sets x and y.

[edit] Discussion

GST is a very simple axiomatic theory because its axioms contain only two existentially quantified variables. Also, the axioms can be recast so that no part of any axiom lies in the scope of more than three quantifiers.

Separation assures the existence of the empty set, from which the usual successor ordinal numbers can be built via the axiom of adjunction. Adjuction acts like an axiom of infinity because it states that whenever x is a set then so is $S(x) = x \cup \{x\}$ . Using this axiom, the natural numbers can defined to be $\varnothing, S(\varnothing),S(S(\varnothing)),\ldots$ , as discussed in the article on Peano's axioms. The three axioms above do not imply that there is a single set containing all these natural numbers, or any other infinite set; given any model M of ZFC, the collection of hereditarily finite sets in M will satisfy the three axioms above.

GST has an infinite number of axioms because Separation is an axiom schema. Montague (1961) showed that ZFC cannot be axiomatized by means of a finite number of axioms; 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).

GST generalizes an axiomatic set theory called S' in Tarski, Mostowski, and Robinson (1953: 34). S' replaces the axiom schema of Separation with an axiom asserting that the empty set exists. Despite its seeming weakness, S' is strong enough to prove the axioms of a simple yet nontrivial mathematical system, Robinson arithmetic (Tarski et al. 1953: 34). Because the axioms of S' are GST theorems, and S' interprets Robinson arithmetic, then GST interprets Robinson arithmetic as well. Because Robinson arithmetic obeys Gödel's incompleteness theorems, GST cannot be both consistent and complete. Moreover, the consistency of GST cannot be proved within GST itself (unless GST is in fact inconsistent). Because S' is undecidable, all theories in which the axioms of S' are theorems are undecidable. Since the axioms of S' are theorems of all known axiomatic set theories including GST, these theories are all undecidable.

GST is immune to the three great paradoxes of naïve set theory: Russell's, Burali-Forti's, and Cantor's.

Boolos (1998) invoked GST several times in his many papers discussing the systems of Frege's Grundlagen and Grundgesetze, and how these could be modified to eliminate Russell's paradox.

[edit] See also

[edit] Bibliography

George Boolos, 1998. Logic, Logic, and Logic. Harvard 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.