In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of replacement is a schema of axioms in Zermelo-Fraenkel set theory. Set theory is a branch of mathematics created principally by the German mathematician Georg Cantor at the end of the 19th century. ... Logic (from ancient Greek λόγος (logos), originally meaning the word, or what is spoken, but coming to mean thought or reason) is most often said to be the study of arguments, although the exact definition of logic is a matter of controversy amongst philosophers (see below). ... Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote quotations related to: Mathematics Look up Mathematics in Wiktionary, the free dictionary Wikimedia Commons has more media related to: Mathematics Bogomolny, Alexander: Interactive Mathematics Miscellany and Puzzles. ... Edsger Dijkstra said: Computer science is no more about computers than astronomy is about telescopes. ... The word schema comes from the Greek word σχήμα (skhēma) that means shape or more generally plan. ... In epistemology, an axiom is a self-evident truth upon which other knowledge must rest, from which other knowledge is built up. ... The Zermelo-Fraenkel axioms of set theory (ZF) are the standard axioms of axiomatic set theory on which, together with the axiom of choice, all of ordinary mathematics is based in modern formulations. ...

Suppose P is any predicate in two variables that doesn't use the symbol B. Then in the formal language of the Zermelo-Fraenkel axioms, the axiom schema reads: In mathematics, a predicate is a relation. ... In computer science and mathematics, a variable is a symbol denoting a quantity or symbolic representation. ... In mathematics, logic and computer science, a formal language is a set of finite-length words (i. ...

or in words:

If, given any set X, there is a unique set Y such that P holds for X and Y, then, given any set A, there is a set B such that, given any set C, C is a member of B if and only if there is a set D such that D is a member of A and P holds for D and C.

Note that there is one axiom for every such predicate P; thus, this is an axiom schema. In logical calculus of mathematics, the logical conditional (also known as the material implication, sometimes material conditional) is a binary logical operator connecting two statements, if p then q where p is a hypothesis (or antecedent) and q is a conclusion (or consequent). ... In predicate logic, universal quantification is an attempt to formalise the notion that something (a logical predicate) is true for everything, or every relevant thing. ... The notion of a set is one of the most important and fundamental concepts in modern mathematics. ... In predicate logic, existential quantification is an attempt to formalize the notion that something (a logical predicate) is true for something, or at least one relevant thing. ... In predicate logic, existential quantification is an attempt to formalize the notion that something (a logical predicate) is true for something, or at least one relevant thing. ... In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. It is often, not always, written italicized: iff. ... AND Logic Gate Logical conjunction (usual symbol and) is a logical operator that results in true if both of the operands are true. ... In symbolic logic, it is sometimes inconvenient or impossible to express an axiomatic system in a finite number of axioms. ...

To understand this axiom, first note that the clause in the first set of parentheses above is exactly what one needs to construct a functional predicate F in one variable such that F(X) = Y if and only if P(X,Y). Indeed, if one formalises the language of predicate logic to allow the use of derived functional predicates in axiom schemas, then the axiom schema may be rewritten as: In formal logic and related branches of mathematics, a functional predicate, or function symbol, is a logical symbol that may be applied to an object term to produce another object term. ... ...

for each derived functional predicate F in one variable; or in words:

Given any set A, there is a set B such that, given any set C, C is a member of B if and only if there is a set D such that D is a member of A and C is equal to the value of F at D.

Next, note that the clause in parentheses in the reformulation above (equivalent to the second clause in parentheses in the original statement) simply states that C is the value of F at some member D of A. Thus, what the axiom schema is really saying is that, given a set A, we can find a set B whose members are precisely the values of F at the members of A. See also the disambiguation page title equality. ...

We can use the axiom of extensionality to show that this set B is unique. We call the set B the image of A under F, and denote it F(A) or (using a form of set-builder notation) {F(D) : D in A}. Thus the essence of the axiom schema is: 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. ... Image of the Wikimedia Commons logo. ... In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by indicating the properties that its members must satisfy. ...

The image of a set under a mapping is a set.

History and philosophy

