Misplaced Pages

#487512

54-455: 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

108-454: A {\displaystyle a} and b {\displaystyle b} . 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

162-416: 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 denoted by ZF . Adding to ZF either the axiom of choice (AC) or

216-434: A least element under the order R {\displaystyle R} . Given axioms 1  –  8 , many statements are provably equivalent to axiom 9 . The most common of these goes as follows. Let X {\displaystyle X} be a set whose members are all nonempty. Then there exists a function f {\displaystyle f} from X {\displaystyle X} to

270-585: A finite number of nodes. There are many equivalent formulations of the ZFC axioms. The following particular axiom set is from Kunen (1980) . 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 Kunen (1980) , 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

324-409: A hierarchy by assigning to each set the first stage at which that set was added to V . Hereditary set In set theory , a hereditary set (or pure set ) is a set whose elements are all hereditary sets. That is, all elements of the set are themselves sets, as are all elements of the elements, and so on. For example, it is vacuously true that the empty set is a hereditary set, and thus

378-528: 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

432-537: A set z {\displaystyle z} is a subset of a set x {\displaystyle x} if and only if every element of z {\displaystyle z} is also an element of x {\displaystyle x} : The Axiom of power set states that for any set x {\displaystyle x} , there is a set y {\displaystyle y} that contains every subset of x {\displaystyle x} : The axiom schema of specification

486-498: A set X having infinitely many members. (It must be established, however, that these members are all different because if two elements are the same, the sequence will loop around in a finite cycle of sets. The axiom of regularity prevents this from happening.) The minimal set X satisfying the axiom of infinity is the von Neumann ordinal ω which can also be thought of as the set of natural numbers N . {\displaystyle \mathbb {N} .} By definition,

540-520: A set that contains only itself is a hereditary set. Abraham Fraenkel Abraham Fraenkel ( Hebrew : אברהם הלוי (אדולף) פרנקל ; 17 February, 1891 – 15 October, 1965) was a German-born Israeli mathematician . He was an early Zionist and the first Dean of Mathematics at the Hebrew University of Jerusalem . He is known for his contributions to axiomatic set theory , especially his additions to Ernst Zermelo 's axioms, which resulted in

594-466: A set with exactly these two elements. The axiom of pairing is part of Z, but is redundant in ZF because it follows from the axiom schema of replacement if we are given a set with at least two elements. The existence of a set with at least two elements is assured by either the axiom of infinity , or by the axiom schema of specification and the axiom of the power set applied twice to any set. The union over

SECTION 10

#1732765855488

648-419: A statement that is equivalent to it yields ZFC. 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 ∈ {\displaystyle \in } , which

702-402: Is well-founded (i.e., the axiom of regularity ), otherwise the recurrence may not have a unique solution. However, it can be restated non-inductively as follows: a set is hereditary if and only if its transitive closure contains only sets. In this way the concept of hereditary sets can also be extended to non-well-founded set theories in which sets can be members of themselves. For example,

756-419: Is a finite set is easily proved from axioms 1–8 , AC only matters for certain infinite sets . AC is characterized as nonconstructive because it asserts the existence of a choice function but says nothing about how this choice function is to be "constructed". One motivation for the ZFC axioms is the cumulative hierarchy of sets introduced by John von Neumann . In this viewpoint, the universe of set theory

810-464: Is a member of b {\displaystyle b} ). 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: With this alphabet,

864-661: Is a member of X and, whenever a set y is a member of X then S ( y ) {\displaystyle S(y)} is also a member of X . or in modern notation: ∃ X [ ∅ ∈ X ∧ ∀ y ( y ∈ X ⇒ S ( y ) ∈ X ) ] . {\displaystyle \exists X\left[\varnothing \in X\land \forall y(y\in X\Rightarrow S(y)\in X)\right].} More colloquially, there exists

