Editing Stratification (mathematics)

{{Unreferenced|date=December 2009}}
'''Stratification''' has several usages in mathematics.

==In mathematical logic==

In [[mathematical logic]], '''stratification''' is any consistent assignment of numbers to [[Predicate (logic)|predicate]] symbols guaranteeing that a unique formal [[Interpretation (logic)|interpretation]] of a logical theory exists. Specifically, we say that a set of [[Clause (logic)|clauses]] of the form <math>Q_1 \wedge \dots \wedge Q_n \wedge \neg Q_{n+1} \wedge \dots \wedge \neg Q_{n+m} \rightarrow P</math> is stratified if and only if
there is a stratification assignment S that fulfills the following conditions:

# If a predicate P is positively derived from a predicate Q (i.e., P is the head of a rule, and Q occurs positively in the body of the same rule), then the stratification number of P must be greater than or equal to the stratification number of Q, in short <math>S(P) \geq S(Q)</math>.
# If a predicate P is derived from a negated predicate Q (i.e., P is the head of a rule, and Q occurs negatively in the body of the same rule), then the stratification number of P must be greater than the stratification number of Q, in short <math>S(P) > S(Q)</math>.

The notion of stratified negation leads to a very effective operational semantics for stratified programs in terms of the stratified least fixpoint, that is obtained by iteratively applying the fixpoint operator to each ''stratum'' of the program, from the lowest one up.
Stratification is not only useful for guaranteeing unique interpretation of [[Horn clause]]
theories. 

==In a specific set theory==

In [[New Foundations]] (NF) and related set theories, a formula <math>\phi</math> in the language of first-order logic with equality and membership is said to be
'''stratified''' if and only if there is a function
<math>\sigma</math> which sends each variable appearing in <math>\phi</math> (considered as an item of syntax) to
a natural number (this works equally well if all integers are used) in such a way that
any atomic formula <math>x \in y</math> appearing in <math>\phi</math> satisfies <math>\sigma(x)+1 = \sigma(y)</math> and any [[atomic formula]] <math>x = y</math> appearing in <math>\phi</math> satisfies <math>\sigma(x) = \sigma(y)</math>.

It turns out that it is sufficient to require that these conditions be satisfied only when
both variables in an atomic formula are bound in the set abstract <math>\{x \mid \phi\}</math>
under consideration.  A set abstract satisfying this weaker condition is said to be
'''weakly stratified'''.

The stratification of [[New Foundations]] generalizes readily to languages with more
predicates and with term constructions.  Each primitive predicate needs to have specified
required displacements between values of <math>\sigma</math> at its (bound) arguments
in a (weakly) stratified formula.  In a language with term constructions, terms themselves
need to be assigned values under <math>\sigma</math>, with fixed displacements from the
values of each of their (bound) arguments in a (weakly) stratified formula.  Defined term
constructions are neatly handled by (possibly merely implicitly) using the theory
of descriptions:  a term <math>(\iota x.\phi)</math> (the x such that <math>\phi</math>) must
be assigned the same value under <math>\sigma</math> as the variable x.

A formula is stratified if and only if it is possible to assign types to all variables appearing
in the formula in such a way that it will make sense in a version TST of the theory of
types described in the [[New Foundations]] article, and this is probably the best way
to understand the stratification of [[New Foundations]] in practice.

The notion of stratification can be extended to the [[lambda calculus]]; this is found
in papers of Randall Holmes.

A motivation for the use of stratification is to address [[Russell's paradox]], the antinomy considered to have undermined [[Frege]]'s central work ''[[Grundgesetze der Arithmetik]]'' (1902).
{{cite book
 | last = Quine
 | first = Willard Van Orman
 | title = From a Logical Point of View
 | publisher = [[Harper & Row]]
 | edition = 2nd
 | location = New York
 | orig-year = 1961
 | date = 1963
 | page = 90
 | lccn = 61-15277
 }}

==In topology==

{{main|Stratified space}}
In [[singularity theory]], there is a different meaning, of a decomposition of a [[topological space]] ''X'' into disjoint subsets each of which is a [[topological manifold]] (so that in particular a  ''stratification'' defines a  [[partition of a set|partition]] of the topological space). This is not a useful notion when unrestricted; but when the various '''strata''' are defined by some recognisable set of conditions (for example being [[locally closed]]), and fit together manageably, this idea is often applied in geometry. [[Hassler Whitney]] and [[René Thom]] first defined formal conditions for stratification.  See [[Whitney stratification]] and [[topologically stratified space]].

==In statistics==

See [[stratified sampling]].

{{Mathematical logic}}
{{set index article|mathematics}}

{{DEFAULTSORT:Stratification (Mathematics)}}
[[Category:Mathematical logic]]
[[Category:Mathematical terminology]]
[[Category:Set theory]]
[[Category:Stratifications]]