2 Axioms for set theory

The axioms for set theory now most often studied and used, although 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 an infinite schema of axioms, one for each formula.) Each axiom has further information in its own article.

1. Axiom of extensionality: Two sets are the same if and only if they have the same elements.
2. Axiom of empty set: There is a set with no elements. We will use {} to denote this empty set.
3. Axiom of pairing: If x, y are sets, then so is {x,y}, a set containing x and y as its only elements.
4. Axiom of union: For any two sets, there is a set that contains exactly the elements of both.
5. 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}.
6. 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.
7. 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.
8. 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.
9. Axiom of regularity (or axiom of foundation): Every non-empty set x contains some element y such that x and y are disjoint sets.
10. 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 of interest include the Von Neumann-Bernays-Gödel axioms (NBG) and the Kripke-Platek axioms (KP).

3 Independence in set theory

Many important statements are independent of 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 disproved by large cardinal axioms.

Here are some statements whose independence is provable by forcing:

• Continuum hypothesis
• Diamond principle
• Suslin hypothesis
• Kurepa hypothesis

Note: The Diamond Principle implies the Continuum Hypothesis and the negation of the Suslin Hypothesis.
The constructible universe satisfies the Generalized Continuum Hypothesis, the Diamond Principle, and the Kurepa Hypothesis.

4 Set theory foundations for mathematics

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, whilst 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 ) = { { a, b }, { a } }.

Ordered lists of greater length can be constructed inductively:

( a, b, c ) = ( ( a, b ), c ) ( a, b, c, d ) = ( ( a, b, c ), d ) ...

For 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:

0 = {} 1 = { 0 } = { {} } 2 = { 0, 1 } = { {}, { {} } } 3 = { 0, 1, 2 } = { {}, { {} }, { {}, { {} } } } ...

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.

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, rational, real and complex numbers from sets of the natural numbers we are able to model essentially all of the usual infrastructure of daily mathematical practice.

It is often asserted that axiomatic set theory is thus an adequate foundation for current mathematical practice, in the sense that in principle all proofs produced by the mathematical community could be written formally in set theory terms. It is also generally believed that no serious advantage would come from doing that, in almost all cases: the axiomatic foundations normally used are sufficiently closely aligned to the underlying set theory, that full axiomatic translation yields only a little extra, compared to argument in the usual, traditional informal style. One area where a gap can appear between practice and easy formalisation is in category theory, where for example a concept like 'the category of all categories' requires more careful set-theoretic handling.

5 Well-foundedness and hypersets

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

a set, x0, is well-founded iff it has no infinite descending membership sequence:

· · ·

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:

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

The first of these, AFA, is based on accessible pointed graph s (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.

6 Objections to set theory

Since its inception, there have been some mathematicians who have objected to using set theory as a foundation for mathematics, claiming that it is just a game which includes elements of fantasy. Notably, Henri Poincaré is supposed to have said "set theory is a disease from which mathematics will one day recover", (this quotation is part of the folklore of mathematics; the original source is unknown) and Errett Bishop dismissed set theory as God's mathematics, which we should leave for God to do.

The most frequent objection to set theory is based on the constructivist view that, loosely, mathematics has something to do with computation. See mathematical constructivism. On the other hand this is not really an objection to axiomatic set theory, as a formal theory. It is a comment on the naive set theory that is being formalised, and its admission of non-computational elements.

Topos theory has been proposed as an alternative to traditional axiomatic set theory.

7 See also

• Zermelo-Fraenkel set theory
• Simple theorems in the algebra of sets
• Naive set theory
• Cantor-Bernstein-Schroeder theorem
• Zorn's lemma
• Cantor's theorem
• Cantor's diagonal argument
• Model theory
• Internal set theory

8 External links

• Metamath -- the foundations of mathematics explored

For information on the history of the notation see

• Earliest uses of symbols of set theory and logic

Set theory Mathematical logic

<Hide>