< is defined in terms of plus by saying x<y iff there exists a such that y=z+x. + is supposed to be provided as a primitive operation as part of the data consisting of a model of PA. It’s not actually possible to give a concrete description of what + looks like in general for non-standard models because of Tenenbaums’s Theorem, but at least when one of x or y (say x) is a standard number it’s exactly what you’d expect: x+y is what you get by starting at y and going x steps to the right.
To see that x<y whenever x is a standard number and y isn’t, you need to be a little tricky. You actually prove an infinite family of statements. The first one is “for all x, either x=0 or else x>0”. The second is “for all x, either x=0 or x=1 or x>1″, and in general it’s “for all x, either x=0,1,..., or n, or else x>n”. Each of these can be proven by induction, and the entire infinite family together implies that a non-standard number is bigger than every standard number.
I suppose you can’t prove a statement like “No matter how many times you expand this infinite family of axioms, you’ll never encounter a non-standard number” in first-order logic? Should I not think of numbers and non-standard numbers as having different types? Or should I think of > as accepting differently typed things? (where I’m using the definition of “type” from computer science, e.g. “strongly-typed language”)
Sorry I didn’t answer this before; I didn’t see it. To the extent that the analogy applies, you should think of non-standard numbers and standard numbers as having the same type. Specifically, the type of things that are being quantified over in whatever first order logic you are using. And you’re right that you can’t prove that statement in first order logic; Worse, you can’t even say it in first order logic (see the next post, on Godel’s theorems and Compactness/Lowenheim Skolem for why).
Thanks. Hm. I think I see why that can’t be said in first order logic.
...my brain is shouting “if I start at 0 and count up I’ll never reach a nonstandard number, therefore they don’t exist” at me so loudly that it’s very difficult to restrict my thoughts to only first-order ones.
This is largely a matter of keeping track of the distinction between “first order logic: the mathematical construct” and “first order logic: the form of reasoning I sometimes use when thinking about math”. The former is an idealized model of the latter, but they are distinct and belong in distinct mental buckets.
It may help to write a proof checker for first order logic. Or alternatively, if you are able to read higher math, study some mathematical logic/model theory.
In mathematics, a [binary] relation (like >, since it considers two natural numbers and then is either true or false, based on which numbers are considered) is just a set of ordered pairs. Within the standard model of the natural numbers, > is just the [infinite] collection of ordered pairs { (2,1) , (3,1) , (3,2) , (4,1) , (4,2) , (4,3) , … }. So, suppose we have two chains of number-thingies...1, 2, 3,… and 1^, 2^, 3^, …. We can make the ‘>’ rule as follows: ” ‘x > y’ if and only if ‘x has a caret and y does not, or (in this case, both numbers must be in the same chain) x is greater than y within its own chain’ ”. This [infinite] collection of ordered pairs would be { (2,1) , (2^,1^) , (1^,1) , (3^,1^) , (3,2) , (3^,2^) , (3,1) , (4^,1^) , (1^,2) , (4^,2^) , (4,3) , (4^,3^) , … }.
So ‘>’ is a valid relation on two disconnected chains of number-thingies, because we define it to be so by fiat. The numbers we’re working with are nonstandard...so there is no reason to expect that there should be some standard, natural meaning for ‘>’.
Important Note: This explanation of ‘>’ does not correspond to a nonstandard model of first-order Peano arithmetic (and, clearly, not the standard model, either). If you want to know more about that, look to earthwormchuck163′s comment. I thought it might be helpful to you to understand it in a case that’s easier to picture, before jumping to the case of a nonstandard model of first-order Peano arithmetic. That case is even more complex than Eliezer revealed within his post. It would probably be extremely helpful to you to learn about well-orders, order types, and the ordinal numbers to get a handle on this stuff. You are more talented than I if you are able to understand it without that background knowledge.
Hope this helps.
Edit: Annoyingly (in this case), the asterisk causes italicization. Changed asterisks to carets.
Edit 2: Changed “operation” to “relation” everywhere, as per paper-machine’s correct comment.
In mathematics, a [binary] operation (like >, since it considers two natural numbers and then is either true or false, based on which numbers are considered) is just a set of ordered pairs.
Not to nitpick, but “>” is a binary relation, not a binary operation.
This really benefits from a picture. Calling something “a nonstandard number” doesn’t really convey anything about them and a better name I’ll use is “infinitely big”, because they are.
< makes sense because the 2 chains are finite numbers and infinitely big numbers and an infinitely big number is bigger than any finite one because it’s , well, infinite. I can elaborate more technically, but I think trying to develop some numeracy for infinite numbers is a lot like learning about negatives and rationals and complex numbers. Just play with some expressions and get used to them. then look at the more technical treatment even if you have the ability to read it. Someone gave that example with a flat list but I think and feel that tapping into one’s existing NUMBER (and not list) sense is very powerful since it’s the first math we learn and the only one people use every single day.
Can someone explain this? I don’t understand how > can be a valid operation on two disconnected chains of number-thingies.
< is defined in terms of plus by saying x<y iff there exists a such that y=z+x. + is supposed to be provided as a primitive operation as part of the data consisting of a model of PA. It’s not actually possible to give a concrete description of what + looks like in general for non-standard models because of Tenenbaums’s Theorem, but at least when one of x or y (say x) is a standard number it’s exactly what you’d expect: x+y is what you get by starting at y and going x steps to the right.
To see that x<y whenever x is a standard number and y isn’t, you need to be a little tricky. You actually prove an infinite family of statements. The first one is “for all x, either x=0 or else x>0”. The second is “for all x, either x=0 or x=1 or x>1″, and in general it’s “for all x, either x=0,1,..., or n, or else x>n”. Each of these can be proven by induction, and the entire infinite family together implies that a non-standard number is bigger than every standard number.
Thanks!
I suppose you can’t prove a statement like “No matter how many times you expand this infinite family of axioms, you’ll never encounter a non-standard number” in first-order logic? Should I not think of numbers and non-standard numbers as having different types? Or should I think of > as accepting differently typed things? (where I’m using the definition of “type” from computer science, e.g. “strongly-typed language”)
Sorry I didn’t answer this before; I didn’t see it. To the extent that the analogy applies, you should think of non-standard numbers and standard numbers as having the same type. Specifically, the type of things that are being quantified over in whatever first order logic you are using. And you’re right that you can’t prove that statement in first order logic; Worse, you can’t even say it in first order logic (see the next post, on Godel’s theorems and Compactness/Lowenheim Skolem for why).
Thanks. Hm. I think I see why that can’t be said in first order logic.
...my brain is shouting “if I start at 0 and count up I’ll never reach a nonstandard number, therefore they don’t exist” at me so loudly that it’s very difficult to restrict my thoughts to only first-order ones.
This is largely a matter of keeping track of the distinction between “first order logic: the mathematical construct” and “first order logic: the form of reasoning I sometimes use when thinking about math”. The former is an idealized model of the latter, but they are distinct and belong in distinct mental buckets.
It may help to write a proof checker for first order logic. Or alternatively, if you are able to read higher math, study some mathematical logic/model theory.
In mathematics, a [binary] relation (like >, since it considers two natural numbers and then is either true or false, based on which numbers are considered) is just a set of ordered pairs. Within the standard model of the natural numbers, > is just the [infinite] collection of ordered pairs { (2,1) , (3,1) , (3,2) , (4,1) , (4,2) , (4,3) , … }. So, suppose we have two chains of number-thingies...1, 2, 3,… and 1^, 2^, 3^, …. We can make the ‘>’ rule as follows: ” ‘x > y’ if and only if ‘x has a caret and y does not, or (in this case, both numbers must be in the same chain) x is greater than y within its own chain’ ”. This [infinite] collection of ordered pairs would be { (2,1) , (2^,1^) , (1^,1) , (3^,1^) , (3,2) , (3^,2^) , (3,1) , (4^,1^) , (1^,2) , (4^,2^) , (4,3) , (4^,3^) , … }.
So ‘>’ is a valid relation on two disconnected chains of number-thingies, because we define it to be so by fiat. The numbers we’re working with are nonstandard...so there is no reason to expect that there should be some standard, natural meaning for ‘>’.
Important Note: This explanation of ‘>’ does not correspond to a nonstandard model of first-order Peano arithmetic (and, clearly, not the standard model, either). If you want to know more about that, look to earthwormchuck163′s comment. I thought it might be helpful to you to understand it in a case that’s easier to picture, before jumping to the case of a nonstandard model of first-order Peano arithmetic. That case is even more complex than Eliezer revealed within his post. It would probably be extremely helpful to you to learn about well-orders, order types, and the ordinal numbers to get a handle on this stuff. You are more talented than I if you are able to understand it without that background knowledge.
Hope this helps.
Edit: Annoyingly (in this case), the asterisk causes italicization. Changed asterisks to carets.
Edit 2: Changed “operation” to “relation” everywhere, as per paper-machine’s correct comment.
Not to nitpick, but “>” is a binary relation, not a binary operation.
Ha, thanks. I don’t mind nitpicking. I’ll edit the comment.
Actually, a binary relation is a binary operation (it returns 1 if true and 0 if false). You passed up a chance to counter-nitpick the nitpicker.
Yes, if you want a two-sorted theory, then you can make a boolean type and lift all relations to operations.
That’s not the typical use of the word “operation” in model theory, however.
Thanks, that last link was very helpful.
This really benefits from a picture. Calling something “a nonstandard number” doesn’t really convey anything about them and a better name I’ll use is “infinitely big”, because they are.
< makes sense because the 2 chains are finite numbers and infinitely big numbers and an infinitely big number is bigger than any finite one because it’s , well, infinite. I can elaborate more technically, but I think trying to develop some numeracy for infinite numbers is a lot like learning about negatives and rationals and complex numbers. Just play with some expressions and get used to them. then look at the more technical treatment even if you have the ability to read it. Someone gave that example with a flat list but I think and feel that tapping into one’s existing NUMBER (and not list) sense is very powerful since it’s the first math we learn and the only one people use every single day.