In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice",: "Zermelo-Fraenkel axioms (abbreviated as ZFC where C stands for the axiom of Choice)" and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.
Informally, Zermelo–Fraenkel set theory is intended to formalize a single primitive notion, that of a hereditary well-founded set, so that all entities in the universe of discourse are such sets. Thus the axioms of Zermelo–Fraenkel set theory refer only to pure sets and prevent its models from containing urelements (elements that are not themselves sets). Furthermore, proper classes (collections of mathematical objects defined by a property shared by their members where the collections are too big to be sets) can only be treated indirectly. Specifically, Zermelo–Fraenkel set theory does not allow for the existence of a universal set (a set containing all sets) nor for unrestricted comprehension, thereby avoiding Russell's paradox. Von Neumann–Bernays–Gödel set theory (NBG) is a commonly used conservative extension of Zermelo–Fraenkel set theory that does allow explicit treatment of proper classes.
There are many equivalent formulations of the axioms of Zermelo–Fraenkel set theory. Most of the axioms state the existence of particular sets defined from other sets. For example, the axiom of pairing implies that given any two sets and there is a new set containing exactly and . Other axioms describe properties of set membership. A goal of the axioms is that each axiom should be true if interpreted as a statement about the collection of all sets in the von Neumann universe (also known as the cumulative hierarchy).
The metamathematics of Zermelo–Fraenkel set theory has been extensively studied. Landmark results in this area established the logical independence of the axiom of choice from the remaining Zermelo-Fraenkel axioms and of the continuum hypothesis from ZFC. The consistency of a theory such as ZFC cannot be proved within the theory itself, as shown by Gödel's second incompleteness theorem.
History
The modern study of set theory was initiated by Georg Cantor and Richard Dedekind in the 1870s. However, the discovery of paradoxes in naive set theory, such as Russell's paradox, led to the desire for a more rigorous form of set theory that was free of these paradoxes.
In 1908, Ernst Zermelo proposed the first axiomatic set theory, Zermelo set theory. However, as first pointed out by Abraham Fraenkel in a 1921 letter to Zermelo, this theory was incapable of proving the existence of certain sets and cardinal numbers whose existence was taken for granted by most set theorists of the time, notably the cardinal number aleph-omega () and the set where is any infinite set and is the power set operation. Moreover, one of Zermelo's axioms invoked a concept, that of a "definite" property, whose operational meaning was not clear. In 1922, Fraenkel and Thoralf Skolem independently proposed operationalizing a "definite" property as one that could be formulated as a well-formed formula in a first-order logic whose atomic formulas were limited to set membership and identity. They also independently proposed replacing the axiom schema of specification with the axiom schema of replacement. Appending this schema, as well as the axiom of regularity (first proposed by John von Neumann), to Zermelo set theory yields the theory ZFC.
Formal language
Formally, ZFC is a one-sorted theory in first-order logic. The equality symbol can be treated as either a primitive logical symbol or a high-level abbreviation for having exactly the same elements. The former approach is the most common. The signature has a single predicate symbol, usually denoted , which is a predicate symbol of arity 2 (a binary relation symbol). This symbol symbolizes a set membership relation. For example, the formula means that is an element of the set (also read as is a member of ).
There are different ways to formulate the formal language. Some authors may choose a different set of connectives or quantifiers. For example, the logical connective NAND alone can encode the other connectives, a property known as functional completeness. This section attempts to strike a balance between simplicity and intuitiveness.
The language's alphabet consists of:
A countably infinite number of variables used for representing sets The logical connectives , , The quantifier symbols , The equality symbol The set membership symbol Brackets ( )
With this alphabet, the recursive rules for forming well-formed formulae (wff) are as follows:
Let and be metavariables for any variables. These are the two ways to build atomic formulae (the simplest wffs):
Let and be metavariables for any wff, and be a metavariable for any variable. These are valid wff constructions:
A well-formed formula can be thought as a syntax tree. The leaf nodes are always atomic formulae. Nodes and have exactly two child nodes, while nodes , and have exactly one. There are countably infinitely many wffs; however, each wff has a finite number of nodes.
Axioms
There are many equivalent formulations of the ZFC axioms. The following particular axiom set is from . The axioms in order below are expressed in a mixture of first-order logic and high-level abbreviations.
Axioms 1–8 form ZF, while the axiom 9 turns ZF into ZFC. Following , we use the equivalent well-ordering theorem in place of the axiom of choice for axiom 9.
All formulations of ZFC imply that at least one set exists. Kunen includes an axiom that directly asserts the existence of a set, although he notes that he does so only "for emphasis".. Its omission here can be justified in two ways. First, in the standard semantics of first-order logic in which ZFC is typically formalized, the domain of discourse must be nonempty. Hence, it is a logical theorem of first-order logic that something existsusually expressed as the assertion that something is identical to itself, . Consequently, it is a theorem of every first-order theory that something exists. However, as noted above, because in the intended semantics of ZFC, there are only sets, the interpretation of this logical theorem in the context of ZFC is that some set exists. Hence, there is no need for a separate axiom asserting that a set exists. Second, however, even if ZFC is formulated in so-called free logic, in which it is not provable from logic alone that something exists, the axiom of infinity asserts that an infinite set exists. This implies that a set exists, and so, once again, it is superfluous to include an axiom asserting as much.
Axiom of extensionality - 1
Two sets are equal (are the same set) if they have the same elements.
The converse of this axiom follows from the substitution property of equality. ZFC is constructed in first-order logic. Some formulations of first-order logic include identity; others do not. If the variety of first-order logic in which one is constructing set theory does not include equality "", may be defined as an abbreviation for the following formula:, def. 1.
In this case, the axiom of extensionality can be reformulated as
which says that if and have the same elements, then they belong to the same sets.
Axiom of regularity (also called the axiom of foundation) - 2
Every non-empty set contains a member such that and are disjoint sets.
or in modern notation:
With the axioms of pairing and union, this implies that no set is an element of itself. With the axioms of infinity, replacement, and union, this implies that every set has an ordinal rank.
Axiom schema of specification (or of separation, or of restricted comprehension) - 3
Subsets are commonly constructed using set builder notation. For example, the even integers can be constructed as the subset of the integers satisfying the congruence modulo predicate :
In general, the subset of a set obeying a formula with one free variable may be written as:
The axiom schema of specification states that this subset always exists (it is an axiom schema because there is one axiom for each ). Formally, let be any formula in the language of ZFC with all free variables among ( is not free in ). Then:
Note that the axiom schema of specification can only construct subsets and does not allow the construction of entities of the more general form:
This restriction is necessary to avoid Russell's paradox (let then ) and its variants that accompany naive set theory with unrestricted comprehension (since under this restriction only refers to sets within that don't belong to themselves, and has not been established, even though is the case, so stands in a separate position from which it can't refer to or comprehend itself; therefore, in a certain sense, this axiom schema is saying that in order to build a on the basis of a formula , we need to previously restrict the sets will regard within a set that leaves outside so can't refer to itself; or, in other words, sets shouldn't refer to themselves).
In some other axiomatizations of ZF, this axiom is redundant in that it follows from the axiom schema of replacement and the axiom of the empty set.
On the other hand, the axiom schema of specification can be used to prove the existence of the empty set, denoted , once at least one set is known to exist. One way to do this is to use a property which no set has. For example, if is any existing set, the empty set can be constructed as
Thus, the axiom of the empty set is implied by the nine axioms presented here. The axiom of extensionality implies the empty set is unique (does not depend on ). It is common to make a definitional extension that adds the symbol "" to the language of ZFC.
Axiom of pairing - 4
If and are sets, then there exists a set which contains and as elements; for example, if and , then might be .
The axiom schema of specification must be used to reduce this to a set with exactly these two elements.
Axiom of union - 5
The union over the elements of a set exists. For example, the union over the elements of the set is
The axiom of union states that for any set of sets , there is a set containing every element that is a member of some member of :
Although this formula doesn't directly assert the existence of , the set can be constructed from in the above using the axiom schema of specification:
Axiom schema of replacement - 6
The axiom schema of replacement asserts that the image of a set under any definable function will also fall inside a set.
Formally, let be any formula in the language of ZFC whose free variables are among so that in particular is not free in . Then:
(The unique existential quantifier denotes the existence of exactly one element such that it follows a given statement.)
In other words, if the relation represents a definable function , represents its domain, and is a set for every then the range of is a subset of some set . The form stated here, in which may be larger than strictly necessary, is sometimes called the axiom schema of collection.
Axiom of infinity - 7
+ First several von Neumann ordinals 0 = {} = ∅ 1 = {0} = {∅} 2 = {0,1} = {∅,{∅}} 3 = {0,1,2} = {∅,{∅},{∅,{∅}}} 4 = {0,1,2,3} = {∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}}}