Axiomatic set theory

From Wikipedia, the free encyclopedia

• Ten things you didn't know about Wikipedia •

In mathematics, axiomatic set theory is a rigorous reformulation of set theory in first-order logic, created to address paradoxes in naive set theory. Set theory was created principally by the German mathematician Georg Cantor at the end of the 19th century.

Initially controversial, set theory has come to play the role of a foundational theory in modern mathematics, in the sense that it interprets propositions about mathematical objects (numbers, functions, etc.,) from all the traditional areas of mathematics (algebra, analysis, topology, etc.) in a single theory, and provides a standard set of axioms to prove or disprove them. At the same time the basic concepts of set theory are used throughout mathematics, the subject is pursued in its own right as a specialty by a comparatively small group of mathematicians and logicians. It should be mentioned that there are also mathematicians using and promoting different approaches to the foundations of mathematics.

The basic concepts of set theory are set and membership. A set is thought of as any collection of objects, called the members (or elements) of the set. In mathematics, the members of sets are any mathematical objects, and in particular can themselves be sets. Thus one speaks of the set N of natural numbers { 0, 1, 2, 3, 4, ... }, the set of real numbers, and the set of functions from the natural numbers to the natural numbers; but also, for example, of the set { 0, 2, N } which has as members the numbers 0 and 2 and the set N.

Initially, what is now known as "naive" or "intuitive" set theory was developed. As it turned out, assuming that one could perform any operations on sets without restriction led to paradoxes such as Russell's paradox. To address these problems, set theory had to be re-constructed, using an axiomatic approach.

[hide]

[edit] The origins of rigorous set theory

The important idea of Cantor's, which got set theory going as a new field of study, was to define two sets A and B to have the same number of members (the same cardinality) when there is a way of pairing off members of A exhaustively with members of B. Then the set N of natural numbers has the same cardinality as the set Q of rational numbers (they are both said to be countably infinite), even though N is a proper subset of Q. On the other hand, the set R of real numbers does not have the same cardinality as N or Q, but a larger one (it is said to be uncountable). Cantor gave two proofs that R is not countable, and the second of these, using what is known as the diagonal construction, has been extraordinarily influential and has had many applications in logic and mathematics.

Cantor constructed infinite hierarchies of infinite sets, the ordinal and cardinal numbers. This was controversial in his day, with the opposition led by the finitist Leopold Kronecker, but there is no significant disagreement among mathematicians today that Cantor had the right idea.

Cantor's development of set theory was still "naive" in the sense that he did not have a precise axiomatization in mind. In retrospect, we can say that Cantor was tacitly using the axiom of extensionality, the axiom of infinity, and the axiom schema of (unrestricted) comprehension. Some do not agree that Cantor actually made the last assumption: Frege certainly did, and it was Frege's theory that Russell was actually addressing when he formulated Russell's paradox by constructing the set S := {A : A is not in A} of all sets that do not belong to themselves. (If S belongs to itself, then it does not, giving a contradiction, so S must not belong to itself. But then S would belong to itself, giving a final and absolute contradiction.) Therefore, set theorists were forced to abandon either classical logic or unrestricted comprehension, and the latter was far more reasonable to most. (Although intuitionism had a significant following, the paradox still goes through with intuitionistic logic. There is no paradox in Brazilian logic, but that was almost completely unknown at the time.)

In order to avoid this and similar paradoxes, Ernst Zermelo, working in Germany, put forth a system of axioms for set theory in 1908. He included in this system the axiom of choice, a controversial axiom that he needed to prove the well-ordering theorem. This system was later refined by Adolf Fraenkel and Thoralf Skolem, giving the axioms used today.

[edit] Axioms for set theory

One particular set of axioms for set theory, put in their final form by Skolem, are called the Zermelo-Fraenkel set theory (ZF). Actually, this term usually excludes the axiom of choice, which was once more controversial than it is today. When this axiom is included, the resulting system is called ZFC.

An important feature of ZFC is that every object that it deals with is a set. In particular, every element of a set is itself a set. Other familiar mathematical objects, such as numbers, must be subsequently defined in terms of sets.

The ten axioms of ZFC are listed below. (Strictly speaking, the axioms of ZFC are just strings of logical symbols. What follows should therefore be viewed only as an attempt to express the intended meaning of these axioms in English. Moreover, the axiom of separation, along with the axiom of replacement, is actually a schema of axioms, one for each proposition). Each axiom has further information in its own article.

