4 ms·

Author here :-) There's two layers to it, and you've described the first one. The argument you give about tuples of non-negative integers is what implies the c

Author here :-) There's two layers to it, and you've described the first one. The argument you give about tuples of non-negative integers is what implies the consistency of PRA or Primitive Recursive Arithmetic (roughly: the finitary, computable part of arithmetic). This argument is done in a system that is the weakest that Gödel's theorem applies to, but you really have to start assuming a small amount of consistency somewhere. With consistency of PRA under your belt, you can then trust the proof that induction over the set of finite trees implies the consistency of Peano Arithmetic, which is done in PRA. At that point you then need to make a second leap intuitive, non-formal argument for being able to do induction over the set of finite trees (there is a canonical ordering on these). So no only does one have to worry about height induction, but also induction over width at each level of the trees, so it's genuinely more complicated. Chow gives an argument (to which I link) in terms of Turing machines outputting descending sequences of trees as to why you should think this reasonable. So it's all very interesting.

btilly 7y ago
What is the canonical ordering on the set of trees? Given how quickly the Goodstein sequence explodes, the "finite" in these cases may be very, very large...
- highergeometer 7y ago
  "An order on the set of finite rooted trees is defined recursively: we first order the subtrees joined to the root in decreasing order, and then use lexicographic order on these ordered sequences of subtrees. In this way the set of all finite rooted trees becomes a well-ordered set which is order-isomorphic to ε0." (https://en.wikipedia.org/wiki/Epsilon_numbers_(mathematics)#Representation_of_'%22%60UNIQ--postMath-00000028-QINU%60%22'_by_rooted_trees https://en.wikipedia.org/wiki/Epsilon_numbers_(mathematics)#...) and yes, growth rates of fast-growing functions are an important facet of this analysis. EDIT: you should think of a rooted tree as coding an ordinal written in Cantor normal form (https://en.wikipedia.org/wiki/Ordinal_arithmetic#Cantor_normal_form https://en.wikipedia.org/wiki/Ordinal_arithmetic#Cantor_norm...) using only ordinals less than or equal to omega. In fact, here's a nice thesis that sets it out: https://folk.uio.no/alfredb/Masteroppgave%20Alfred%20Bratterud%20v2.pdf https://folk.uio.no/alfredb/Masteroppgave%20Alfred%20Bratter...

btilly 7y ago

What is the canonical ordering on the set of trees? Given how quickly the Goodstein sequence explodes, the "finite" in these cases may be very, very large...

highergeometer 7y ago
"An order on the set of finite rooted trees is defined recursively: we first order the subtrees joined to the root in decreasing order, and then use lexicographic order on these ordered sequences of subtrees. In this way the set of all finite rooted trees becomes a well-ordered set which is order-isomorphic to ε0." (https://en.wikipedia.org/wiki/Epsilon_numbers_(mathematics)#Representation_of_'%22%60UNIQ--postMath-00000028-QINU%60%22'_by_rooted_trees https://en.wikipedia.org/wiki/Epsilon_numbers_(mathematics)#...) and yes, growth rates of fast-growing functions are an important facet of this analysis. EDIT: you should think of a rooted tree as coding an ordinal written in Cantor normal form (https://en.wikipedia.org/wiki/Ordinal_arithmetic#Cantor_normal_form https://en.wikipedia.org/wiki/Ordinal_arithmetic#Cantor_norm...) using only ordinals less than or equal to omega. In fact, here's a nice thesis that sets it out: https://folk.uio.no/alfredb/Masteroppgave%20Alfred%20Bratterud%20v2.pdf https://folk.uio.no/alfredb/Masteroppgave%20Alfred%20Bratter...