In many popular versions of
axiomatic set theory
Set theory is the branch of mathematical logic that studies 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, is mostly conce ...
, 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 a ...
. 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 conta ...
, several mathematicians including
Zermelo,
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 bet ...
φ in the language of set theory with
free variables 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:
:
or in words:
: Given any
set ''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 ...
a set ''B'' (a subset of ''A'') such that, given any set ''x'', ''x'' is a member of ''B''
if and only if ''x'' is a member of ''A''
and φ 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 a ...
.
To understand this axiom schema, note that the set ''B'' must be a
subset 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 eleme ...
this set is unique. We usually denote this set using
set-builder notation 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 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, is mostly conce ...
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 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 equ ...
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 axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language. It d ...
. 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 modifi ...
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.
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 infinit ...
.
First, recall this axiom schema:
:
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 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 demonstra ...
.
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:
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 axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language. It d ...
, 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 conta ...
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 to
intuitionistic logic 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 eleme ...
, 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 ...
, 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 collection ...
) 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 formulae in
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 equ ...
. 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 coll ...
, 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 schema that reads
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
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
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 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 expr ...
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 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.
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 axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language. It d ...
''. 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