Namespaces
Variants
Actions

Non-predicative definition

From Encyclopedia of Mathematics
Jump to: navigation, search

A definition that is meaningful only when the object to be defined is assumed to exist.

The formation of the set of all sets is non-predicative. So is the definition of the least upper bound of an arbitrary set of real numbers. Any non-predicative definition can be regarded as a property that selects the required object from a certain given aggregate. Since here the problem of the existence of the object in question remains open, instead of non-predicative definitions one can also speak of non-predicative properties. Once the language in which the properties are expressed is fixed, the concept of non-predicativity can be made more precise as follows. A property (more accurately, a linguistic expression for the relevant property) is called non-predicative if it contains a bound variable such that the object to be defined falls within its range of applicability. A property is called predicative if it contains no such bound variables.

The concept of non-predicativity arose in connection with the discovery of set-theoretical paradoxes, and the term itself is due to H. Poincaré (1906), who was first to raise objections against non-predicative definitions.

The antinomies (cf. Antinomy) discovered at the beginning of the 20th century contain non-predicativities. For example, in Russell's paradox the set $R$ of all sets that do not contain themselves as elements is defined by the formula:

$$\forall x(x\in R\Leftrightarrow\neg x\in x),$$

where $x$ is a variable ranging over all sets. In this formula $R$ is a possible value of the variable $x$. In mathematics non-predicative definitions are widely used. For example, the union $S$ of all sets of natural numbers satisfying a condition $\phi$ can be defined by the formula

$$\forall n(n\in S\Leftrightarrow\exists M(\phi(M)\mathbin{\&}n\in M)),\label{*}\tag{*}$$

where $n$ is a variable ranging over the natural numbers and $M$ a variable ranging over subsets of the natural numbers. In this formula $S$ is a possible value of the bound variable. A non-predicative way of specifying an object can sometimes be replaced by a predicative one. For example, if for the property $\phi(M)$ one takes the formula $M=A\lor M=B$, where $A$ and $B$ are certain fixed sets, then \eqref{*} is equivalent to the predicative formula

$$\forall n(n\in S\leftrightarrow n\in A\lor n\in B),$$

which expresses that $S$ is the union of $A$ and $B$.

B. Russell made an attempt of constructing mathematics on a predicative basis. In the theory of types (cf. Types, theory of) which he developed, sets are arranged in a hierarchy in accordance with the expressions defining them. For example, the set $S$ in \eqref{*} must be assigned to a higher level in the hierarchy than that of $M$ and those of the variables contained in the formula for $\phi$. On the predicative basis one cannot build up analysis to its full extent. A statement is meaningful only if certain restrictions on the levels occurring in that statement are satisfied. Russell was forced to introduce an axiom of reducibility, which practically wiped out the distinction between levels. However, the predicative theory in the presence of the axioms of arithmetic makes it possible to build up analysis to an extent sufficient for many applications (see [4]).

The phenomenon of non-predicativity is based essentially on the absolute character of the understanding the word "all" (all without any restrictions, decisively all). The division of all sets into distinct "levels of sets" is an attempt to restrict this absolute character. A more radical revision of the method of thinking based on an absolute understanding of the concept "all" is undertaken by the intuitionistic and constructive trends in mathematics (cf. Intuitionism; Constructive mathematics).

References

[1] A. Church, "Introduction to mathematical logic" , 1 , Princeton Univ. Press (1956)
[2] A.A. Fraenkel, Y. Bar-Hillel, "Foundations of set theory" , North-Holland (1958)
[3] D. Hilbert, W. Ackermann, "Principles of mathematical logic" , Chelsea (1950) (Translated from German)
[4] G. Takeuti, "Two applications of logic to mathematics" , Iwanami Shoten (1978)
How to Cite This Entry:
Non-predicative definition. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Non-predicative_definition&oldid=44742
This article was adapted from an original article by V.N. Grishin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article