918-393: Is a predicate symbol of arity 2 (a binary relation symbol). This symbol symbolizes a set membership relation. For example, the formula a ∈ b {\displaystyle a\in b} means that a {\displaystyle a} is an element of the set b {\displaystyle b} (also read as a {\displaystyle a}

972-499: Is a set A {\displaystyle A} containing every element that is a member of some member of F {\displaystyle {\mathcal {F}}} : Although this formula doesn't directly assert the existence of ∪ F {\displaystyle \cup {\mathcal {F}}} , the set ∪ F {\displaystyle \cup {\mathcal {F}}} can be constructed from A {\displaystyle A} in

1026-615: Is a set for every x ∈ A , {\displaystyle x\in A,} then the range of f {\displaystyle f} is a subset of some set B {\displaystyle B} . The form stated here, in which B {\displaystyle B} may be larger than strictly necessary, is sometimes called the axiom schema of collection . Let S ( w ) {\displaystyle S(w)} abbreviate w ∪ { w } , {\displaystyle w\cup \{w\},} where w {\displaystyle w}

1080-399: 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

1134-407: 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 w {\displaystyle w} ). It is common to make a definitional extension that adds the symbol " ∅ {\displaystyle \varnothing } " to

SECTION 20

#1732765855488

1188-406: Is any infinite set and P {\displaystyle {\mathcal {P}}} 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

1242-445: Is built up in stages, with one stage for each ordinal number . At stage 0, there are no sets yet. At each following stage, a set is added to the universe if all of its elements have been added at previous stages. Thus the empty set is added at stage 1, and the set containing the empty set is added at stage 2. The collection of all sets that are obtained in this way, over all the stages, is known as V . The sets in V can be arranged into

1296-577: Is not free in φ {\displaystyle \varphi } . Then: (The unique existential quantifier ∃ ! {\displaystyle \exists !} denotes the existence of exactly one element such that it follows a given statement.) In other words, if the relation φ {\displaystyle \varphi } represents a definable function f {\displaystyle f} , A {\displaystyle A} represents its domain , and f ( x ) {\displaystyle f(x)}

1350-498: 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. 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

1404-438: Is some set. (We can see that { w } {\displaystyle \{w\}} is a valid set by applying the axiom of pairing with x = y = w {\displaystyle x=y=w} so that the set z is { w } {\displaystyle \{w\}} ). Then there exists a set X such that the empty set ∅ {\displaystyle \varnothing } , defined axiomatically,

1458-409: Is the case, so y {\displaystyle y} 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 y {\displaystyle y} on the basis of a formula φ ( x ) {\displaystyle \varphi (x)} , we need to previously restrict

1512-506: Is then used to define the power set P ( x ) {\displaystyle {\mathcal {P}}(x)} as the subset of such a y {\displaystyle y} containing the subsets of x {\displaystyle x} exactly: Axioms 1–8 define ZF. Alternative forms of these axioms are often encountered, some of which are listed in Jech (2003) . Some ZF axiomatizations include an axiom asserting that

1566-588: The Zermelo–Fraenkel set theory . Abraham Adolf Halevi Fraenkel studied mathematics at the Universities of Munich , Berlin , Marburg and Breslau . After graduating, he lectured at the University of Marburg from 1916, and was promoted to professor in 1922. In 1919, he married Wilhelmina Malka A. Prins (1892–1983). Due to the severe housing shortage in post-First World war Germany, for a few years

1620-567: The axiom of choice , is presented here as a property about well-orders , as in Kunen (1980) . For any set X {\displaystyle X} , there exists a binary relation R {\displaystyle R} which well-orders X {\displaystyle X} . This means R {\displaystyle R} is a linear order on X {\displaystyle X} such that every nonempty subset of X {\displaystyle X} has

1674-465: 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 ∅ {\displaystyle \varnothing } , once at least one set is known to exist. One way to do this is to use a property φ {\displaystyle \varphi } which no set has. For example, if w {\displaystyle w}

Zermelo–Fraenkel set theory - Misplaced Pages Continue

