Mathematical Induction and Peano Arithmetic

154 Views Asked by At

Peano Arithmetic cannot employ Induction for any ε0 ordering. My question is too easy to be interesting and there is a reason obviously for why it has a negative answer. Can you please provide it for me? Is there no way to build Induction upon the simple ω order that the towers of ε0 represent as written down? E.g. Prove something for the elements of the first ω at the bottom of the tower. Then assume that all elements up to some ω exponent have the same property, and manage (?) to prove that on this assumption all elements up the next exponent have it as well. Is there anything wrong with this approach in principle? This is a follow up after Andrés' illuminating reply. So, if I've got that right, on the assumption that the Church-Turing thesis is true, there must be no algorithm that represents how the Inductive proofs of some level in the tower behave relative to how they behave at the previous level. Otherwise, it would have being possible to assume that all elements up the nth omega level have the property, and, then, by using the algorithm establish the presence of an Inductive proof for all the elements of level n+1. (Proofs for all finite towers of omegas are assumed to be recursive here.) Thank you Andrés, I think I've got it now. One cannot built/code the entire Σ(n) inductive schema within any of the particular instances of it, and therefore nor within an ω exponent.