Axiom of extensionality: Two sets are the same if and only if they have the same elements.
Axiom of empty set: There is a set with no elements. We will use {} to denote this empty set.
Axiom of pairing: If x, y are sets, then so is {x,y}, a set containing x and y as its only elements.
Axiom of union: Every set has a union. That is, for any set x there is a set y whose elements are precisely the elements of the elements of x.
Axiom of infinity: There exists a set x such that {} is in x and whenever y is in x, so is the union y U {y}.
Axiom of separation (or subset axiom): Given any set and any proposition P(x), there is a subset of the original set containing precisely those elements x for which P(x) holds.
Axiom of replacement: Given any set and any mapping, formally defined as a proposition P(x,y) where P(x,y) and P(x,z) implies y = z, there is a set containing precisely the images of the original set's elements.
Axiom of power set: Every set has a power set. That is, for any set x there exists a set y, such that the elements of y are precisely the subsets of x.
Axiom of regularity (or axiom of foundation): Every non-empty set x contains some element y such that x and y are disjoint sets.
Axiom of choice: (Zermelo's version) Given a set x of mutually disjoint nonempty sets, there is a set y (a choice set for x) containing exactly one element from each member of x.

The axioms of choice and regularity are still controversial today among a minority of mathematicians. Other axiom systems for set theory are Von Neumann-Bernays-Gödel set theory (NBG), the Kripke-Platek set theory (KP), Kripke-Platek set theory with urelements (KPU) and Morse-Kelley set theory. All of these are axiomatic set theories closely related to ZFC: axiomatic set theories with quite different approaches are (for example) New Foundations and systems of positive set theory.

[edit] Independence in ZFC

Many important statements are independent of ZFC, see the list of statements undecidable in ZFC. The independence is usually proved by forcing, that is, it is shown that every countable transitive model of ZFC (plus, occasionally, large cardinal axioms) can be expanded to satisfy the statement in question, and (through a different expansion) its negation. An independence proof by forcing automatically proves independence from arithmetical statements, other concrete statements, and large cardinal axioms. Some statements independent of ZFC can be proven to hold in particular inner models, such as in the constructible universe. However, some statements that are true about constructible sets are not consistent with hypothesised large cardinal axioms.

Here are some statements whose independence is provable by forcing:

Continuum hypothesis
Diamond principle
Suslin hypothesis
Kurepa hypothesis
Martin's axiom (Note despite the name this is NOT an axiom of ZFC)
Axiom of Constructibility (V=L) (also not an axiom of ZFC)

Notes:

Consistency of V=L is not provable by forcing, but is provable through inner models: every model of ZF can be trimmed to be a model of ZFC+V=L.
The Diamond Principle implies the Continuum Hypothesis and the negation of the Suslin Hypothesis.
Martin's axiom plus the negation of the Continuum Hypothesis implies the Suslin Hypothesis.
The constructible universe satisfies the Generalized Continuum Hypothesis, the Diamond Principle, Martin's Axiom and the Kurepa Hypothesis.

A variation on the method of forcing can also be used to demonstrate the consistency and unprovability of the axiom of choice, i.e., that the axiom of choice is independent of ZF. The consistency of choice can be (relatively) easily verified by proving the inner model L satisfies choice (thus every model of ZF contains a submodel of ZFC hence Con(ZF) implies Con(ZFC)). Since forcing preserves choice we cannot directly produce a model contradicting choice from a model satisfying choice. However, we can use forcing to create a model which contains a suitable submodel, namely one which satisfies ZF but not C.

Forcing is perhaps the most useful method of proving independence results but not the only method. In particular Godel's 2^nd incompleteness theorem which asserts that no sufficiently complex recursively axiomatizable system can prove its own consistency can be used to prove independence results. In this approach it is demonstrated that a particular statement in set theory can be used to prove the existence of a set model of ZFC and thereby demonstrate the consistency of ZFC. Since we know that Con(ZFC) (the sentence asserting the consistency of ZFC in the language of set theory) is unprovable in ZFC no statement allowing such a proof can itself be provable in ZFC. For instance this method can be used to demonstrate the existence of large cardinals is not provable in ZFC (but it is essentially impossible to show they are consistent).

[edit] Set theory (ZFC) foundations for mathematics

Main article: Set-theoretic definition of natural numbers

From these initial axioms for sets one can construct all other mathematical concepts and objects: number (discrete and continuous), order, relation, function , etc.

For example, while the elements of a set have no intrinsic ordering it is possible to construct models of ordered lists. The essential step is to be able to model the ordered pair (a, b) which represents the pairing of two objects in this order. The defining property of an ordered pair is that (a, b) = (c, d) if and only if a = c and b = d. The approach is basically to specify the two elements and additionally note which one is the first using the construction:

$( a, b ) = \lbrace \lbrace a, b \rbrace, \lbrace a \rbrace \rbrace\,$

Ordered lists of greater length can be constructed inductively:

$\begin{align} (a, b, c) & = ( (a, b), c ) \\ (a, b, c, d) & = ( (a, b, c), d ) \\ \vdots \end{align}$

As another example, there is a minimalist construction for the natural numbers, principally drawing on the axiom of infinity, due to von Neumann. We require to produce an infinite sequence of distinct sets with a successor relation as a model for the Peano axioms. This provides a canonical representation for the number N as being a particular choice of set containing precisely N distinct elements. We proceed inductively:

$\begin{align} 0 & = \lbrace \rbrace \\ 1 & = \lbrace 0 \rbrace & =\,\, & \lbrace \lbrace \rbrace \rbrace \\ 2 & = \lbrace 0, 1 \rbrace & =\,\, & \lbrace \lbrace \rbrace, \lbrace \lbrace \rbrace \rbrace \rbrace \\ 3 & = \lbrace 0, 1, 2 \rbrace & =\,\, & \lbrace \lbrace \rbrace, \lbrace \lbrace \rbrace \rbrace, \lbrace \lbrace \rbrace, \lbrace \lbrace \rbrace \rbrace \rbrace \rbrace \\ \vdots \end{align}$

At each stage we construct a new set with N elements as being the set containing the (already defined) elements 0, 1, 2, ..., N-1. More formally, at each step the successor of N is N ∪ { N }. Remarkably this produces a suitable model for the entire collection of natural numbers, from the barest of materials.

The original set theoretical definition of the natural numbers defined each natural number n as the set of all sets with n elements (this can be managed without the apparent circularity of this brief summary). This definition (due to Frege and Russell) does not work in ZFC because the collections involved are too large to be sets. However, this approach does work in New Foundations and subsystems of NF known to be consistent.

Since relations, and most specifically functions, are defined to be sets of ordered pairs, and there are well-known constructions progressively building up the integers, rationals, reals, and complex numbers from sets of the natural numbers, we are able to model essentially all of the usual infrastructure of daily mathematical practice.

[edit] Well-foundedness and hypersets

In 1917 Dimitri Mirimanoff (also spelled Dmitry Mirimanov) introduced the concept of well-foundedness:

a set, x₀, is well founded iff it has no infinite descending membership sequence:

· · · $\in x_2 \in x_1 \in x_0.$

In ZFC, there is no infinite descending ∈-sequence by the axiom of regularity (for a proof see Axiom of regularity). In fact, the axiom of regularity is often called the foundation axiom since it can be proved within ZFC- (that is, ZFC without the axiom of regularity) that well-foundedness implies regularity.

In variants of ZFC without the axiom of regularity, the possibility of non-well-founded sets arises. When working in such a system, a set that is not necessarily well founded is called a hyperset. Clearly, if A ∈ A, then A is a non-well-founded hyperset.

The theory of hypersets has been applied in computer science (process algebra and final semantics), linguistics (situation theory), and philosophy (work on the Liar Paradox).

Three distinct anti-foundation axioms are well known:

AFA (‘Anti-Foundation Axiom’) — due to M. Forti and F. Honsell;
FAFA (‘Finsler’s AFA’) — due to P. Finsler;
SAFA (‘Scott’s AFA’) — due to Dana Scott.

The first of these, AFA, is based on accessible pointed graphs (apg) and states that two hypersets are equal if and only if they can be pictured by the same apg. Within this framework, it can be shown that the so-called Quine atom, formally defined by Q={Q}, exists and is unique.

It is worth emphasizing that hyperset theory is an extension of classical set theory rather than a replacement: the well-founded sets within a hyperset domain conform to classical set theory. The kinds of non-well-foundedness found in New Foundations or positive set theory (or more generally any set theory with a universal set which is an element of itself) are rather different.

[edit] References

Keith Devlin, 1992. The Joy of Sets, 2nd ed. Springer-Verlag.
Potter, Michael, 2004. Set Theory and Its Philosophy. Oxford Univ. Press. ISBN 0-19-927041-4.
Suppes, Patrick, 1972. Axiomatic Set Theory. Dover Publications. ISBN 0-486-61630-4.
Tourlakis, George, 2003. Lectures in Logic and Set Theory, Vol. 2. Cambridge Univ. Press.

[edit] See also

[edit] External links

Metamath: A web site devoted to an ongoing derivation of mathematics from the axioms of ZFC and first-order logic. Principia Mathematica done right.
Stanford Encyclopedia of Philosophy:
- Set Theory -- by Thomas Jech.
- Quine's New Foundations -- by Thomas Forster.
- Alternative axiomatic set theories -- by Randall Holmes.
Randall Holmes's bibliography for set theories allowing a universal set.
Mathias, A. R. D., 2004, "The Strength of Mac Lane Set Theory." Surveys, and sets out new results and new proofs for old results, for a number of alternatives to ZFC, including ZBQC (proposed by Saunders Mac Lane), topos theory, Kripke-Platek set theory, Foster-Kaye set theory, Harvey Friedman, and systems similar to New Foundations.
Axioms of Set Theory at ProvenMath

For information on the history of set theory notation, see:

The history of set theory and logic notation.

Retrieved from "http://en.wikipedia.org/wiki/Axiomatic_set_theory"

Categories: Systems of set theory | Logic

Euclideanelements

Sunday, September 9, 2007