general set theory on:  
[Wikipedia]  
[Google]  
[Amazon]
General set theory (GST) is
George Boolos
George Stephen Boolos (; 4 September 1940 – 27 May 1996) was an American philosopher and a mathematical logician who taught at the Massachusetts Institute of Technology.
Life
Boolos is of Greek-Jewish descent. He graduated with an A.B. in ...
's (1998) name for a fragment of the
axiomatic set theory
Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, ...
Z. GST is sufficient for all mathematics not requiring
infinite set
In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable.
Properties
The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set th ...
s, and is the weakest known set theory whose
theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of th ...
s include the
Peano axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...
.
Ontology
The ontology of GST is identical to that of
ZFC, and hence is thoroughly canonical. GST features a single
primitive ontological
In metaphysics, ontology is the philosophical study of being, as well as related concepts such as existence, becoming, and reality.
Ontology addresses questions like how entities are grouped into categories and which of these entities exis ...
notion, that of
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
, and a single ontological assumption, namely that all individuals in the
universe of discourse
In the formal sciences, the domain of discourse, also called the universe of discourse, universal set, or simply universe, is the set of entities over which certain variables of interest in some formal treatment may range.
Overview
The domain ...
(hence all
mathematical object
A mathematical object is an abstract concept arising in mathematics.
In the usual language of mathematics, an ''object'' is anything that has been (or could be) formally defined, and with which one may do deductive reasoning and mathematical pr ...
s) are sets. There is a single
primitive binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
,
set membership
In mathematics, an element (or member) of a set is any one of the distinct objects that belong to that set.
Sets
Writing A = \ means that the elements of the set are the numbers 1, 2, 3 and 4. Sets of elements of , for example \, are subsets o ...
; 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
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
with
identity
Identity may refer to:
* Identity document
* Identity (philosophy)
* Identity (social science)
* Identity (mathematics)
Arts and entertainment Film and television
* ''Identity'' (1987 film), an Iranian film
* ''Identity'' (2003 film), ...
. Indeed, GST is the fragment of Z obtained by omitting the axioms
Union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
,
Power Set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
, Elementary Sets (essentially
Pairing
In mathematics, a pairing is an ''R''-bilinear map from the Cartesian product of two ''R''-modules, where the underlying ring ''R'' is commutative.
Definition
Let ''R'' be a commutative ring with unit, and let ''M'', ''N'' and ''L'' be ''R''-modu ...
) and
Infinity
Infinity is that which is boundless, endless, or larger than any natural number. It is often denoted by the infinity symbol .
Since the time of the ancient Greeks, the philosophical nature of infinity was the subject of many discussions amo ...
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
In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of extensionality, or axiom of extension, is one of the axioms of Zermelo–Fraenkel set theory. It says that sets having the same elements ...
: The sets ''x'' and ''y'' are the same set if they have the same members.
:
to ''z'' is necessary to avoid
Russell's paradox
In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains a ...
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 \in y \leftrightarrow ( x \in z \land \phi(x))
3)
Axiom of Adjunction In mathematical set theory, the axiom of adjunction states that for any two sets ''x'', ''y'' there is a set ''w'' = ''x'' ∪ given by "adjoining" the set ''y'' to the set ''x''.
: \forall x \,\forall y \,\exists w \,\forall z ...
: 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''.
:
\forall x \forall y \exist 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
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
.
ST is GST with the axiom schema of specification replaced by the
axiom of empty set
In axiomatic set theory, the axiom of empty set is a statement that asserts the existence of a set with no elements. It is an axiom of Kripke–Platek set theory and the variant of general set theory that Burgess (2005) calls "ST," and a demonstrab ...
.
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 include at least one
axiom schema In mathematical logic, an axiom schema (plural: axiom schemata or axiom schemas) generalizes the notion of axiom.
Formal definition
An axiom schema is a formula in the metalanguage of an axiomatic system, in which one or more schematic variables ap ...
.
With its simple axioms, GST is also immune to the three great antinomies of
naïve set theory
Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics.
Unlike axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language. It de ...
:
Russell's,
Burali-Forti's, and
Cantor's.
GST is Interpretable in
relation algebra
In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation. The motivating example of a relation algebra is the algebra 2''X''² of all binary relations ...
because no part of any GST axiom lies in the scope of more than three
quantifiers. This is the
necessary and sufficient condition
In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If then ", is necessary for , because the truth of ...
given in Tarski and Givant (1987).
Peano arithmetic
Setting φ(''x'') in ''Separation'' to ''x''≠''x'', and assuming that the
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
is nonempty, assures the existence of the
empty set
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
. ''Adjunction'' implies that if ''x'' is a set, then so is
S(x) = x \cup \. Given ''Adjunction'', the usual construction of the
successor ordinal In set theory, the successor of an ordinal number ''α'' is the smallest ordinal number greater than ''α''. An ordinal number that is a successor is called a successor ordinal. Properties
Every ordinal other than 0 is either a successor ordin ...
s from the
empty set
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
can proceed, one in which the
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s are defined as
\varnothing,\,S(\varnothing),\,S(S(\varnothing)),\,\ldots,. See
Peano's axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...
.
GST is mutually interpretable with
Peano arithmetic
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
(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
In mathematics, Robinson arithmetic is a finitely axiomatized fragment of first-order Peano arithmetic (PA), first set out by R. M. Robinson in 1950. It is usually denoted Q. Q is almost PA without the axiom schema of mathematical induction. Q is ...
(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. 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
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
with a single
binary predicate letter.
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
In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent ...
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 set
In mathematics and set theory, hereditarily finite sets are defined as finite sets whose elements are all hereditarily finite sets. In other words, the set itself is finite, and all of its elements are finite sets, recursively all the way down to t ...
s in ''M'' will satisfy the GST axioms. Therefore, GST cannot prove the existence of even a countable
infinite set
In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable.
Properties
The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set th ...
, that is, of a set whose cardinality is ℵ
0. Even if GST did afford a countably infinite set, GST could not prove the existence of a set whose
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
is
\aleph_1, because GST lacks the
axiom of power set
In mathematics, the axiom of power set is one of the Zermelo–Fraenkel axioms of axiomatic set theory.
In the formal language of the Zermelo–Fraenkel axioms, the axiom reads:
:\forall x \, \exists y \, \forall z \, \in y \iff \forall w \ ...
. Hence GST cannot ground
analysis
Analysis ( : analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (38 ...
and
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, 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
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
. He never lingered over GST, only mentioning it briefly in several papers discussing the systems of
Frege
Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic ph ...
's ''
Grundlagen'' and ''Grundgesetze'', and how they could be modified to eliminate
Russell's paradox
In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains a ...
. The system Aξ'
0">delta;0in Tarski and Givant (1987: 223) is essentially GST with an
axiom schema of induction replacing
Specification
A specification often refers to a set of documented requirements to be satisfied by a material, design, product, or service. A specification is often a type of technical standard.
There are different types of technical or engineering specificati ...
, and with the existence of an
empty set
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
explicitly assumed.
GST is called STZ in Burgess (2005), p. 223. Burgess's theory ST
[Called S' in Tarski et al. (1953: 34).] is GST with
Empty Set
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
replacing the
axiom schema of specification
In many popular versions of axiomatic set theory, the axiom schema of specification, also known as the axiom schema of separation, subset axiom scheme or axiom schema of restricted comprehension is an axiom schema. Essentially, it says that any ...
. That the letters "ST" also appear in "GST" is a coincidence.
Footnotes
References
*
George Boolos
George Stephen Boolos (; 4 September 1940 – 27 May 1996) was an American philosopher and a mathematical logician who taught at the Massachusetts Institute of Technology.
Life
Boolos is of Greek-Jewish descent. He graduated with an A.B. in ...
(1999) ''Logic, Logic, and Logic''. Harvard Univ. Press.
*Burgess, John, 2005. ''Fixing Frege''. Princeton Univ. Press.
*
Richard Montague
Richard Merritt Montague (September 20, 1930 – March 7, 1971) was an American mathematician and philosopher who made contributions to mathematical logic and the philosophy of language. He is known for proposing Montague grammar to formalize th ...
(1961) "Semantical closure and non-finite axiomatizability" in ''Infinistic Methods''. Warsaw: 45-69.
*
Alfred Tarski
Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
,
Andrzej Mostowski, and
Raphael Robinson
Raphael Mitchel Robinson (November 2, 1911 – January 27, 1995) was an United States of America, American mathematician.
Born in National City, California, National City, California, Robinson was the youngest of four children of a lawyer and a t ...
(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
The ''Stanford Encyclopedia of Philosophy'' (''SEP'') combines an online encyclopedia of philosophy with peer-reviewed publication of original papers in philosophy, freely accessible to Internet users. It is maintained by Stanford University. Eac ...
Set Theory€”by Thomas Jech.
{{Mathematical logic
Systems of set theory
Z notation