[FOM] Gamma_0

Nik Weaver nweaver at math.wustl.edu
Mon Dec 13 13:20:18 EST 2010

Thomas Forster forwarded the comment

> I can see how to prove the existence of wellorders of the naturals
> of all smaller lengths without using power set (or Hartogs'..) but
> it seems to me that i can do the same for Gamma_0 itself.

Is the writer really sure about the first point?  Uncontroversially
predicative systems typically don't get very far beyond \epsilon_0.
The usual error in this kind of claim involves failing to distinguish
between different versions of the concept "well-ordered".

Let's say we have a total ordering < of the natural numbers that we
know is well-ordered: every nonempty subset has a smallest element
for <.  Suppose also that the property P is progressive for <, i.e.,
for every number a we have that [(forall b < a)P(b)] implies P(a).
Can we conclude that P(a) holds for all a?  Yes, we can prove this
by considering the set {a: P(a) is false}.  If this set is nonempty
then it has a smallest element, which contradicts progressivity of <.
Therefore the set must be empty.

*However*, this argument requires some sort of comprehension axiom in
order to form the set {a: P(a) is false}.  If the property P involves
quantification over the power set of the natural numbers, then
predicativists would reject the relevant comprehension axiom and so
would not be able to make the stated inference.

This error is so common, I am willing to bet that the writer has made
an illegitimate inference of this type in his well-ordering proof.

I explain this issue in more detail in Sections 7 and 8 of my paper
"What is predicativism?", and I discuss it at great length throughout
the entire first half of the paper "Predicativity beyond Gamma_0".
Both are available on my website at


Nik Weaver
Math Dept.
Washington University
St. Louis, MO 63130 USA
nweaver at math.wustl.edu

More information about the FOM mailing list