Hi, I met several times the expressions "predicative definition" and "unpredicative definiton" in texts about logic. What these expressions do mean ? I precise I'm a french student, thanks for your help.
Asked
Active
Viewed 968 times
3 Answers
14
A definition of an object X is called impredicative if it quantifies over a collection Y to which X itself belongs (or at least could belong). The classic example is the set occurring in Russell's paradox, defined by "the members of X are all sets s that are not members of themselves". This quantifies over all sets, including X itself.
But impredicative definitions occur (without paradox) in ordinary mathematics also. For example, one might define a real number r as the supremum of a set A that might have r itself among its members. Unraveling the definition of "supremum" we would find quantification over A (and indeed quantification over the set of all real numbers).
Russell proposed to eliminate the set-theoretic and logical paradoxes by eliminating impredicative definitions, and "Principia Mathematica" (by Russell and Whitehead) develops an elaborate mechanism for this. Unfortunately, too much of ordinary mathematics was unprovable in that system, so Russell and Whitehead found it necessary to add the so-called axiom of reducibility, whose principal effect is to counteract the predicativity-enforcing mechanism and make impredicative mathematics available again.
Andreas Blass
- 72,290
-
The supremum and Russell's paradox seem classical examples. I wonder about the definition of the identity element in GroupTheory. It is an element e for which ex = xe = x for all x. Since in this definition there is a quantification over all elements x, including e itself, is it not also an example of an impredicative definition? In which case, is there some reason why this example would be less important, or at least less referred to, than the others? – Tommy R. Jensen Oct 20 '19 at 22:33
-
Another instance that I wonder about is when Nelson in his 1986 pamphlet "predicative Arithmetic" states that "the principle of induction" is impredicative. How can induction fall into the scope of having an impredicative definition, given that "induction" is not a mathematical object? – Tommy R. Jensen Oct 20 '19 at 22:41
-
@TommyR.Jensen The identity element of a group admits an alternative definition, as the only element satisfying xx=x, so one can avoid impredicativity there. As for induction, I don't claim to understand Nelson's work, but he might have been referring to the usual set-theoretic definition of $\mathbb N$ as the intersection of all sets that contain $0$ and are closed under successor. That definition, which implies the induction principle, is impredicative because $\mathbb N$ itself is a set that contains $0$ and is closed under successor. – Andreas Blass Oct 21 '19 at 03:13
-
I would think that definition of $\mathbb{N}$ is not usual in set-theories like ZF, since it seems to assume a set of all inductive sets, to allow defining their intersection. It sounds similarly bad as the "set of all sets". – Tommy R. Jensen Oct 22 '19 at 11:26
-
1@TommyR.Jensen In ZF, the axiom of infinity says there is an inductive set. Then one defines $\mathbb N$ as the intersection of all inductive subsets of an inductive set $A$, after proving that the resulting $\mathbb N$ is independent of the choice of $A$. – Andreas Blass Oct 22 '19 at 12:09
-
quite, thanks! I still have to wrap my head around how it is that the intersection of the elements of the powerset of $A$ is not a predicative thing. After all, it might turn out to be different from all those subsets. That the intersection is itself inductive must be proven afterwards. By the way, the condition $xx=x$ in a group of linear maps seems to characterize a projection, not just the identity. – Tommy R. Jensen Oct 22 '19 at 13:12
-
@TommyR.Jensen (1) For any inductive set $A$, we have that $\mathbb N$ is an inductive subset of $A$, so it's one of the sets being intersected in the definition of $\mathbb N$. (2) In operator algebras, $xx=x$ characterizes projections, but in groups it characterizes the identity (just multiply both sides of $xx=x$ by $x^{-1}$). – Andreas Blass Oct 22 '19 at 14:03
-
(1) This is true. But at the point in time at which we formulate the axioms, we may not be aware of the theorem that $\mathbb{N}$ is also among the sets being intersected. After all, the theorem is proved from the axioms, and this is one of them. In which case the statement that the definition is impredicative is itself what? Impredicative? – Tommy R. Jensen Oct 22 '19 at 22:23
-
(2) But we cannot state an axiom "x is an identity if xx=x" because it only captures the notion of a projection, which is not what we mean. And if we say "x is an identity if xx=x and for all y, if yy=y, then y=x", then this is also impredicative, because x is one of the possible values for y. – Tommy R. Jensen Oct 22 '19 at 22:24
-
(1) I don't think predicavists would consider "we may not be aware of" the impredicativity of a definition sufficient to make it predicative. They'd require definitions to quantify only over totalities known to not contain the entity being defined. (2) Once we've defined what a group is, we can perfectly well define, in the context of any group, "the identity element is the unique element x that satisfied xx=x." – Andreas Blass Oct 22 '19 at 23:04
-
Behold my predicative definition of $\mathbb{N}$. Call a set $B$ in ZF "super-inductive" if $0\not\in B$ and ${0}\in B,$ and for every $x\in B$ also $x\cup {x}\in B.$ Let $A$ be the inductive set provided by AI. Then $B:=A\setminus {0}$ is super-inductive. Define $\mathbb{N}$ as the union of ${0}$ with the intersection set of all subsets of $B.$ – Tommy R. Jensen Oct 23 '19 at 11:46
-
Let us continue this discussion in chat. – Tommy R. Jensen Oct 23 '19 at 12:18
8
I don't think "predicative" has a generally accepted precise definition, though roughly speaking it refers to definitions of objects that only depend on previously constructed objects. For example, the axiom of replacement in set theory is impredicative because it constructs new sets, but the construction involves quantifying over all sets, including the one you are trying to construct. The Feferman-Schutte ordinal is sometimes said to be the first impredicative ordinal (though I've never really understood why), in which case predicative mathematics consists roughly of theorems that only depend on transfinite induction up to smaller ordinals.
Richard Borcherds
- 20,442
-
If my view of the axioms of ZF is that, whenever I am presented with some given structure, the axioms allow me to decide whether or not the structure is a model of ZF, and all that is needed is to verify or fail to verify them. Is it then not natural that it is hard for me to grasp the meaning of these terms? After all, it is how structures in math are first presented to students. Example: a textbook presents a composition table for $S_3$ and you are required to verify from the axioms that $S_3$ is a group. In particular, nothing seems "constructed". – Tommy R. Jensen Oct 29 '19 at 15:52