1728-400: The empty set exists . The axioms of pairing, union, replacement, and power set are often stated so that the members of the set x {\displaystyle x} whose existence is being asserted are just those sets which the axiom asserts x {\displaystyle x} must contain. The following axiom is added to turn ZF into ZFC: The last axiom, commonly known as

1782-475: 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 . 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

1836-548: The above using the axiom schema of specification: The axiom schema of replacement asserts that the image of a set under any definable function will also fall inside a set. Formally, let φ {\displaystyle \varphi } be any formula in the language of ZFC whose free variables are among x , y , A , w 1 , … , w n , {\displaystyle x,y,A,w_{1},\dotsc ,w_{n},} so that in particular B {\displaystyle B}

1890-839: The axiom of extensionality can be reformulated as which says that if x {\displaystyle x} and y {\displaystyle y} have the same elements, then they belong to the same sets. Every non-empty set x {\displaystyle x} contains a member y {\displaystyle y} such that x {\displaystyle x} and y {\displaystyle y} are disjoint sets . or in modern notation: ∀ x ( x ≠ ∅ ⇒ ∃ y ( y ∈ x ∧ y ∩ x = ∅ ) ) . {\displaystyle \forall x\,(x\neq \varnothing \Rightarrow \exists y(y\in x\land y\cap x=\varnothing )).} This (along with

1944-397: 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 says that given any two sets a {\displaystyle a} and b {\displaystyle b} there is a new set { a , b } {\displaystyle \{a,b\}} containing exactly

1998-513: The axioms of pairing and union) implies, for example, that no set is an element of itself and that every set has an ordinal rank . Subsets are commonly constructed using set builder notation . For example, the even integers can be constructed as the subset of the integers Z {\displaystyle \mathbb {Z} } satisfying the congruence modulo predicate x ≡ 0 ( mod 2 ) {\displaystyle x\equiv 0{\pmod {2}}} : In general,

2052-818: The construction of entities of the more general form: This restriction is necessary to avoid Russell's paradox (let y = { x : x ∉ x } {\displaystyle y=\{x:x\notin x\}} then y ∈ y ⇔ y ∉ y {\displaystyle y\in y\Leftrightarrow y\notin y} ) and its variants that accompany naive set theory with unrestricted comprehension (since under this restriction y {\displaystyle y} only refers to sets within z {\displaystyle z} that don't belong to themselves, and y ∈ z {\displaystyle y\in z} has not been established, even though y ⊆ z {\displaystyle y\subseteq z}

2106-479: The couple lived with fellow professor Kurt Hensel as subtenants. After leaving Marburg in 1928, Fraenkel taught at the University of Kiel for a year. He then made the choice of accepting a position at the Hebrew University of Jerusalem , which had been founded four years earlier, where he spent the rest of his career. He became the first dean of the faculty of mathematics, and for a while served as rector of

2160-409: 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

2214-425: The elements of a set exists. For example, the union over the elements of the set { { 1 , 2 } , { 2 , 3 } } {\displaystyle \{\{1,2\},\{2,3\}\}} is { 1 , 2 , 3 } . {\displaystyle \{1,2,3\}.} The axiom of union states that for any set of sets F {\displaystyle {\mathcal {F}}} , there

Zermelo–Fraenkel set theory - Misplaced Pages Continue

2268-500: The empty set, is a hereditary set. In formulations of set theory that are intended to be interpreted in the von Neumann universe or to express the content of Zermelo–Fraenkel set theory , all sets are hereditary, because the only sort of object that is even a candidate to be an element of a set is another set. Thus the notion of hereditary set is interesting only in a context in which there may be urelements . The inductive definition of hereditary sets presupposes that set membership

2322-527: 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 exists — usually expressed as the assertion that something is identical to itself, ∃ x ( x = x ) {\displaystyle \exists x(x=x)} . Consequently, it

