Définitions prédicatives et imprédicatives

The distinction between predicative and impredicative definitions is today widely regarded as an important watershed in logic and the philosophy of mathematics. A definition is said to be impredicative if it generalizes over a totality to which the entity being defined belongs. Otherwise the definition is said to be predicative. In the examples below, (2) et (4) are impredicative.

Let π be the ratio between the circumference and diameter of a circle.
Let n be the least natural number such that n cannot be written as the sum of at most four cubes.
A natural number n is prime if and only if n > 1 and the only divisors of n are 1 and n itself.
A person x is general-like if and only if, for every property P which all great generals have, x too has P.

Définition (1) is predicative since π is defined solely in terms of the circumference and diameter of some given circle. Définition (2), d'autre part, is impredicative, as this definition generalizes over all natural numbers, including n itself. Définition (3) is predicative, as the property of being prime is defined without any generalization over properties. Par contre, définition (4) is impredicative, as the property of being general-like is defined by generalization over the totality of all properties.

Impredicative definitions have long been controversial in logic and the philosophy of mathematics. Many prominent logicians and philosophers—most importantly Henri Poincaré, Bertrand Russel, and Hermann Weyl—have rejected such definitions as viciously circular. Toutefois, it turns out that the rejection of such definitions would require a major revision of classical mathematics. The most common contemporary view is probably that of Kurt Gödel, who argued that impredicative definitions are legitimate provided one holds a realist view of the entities in question.

Although few theorists any longer reject all impredicative definitions, it is widely recognized that such definitions require stronger theoretical assumptions than do predicative definitions.

Table des matières
Paradoxes and the Vicious Circle Principle
Impredicativity in Classical Mathematics
Defenses of Impredicative Definitions
References and Further Readings
1. Paradoxes and the Vicious Circle Principle

The notion of predicativity has its origin in the early twentieth century debate between Poincaré, Russell and others about the nature and source of the logical paradoxes. ([Poincaré 1906], [Russell 1908]) Ainsi, it will be useful to review some of the most important logical paradoxes.

Russell’s paradox. Let the Russell class R be the class of all classes that are not members of themselves. If R is a member of itself, then it doesn’t satisfy the membership criterion and hence isn’t a member of itself. Si, d'autre part, R isn’t a member of itself, then it does satisfy the membership criterion and hence is a member of itself after all. Ainsi, R is a member of itself iff (si et seulement si) R is not a member of itself.

The Liar paradox. “This sentence is false.” If this quoted sentence is true, then what it says is correct, which means that the sentence is false. Si, d'autre part, the sentence is false, then what it says is correct, which means that the sentence is true. Ainsi, the sentence is true just in case it is false.

Berry’s paradox. There are only finitely many strings of the English alphabet of less than 200 characters. But there are infinitely many natural numbers. Hence there must be a least integer not nameable in less than 200 characters. But we have just named it in less than 200 characters!

Both Poincaré and Russell argued that the paradoxes are caused by some form of vicious circularity. What goes wrong, they claimed, is that an entity is defined, or a proposition is formulated, in a way that is unacceptably circular. Sometimes this circularity is transparent, as in the Liar paradox. But in other paradoxes there is no explicit circularity. Par exemple, the definition of the Russell class makes no explicit reference to the class being defined. Nor does the definition in Berry’s paradox make any explicit reference to itself.

Toutefois, Poincaré and Russell argued that paradoxes such as Russell’s and Berry’s are guilty of an implicit form of circularity. The problem with the Russell class is said to be that its definition generalizes over a totality to which the defined class would belong. This is because the Russell class is defined as the class whose members are all and only the non-self-membered objects. So one of the objects that needs to be considered for membership in the Russell class is this very class itself. De la même manière, the definition in Berry’s paradox generalizes over all definitions, including the very definition in question.

Poincaré’s and Russell’s diagnosis is very general. Whenever we generalize over a totality, we presuppose all the entities that make up this totality. So when we attempt to define an entity by generalizing over a totality to which this entity would belong, we are tacitly presupposing the entity we are trying to define. And this, they claim, involves a vicious circle. The solution to the paradoxes is therefore to ban such circles by laying down what Russell calls the Vicious Circle Principle. This principle has received a bewildering variety of formulations. Here are two famous examples (depuis ([Russell 1908], p. 225):

Whatever involves all of a collection must not be one of the collection.

Si, provided a certain collection has a total, it would have members only definable in terms of that total, then the said collection has no total.

In a justly famous analysis, Gödel distinguishes between the following three forms of the Vicious Circle Principle ([Gödel 1944]):

(VCP1) No entity can be defined in terms of a totality to which this entity belongs.

(VCP2) No entity can involve a totality to which this entity belongs.

(VCP3) No entity can presuppose a totality to which this entity belongs.

The clearest of these principles is probably (VCP1). For this principle is simply a ban on impredicative definitions. This principle requires that a definition not generalize over a totality to which the entity defined would belong.

According to Gödel, the other two principles, (VCP2) et (VCP3), are more plausible than the first, if not necessarily convincing. The tenability of these two principles is a fascinating question but beyond the scope of this survey.

For two other introductions to the question of predicativity, voir [Giaquinto 2002] et (a bit more advanced) [Feferman 2005].

2. Impredicativity in Classical Mathematics

Assume Poincaré and Russell are right that impredicative definitions must be banned. What consequences would this ban have? It was soon realized that classical mathematics relies heavily on impredicative definitions. Here are two famous examples. (The examples inevitably involve some mathematics but can be skimmed by less mathematically inclined readers.)

Example 1: Arithmétique

In many approaches to the foundations of mathematics, the property N of being a natural number is defined as follows. An object x has the property N just in case x has every property F which is had by zero and is inherited from any number u to its successor u+1. Or in symbols:

Def-N N(X) ↔ ∀F[F(0) ∧ ∀u(F(tu) → F(u + 1)) → F(X)]

This definition has the nice feature of entailing the principle of mathematical induction, which says that any property F which is had by zero and is inherited from any number u to its successor u+1 is had by every natural number:

∀F{F(0) ∧ ∀u(F(tu) → F(u + 1)) → ∀x(N(X) → F(X))}

Toutefois, Def-N is impredicative because it defines the property N by generalizing over all arithmetical properties, including the one being defined.

Example 2: Analyse

Assume the rational numbers Q have been constructed from sets. Assume we want to go on and construct the real numbers R as lower Dedekind cuts of rationals. C'est, assume we want to represent each real number by an appropriate downward closed set of rationals. An important task will then be to ensure that the Dedekind cuts which we use to represent real numbers have the following property, which plays a key role in many proofs in real analysis:

Least Upper Bound Property. Let X be a non-empty collection of reals with an upper bound. (An upper bound of X is a real number which is larger than any element of X.) Then X has a least upper bound. C'est, X has an upper bound which is smaller than or equal to any other upper bound of X.

The standard proof that the class of Dedekind cuts has the Least Upper Bound Property involves the following definition of a Dedekind cut z, which can be seen to be the least upper bound of some given non-empty set X which has an upper bound:

∀q[q ∈ z ↔ ∃y(y ∈ X ∧ q ∈ y)]

Toutefois, this definition of the Dedekind cut z is impredicative because it generalizes over all Dedekind cuts y.

Responses to impredicativity in classical mathematics

So classical mathematics relies on impredicative definitions. What does this mean for the proposed ban on such definitions? Three different kinds of response have been developed.

Russell and Whitehead’s response in their famous Principia Mathematica was to adopt the Axiom of Reducibility. This axioms says (loosely speaking) that every impredicative definition can be turned into a predicative one. Toutefois, this axioms has struck most people as intolerably ad hoc.
Another response was initiated by Hermann Weyl [Weyl 1918] and has more recently been pursued by Solomon Feferman. (Voir [Feferman 1998] ainsi que [Feferman 2005] for a survey.) This response is to reconstruct as much of classical mathematics as possible in a way that avoids the use of impredicative definitions. Although this approach is hard to carry out and sometimes rather cumbersome, it has turned out that a surprisingly large amount of mathematics—including most of what is needed for the purposes of empirical science—can be reconstructed in a way that is predicative given the natural numbers.
A third response is associated with Gödel. The fact that classical mathematics uses impredicative definitions should, according to Gödel, be considered a refutation of the vicious circle principle and its ban on impredicative definitions rather than the other way round. In Gödel’s words, we should “consider this rather as a proof that the vicious circle principle is false than that classical mathematics is false.” ([Gödel 1944], p. 135)
3. Defenses of Impredicative Definitions

The response of Gödel’s that we have just considered amounts to a pragmatic defense of impredicative definitions. Since classical mathematics is a scientifically respectable discipline, we have good reason to believe that its core forms of definition are legitimate, including many impredicative ones. But although this pragmatic defense of impredicative definitions has significant force, it would be useful to know why such definitions are legitimate despite their apparent circularity. We will now consider some attempted answers to this question, including one due to Gödel himself.

Our journey begins with Frank Ramsey’s “Foundations of Mathematics” ([Ramsey 1931]), written in 1925 when he was merely 22 years old. Ramsey provides some examples of impredicative definitions which appear to be entirely unproblematic:

(5) Let Julius be tallest person in the room.

(6) Let f(p,q) be the truth-function which is the conjunction of p, q, p v q, and p ∧ q.

(A truth-function is a function from truth-values to truth-values.) These definitions are impredicative because (5) generalizes over all people in the room, including Julius (whoever he or she turns out to be) and because (6) defines the truth-function f(p,q) by generalizing over the four listed truth-functions, one of which is easily seen to be identical to f(p,q), namely p ∧ q.

Ramsey is surely right that these two definitions are harmless. But why is that so? Ramsey isn’t entirely explicit here. His core idea appears to be that an impredicative definition is permissible provided the entity defined can at least in principle be specified or characterized independently of the totality in terms of which it is defined. En effet, Julius (whoever he or she may be) can be specified by pointing to a person, and f(p,q), by means of a truth tables.

This theme of independent specifiability is developed further in an influential article by Paul Bernays, [Bernays 1935]. Bernays is particularly interested in our conception of sets, qui, he argues, does not require all sets to be explicitly definable. Consider first the case of a finite set, say a set S with n elements. By means of what Bernays calls “combinatorial reasoning”—that is, reasoning based on the grouping and selecting objects—we establish that S has 2n subsets. We establish this by observing that all the different subsets of S correspond to all the different ways of making an independent choice as to whether each element of S is to be included in some given subset. There is no need to define all the subsets explicitly.

Much the same goes for infinite sets, according to Bernays. Our conception of infinite sets is “quasi-combinatorial” in the sense that it is based on an analogy with the combinatorial conception of finite sets. Par exemple, this enables us to establish that the number of subsets of the set N of natural numbers is 2ω, where ω is the cardinality or size of N. Note that this fact is established without any need to provide an explicit definition of all the subsets.

The quasi-combinatorial conception of sets ensures that sets can, du moins en principe, be specified independently of their definitions. And this in turn ensures that impredicative definitions of sets are permissible. This is because sets do not depend on their explicit definitions, si seulement, but rather are tied to their quasi-combinatorial specifications.

Gödel also provides a philosophical defense of impredicative definitions, which supplements his pragmatic defense mentioned above. This philosophical defense has been very influential and is the source of what is probably the dominant contemporary view on the matter. According to Gödel, impredicative definitions are indeed problematic if one believes that mathematical objects are in some sense constructed by us. Pour:

the construction of a thing can certainly not be based on a totality of things to which the thing to be constructed belongs. ([Gödel 1944], p. 136)

But there is no such problem if instead one holds a realist view of mathematical objects:

Si, cependant, it is a question of objects that exist independently of our constructions, there is nothing in the least absurd in the existence of totalities containing members which can be described […] only by reference to this totality. (ibid.)

Gödel’s view is thus that a ban on impredicative definitions is justified if one holds a constructivist view of the entities concerned but not if one holds a realist view.

This means that Gödel’s analysis differs from Ramsey’s and Bernays’. Gödel bases the legitimacy of impredicative definitions on the independent existence of the entities in question, whereas Ramsey and Bernays base it on these entities’ independent specifiability. Which analysis is more plausible? Examples such as (5) are handled well by both analyses. But other examples are handled much better by the Ramsey-Bernay analysis than by Gödel’s. Par exemple, it seems unlikely that one has to be a realist about truth-functions in order to accept the legitimacy of Ramsey’s impredicative definition (6). Dans le même esprit, it seems unlikely that one has to be a realist about fictional characters in order to accept the legitimacy of the following impredicative definition.

(7) Let Julia be the most beautiful character in the story of Cinderella.

Clairement, Julia is identical to Cinderella. And this identification does not require a fictional character to enjoy any real or independent existence.

These considerations suggest that the Ramsey-Bernays analysis has at least as much initial plausibility as Gödel’s. But further investigation will be needed to settle the matter.

4. References and Further Readings
Benacerraf, P. and Putnam, H., éditeurs (1983). Philosophie des mathématiques: Lectures sélectionnées, Cambridge. la presse de l'Universite de Cambridge. Second edition.
Bernays, P. (1935). “On Platonism in Mathematics.” Reprinted in (Benacerraf and Putnam, 1983).
Ewald, O. (1996). From Kant to Hilbert: A Source Book in the Foundations of Mathematics volume 2. Presse universitaire d'Oxford, Oxford.
Feferman, S. (1998). “Weyl Vindicated: Das Kontinuum Seventy Years Laters.” In Feferman’s In the Light of Logic, pages 249-283. Presse universitaire d'Oxford, Oxford.
Feferman, S. (2005). “Predicativity.” In Shapiro, S., éditeur, Oxford Handbook of the Philosophy of Mathematics and Logic, pages 590-624. Presse universitaire d'Oxford, Oxford.
Giaquinto, M. (2002). The Search for Certainty: A Philosophical Account of Foundations of Mathematics. Clarendon, Oxford.
Godel, K. (1944). “Russell’s Mathematical Logic.” In (Benacerraf and Putnam, 1983).
Poincaré, H. (1906). “Les Mathematiques et la Logique.” Revue de Métaphysique et de Morale, 14:294-317. Translated as “Mathematics and Logic, II” in (Ewald, 1996), pp. 1038-1052.
Ramsey, F. (1931). “The Foundations of Mathematics.” In Braithwaite, R., éditeur, The Foundations of Mathematics and Other Essays. Routledge & Paul Kegan, Londres.
Russel, B. (1908). “Mathematical logic as based on a theory of types.” American Journal of Mathematics, 30:222-262.
Weyl, H. (1918). Das Kontinuum. Verlag von Veit & Comp, Leipzig. Translated as The Continuum by S. Pollard and T. Bole, Douvres, 1994.
Informations sur l’auteur

Oystein Linnebo
Messagerie: [email protected]
Birkbeck, University of London
Grande-Bretagne