In article <email@example.com>, John Baez <firstname.lastname@example.org> wrote: >I'd love to hear a bit more of the story, especially if you can tell >it in a charming and not too rigorous manner. In particular, nothing >in the paragraph says what's special about Gamma_0. For example, >suppose I have an ordinal smaller than Gamma_0. How can I give a >"predicative" proof of induction up to that ordinal? What breaks >down at Gamma_0?
To get induction up to some ordinal, one first needs to introduce ordinal notations to speak of the ordinals. The first technical hitch is that proving that your ordinal notation system "makes sense" (i.e., has all the self-consistency and uniqueness properties that you want) can in principle involve an arbitrary amount of arithmetical knowledge. If you're starting with only PA and the notion of the set of integers, then this puts an upper bound on how much arithmetical knowledge of this type you're allowed to assume, and hence an upper bound on the ordinals you have a right to work with.
The second hitch is that if you're a predicativist, then you're not going to allow quantification over arbitrary sets but only over the set of integers and sets that you've already defined. This puts another restriction on how far your induction can proceed.
Putting these restrictions together gets you up to Gamma_0. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences