HOME

TheInfoList



OR:

In many popular versions of
axiomatic set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, ...
, the axiom schema of specification, also known as the axiom schema of separation, subset axiom scheme or axiom schema of restricted comprehension is an
axiom schema In mathematical logic, an axiom schema (plural: axiom schemata or axiom schemas) generalizes the notion of axiom. Formal definition An axiom schema is a formula in the metalanguage of an axiomatic system, in which one or more schematic variables ap ...
. Essentially, it says that any definable subclass of a set is a set. Some mathematicians call it the axiom schema of comprehension, although others use that term for ''unrestricted'' comprehension, discussed below. Because restricting comprehension avoided
Russell's paradox In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains a ...
, several mathematicians including
Zermelo Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic se ...
, Fraenkel, and Gödel considered it the most important axiom of set theory.


Statement

One instance of the schema is included for each
formula In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwee ...
φ in the language of set theory with
free variables In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation (symbol) that specifies places in an expression where substitution may take place and is not ...
among ''x'', ''w''1, ..., ''w''''n'', ''A''. So ''B'' does not occur free in φ. In the formal language of set theory, the axiom schema is: :\forall w_1,\ldots,w_n \, \forall A \, \exists B \, \forall x \, ( x \in B \Leftrightarrow x \in A \land \varphi(x, w_1, \ldots, w_n , A) ) or in words: : Given any
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
''A'',
there is English grammar is the set of structural rules of the English language. This includes the structure of words, phrases, clauses, sentences, and whole texts. This article describes a generalized, present-day Standard English – a form of speech an ...
a set ''B'' (a subset of ''A'') such that, given any set ''x'', ''x'' is a member of ''B''
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...
''x'' is a member of ''A''
and or AND may refer to: Logic, grammar, and computing * Conjunction (grammar), connecting two words, phrases, or clauses * Logical conjunction in mathematical logic, notated as "∧", "⋅", "&", or simple juxtaposition * Bitwise AND, a boolea ...
φ holds for ''x''. Note that there is one axiom for every such
predicate Predicate or predication may refer to: * Predicate (grammar), in linguistics * Predication (philosophy) * several closely related uses in mathematics and formal logic: **Predicate (mathematical logic) **Propositional function **Finitary relation, o ...
φ; thus, this is an
axiom schema In mathematical logic, an axiom schema (plural: axiom schemata or axiom schemas) generalizes the notion of axiom. Formal definition An axiom schema is a formula in the metalanguage of an axiomatic system, in which one or more schematic variables ap ...
. To understand this axiom schema, note that the set ''B'' must be a
subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
of ''A''. Thus, what the axiom schema is really saying is that, given a set ''A'' and a predicate ''P'', we can find a subset ''B'' of ''A'' whose members are precisely the members of ''A'' that satisfy ''P''. By the
axiom of extensionality 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. It says that sets having the same elements ...
this set is unique. We usually denote this set using
set-builder notation In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by enumerating its elements, or stating the properties that its members must satisfy. Defining ...
as . Thus the essence of the axiom is: : Every subclass of a set that is defined by a predicate is itself a set. The axiom schema of specification is characteristic of systems of
axiomatic set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, ...
related to the usual set theory ZFC, but does not usually appear in radically different systems of
alternative set theory In a general sense, an alternative set theory is any of the alternative mathematical approaches to the concept of set and any alternative to the de facto standard set theory described in axiomatic set theory by the axioms of Zermelo–Fraenkel set ...
. For example,
New Foundations In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of ''Principia Mathematica''. Quine first proposed NF in a 1937 article titled "New Foundations ...
and
positive set theory In mathematical logic, positive set theory is the name for a class of alternative set theories in which the axiom of comprehension holds for at least the positive formulas \phi (the smallest class of formulas containing atomic membership and equal ...
use different restrictions of the
axiom of comprehension In many popular versions of axiomatic set theory, the axiom schema of specification, also known as the axiom schema of separation, subset axiom scheme or axiom schema of restricted comprehension is an axiom schema. Essentially, it says that any ...
of
naive set theory Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike Set theory#Axiomatic set theory, axiomatic set theories, which are defined using Mathematical_logic#Formal_logical_systems, forma ...
. The
Alternative Set Theory In a general sense, an alternative set theory is any of the alternative mathematical approaches to the concept of set and any alternative to the de facto standard set theory described in axiomatic set theory by the axioms of Zermelo–Fraenkel set ...
of Vopenka makes a specific point of allowing proper subclasses of sets, called
semiset {{distinguish, Semialgebraic set In set theory, a semiset is a proper class that is a subclass of a set. The theory of semisets was proposed and developed by Czech mathematicians Petr Vopěnka and Petr Hájek (1972). It is based on a modification ...
s. Even in systems related to ZFC, this scheme is sometimes restricted to formulas with bounded quantifiers, as in
Kripke–Platek set theory with urelements The Kripke–Platek set theory with urelements (KPU) is an axiom system for set theory with urelements, based on the traditional (urelement-free) Kripke–Platek set theory. It is considerably weaker than the (relatively) familiar system ZFU. The ...
.


Relation to the axiom schema of replacement

The axiom schema of separation can almost be derived from the
axiom schema of replacement In set theory, the axiom schema of replacement is a schema of axioms in Zermelo–Fraenkel set theory (ZF) that asserts that the image of any set under any definable mapping is also a set. It is necessary for the construction of certain infinite ...
. First, recall this axiom schema: :\forall A \, \exists B \, \forall C \, ( C \in B \iff \exists D \, D \in A \land C = F(D) ) for any
functional predicate 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. Functional predicates are also sometimes called mappings, but ...
''F'' in one
variable Variable may refer to: * Variable (computer science), a symbolic name associated with a value and whose associated value may be changed * Variable (mathematics), a symbol that represents a quantity in a mathematical expression, as used in many ...
that doesn't use the symbols ''A'', ''B'', ''C'' or ''D''. Given a suitable predicate ''P'' for the axiom of specification, 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 separation is the
empty set In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
, so the axiom of separation follows from the axiom of replacement together with the
axiom of empty set In axiomatic set theory, the axiom of empty set is a statement that asserts the existence of a set with no elements. It is an axiom of Kripke–Platek set theory and the variant of general set theory that Burgess (2005) calls "ST," and a demonstrab ...
. For this reason, the axiom schema of specification is often left out of modern lists of the Zermelo–Fraenkel axioms. However, it's still important for historical considerations, and for comparison with alternative axiomatizations of set theory, as can be seen for example in the following sections.


Unrestricted comprehension

The axiom schema of unrestricted comprehension reads: \forall w_1,\ldots,w_n \, \exists B \, \forall x \, ( x \in B \Leftrightarrow \varphi(x, w_1, \ldots, w_n) ) that is: This set is again unique, and is usually denoted as This axiom schema was tacitly used in the early days of
naive set theory Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike Set theory#Axiomatic set theory, axiomatic set theories, which are defined using Mathematical_logic#Formal_logical_systems, forma ...
, before a strict axiomatization was adopted. Unfortunately, it leads directly to
Russell's paradox In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains a ...
by taking to be (i.e., the property that set is not a member of itself). Therefore, no useful axiomatization of set theory can use unrestricted comprehension. Passing from
classical logic Classical logic (or standard logic or Frege-Russell logic) is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy. Characteristics Each logical system in this class ...
to
intuitionistic logic Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems ...
does not help, as the proof of Russell's paradox is intuitionistically valid. Accepting only the axiom schema of specification was the beginning of axiomatic set theory. Most of the other Zermelo–Fraenkel axioms (but not the
axiom of extensionality 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. It says that sets having the same elements ...
, the
axiom of regularity In mathematics, the axiom of regularity (also known as the axiom of foundation) is an axiom of Zermelo–Fraenkel set theory that states that every non-empty set ''A'' contains an element that is disjoint from ''A''. In first-order logic, the axi ...
, or the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
) then became necessary to make up for some of what was lost by changing the axiom schema of comprehension to the axiom schema of specification – each of these axioms states that a certain set exists, and defines that set by giving a predicate for its members to satisfy, i.e. it is a special case of the axiom schema of comprehension. It is also possible to prevent the schema from being inconsistent by restricting which formulae it can be applied to, such as only
stratified Stratification may refer to: Mathematics * Stratification (mathematics), any consistent assignment of numbers to predicate symbols * Data stratification in statistics Earth sciences * Stable and unstable stratification * Stratification, or st ...
formulae in
New Foundations In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of ''Principia Mathematica''. Quine first proposed NF in a 1937 article titled "New Foundations ...
(see below) or only positive formulae (formulae with only conjunction, disjunction, quantification and atomic formulae) in
positive set theory In mathematical logic, positive set theory is the name for a class of alternative set theories in which the axiom of comprehension holds for at least the positive formulas \phi (the smallest class of formulas containing atomic membership and equal ...
. Positive formulae, however, typically are unable to express certain things that most theories can; for instance, there is no
complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...
or relative complement in positive set theory.


In NBG class theory

In
von Neumann–Bernays–Gödel set theory In the foundations of mathematics, von Neumann–Bernays–Gödel set theory (NBG) is an axiomatic set theory that is a conservative extension of Zermelo–Fraenkel–choice set theory (ZFC). NBG introduces the notion of class, which is a collect ...
, a distinction is made between sets and classes. A class is a set if and only if it belongs to some class . In this theory, there is a
theorem In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of th ...
schema that reads \exists D \forall C \, ( C \in D \iff P (C) \land \exists E \, ( C \in E ) ) \,, that is, provided that the quantifiers in the predicate are restricted to sets. This theorem schema is itself a restricted form of comprehension, which avoids Russell's paradox because of the requirement that be a set. Then specification for sets themselves can be written as a single axiom \forall D \forall A \, ( \exists E \, A \in E \implies \exists B \, \exists E \, ( B \in E ) \land \forall C \, ( C \in B \iff [ C \in A \land C \in D ) ] ) \,, that is, or even more simply In this axiom, the predicate is replaced by the class , which can be quantified over. Another simpler axiom which achieves the same effect is \forall A \forall B \, ( \exists E \, ( A \in E ) \land \forall C \, ( C \in B \implies C \in A ) \implies \exists E \, B \in E ) \,, that is,


In higher-order settings

In a typed language where we can quantify over predicates, the axiom schema of specification becomes a simple axiom. This is much the same trick as was used in the NBG axioms of the previous section, where the predicate was replaced by a class that was then quantified over. In
second-order logic In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory. First-order logic quantifies onl ...
and
higher-order logic mathematics and logic, a higher-order logic is a form of predicate logic that is distinguished from first-order logic by additional quantifiers and, sometimes, stronger semantics. Higher-order logics with their standard semantics are more express ...
with higher-order semantics, the axiom of specification is a logical validity and does not need to be explicitly included in a theory.


In Quine's New Foundations

In the
New Foundations In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of ''Principia Mathematica''. Quine first proposed NF in a 1937 article titled "New Foundations ...
approach to set theory pioneered by
W. V. O. Quine W. may refer to: * SoHo (Australian TV channel) (previously W.), an Australian pay television channel * ''W.'' (film), a 2008 American biographical drama film based on the life of George W. Bush * "W.", the fifth track from Codeine's 1992 EP ''Bar ...
, the axiom of comprehension for a given predicate takes the unrestricted form, but the predicates that may be used in the schema are themselves restricted. The predicate ( is not in ) is forbidden, because the same symbol appears on both sides of the membership symbol (and so at different "relative types"); thus, Russell's paradox is avoided. However, by taking to be , which is allowed, we can form a set of all sets. For details, see
stratification Stratification may refer to: Mathematics * Stratification (mathematics), any consistent assignment of numbers to predicate symbols * Data stratification in statistics Earth sciences * Stable and unstable stratification * Stratification, or st ...
.


References

* * Halmos, Paul, ''
Naive Set Theory Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike Set theory#Axiomatic set theory, axiomatic set theories, which are defined using Mathematical_logic#Formal_logical_systems, forma ...
''. Princeton, New Jersey: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. (Springer-Verlag edition). *Jech, Thomas, 2003. ''Set Theory: The Third Millennium Edition, Revised and Expanded''. Springer. . *Kunen, Kenneth, 1980. ''Set Theory: An Introduction to Independence Proofs''. Elsevier. . {{Set theory Axioms of set theory