“Because if you had another separated chain, you could have a property P that was true all along the 0-chain, but false along the separated chain. And then P would be true of 0, true of the successor of any number of which it was true, and not true of all numbers.”
But the axiom schema of induction does not completely exclude nonstandard numbers. Sure if I prove some property P for P(0) and for all n, P(n) ⇒ P(n+1) then for all n, P(n); then I have excluded the possibility of some nonstandard number “n” for which not P(n) but there are some properties which cannot be proved true or false in Peano Arithmetic and therefore whose truth hood can be altered by the presence of nonstandard numbers.
Can you give me a property P which is true along the zero-chain but necessarily false along a separated chain that is infinitely long in both directions? I do not believe this is possible but I may be mistaken.
Can you give me a property P which is true along the zero-chain but necessarily false along a separated chain that is infinitely long in both directions?
Pn(x) is “x is the nth successor of 0” (the 0th successor of a number is itself).
P(x) is “there exists some n such that Pn(x)”.
But any nonstandard number is not an nth successor of 0 for any n, even nonstandard n (whatever that would mean). So your rephrasing doesn’t mean the same thing, intuitively—P is, intuitively, “x is reachable from 0 using the successor function”.
Couldn’t you say:
P0: x = 0
PS0: x = S0
PSS0: x = SS0
and so on, defining a set of properties (we can construct these inductively, and so there is no Pn for nonstandard n), and say P(x) is “x satisfies one such property”?
Not sure if I understand the point of your argument.
Are you saying that in reality every property P has actually three outcomes: true, false, undecidable? And that those always decidable, like e.g. “P(n) <-> (n = 2)” cannot be true for all natural numbers, while those which can be true for all natural numbers, but mostly false otherwise, are always undecidable for… some other values?
Can you give me a property P which is true along the zero-chain but necessarily false along a separated chain that is infinitely long in both directions? I do not believe this is possible but I may be mistaken.
I don’t know.
Let’s suppose that for any specific value V in the separated chain it is possible to make such property PV. For example “PV(x) <-> (x <> V)”. And let’s suppose that it is not possible to make one such property for all values in all separated chains, except by saying something like “P(x) <-> there is no such PV which would be true for all numbers in the first chain and false for x”.
What would that prove? Would it contradict the article? How specifically?
Are you saying that in reality every property P has actually three outcomes: true, false, undecidable?
By Godel’s incompleteness theorem yes, unless your theory of arithmetic has a non-recursively enumerable set of axioms or is inconsistent.
And that those always decidable, like e.g. “P(n) <-> (n = 2)” cannot be true for all natural numbers, while those which can be true for all natural numbers, but mostly false otherwise, are always undecidable for… some other values?
I’m having trouble understanding this sentence but I think I know what you are asking about.
There are some properties P(x) which are true for every x in the 0 chain, however, Peano Arithmetic does not include all these P(x) as theorems. If PA doesn’t include P(x) as a theorem, then it is independent of PA whether there exist nonstandard elements for which P(x) is false.
Let’s suppose that for any specific value V in the separated chain it is possible to make such property PV.
What would that prove? Would it contradict the article? How specifically?
I think this is what I am saying I believe to be impossible. You can’t just say “V is in the separated chain”. V is a constant symbol. The model can assign constants to whatever object in the domain of discourse it wants to unless you add axioms forbidding it.
Honestly I am becoming confused. I’m going to take a break and think about all this for a bit.
If our axiom set T is independent of a property P about numbers then by definition there is nothing inconsistent about the theory T1 = “T and P” and also nothing inconsistent about the theory T2= “T and not P”.
To say that they are not inconsistent is to say that they are satisfiable, that they have possible models. As T1 and T2 are inconsistent with each other, their models are different.
The single zero-based chain of numbers without nonstandard numbers is a single model. Therefore, if there exists a property about numbers that is independent of any theory of arithmetic, that theory of arithmetic does not logically exclude the possibility of nonstandard elements.
By Godel’s incompleteness theorems, a theory must have statements that are independent from it unless it is either inconsistent or has a non-recursively-enumerable theorem set.
Each instance of the axiom schema of induction can be constructed from a property. The set of properties is recursively enumerable, therefore the set of instances of the axiom schema of induction is recursively enumerable.
Every theorem of Peano Arithmetic must use a finite number of axioms in its proof. We can enumerate the theorems of Peano Arithmetic by adding increasingly larger subsets of the infinite set of instances of the axiom schema of induction to our axiom set.
Since the theory of Peano Arithmetic has a recursively enumerable set of theorems it is either inconsistent or is independent of some property and thus allows for the existence of nonstandard elements.
I don’t see what the difference is… They look very similar to me.
At some point you have to translate it into a (possibly infinite) set of first-order axioms or you wont be able to perform first-order resolution anyway.
Can you give me a property P which is true along the zero-chain but necessarily false along a separated chain that is infinitely long in both directions? I do not believe this is possible but I may be mistaken.
For any number n, n-n=0.
If you have a separate chain that isn’t connected to zero, then this isn’t true.
However this statement is pretty simple and can be expressed in first order logic. I have no idea why EY believes that it requires second order logic to eliminate the possibility of other chains that aren’t derived from zero.
But the axiom schema of induction does not completely exclude nonstandard numbers. Sure if I prove some property P for P(0) and for all n, P(n) ⇒ P(n+1) then for all n, P(n); then I have excluded the possibility of some nonstandard number “n” for which not P(n) but there are some properties which cannot be proved true or false in Peano Arithmetic and therefore whose truth hood can be altered by the presence of nonstandard numbers.
Can you give me a property P which is true along the zero-chain but necessarily false along a separated chain that is infinitely long in both directions? I do not believe this is possible but I may be mistaken.
Pn(x) is “x is the nth successor of 0” (the 0th successor of a number is itself). P(x) is “there exists some n such that Pn(x)”.
I don’t see how you would define Pn(x) in the language of PA.
Let’s say we used something like this:
Let’s look at the definition of +, a function symbol that our model is allowed to define:
“x + 0 = x” should work perfectly fine for nonstandard numbers.
So going back to P(x):
“there exists some n such that ((0 + n) = x)”
for a nonstandard number x, does there exist some number n such that ((0+n) = x)? Yup, the nonstandard number x! Set n=x.
Oh, but when you said nth successor you meant n had to be standard? Well, that’s the whole problem isn’t it!
But any nonstandard number is not an nth successor of 0 for any n, even nonstandard n (whatever that would mean). So your rephrasing doesn’t mean the same thing, intuitively—P is, intuitively, “x is reachable from 0 using the successor function”.
Couldn’t you say:
P0: x = 0
PS0: x = S0
PSS0: x = SS0
and so on, defining a set of properties (we can construct these inductively, and so there is no Pn for nonstandard n), and say P(x) is “x satisfies one such property”?
An infinite number of axioms like in an axiom schema doesn’t really hurt anything, but you can’t have infinitely long single axioms.
is not an option. And neither is the axiom set
We could instead try the axioms
but then again we have the problem of n being a nonstandard number.
What is n?
It’s non-strictly-mathematical shorthand for this.
Not sure if I understand the point of your argument.
Are you saying that in reality every property P has actually three outcomes: true, false, undecidable? And that those always decidable, like e.g. “P(n) <-> (n = 2)” cannot be true for all natural numbers, while those which can be true for all natural numbers, but mostly false otherwise, are always undecidable for… some other values?
I don’t know.
Let’s suppose that for any specific value V in the separated chain it is possible to make such property PV. For example “PV(x) <-> (x <> V)”. And let’s suppose that it is not possible to make one such property for all values in all separated chains, except by saying something like “P(x) <-> there is no such PV which would be true for all numbers in the first chain and false for x”.
What would that prove? Would it contradict the article? How specifically?
By Godel’s incompleteness theorem yes, unless your theory of arithmetic has a non-recursively enumerable set of axioms or is inconsistent.
I’m having trouble understanding this sentence but I think I know what you are asking about.
There are some properties P(x) which are true for every x in the 0 chain, however, Peano Arithmetic does not include all these P(x) as theorems. If PA doesn’t include P(x) as a theorem, then it is independent of PA whether there exist nonstandard elements for which P(x) is false.
I think this is what I am saying I believe to be impossible. You can’t just say “V is in the separated chain”. V is a constant symbol. The model can assign constants to whatever object in the domain of discourse it wants to unless you add axioms forbidding it.
Honestly I am becoming confused. I’m going to take a break and think about all this for a bit.
If our axiom set T is independent of a property P about numbers then by definition there is nothing inconsistent about the theory T1 = “T and P” and also nothing inconsistent about the theory T2= “T and not P”.
To say that they are not inconsistent is to say that they are satisfiable, that they have possible models. As T1 and T2 are inconsistent with each other, their models are different.
The single zero-based chain of numbers without nonstandard numbers is a single model. Therefore, if there exists a property about numbers that is independent of any theory of arithmetic, that theory of arithmetic does not logically exclude the possibility of nonstandard elements.
By Godel’s incompleteness theorems, a theory must have statements that are independent from it unless it is either inconsistent or has a non-recursively-enumerable theorem set.
Each instance of the axiom schema of induction can be constructed from a property. The set of properties is recursively enumerable, therefore the set of instances of the axiom schema of induction is recursively enumerable.
Every theorem of Peano Arithmetic must use a finite number of axioms in its proof. We can enumerate the theorems of Peano Arithmetic by adding increasingly larger subsets of the infinite set of instances of the axiom schema of induction to our axiom set.
Since the theory of Peano Arithmetic has a recursively enumerable set of theorems it is either inconsistent or is independent of some property and thus allows for the existence of nonstandard elements.
Eliezer isn’t using an axiom schema, he’s using an axiom of second order logic.
I don’t see what the difference is… They look very similar to me.
At some point you have to translate it into a (possibly infinite) set of first-order axioms or you wont be able to perform first-order resolution anyway.
What’s wrong with second order resolution?
There’s no complete deductive system for second-order logic.
For any number n, n-n=0.
If you have a separate chain that isn’t connected to zero, then this isn’t true.
However this statement is pretty simple and can be expressed in first order logic. I have no idea why EY believes that it requires second order logic to eliminate the possibility of other chains that aren’t derived from zero.