That breaks the single chain; what prohibits the finite loop, or the infinite chain
Consider the infinite set of properties of the form x ≠ Sn(x)… and every finite chain is also broken, through a similar method.
However, 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.
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.”
And why aren’t −1, every predecessors of −1, and every successor of −1 a standard number? Or are we simply using second-order logic to declare in a roundabout way that there is exactly one series of numbers?
Let us postulate a predecessor function: Iff a number x is a successor of another number, then the predecessor of x is the number which has x as a successor. The predecessor function retains every property that is defined to be retained by the successor function. The alternate chain C’ has o: o has EVERY property of 0 (including null properties) except that it is the successor to -a, and the successor to o is a. Those two properties are not true of S(x) given that they are true of x. every successor of o in the chain meets the definition of number; I can’t find a property that is not true of -a and the predecessors of a but that is true for every natural number.
The above basically says that P(k) is “is within the successor chain of 0”. Note that the base case is k = 0, not k = o. Anyway, the point is, since such a property is possible (including only the objects that are some n-successor of 0), the axiom of induction implies that numbers that follow 0 are the only numbers.
ETA: Reading your parent post again, the problem is it’s impossible to have an o that has every property 0 does. As a demonstration, Z(k) := (k = 0) is a valid property. It’s true only of 0. R(k, 0) is similarly a property that is only true of 0, or SS..0.
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 think that this is the sort of case in which it is useful to do some hand-waving to indicate that you’ve realized that your reasoning was wrong but that you have additional reasoning to back up your conclusion, as otherwise it can appear that you’ve realized your reasoning was wrong but want to stick to the conclusion anyway, and therefore need to come up with new reasoning to support it.
Anyway, consider the following: let Pn(x) mean “x is the nth successor of 0” (where the 0th successor of a number is itself). Then, by induction, every number x has the property “there exists some n such that Pn(x)”.
I don’t think that change has an effect, you’re just adding “if two numbers are the same number, they have the same successor”, right? Which is already true.
As I said, the “zeroth successor” of a number is itself. That is, zero is the result of applying the successor function to itself zero times. You have to apply a function at least once in order to have applied the function (and thus obtained a result of applying the function, e.g., calculated a successor).
If you don’t like the term, you can think of it this way:
That breaks the single chain; what prohibits the finite loop, or the infinite chain
Consider the infinite set of properties of the form x ≠ Sn(x)… and every finite chain is also broken, through a similar method.
However, 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.
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.”
Let the property P be, “is a standard number”.
Then P would be true of 0, true along the successor-chain of 0, and false at a separated infinite successor-chain.
Thus P would be a property that was true of 0 and true of the successor of every object of which it was true, yet not true of all numbers.
This would contradict the second-order axiom, so this must not be a model of second-order PA.
And why aren’t −1, every predecessors of −1, and every successor of −1 a standard number? Or are we simply using second-order logic to declare in a roundabout way that there is exactly one series of numbers?
Let us postulate a predecessor function: Iff a number x is a successor of another number, then the predecessor of x is the number which has x as a successor. The predecessor function retains every property that is defined to be retained by the successor function. The alternate chain C’ has o: o has EVERY property of 0 (including null properties) except that it is the successor to -a, and the successor to o is a. Those two properties are not true of S(x) given that they are true of x. every successor of o in the chain meets the definition of number; I can’t find a property that is not true of -a and the predecessors of a but that is true for every natural number.
P(k) := R(k, 0)R(k, n) := (k = n) ∨ R(k, Sn)P(0) and P(k) ⇒ P(Sk) can be easily proved, so
P(k) for all kOr something like that.
In that case, P(o) is true, and P(k)->P(Pk) is equally provable.
No...?
The above basically says that
P(k)is “is within the successor chain of 0”. Note that the base case isk = 0, notk = o. Anyway, the point is, since such a property is possible (including only the objects that are some n-successor of 0), the axiom of induction implies that numbers that follow 0 are the only numbers.ETA: Reading your parent post again, the problem is it’s impossible to have an
othat has every property0does. As a demonstration,Z(k) := (k = 0)is a valid property. It’s true only of0.R(k, 0)is similarly a property that is only true of0, orSS..0.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.
I think that this is the sort of case in which it is useful to do some hand-waving to indicate that you’ve realized that your reasoning was wrong but that you have additional reasoning to back up your conclusion, as otherwise it can appear that you’ve realized your reasoning was wrong but want to stick to the conclusion anyway, and therefore need to come up with new reasoning to support it.
Anyway, consider the following: let Pn(x) mean “x is the nth successor of 0” (where the 0th successor of a number is itself). Then, by induction, every number x has the property “there exists some n such that Pn(x)”.
I don’t think that change has an effect, you’re just adding “if two numbers are the same number, they have the same successor”, right? Which is already true.
Is zero the zeroth successor of zero, by that property? Is that compatible with zero not being a successor of any number?
As I said, the “zeroth successor” of a number is itself. That is, zero is the result of applying the successor function to itself zero times. You have to apply a function at least once in order to have applied the function (and thus obtained a result of applying the function, e.g., calculated a successor).
If you don’t like the term, you can think of it this way:
P0(x): x = 0
P1(x): x = S0
P2(x): x = SS0
and so forth.