I can’t figure out why induction is considered an axiom. It seems like it should follow from other axioms.
I did some googling and the answers were all something like “if you don’t assume it, then you can’t prove that all natural numbers can be reached by repeatedly applying S(x) from 0.” But why can’t you just assume that as an axiom, instead of induction?
You could argue that it doesn’t matter because they are equivalent, and that seems to be what people said. But it doesn’t feel like that. I think you could express that in first order logic, but the axiom of induction can’t be expressed in first order logic (according to wikipedia.) And that seems like a huge issue and bothers me.
“if you don’t assume it, then you can’t prove that all natural numbers can be reached by repeatedly applying S(x) from 0.” But why can’t you just assume that as an axiom, instead of induction?
How would you say “repeatedly” in formal language? Would it be something like, ‘every number can be reached by applying the successor operation some number of times’? To the extent we can say that, it already seems included in the definition of addition. But it doesn’t rule out non-standard numbers, because you can reach one of them from zero by applying S(x) a non-standard number of times.
IIRC some of the axioms use recursion so I don’t see why that wouldn’t be allowed. I’m not entirely certain how you would set it up but it doesn’t seem like it should be impossible. That link looks interesting though, perhaps it addresses it.
I can’t figure out why induction is considered an axiom. It seems like it should follow from other axioms.
You can prove that any individual natural number is part of a set by applying S(x) finitely many times, but getting all of them either requires an infinitely long proof (bad) or an axiom.
I think you could express that in first order logic, but the axiom of induction can’t be expressed in first order logic (according to wikipedia.) And that seems like a huge issue and bothers me.
You run into Lowenheim-Skolem. If you could express the axiom of induction in first-order logic, then you’d have a model of arithmetic with k numbers for every infinite cardinal k. That’s the advantage of second-order logic: the original Peano axioms give only one set of natural numbers (up to isomorphism). I believe there are certain formulations that only use first-order logic, but they give weaker results.
I can’t figure out why induction is considered an axiom. It seems like it should follow from other axioms.
I did some googling and the answers were all something like “if you don’t assume it, then you can’t prove that all natural numbers can be reached by repeatedly applying S(x) from 0.” But why can’t you just assume that as an axiom, instead of induction?
You could argue that it doesn’t matter because they are equivalent, and that seems to be what people said. But it doesn’t feel like that. I think you could express that in first order logic, but the axiom of induction can’t be expressed in first order logic (according to wikipedia.) And that seems like a huge issue and bothers me.
How would you say “repeatedly” in formal language? Would it be something like, ‘every number can be reached by applying the successor operation some number of times’? To the extent we can say that, it already seems included in the definition of addition. But it doesn’t rule out non-standard numbers, because you can reach one of them from zero by applying S(x) a non-standard number of times.
IIRC some of the axioms use recursion so I don’t see why that wouldn’t be allowed. I’m not entirely certain how you would set it up but it doesn’t seem like it should be impossible. That link looks interesting though, perhaps it addresses it.
You can prove that any individual natural number is part of a set by applying S(x) finitely many times, but getting all of them either requires an infinitely long proof (bad) or an axiom.
You run into Lowenheim-Skolem. If you could express the axiom of induction in first-order logic, then you’d have a model of arithmetic with k numbers for every infinite cardinal k. That’s the advantage of second-order logic: the original Peano axioms give only one set of natural numbers (up to isomorphism). I believe there are certain formulations that only use first-order logic, but they give weaker results.
It is induction. And no, you can’t express it in first-order logic, for the exact same reason as you can’t with other formulations of induction.