4
$\begingroup$

I'm looking to know the difference between the concepts of impredicativity and recursion.

For impredicativity, I've got this defintion from wikipedia:

Something that is impredicative, in mathematics and logic, is a self-referencing definition.

And this one for recursion:

Recursion occurs when a thing is defined in terms of itself or of its type.

Even after reading these articles I don't get the subtlety here.

In what are they different?

Thank you

$\endgroup$
3
6
$\begingroup$

Maybe the moral is: don't always believe the first thing you read on Wikipedia??? [Actually, a lot of the more detailed explanations of mathematical topics on Wikipedia can be pretty good: but sometimes, as here, the thumbnail summary sketches can be misleading or worse.]

So: a better thumbnail definition of impredicativity would be along the following lines

A definition of an object $X$ is impredicative if it quantifies over a collection $Y$ to which $X$ itself belongs.

Some impredicative definitions seem fine -- e.g. "the tallest man in the room" picks out an object by a quantification over men in the room, including the tallest one. Other impredicative definitions look more problematic. A famous troublesome case is the Russell set -- which we try to define by quantifying over all sets including, supposedly, the Russell set itself.

And a better thumbnail definition of recursion might say something like this

A recursive procedure or function is one that can call the results of its own previous application.

So for example, we define the exponeniation function over the naturals recursively in terms of a prior application of the same function as when we write $x^{y + 1} = x^y * x$. We define the well-formed formulae of a formal language by clauses like 'if $\alpha$ is a wff, so is $\neg\alpha$', so the wff-forming procedure can call the outputs of previous rounds of wff-formation.

We can now see these are very different ideas. Defining a class of widgets by recursion involves thinking of it as built up, stage by stage, by repeated application of some procedure (where we can feed back the results of earlier applications into another application of the procedure). It is the very paradigm of a constructive idea: we go, by recursive steps, to the constructed class. On the other hand, picking out $X$ from a totality of widgets by an impredicative definition goes in the opposite direction, we go from the totality to one of its members -- we have to think of the widgets as already somehow given to us, and then we then pick out $X$ by reference to that totality, and that might be very non-constructive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.