I’m having a hard time parsing what you are trying to say here.
That breaks the single chain; what prohibits the finite loop, or the infinite chain?
A finite loop of size one is prohibited by ∀x (x ≠ S(x)); this is provable from the Peano axioms (and thus holds true in all models of the Peano axioms), a finite loop of size two is prohibited by ∀x (x ≠ S(S(x))); this is provable from the Peano axioms, a finite loop of size three is prohibited by ∀x (x ≠ S(S(S(x)))); this is provable from the Peano axioms, and so on.
I don’t see what property is true of zero and all of its successors that cannot be true of an infinite chain, every member of which is a successor to a different number.
Consider the chains 0, 1, 2, 3, … and 0|, 1|, 2|, 3|, …. Let P(n) be “n is a number without a ‘|’.” This is true for every number in the first chain (“zero and all of its successors”), and not true in the other chain. Thus the set of numbers in either of those two chains is not a model of the Peano axioms. This is exactly what Eliezer said, but I thought it might be helpful for you to see it visually.
Something you should note is that properties are fundamentally extensionally defined in mathematics. So Q(n) := “n is a natural number less than 3” is actually, fundamentally, the collection of numbers {0,1,2}. It does not need a description. Math is structurally based. The names we give numbers and properties don’t matter; it is the relationships between them that we care about. So if we define the same rules about the “magically change” operation and the starting number “fairy” that we do about the “successor” operation and the starting number “zero” in the Peano axioms, you are referring to the same structure. Read the beginning of Truly Part of You.
As for the proof of this fact, it’s unfortunately not trivial. A mathematical logic professor at your local college could probably explain it to you. Also, see this page. The proof is incomplete, but you could check the reference there, if you’re curious.
I would also ask if it is any different to make the change “IFF two numbers have the same successor, they are the same number.”
“Only if two numbers have the same successor are they the same number.” This is a tautology in logic. If two numbers are really the same, everything about them must be the same, including their successors (and it is kind of wrong to say “two” in the first place). The other direction of implication is non-trivial, and thus it must be included in the Peano axioms.
The integers with that ordering are not a model of the Peano axioms! (By the way, the integers can be well-ordered: 0, −1, 1, −2, 2, …)
Read the Wikipedia article on the Peano axioms up through the first paragraph in the models section. Do you disagree with the article’s statement that “Any two models of the Peano axioms are isomorphic.”? If so, why? It has been proven by at least Richard Dedekind and Seth Warner; it also seems intuitively true to me. Given that, I’d need strong evidence to change my position.
If you don’t disagree with that, what is it, specifically, that Eliezer said in this post that you disagree with? I had a lot of trouble understanding your original top-level comment, but it seemed like you had a contrarian tone. If I misinterpreted your original comment, forgive me; I have no criticism of it except for that it was not clearly worded. But I think Eliezer’s post was very well-written and useful.
Specifically: I don’t think that the listed constraints are sufficient to uniquely describe exactly the set natural numbers. If the property ‘Is either zero or in the succession chain of zero’ is allowed as a property of a number, then the roundabout description “every property true at 0, and for which P(Sx) is true whenever P(x) is true, is true of all numbers” is logically identical with “There are no chains that do not start with zero.”
Why not simply state that directly as part of your definition, since it is the intent? It can even be done in first-order logic with a little bit of work somewhat above my level.
EDIT: I hadn’t considered that every finite and countably infinite set could be well-ordered by fiat. It seems counterintuitive that any number could be defined to be the least element, but there’s nothing in definition of well-ordered that prevents selecting an arbitrary least element.
I think we’re in agreement with each other. The integers are not well-ordered by ‘<’ as ‘<’ is traditionally interpreted; they are well-ordered by other, different relations (that can be formalized in logic); see the Wikipedia article on well-ordering.
The reason that we don’t start out with “There are no chains that do not start with zero.” is, I speculate, at least two-fold:
In Peano’s original axioms, he used the other formulation. So there is a precedent.
Peano’s formulation can be expressed easily in first-order Peano arithmetic. Peano’s formulation describes what is going on within the system; whereas “there are no chains that do not start with zero” is discussing the structure of the system from the outside. They do come out equivalent (I think) in second-order logic, but Peano’s formulation is the one that is easily expressed in first-order logic.
“All natural numbers can be generated by iterating the successor function on zero.”
“The smallest set k which includes zero and the successor of every member of itself is the set of natural numbers.”
I think that both of those formulations can be phrased in first-order logic...
Properties are sets of numbers, so without getting into technicalities, you need second-order logic to talk about the smallest set such that whatever (since you need to quantify over all candidate sets).
Similarly, to say that you can get x by iterating the successor function on zero requires second-order logic. First-order logic isn’t even sufficient to define addition without adding axioms for what addition does.
If you use set theory, then yes. Usually, however, mathematicians don’t want to have to worry about things like the axiom of regularity when all they wanted to talk about in the first place was the natural numbers!
You can’t talk about what the natural numbers are and are not without some form of set theory.
But you can talk about some of the properties they have, and quite often that is all we care about.
Also, the stronger your system is, the more likely it is that your formulation is inconsistent (and if the system is inconsistent, you’re definitely not describing anything meaningful). I’m much more confident that first-order Peano arithmetic is consistent than I am that first-order ZFC set theory is consistent.
Enjoy A Problem Course in Mathematical Logic. Read Definition 6.4, Definition 6.5, and Definition 6.6 (Edit: They are on PDF pages 47-50, book pages 35-38.). It means that, within each model of the axioms, it is the case that every object in the model has the specified property. The natural numbers happen to be a model of first-order Peano arithmetic.
Let me ask you what “every x” means in first-order ZFC set theory. Answer carefully—it has a countable model.
I’m having a hard time parsing what you are trying to say here.
A finite loop of size one is prohibited by ∀x (x ≠ S(x)); this is provable from the Peano axioms (and thus holds true in all models of the Peano axioms), a finite loop of size two is prohibited by ∀x (x ≠ S(S(x))); this is provable from the Peano axioms, a finite loop of size three is prohibited by ∀x (x ≠ S(S(S(x)))); this is provable from the Peano axioms, and so on.
Consider the chains 0, 1, 2, 3, … and 0|, 1|, 2|, 3|, …. Let P(n) be “n is a number without a ‘|’.” This is true for every number in the first chain (“zero and all of its successors”), and not true in the other chain. Thus the set of numbers in either of those two chains is not a model of the Peano axioms. This is exactly what Eliezer said, but I thought it might be helpful for you to see it visually.
Something you should note is that properties are fundamentally extensionally defined in mathematics. So Q(n) := “n is a natural number less than 3” is actually, fundamentally, the collection of numbers {0,1,2}. It does not need a description. Math is structurally based. The names we give numbers and properties don’t matter; it is the relationships between them that we care about. So if we define the same rules about the “magically change” operation and the starting number “fairy” that we do about the “successor” operation and the starting number “zero” in the Peano axioms, you are referring to the same structure. Read the beginning of Truly Part of You.
As for the proof of this fact, it’s unfortunately not trivial. A mathematical logic professor at your local college could probably explain it to you. Also, see this page. The proof is incomplete, but you could check the reference there, if you’re curious.
“Only if two numbers have the same successor are they the same number.” This is a tautology in logic. If two numbers are really the same, everything about them must be the same, including their successors (and it is kind of wrong to say “two” in the first place). The other direction of implication is non-trivial, and thus it must be included in the Peano axioms.
That proof only applies to well ordered sets. The set [… -a, o, a, …] has no least element, and is therefore not well ordered.
The integers with that ordering are not a model of the Peano axioms! (By the way, the integers can be well-ordered: 0, −1, 1, −2, 2, …)
Read the Wikipedia article on the Peano axioms up through the first paragraph in the models section. Do you disagree with the article’s statement that “Any two models of the Peano axioms are isomorphic.”? If so, why? It has been proven by at least Richard Dedekind and Seth Warner; it also seems intuitively true to me. Given that, I’d need strong evidence to change my position.
If you don’t disagree with that, what is it, specifically, that Eliezer said in this post that you disagree with? I had a lot of trouble understanding your original top-level comment, but it seemed like you had a contrarian tone. If I misinterpreted your original comment, forgive me; I have no criticism of it except for that it was not clearly worded. But I think Eliezer’s post was very well-written and useful.
Specifically: I don’t think that the listed constraints are sufficient to uniquely describe exactly the set natural numbers. If the property ‘Is either zero or in the succession chain of zero’ is allowed as a property of a number, then the roundabout description “every property true at 0, and for which P(Sx) is true whenever P(x) is true, is true of all numbers” is logically identical with “There are no chains that do not start with zero.”
Why not simply state that directly as part of your definition, since it is the intent? It can even be done in first-order logic with a little bit of work somewhat above my level.
EDIT: I hadn’t considered that every finite and countably infinite set could be well-ordered by fiat. It seems counterintuitive that any number could be defined to be the least element, but there’s nothing in definition of well-ordered that prevents selecting an arbitrary least element.
I think we’re in agreement with each other. The integers are not well-ordered by ‘<’ as ‘<’ is traditionally interpreted; they are well-ordered by other, different relations (that can be formalized in logic); see the Wikipedia article on well-ordering.
The reason that we don’t start out with “There are no chains that do not start with zero.” is, I speculate, at least two-fold:
In Peano’s original axioms, he used the other formulation. So there is a precedent.
Peano’s formulation can be expressed easily in first-order Peano arithmetic. Peano’s formulation describes what is going on within the system; whereas “there are no chains that do not start with zero” is discussing the structure of the system from the outside. They do come out equivalent (I think) in second-order logic, but Peano’s formulation is the one that is easily expressed in first-order logic.
“All natural numbers can be generated by iterating the successor function on zero.” “The smallest set k which includes zero and the successor of every member of itself is the set of natural numbers.”
I think that both of those formulations can be phrased in first-order logic...
Properties are sets of numbers, so without getting into technicalities, you need second-order logic to talk about the smallest set such that whatever (since you need to quantify over all candidate sets).
Similarly, to say that you can get x by iterating the successor function on zero requires second-order logic. First-order logic isn’t even sufficient to define addition without adding axioms for what addition does.
If you use set theory, then yes. Usually, however, mathematicians don’t want to have to worry about things like the axiom of regularity when all they wanted to talk about in the first place was the natural numbers!
You can’t talk about what the natural numbers are and are not without some form of set theory.
“0 is the only number which is not the successor of any number” requires set theory to be meaningful.
But you can talk about some of the properties they have, and quite often that is all we care about.
Also, the stronger your system is, the more likely it is that your formulation is inconsistent (and if the system is inconsistent, you’re definitely not describing anything meaningful). I’m much more confident that first-order Peano arithmetic is consistent than I am that first-order ZFC set theory is consistent.
No. You can rephrase that as: “Every natural number is either 0 or the successor of some number”.
What does “Every x” mean in the absence of set theory?
Enjoy A Problem Course in Mathematical Logic. Read Definition 6.4, Definition 6.5, and Definition 6.6 (Edit: They are on PDF pages 47-50, book pages 35-38.). It means that, within each model of the axioms, it is the case that every object in the model has the specified property. The natural numbers happen to be a model of first-order Peano arithmetic.
Let me ask you what “every x” means in first-order ZFC set theory. Answer carefully—it has a countable model.