[FOM] Predicativity in CZF: Correction

William Tait williamtait at mac.com
Wed Jun 18 10:49:48 EDT 2008

On Jun 16, 2008 I mistakenly wrote:

> On Jun 15, 2008, at 12:32 PM, Nik Weaver wrote:
>> But look what happens.  Let's say we want to inductively
>> define a class A satisfying some closure conditions.  We
>> tell the predicativist to build A up in a series of
>> well-ordered stages.  Then he has to prove that A is
>> minimal, i.e., it is contained in any other class B that
>> satisfies the same closure conditions.
>> Well, since A is built up in well-ordered stages we'll
>> prove this by induction.  Let S be the set of stages at
>> which elements of A appear that do not belong to B.  If
>> S is nonempty then it has a least element and we can now
>> get a contradiction from the fact that B satisfies the
>> closure conditions which define A.  But wait a minute.
>> Was S a predicatively legitimate set?
> Nik, This cannot be quite the right way to think about inductive
> definitions constructively. The simplest example (it was Brouwer's) of
> a non-elementary inductively defined set for a constructivist IS the
> constructive second number class A=O. In this case, S=A.

I have just reread what Nic Weaver wrote and my response and realized  
that I had mis-read his definition of S. But it remains true that this  
is not the way to understand inductive definitions constructively.   
For the argument shows only that S is not-not-empty, which does not  
imply constructively that it is empty.

I remain happy with the remainder of what I wrote.

Bill Tait

More information about the FOM mailing list