Most of the applications to which replacement might naïvely be put in fact do not require it. For example, suppose that f is a function from a set S to a set T. Then we may construct a functional predicate F such that F(x) = f(x) whenever x is a member of S, letting F(x) be anything we like otherwise (it won't matter for this application). Then given a subset A of S, applying the axiom schema of replacement to F constructs the image f(A) of the subset A under the function f; it is just F'(A). However, replacement is in fact not needed here, because f(A) is a subset of T, so we could instead construct this image using the axiom schema of specification as the set {y in T : for some x in A, y = f(x)}. In general, specification will suffice when the values of F at the members of A all belong to some previously constructed set T; replacement is needed only when such a T isn't already available. In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique element of another (possibly the same) set (the codomain, not to be confused with the range). ... A is a subset of B If X and Y are sets and every element of X is also an element of Y, then we say or write: X is a subset of (or is included in) Y; X ⊆ Y; Y is a superset of (or includes) X; Y ⊇ X... Image of the Wikimedia Commons logo. ... In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of specification, or axiom schema of separation, or axiom schema of restricted comprehension, is a schema of axioms in Zermelo-Fraenkel set theory. ...

According to some philosophies, it's preferable to apply specification to a set like T in the example above, since specification is logically weaker than replacement (as explained in the next section). Indeed, replacement is arguably unnecessary in ordinary mathematics, needed only for certain features of axiomatic set theory. For example, you need replacement to construct the von Neumann ordinals from ω2 onwards, and the von Neumann ordinals are necessary for certain set-theoretic results. However, you don't need replacement to construct these ordinal numbers in other ways that are sufficient for applications to the theory of well-ordered sets. Some mathematicians working on the foundations of mathematics, particularly those that focus on type theory as opposed to set theory, find this axiom unnecessary for any purpose and therefore do not include it (nor a type-theoretic analogue) in their foundations. Replacement is difficult to express at all in foundations built upon topos theory, so it's usually left out there as well. Nevertheless, replacement is not controversial in the sense that some people find its consequences to be necessarily false (a sense in which the axiom of choice, for example, is controversial); it's just that they find it unnecessary. Set theory is a branch of mathematics created principally by the German mathematician Georg Cantor at the end of the 19th century. ... Ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. ... Commonly, ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. ... In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ... The term foundations of mathematics is sometimes used for certain fields of mathematics itself, namely for mathematical logic, axiomatic set theory, proof theory, model theory, and recursion theory. ... At the broadest level, type theory is the branch of mathematics and logic that concerns itself with classifying entities into sets called types. ... In mathematics, a topos (plural: topoi or toposes - this is a contentious topic) is a type of category which allows the formulation of all of mathematics inside it. ... In mathematics, the axiom of choice is an axiom of set theory. ...

The axiom schema of replacement wasn't part of Ernst Zermelo's 1908 axiomatisation of set theory (Z); its introduction by Adolf Fraenkel in 1922 is what makes modern set theory Zermelo-Fraenkel set theory (ZF). The axiom was independently discovered by Thoralf Skolem later in the same year, and it is in fact Skolem's final version of the axiom list that we use today -- but he usually gets no credit since each individual axiom was developed earlier by either Zermelo or Fraenkel. Including replacement makes a big difference from the proof-theoretic point of view; adding this schema to Zermelo's axioms makes for a much stronger system logically, allowing one to prove more statements. In particular, in ZF one can prove the consistency of Z by constructing the von Neumann universe V_ω2 as a model. (Of course, Gödel's second incompleteness theorem shows that neither of these theories can prove its own consistency, if it is consistent.) Ernst Friedrich Ferdinand Zermelo (July 27, 1871 – May 21, 1953) was a German mathematician and philosopher. ... 1908 is a leap year starting on Wednesday (link will take you to calendar). ... Adolf Abraham Halevi Fraenkel (February 17, 1891 - October 15, German / Israeli mathematician. ... 1922 was a common year starting on Sunday (see link for calendar). ... Albert Thoralf Skolem (May 23, 1887 - March 23, 1963) was a Norwegian mathematician. ... Proof theory, studied as a branch of mathematical logic, represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. ... Consistency has three technical meanings: In mathematics and logic, as well as in theoretical physics, it refers to the proposition that a formal theory or a physical theory contains no contradictions. ... In axiomatic set theory and related branches of mathematics, the Von Neumann universe, or Von Neumann hierarchy of sets is the class of all sets, divided into a transfinite hierarchy of individual sets. ... In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the models which underlie mathematical systems. ... In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proved by Kurt Gödel in 1931. ...

Relation to the axiom schema of specification

The axiom schema of specification can almost be derived from the axiom schema of replacement. In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of specification, or axiom schema of separation, or axiom schema of restricted comprehension, is a schema of axioms in Zermelo-Fraenkel set theory. ...

First, recall this axiom schema:

for any predicate P in one variable that doesn't use the symbol B. Given such a predicate P, define the mapping F by F(D) = D if P(D) is true and F(D) = E if P(D) is false, where E is any member of A such that P(E) is true. Then the set B guaranteed by the axiom of replacement is precisely the set B required for the axiom of specification. The only problem is if no such E exists. But in this case, the set B required for the axiom of specification is the empty set, so the axiom schema follows in general using also the axiom of empty set. In mathematics, the empty set is the set with no elements. ... In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of empty set is one of the axioms of Zermelo_Fraenkel set theory. ...

For this reason, the axiom schema of specification is often left out of modern lists of the Zermelo-Fraenkel axioms. However, specification is still important for historical considerations, and for comparison with alternative axiomatisations of set theory. For example, the argument above used the law of excluded middle, so specification can't be left out of an intuitionistic set theory. And any formulation of set theory that excludes replacement as unnecessary certainly will want to keep specification. The law of excluded middle (tertium non datur in Latin) states that for any proposition P, it is true that (P or ~P). ... Intuitionistic logic, or constructivist logic, is the logic used in mathematical intuitionism and other forms of mathematical constructivism. ...