2376-414: The language of ZFC with all free variables among x , z , w 1 , … , w n {\displaystyle x,z,w_{1},\ldots ,w_{n}} ( y {\displaystyle y} is not free in φ {\displaystyle \varphi } ). Then: Note that the axiom schema of specification can only construct subsets and does not allow

2430-414: The language of ZFC. If x {\displaystyle x} and y {\displaystyle y} are sets, then there exists a set which contains x {\displaystyle x} and y {\displaystyle y} as elements, for example if x = {1,2} and y = {2,3} then z will be {{1,2},{2,3}} The axiom schema of specification must be used to reduce this to

2484-625: The recursive rules for forming well-formed formulae (wff) are as follows: A well-formed formula can be thought as a syntax tree. The leaf nodes are always atomic formulae. Nodes ∧ {\displaystyle \land } and ∨ {\displaystyle \lor } have exactly two child nodes, while nodes ¬ {\displaystyle \lnot } , ∀ x {\displaystyle \forall x} and ∃ x {\displaystyle \exists x} have exactly one. There are countably infinitely many wffs, however, each wff has

2538-418: The set { ∅ } {\displaystyle \{\varnothing \}} containing only the empty set ∅ {\displaystyle \varnothing } is a hereditary set. Similarly, a set { ∅ , { ∅ } } {\displaystyle \{\varnothing ,\{\varnothing \}\}} that contains two elements: the empty set and the set that contains only

2592-407: The sets y {\displaystyle y} will regard within a set z {\displaystyle z} that leaves y {\displaystyle y} outside so y {\displaystyle y} 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

2646-543: The subset of a set z {\displaystyle z} obeying a formula φ ( x ) {\displaystyle \varphi (x)} with one free variable x {\displaystyle x} 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 φ {\displaystyle \varphi } ). Formally, let φ {\displaystyle \varphi } be any formula in

2700-629: The time, notably the cardinal number ℵ ω {\displaystyle \aleph _{\omega }} and the set { Z 0 , P ( Z 0 ) , P ( P ( Z 0 ) ) , P ( P ( P ( Z 0 ) ) ) , . . . } , {\displaystyle \{Z_{0},{\mathcal {P}}(Z_{0}),{\mathcal {P}}({\mathcal {P}}(Z_{0})),{\mathcal {P}}({\mathcal {P}}({\mathcal {P}}(Z_{0}))),...\},} where Z 0 {\displaystyle Z_{0}}

2754-533: The union of the members of X {\displaystyle X} , called a " choice function ", such that for all Y ∈ X {\displaystyle Y\in X} one has f ( Y ) ∈ Y {\displaystyle f(Y)\in Y} . A third version of the axiom, also equivalent, is Zorn's lemma . Since the existence of a choice function when X {\displaystyle X}

SECTION 50

#1732765855488

2808-642: The university. Fraenkel was a fervent Zionist and as such was a member of Jewish National Council and the Jewish Assembly of Representatives under the British mandate . He also belonged to the Mizrachi religious wing of Zionism, which promoted Jewish religious education and schools, and which advocated giving the Chief Rabbinate authority over marriage and divorce. Fraenkel's early work

2862-600: The variety of first-order logic in which you are constructing set theory does not include equality " = {\displaystyle =} ", x = y {\displaystyle x=y} may be defined as an abbreviation for the following formula: ∀ z [ z ∈ x ⇔ z ∈ y ] ∧ ∀ w [ x ∈ w ⇔ y ∈ w ] . {\displaystyle \forall z[z\in x\Leftrightarrow z\in y]\land \forall w[x\in w\Leftrightarrow y\in w].} In this case,

2916-458: Was on Kurt Hensel 's p-adic numbers and on the theory of rings . He is best known for his work on axiomatic set theory , publishing his first major work on the topic Einleitung in die Mengenlehre (Introduction to set theory) in 1919. In 1922 and 1925, he published two papers that sought to improve Zermelo 's axiomatic system; the result is the Zermelo–Fraenkel axioms . Fraenkel worked in set theory and foundational mathematics . Fraenkel

#487512