What Makes Prime Numbers So Mysterious?

[dodo]

Do axiomatic systems like Peano have internal state? Can some axiomatic systems have an internal state and others not have one?

I think we take the machine analogy too far. Axiomatic systems are meant to provide a set of initial assumptions from which to construct the rest of the building. They are not algorithms, but logical propositions accepted by convention as true (so that all derived statements can be proven true). By themselves, they do not travel in time; our reasonings and explanations do, but only because our talking does.

One of the points all all this discussion is that you have built on top of something to get "numbers". The thing (stepping stone) you start with is the tick system.

I'm getting lost. I thought you said you didn't want the ticks to represent numbers, since there is no way of telling the 5th from the 625th.

 

[philiprdutton]

order and elements

You want your system to have elements ('number' which function as atoms or ur-elements) and a (presumably transitive) order on those elements, and you want to know if all systems with those properties can talk about primality in some restricted way or not? Is that right?

Yes you are following me. I felt originally that if a system has the two things (elements and order) you could not guarantee the ability to talk of "primality."

But now I am side tracking to a system where order is out the window. I just want a ticking system (unforntunatley, the algorithmic interpretation of step, next step, next step, next step, etc. DOES indeed imply order.

 

[philiprdutton]

internal state

Internal state?

Sorry, that term was NOT brought into the discussion by me!

 

[CRGreathouse]

But now I am side tracking to a system where order is out the window. I just want a ticking system (unforntunatley, the algorithmic interpretation of step, next step, next step, next step, etc. DOES indeed imply order.

So you want a countably infinite number of elements, but no comparisons between them. Seems like the axiom schema "For each natural number n, there is an element distinct from at least n others" of your counting scheme is what you want. Of course I can't think of a way to use that at all -- not for finding/defining primes, not for counting sheep, not for anything. It's essentially identity calculus.

 

[philiprdutton]

stop using

So you want a countably infinite number of elements, but no comparisons between them. Seems like the axiom schema "For each natural number n, there is an element distinct from at least n others" of your counting scheme is what you want. Of course I can't think of a way to use that at all -- not for finding/defining primes, not for counting sheep, not for anything. It's essentially identity calculus.

Sure I did not expect that anyone would want to use this system. Given what you just said about the identity calculus my question is can the Peano axiom system be built from the identity calculus?

Lets just say I am interested in decomposing the Peano axioms into building blocks (or feature sets) much like you would decompose some number into a combination of primes.

 

[D H]

I am saying why waste so much effort? Just do this:
x 1
x 2
x 3
x 4
x 5
etc.

With this system you need an axiom for each number. This is way too much effort. Moreover, how do you define addition? Why does 2+3=5? I don't see that relation anywhere in your system. The definition of addition falls out naturally from the Peano axioms. Multiplication and division fall out naturally from the definition of addition.

In comparison, defining the "numbers"¹ recursively (or inductively) requires but three axioms: an axiom stating that "one"² is a "number", another that no number has "one" as a successor, and a third stating that if x is a "number" then the successor of x is a "number". Recursion/induction is central to mathematics. It is extremely powerful.

Notes:
¹The Peano axioms define the "natural numbers". Using any other naming scheme in conjunction with the Peano axioms generates a set that is isomorphic (identical characteristics and identical behavior) to the natural numbers.

²Modern treatments start with zero rather than one so that addition and multiplication can be easily defined based on the Peano axioms.

 

[CRGreathouse]

Sure I did not expect that anyone would want to use this system. Given what you just said about the identity calculus my question is can the Peano axiom system be built from the identity calculus?

In what sense? Sure, by adding axioms, but in that sense you can build the Peano axioms from nothing -- so one way to build the Peano axioms from identity calculus is to ignore it and add all the normal axioms.

When I say identity calculus, I mean a system with no operation except "=". If you were somehow able to count the number of cows you and I had (the system has no way to count, but if you were given the numbers by proposition or axiom) then you could say that the two were different numbers but no more.

 

[philiprdutton]

axiomatic systems

With this system you need an axiom for each number. This is way too much effort. Moreover, how do you define addition? Why does 2+3=5? I don't see that relation anywhere in your system. The definition of addition falls out naturally from the Peano axioms. Multiplication and division fall out naturally from the definition of addition.

Okay I admit I just threw those numbers out there when I said:
x 1
x 2
x 3
x 4
x 5

Why do you care that the system has "too much effort"? It is still a valid axiomatic system. I am trying to learn about the process of writing axiomatic systems. I am just trying to learn about the different things I can create with an axiomatic system. Can I create an axiomatic system with infinite axioms? Not in practice but in theory. That is at the far extreme edge of what kind of systems you can create but it is still worth study.

The definition of addition falls out naturally from the Peano axioms. Multiplication and division fall out naturally from the definition of addition.

I must ask you then, to define a prime number in terms of addition (using the Peano axiom system). It should be easy for you to do since multiplication and division just "fall out naturally from the definition of addition."

In comparison, defining the "numbers"¹ recursively (or inductively) requires but three axioms: an axiom stating that "one"² is a "number", another that no number has "one" as a successor, and a third stating that if x is a "number" then the successor of x is a "number". Recursion/induction is central to mathematics. It is extremely powerful.

So I have another question: What do you call the process of writing/defining an axiomatic system? For now I will just call it "FORMALIZER 1.0" since I do not know what it is called but I want to pose another question specifically about it:

Is "FORMALIZER 1.0" built using recursion/induction?

 

[D H]

Addition: Seeding the Peano axioms with zero (rather than one), define

• a+0 = a
• a+S(b) = S(a+b) for all a,b in N

Multiplication is similar: Define

• a*0 = a
• a*S(b) = a*b+a for all a,b in N

Like I told you, recursion is extremely powerful.

 

[philiprdutton]

cool

Addition: Seeding the Peano axioms with zero (rather than one), define

• a+0 = a
• a+S(b) = S(a+b) for all a,b in N

Multiplication is similar: Define

• a*0 = a
• a*S(b) = a*b+a for all a,b in N

Like I told you, recursion is extremely powerful.

Very cool looking. You just defined addition and multiplication. But how do you define a prime number with addition only?

 

[CRGreathouse]

Addition: Seeding the Peano axioms with zero (rather than one), define

• a+0 = a
• a+S(b) = S(a+b) for all a,b in N

Multiplication is similar: Define

• a*0 = a
• a*S(b) = a*b+a for all a,b in N

Nice. I'd use different units for addition and multiplication, though.

 

[CRGreathouse]

Very cool looking. You just defined addition and multiplication. But how do you define a prime number with addition only?

We've done it already -- there can't be a solution to x + x = y, x + x + x = y, ..., (x-1)y = x. Alternately, define other operations recursively and use them to define it more traditionally.

 

[philiprdutton]

without addition

We've done it already -- there can't be a solution to x + x = y, x + x + x = y, ..., (x-1)y = x. Alternately, define other operations recursively and use them to define it more traditionally.

Okay, now this is getting interesting. I need to study the recursive versions a little while. However, I am still left with an important question. If addition is not defined then can you still get numbers? I think someone said earlier that addition is given by default in the Peano system somehow due to the successor function. More generally, can I, using the axiomatic method, define the natural numbers without defining addition?

If yes, then the notion of "prime" is due to the addition or other operations and not the actual number as it lies on the number line. I hope this question makes sense.

Also, Can we talk about "prime" in terms of the metronome system? My guess is "NO". This is interesting because, in my opinion, the number line and the "tick" line of the metronome system are the same thing or same "form".

 

[CRGreathouse]

More generally, can I, using the axiomatic method, define the natural numbers without defining addition?

What's a natural number? Certainly you can define things without defining addition, but could they be considered natural numbers without successors or the ability to add? Once again, philosophy not math. If you have a definition in mind it becomes math again.

I'm not uncomfortable with philosophy, but I know even less of it than I know of math -- I took only a few philosophy courses in college, though I did well in them.

Also, Can we talk about "prime" in terms of the metronome system? My guess is "NO". This is interesting because, in my opinion, the number line and the "tick" line of the metronome system are the same thing or same "form".

I don't understand your use of the term "metronome system".

 

[philiprdutton]

addition is what?

What's a natural number? Certainly you can define things without defining addition, but could they be considered natural numbers without successors or the ability to add? Once again, philosophy not math. If you have a definition in mind it becomes math again.

I'm not uncomfortable with philosophy, but I know even less of it than I know of math -- I took only a few philosophy courses in college, though I did well in them.

So from your point of view, addition is nested succession? Perhaps you could say that addition is a way to specify a "short-cut" style of succession?

I don't understand your use of the term "metronome system".

Sorry. Earlier I attempted to switch from "counting system" to "metronome system."

 

[CRGreathouse]

So from your point of view, addition is nested succession? Perhaps you could say that addition is a way to specify a "short-cut" style of succession?/QUOTE]

Addition is defined with reference to the successor, and multiplication likewise with addition. Outside of such fundamentals, I don't think of them as shortcuts.

Addition is a recursive operation, a member of the Grzegorczyk hierarchy (successor, addition, multiplication, exponentiation, tetration, ...). Each level can be defined for nonnegative integers based on recursion, but then can presumably be generalized beyond that (we can add fractions, not just whole numbers).

 

[philiprdutton]

short cutting

So from your point of view, addition is nested succession? Perhaps you could say that addition is a way to specify a "short-cut" style of succession?/QUOTE]

Addition is defined with reference to the successor, and multiplication likewise with addition. Outside of such fundamentals, I don't think of them as shortcuts.

Addition is a recursive operation, a member of the Grzegorczyk hierarchy (successor, addition, multiplication, exponentiation, tetration, ...). Each level can be defined for nonnegative integers based on recursion, but then can presumably be generalized beyond that (we can add fractions, not just whole numbers).

Thanks for the extra information. You say you do not think of addition as a shortcut and I can accept your viewpoint. Just for the sake of discussion, don't you think that having defined "addition" is essentially the reason why you do not have to rely upon the "counting" or "metronome" interpretation of what comes out of the Peano system?

Also, for the Peano axioms, surely there is some kind of "counting" or "metronome" feature. The reason I reiterate this idea is because, if you think about it, the successor function is always "counting" or "ticking" from the 1. Multiplication, addition, in this peano system, is always given in terms of a count from the 1 mark. Essentially, there is no short cut in a recursive system because everything is in terms of the successor function (in relation to 1). So, addition is inherent. Fine. But as soon as you "reach" into the system and "tag" something as "addition" then you have created a meta-shortcut which is quite useful for interacting with the system. Addition is a "user" short cut not a system short cut.

 

[CRGreathouse]

Essentially, there is no short cut in a recursive system because everything is in terms of the successor function (in relation to 1). So, addition is inherent. Fine. But as soon as you "reach" into the system and "tag" something as "addition" then you have created a meta-shortcut which is quite useful for interacting with the system. Addition is a "user" short cut not a system short cut.

OK.

I agree that the system can be seen as using the successor operation underneath, and that's usually the way things are defined. I don't see it as a shortcut at all on the 'user' level, though: as I mentioned the full operation on rational/real/complex/etc. numbers doesn't follow from the successor operator and must be defined differently.

 

[philiprdutton]

defining numbers

OK.

I agree that the system can be seen as using the successor operation underneath, and that's usually the way things are defined. I don't see it as a shortcut at all on the 'user' level, though: as I mentioned the full operation on rational/real/complex/etc. numbers doesn't follow from the successor operator and must be defined differently.

If the operations are not defined then basically you just have numbers that are defined in terms of their positions in relation to "1"? Would I be correct in saying this?

If this is the case then, once again, I don't see how a number can be "prime" without definitions of the operations (addition, multiplication, etc.). We have agreed that we can define the numbers with just the successor function and that the numbers are fully defined despite not having operations. I just can't understand how anyone could look at this system and say that some particular number is "prime."

 

[CRGreathouse]

If the operations are not defined then basically you just have numbers that are defined in terms of their positions in relation to "1"? Would I be correct in saying this?

Not in general, no. It depends on what is given. Unless you're more specific on what is defined rather than what is not, there's not much I can say.

If this is the case then, once again, I don't see how a number can be "prime" without definitions of the operations (addition, multiplication, etc.). We have agreed that we can define the numbers with just the successor function and that the numbers are fully defined despite not having operations. I just can't understand how anyone could look at this system and say that some particular number is "prime."

One simple way would be to define primality, or build it directly into one's system. A natural way (to me) to define numbers would be to start with the primes as atoms and define the positive integers as the product of some collection of primes, with equality if and only if the number of each prime was the same. The natural "successor" operation S_p(n) would then increment the count of a single prime by one, i.e. "multiply" the number by that prime. Addition would be a complex relation that would be shown to always have a unique answer only by a theorem as profound as the fundamental theorem of arithmetic is on our system.

 

[philiprdutton]

makes sense

Not in general, no. It depends on what is given. Unless you're more specific on what is defined rather than what is not, there's not much I can say.

I think I am getting close to understanding my own confusion.

I still have a few misunderstandings. When Peano fully defined the successor function, did addition fall out automatically (I think this was a point in an earlier posting about recursion)? Looking at the axioms on wikipedia, I can't see an explicit definition of addition. Interestingly the wikipedia editor for the Peano axiom topic has written the following:

"The axioms are based on the successor operation, written Sa or S(a), which adds 1 to its argument."

From that statement, it seems as though the addition is indeed built into the successor function.

I think I finally understand the difference between the Peano axiomatic system and the counting system we talked about earlier. I propose the following thought experiment:

All the arithmetic operations of the Peano system (and hence the notion of prime) could not exist if there was not a reference "point" defined on the "number line." If you take that first axiom away from the Peano system then all you have is a system that acts like a "metronome" ( the "counting system" that we have been talking about).

 

[CRGreathouse]

When Peano fully defined the successor function, did addition fall out automatically (I think this was a point in an earlier posting about recursion)? Looking at the axioms on wikipedia, I can't see an explicit definition of addition.

Off the top of my head:

x + 0 = x
x + S(y) = S(x + y)

These two allow any two numbers to be added, since you just decrease one step by step until it is zero, increasing the sum likewise.

From that statement, it seems as though the addition is indeed built into the successor function.

That was just terminology. The successor just picks the next number; addition is defined in terms of it. It's convenient to mention that once addition is defined x + 1 will be the same as S(x), but that just falls out of the above definition since S(0) = 1.

All the arithmetic operations of the Peano system (and hence the notion of prime) could not exist if there was not a reference "point" defined on the "number line." If you take that first axiom away from the Peano system then all you have is a system that acts like a "metronome" (or the "counting system" that we have been talking about).

Which is the first axiom?

 

[philiprdutton]

oops

All the arithmetic operations of the Peano system (and hence the notion of prime) could not exist if there was not a reference "point" defined on the "number line." If you take that first axiom away from the Peano system then all you have is a system that acts like a "metronome" ( the "counting system" that we have been talking about).

Which is the first axiom?

Ooops! Indeed, the axioms are not ordered! I mean the axiom which states: "1 is a natural number" Also, we might be looking at two different versions of the axioms. I am looking at the list on the wikipedia (which are slightly rephrased from the original perhaps). Anyway, take that out and you basically sever addition and multiplication. Perhaps you also have no way to say what a number is. However, the number line is still there. The form has not been changed, destroyed or altered in any way (this will be very profound to me if it is indeed true).

 

[CRGreathouse]

Ooops! Indeed, the axioms are not ordered! I mean the axiom which states: "1 is a natural number" Also, we might be looking at two different versions of the axioms. I am looking at the list on the wikipedia (which are slightly rephrased from the original perhaps). Anyway, take that out and you basically sever addition and multiplication. Perhaps you also have no way to say what a number is. However, the number line is still there. The form has not been changed, destroyed or altered in any way (this will be very profound to me if it is indeed true).

Without the axiom "1 is a natural number" (which in modern terms is "0 is a natural number") you can't prove the existence of numbers at all.

 

[dodo]

... if there was not a reference "point" defined on the "number line."

Actually that number 1 is not an arbitrary reference point. In informal terms, it is "the step of the successor": when defining addition, we started by a + 1 = S(a). Similarly, when extending the axioms with S(0)=1, the number 0 turns out to be the neutral element of addition, a + 0 = a, all as a consequence of the initial axioms and the definition of addition.

More formally, if you define a function f: N* x N* -> N* (N* being the numbers including 0) as

d(a,b) = the number 's' such that, for a <= b, we have a + s = b;
and for a > b, the number d(b,a)​

then I'd say the function d(a,b) passes the requisites to be considered a metric (non-negativity, identity of elements with distance 0, symmetry and triangular identity), so that N* plus the function d() is now a metric space. So now we can speak of distance: and the distance d(a,S(a)) is exactly 1.

 

[philiprdutton]

true

Without the axiom "1 is a natural number" (which in modern terms is "0 is a natural number") you can't prove the existence of numbers at all.

Yes. I am in agreement with you on that. But I still believe the underlying "form" of what was once called a "number line" would still remain completely the same. Peano, by stating that "1 is a natural number" has basically "encoded" the reference point into the system. However, without the axiom, a user could just define their own reference point outside of the system and just use what is left in the Peano axiom set as a "metronome." The combination of "reference" point and "metronome system" is basically enough to completely build all the numbers. In other words, from an algorithmic perspective if you have memory (for the reference point) and metronome, you can get all the numbers, addition, multiplication, "prime", etc. all in one complete magical "poof!".

Okay. I might be getting the picture now (finally). Peano's axioms just give the user a way to input things into a recursive blackbox which then turns around and spits out a number. It is essentially an interface to recursion. It is a system which, once the recursion is kicked into gear, there is nothing you can do except wait until the answer comes back. You can't peer into the recursive "machinery" to glean or use "internal" information. If you take the "1 is a natural number" axiom out then the black box remains but is basically "disoriented". So:
*Recursion without a reference point is basically a metronome.
*Recursion without a reference point is just unary "counting/ticking."
*Recursion can only be used to define numbers when given a seed.
*Recursion is a powerful thing (mystery) which requires an interface to be used; hence, Peano defined his axioms.
*Pure recursion does not have a reference point.

 

[philiprdutton]

Actually that number 1 is not an arbitrary reference point. In informal terms, it is "the step of the successor": when defining addition, we started by a + 1 = S(a). Similarly, when extending the axioms with S(0)=1, the number 0 turns out to be the neutral element of addition, a + 0 = a, all as a consequence of the initial axioms and the definition of addition.

More formally, if you define a function f: N* x N* -> N* (N* being the numbers including 0) as

d(a,b) = the number 's' such that, for a <= b, we have a + s = b;
and for a > b, the number d(b,a)​

then I'd say the function d(a,b) passes the requisites to be considered a metric (non-negativity, identity of elements with distance 0, symmetry and triangular identity), so that N* plus the function d() is now a metric space. So now we can speak of distance: and the distance d(a,S(a)) is exactly 1.

Thanks for this extra information. I am trying to understand the notion of "the step of the successor" as you called it. But it will require some mind bending. Are you saying that the axiom "0 is a natural number" combined with possibly one of the other axioms were written by Peano specifically to set up some kind of "unit space?" or "unit distance". You seem to be speaking of a kind of unit space when you say things like "the distance d(a,S(a)) is exactly 1." and "N* plus the function d() is now a metric space".

 

[CRGreathouse]

Yes. I am in agreement with you on that. But I still believe the underlying "form" of what was once called a "number line" would still remain completely the same. Peano,` by stating that "1 is a natural number" has basically "encoded" the reference point into the system.

I'm not sure I agree. 1 isn't given any properties, so the axioms would remain unchanged in meaning if you replaced all instances of "1" with "0" or "2007" or "foo".

Now the induction axiom, that's a powerful one. I could understand if you wanted to take that one out. But if you kept it in (considering that it does mention "1") while still taking out the "1 is a natural number" axiom, you'd have one of two situations:
* There are no natural numbers. This is a pretty boring situation, since the other axioms don't tell you much of anything, since they all have to do with numbers.
* 1 isn't a natural number. We'll call it an "ur-element", borrowing from set theory. But apply the successor operation to it enough times and you eventually get a natural number. From then on, the natural numbers operate just like normal -- call the first natural number 1' and define addition (multiplication, etc.) as normal but with 1' instead of 1.

So I don't think taking out the 1 does anything -- either you have a system with literally nothing in it, or you have one just like the ordinary natural numbers.

 

[philiprdutton]

reference point

I'm not sure I agree. 1 isn't given any properties, so the axioms would remain unchanged in meaning if you replaced all instances of "1" with "0" or "2007" or "foo".

Now the induction axiom, that's a powerful one. I could understand if you wanted to take that one out. But if you kept it in (considering that it does mention "1") while still taking out the "1 is a natural number" axiom, you'd have one of two situations:
* There are no natural numbers. This is a pretty boring situation, since the other axioms don't tell you much of anything, since they all have to do with numbers.
* 1 isn't a natural number. We'll call it an "ur-element", borrowing from set theory. But apply the successor operation to it enough times and you eventually get a natural number. From then on, the natural numbers operate just like normal -- call the first natural number 1' and define addition (multiplication, etc.) as normal but with 1' instead of 1.

So I don't think taking out the 1 does anything -- either you have a system with literally nothing in it, or you have one just like the ordinary natural numbers.

So, are you saying that in order for us to apply the definition of "natural number" one must have already "built" support for a reference point in a particular system (like Peano)?

,... you'd have one of two situations:
* There are no natural numbers. This is a pretty boring situation, since the other axioms don't tell you much of anything, since they all have to do with numbers.

True it is boring if you are only interested in numbers. One of the things I am interested in is the system "mechanics" of axiomatic theory. Perhaps it would be helpful if someone could explain the true order of creation of the set of Peano axioms. In other words, what is the first axiom that must be stated? What is the second? What is the third? ... what is the last?

It would be helpful for the sake of stepping through the recreation of the Peano system. With such a list, I am assuming I can hack off the last axiom without even thinking about it and still be able to have "natural numbers". What axioms can be hacked off in this sense?

Also, if there is not one Peano axiom (I am typically looking at the list given on wikipedia) which can not be deleted without affecting the existence of "natural numbers" then it is clearly a system which is describing an existing "thing" as opposed to actually creating the "thing." (here, "thing" is the number line). If is only describing the "thing" then it is clearly only an interface to it.

 

[matt grime]

Peano, by stating that "1 is a natural number" has basically "encoded" the reference point into the system. However, without the axiom, a user could just define their own reference point outside of the system and just use what is left in the Peano axiom set as a "metronome."

I think you're missing a standard result in set theory. If we remove the axiom - there is some natural number (which we call 1), then we're getting to the point where the empty set will satisfy the definition of the natural numbers since the precedent in any remaining axiom is false, thus things are automatically true.

I presume you don't wish to have a set of natural numbers that has no elements.

It isn't that he has declared 1 to be a natural number, just that there is such a thing. I.e. whatever notional model we choose for our axioms must be a non-empty set.

 

[philiprdutton]

notational model

I think you're missing a standard result in set theory. If we remove the axiom - there is some natural number (which we call 1), then we're getting to the point where the empty set will satisfy the definition of the natural numbers since the precedent in any remaining axiom is false, thus things are automatically true.

I presume you don't wish to have a set of natural numbers that has no elements.

It isn't that he has declared 1 to be a natural number, just that there is such a thing. I.e. whatever notional model we choose for our axioms must be a non-empty set.

Interesting result you mentioned.

I am still interested in the properties of the system (what can it do? how can I use it?) even when there is no longer the ability to recognize, talk about, or define "natural numbers." On the one hand it sounds like I am philosophizing everything to death. However, I am working out my understanding of what I consider a practical problem. I will re-iterate it here: I am simply wondering what is the basic core "feature" of an axiomatic system. I am starting to think that the basic core feature is a metronome type "feature." This is what I am exploring. So, I can tolerate a system that does not necessarily have the ability to "internalize" the notion of a "natural number."

 

[CRGreathouse]

So, are you saying that in order for us to apply the definition of "natural number" one must have already "built" support for a reference point in a particular system (like Peano)?

I understood no part of that.

True it is boring if you are only interested in numbers.

No. Either the system is just like the system with the "1" axiom (possibly with a few ur-elements, but they don't change anything) or it's a list of properties that apply to nothing. Consider this system:

1. All unicorns are four-legged.
2. All unicorns have a single horn.
3. All unicorns are pink.
4. All unicorns are good-hearted.
5. Unicorns only allow maidens to ride on them.

It could be an interesting system, in that it gives several properties to the set U of unicorns. But if you know (perhaps as an additional axiom) that there are no unicorns, suddenly 1-5 mean nothing -- they don't add or subtract from the possible properties of any object or creature.

Similarly, using the Wikipedia axioms you use:
2. Every natural number is equal to itself (equality is reflexive).
3. For all natural numbers a and b, a = b if and only if b = a (equality is symmetric).
4. For all natural numbers a, b, and c, if a = b and b = c then a = c (equality is transitive).
5. If a = b and b is a natural number then a is a natural number.
6. If a is a natural number then Sa is a natural number.
7. If a and b are natural numbers then a = b if and only if Sa = Sb.
8. If a is a natural number then Sa is not equal to 1.
9. For every set K, if 1 is in K, and Sx is in K for every natural number x in K, then every natural number is in K.

Literally none of the axioms 2-9 have any meaning whatever if there are no natural numbers. Axioms 2-8 are in that case of the form "False --> x" which is always true, and axiom 9 is of the form "x --> {} is in the set X" which is true for any set X.

 

[CRGreathouse]

One of the things I am interested in is the system "mechanics" of axiomatic theory. Perhaps it would be helpful if someone could explain the true order of creation of the set of Peano axioms. In other words, what is the first axiom that must be stated? What is the second? What is the third? ... what is the last?

They work in any order. It would make sense to have axiom 1 come before axiom 8, but this is not strictly necessary.

Axiom 9 is important for proofs but if left off, many problems could still be stated.

It would be helpful for the sake of stepping through the recreation of the Peano system. With such a list, I am assuming I can hack off the last axiom without even thinking about it and still be able to have "natural numbers". What axioms can be hacked off in this sense?

I leave off 2-5, as these simply define equality. You may amuse yourself by removing one or more of these, which effectively replaces equality with a certain kind of (possibly equivalence) relation.

If #1 is removed, the system is either null, unchanged, or unchanged except with the addition of finitely many ur-elements, which don't actually change things at all from a set-theoretic point of view. (They don't give it more expressive power.) Essentially all proofs are either nonconstructive or conditional.

If #6 is removed, the system may be unchanged or have only finitely many natural numbers -- perhaps only one.

I'm not quite sure what the effects of removing #7 would be. Could S be multivalued, or is it defined as a function? This may lead to natural numbers as an incomparable web rather than a chain. Perhaps Matt will lend his talents here...?

If #8 is removed there may be only finitely many numbers. If so, they may either end at an element (call it "infinity") that is its own successor, or may loop at some point. In either case there would be a finite chain of natural numbers, then a ring that functions like the integers modulo a constant.

If #9 is removed there may be inaccessible natural numbers (numbers not in {1, S(1), S(S(1)), ...}). Proofs become difficult.

 

[philiprdutton]

no meaning

I understood no part of that.
No. Either the system is just like the system with the "1" axiom (possibly with a few ur-elements, but they don't change anything) or it's a list of properties that apply to nothing. Consider this system:

1. All unicorns are four-legged.
2. All unicorns have a single horn.
3. All unicorns are pink.
4. All unicorns are good-hearted.
5. Unicorns only allow maidens to ride on them.

It could be an interesting system, in that it gives several properties to the set U of unicorns. But if you know (perhaps as an additional axiom) that there are no unicorns, suddenly 1-5 mean nothing -- they don't add or subtract from the possible properties of any object or creature.

Similarly, using the Wikipedia axioms you use:
2. Every natural number is equal to itself (equality is reflexive).
3. For all natural numbers a and b, a = b if and only if b = a (equality is symmetric).
4. For all natural numbers a, b, and c, if a = b and b = c then a = c (equality is transitive).
5. If a = b and b is a natural number then a is a natural number.
6. If a is a natural number then Sa is a natural number.
7. If a and b are natural numbers then a = b if and only if Sa = Sb.
8. If a is a natural number then Sa is not equal to 1.
9. For every set K, if 1 is in K, and Sx is in K for every natural number x in K, then every natural number is in K.

Literally none of the axioms 2-9 have any meaning whatever if there are no natural numbers. Axioms 2-8 are in that case of the form "False --> x" which is always true, and axiom 9 is of the form "x --> {} is in the set X" which is true for any set X.

Thanks for the input. So, it sounds as if the axiomatic Peano system basically builds the "structure" that we find in the "number line."

[T or F] The number line doesn't exist until after an axiomatic system is written to create the structure.

[T or F] You can't have a number without the ability to know what it is in terms of it's successor and/or it's predecessor.

[T or F] You can't have a the notion of a "number" separated from operations like addition/multiplication EVEN if you do not define those operations in your axioms.

[T or F] A system that can give us, in order, "1,2,3,4,5,6..." can also be modified to only give us, "blip,blip,blip,blip,..." However, given the modified system, we do not know if "the tape is moving or the tape is not moving". (I am making a play on the Turing machine when I use the word "tape")Thanks for the input. If someone can help me with the above T/F statements then I would be very grateful and will be ready to close this thread (much to everyone's relief I am sure!). Obviously, I need to go study... : )

 

[Hurkyl]

In the practice of formal logic, one considers syntax, and semantics.

Syntax is essentially just formal manipulation of symbols. You define a "language" and "rules of inference", and you can start proving "theorems" and all sorts of interesting stuff.

A "theory" is a collection of statements that you make in the language.

One convenient way to specify a theory is by selecting a collection of statements, which we call "axioms", which have the property that the entire language (and nothing else) can be derived from those axioms by applying the rules of inference.

(Incidentally, this is by no means the only way to specify a theory)



When we try to "interpret" a language, that's semantics. A typical interpretation is to supply a set of "objects", and for each function symbol, relation symbol and constant symbol in the language, one supplies a function, relation, or element on the set of objects.

If a collection of statements are true in this interpretation, then we call it a "model" of those statements.

Note that if a set of axioms generate a theory, then a model of those axioms is the same thing as a model of that theory.

For common theories, we give the models special names. e.g. a model of group theory would be called a "group" -- equivalently, a model of the group axioms would be called a "group". Similarly, a model of Hilbert's axioms would be called a "Euclidean geometry", and a model of Peano's axioms would be called a "set of natural numbers".

Remember -- a model of Peano's axioms is the same thing as a model of the theory it generates. The theory is the important thing here; if we picked a different set of axioms that generated the same theory, we would still call it a "set of natural numbers".

We do this, even if the set of objects doesn't obviously resemble our intuitive notion of a "plane" or a "set of numbers" ought to be. As a practical matter, this is fine, precisely because we tend to design theories so that they capture the essense of our intuitive notions. So, I can still apply all of my geometric intuition, even if I'm working with something that doesn't manifestly appear to have any geometric form at all!



Sometimes, one might step outside of pure mathematics. e.g. we might assert that the numbers we really use to count with in real life are a model of Peano's axioms, or that reality is a model of quantum mechanics.

There is a mathematical theorem that says any consistent theory using elementary Boolean logic has a set-theoretic model. If you want to talk about the possible existence of models in "reality" or in some world of "Platonic ideals", or whatever, then you are no longer talking about mathematics.

 

[philiprdutton]

the basics

In the practice of formal logic, one considers syntax, and semantics.

Syntax is essentially just formal manipulation of symbols. You define a "language" and "rules of inference", and you can start proving "theorems" and all sorts of interesting stuff.

A "theory" is a collection of statements that you make in the language.

One convenient way to specify a theory is by selecting a collection of statements, which we call "axioms", which have the property that the entire language (and nothing else) can be derived from those axioms by applying the rules of inference.

(Incidentally, this is by no means the only way to specify a theory)



When we try to "interpret" a language, that's semantics. A typical interpretation is to supply a set of "objects", and for each function symbol, relation symbol and constant symbol in the language, one supplies a function, relation, or element on the set of objects.

If a collection of statements are true in this interpretation, then we call it a "model" of those statements.

Note that if a set of axioms generate a theory, then a model of those axioms is the same thing as a model of that theory.

For common theories, we give the models special names. e.g. a model of group theory would be called a "group" -- equivalently, a model of the group axioms would be called a "group". Similarly, a model of Hilbert's axioms would be called a "Euclidean geometry", and a model of Peano's axioms would be called a "set of natural numbers".

Remember -- a model of Peano's axioms is the same thing as a model of the theory it generates. The theory is the important thing here; if we picked a different set of axioms that generated the same theory, we would still call it a "set of natural numbers".

We do this, even if the set of objects doesn't obviously resemble our intuitive notion of a "plane" or a "set of numbers" ought to be. As a practical matter, this is fine, precisely because we tend to design theories so that they capture the essense of our intuitive notions. So, I can still apply all of my geometric intuition, even if I'm working with something that doesn't manifestly appear to have any geometric form at all!



Sometimes, one might step outside of pure mathematics. e.g. we might assert that the numbers we really use to count with in real life are a model of Peano's axioms, or that reality is a model of quantum mechanics.

There is a mathematical theorem that says any consistent theory using elementary Boolean logic has a set-theoretic model. If you want to talk about the possible existence of models in "reality" or in some world of "Platonic ideals", or whatever, then you are no longer talking about mathematics.

Thanks for supplying this summary. I am afraid I am not going to be able to absorb it all without spending a lot of time "doing" the math. I figure I will need to start with an understanding of mathematical logic (which is why I posted a question already about "rule of inference" in the logic discussion area).

 

[CRGreathouse]

What did you think of my list of changes by omitting axioms (#133)? I'm curious to see what you think, since this may be ther only place we're properly connecting now.

I'm going to number your questions in bold below.

Thanks for the input. (0) So, it sounds as if the axiomatic Peano system basically builds the "structure" that we find in the "number line."

(1) [T or F] The number line doesn't exist until after an axiomatic system is written to create the structure.

(2) [T or F] You can't have a number without the ability to know what it is in terms of it's successor and/or it's predecessor.

(3) [T or F] You can't have a the notion of a "number" separated from operations like addition/multiplication EVEN if you do not define those operations in your axioms.

(4) [T or F] A system that can give us, in order, "1,2,3,4,5,6..." can also be modified to only give us, "blip,blip,blip,blip,..." (5) However, given the modified system, we do not know if "the tape is moving or the tape is not moving". (I am making a play on the Turing machine when I use the word "tape")

0. I don't understand.
1. I think this statement is essentially "Is mathematical Platonism correct?". If so, it's highly subjective -- but as I said before, I'm something of a Platonist but few mathematicians are.
2. What's a number? There's no reason you can't have objects without successors or predecessors. Still, I'll take a crack at this one. A member of the extended reals should probably be considered a number under a sensible definition of same, and in that system +/- infty could be defined without successor or predecessor.
3. What's a number? In any case definitions don't matter; they're "conservative extensions" of the theory.
4. I don't understand.
5. There are lots of ways to represent numbers on (binary) Turing machines, but unary is most popular: a 0-terminated string of 1s. I don't know what this has to do with the tape moving or your other philosophical questions.

 

[CRGreathouse]

Thanks for supplying this summary. I am afraid I am not going to be able to absorb it all without spending a lot of time "doing" the math. I figure I will need to start with an understanding of mathematical logic (which is why I posted a question already about "rule of inference" in the logic discussion area).

Hurkyl's post was explaining what was meant by the term "model". It's worth a second read -- and if that doesn't do it for you, look it up elsewhere.

Here, since you're already using Wikipedia, let me find you a link there.

Hmm, that's not good. I found http://en.wikipedia.org/wiki/Model_theory but it's considerably more technical than the post.

 

[phoenixthoth]

Thanks for the input. So, it sounds as if the axiomatic Peano system basically builds the "structure" that we find in the "number line."

[T or F] The number line doesn't exist until after an axiomatic system is written to create the structure.

[T or F] You can't have a number without the ability to know what it is in terms of it's successor and/or it's predecessor.

[T or F] You can't have a the notion of a "number" separated from operations like addition/multiplication EVEN if you do not define those operations in your axioms.

[T or F] A system that can give us, in order, "1,2,3,4,5,6..." can also be modified to only give us, "blip,blip,blip,blip,..." However, given the modified system, we do not know if "the tape is moving or the tape is not moving". (I am making a play on the Turing machine when I use the word "tape")


Thanks for the input. If someone can help me with the above T/F statements then I would be very grateful and will be ready to close this thread (much to everyone's relief I am sure!). Obviously, I need to go study... : )

Maybe you can define something structurally equivalent to the set of natural numbers this way...
Let U be any infinite set (which could mean, for instance, that there is a one-to-one correspondence between U and at least one of its proper subsets). Such a set exists in ZF by the axiom of infinity.

Pick out any element of U. Let's call it u*. Now let S be any function with domain U and range contained in U with the following conditions:
1. u* is not in the range of S
2. S has no fixed points (i.e., for all u in U, S(u) is not u)

(u* is going to behave like the number 1 and S like the successor function.)

Now for another definition. A subset A of U is called inductive (or S-inductive because it depends on S) iff the following conditions hold:
1. u* is in A and
2. for all a in A, S(a) is in A.

Let N* be the intersection of all inductive subsets of U. This is going to be what behaves like the set of natural numbers. I think N* will just be the orbit of u*:
{u*, S(u*), S(S(u*)), S(S(S(u*))), S(S(S(S(u*)))), S(S(S(S(S(u*))))), ...}.

N* certainly won't be like N at all if the orbit of u* is finite, so let's add a third condition to S:
1. u* is not in the range of S
2. S has no fixed points (i.e., for all u in U, S(u) is not u)
3. All elements in the set {u*, S(u*), S(S(u*)), S(S(S(u*))), S(S(S(S(u*)))), S(S(S(S(S(u*))))), ...} are different.

Now define a relation on N*, call it R, which will behave like less than or equal to:
(x,y) is in R iff y is in the orbit of x. In other words, (x,y) is in R iff either y=x or y=S(x) or y=S(S(x)) or y=S(S(S(x))) or ... .

I think then that (N, <=) is structurally like (N*, R) in that if we define a function from N to N*, called f, as f(n) is the (n-1)st iterate of u* under S, then f would be a one-to-one correspondence and "relation preserving," i.e., for all n1 and n2 in N, then n1 <= n2 iff R( f(n1), f(n2) ).

If this is true, then for any given U, S with the stated properties on U, then the intersection of all inductive sets would behave like the set of natural numbers.


Incidentally, when the axiom says 1 is a natural number, I'm wondering what 1 is. One way to make that work is to define 1 to be the set whose element is the empty set and for all sets a, define the successor of a to be the union of a with the set whose element is a.

 

[Hurkyl]

Thanks for supplying this summary. I am afraid I am not going to be able to absorb it all without spending a lot of time "doing" the math. I figure I will need to start with an understanding of mathematical logic (which is why I posted a question already about "rule of inference" in the logic discussion area).

The main thing I was trying to say is that there is a separation between syntax and semantics. Theories and proofs are syntactic; they do not come pre-equipped with any sort of "meaning".

It is true that a mathematician often has a particular meaning in mind when 'e creates a theory, and 'e designs it so that the theory can be given the interpretation 'e desires. But once the theory is created, it is a purely syntactic, and if one desires, it can be used with other meanings, or with no meaning attached to it at all!

 

[matt grime]

Thanks for the input. If someone can help me with the above T/F statements then I would be very grateful and will be ready to close this thread (much to everyone's relief I am sure!). Obviously, I need to go study... : )

You can't answer them because it is purely a formal opinion of whether they are true or false. Your T/F questions seem purely ontological, if that's the word. In what sense do any mathematical objects exist?

 

[CRGreathouse]

You can't answer them because it is purely a formal opinion of whether they are true or false. Your T/F questions seem purely ontological, if that's the word. In what sense do any mathematical objects exist?

Heh. The only branch of philosophy I did ever get deeply into was ontology... maybe that's why I can take this discussion. As far as that goes, Matt, you're a formalist, yes?

 

[philiprdutton]

nesting

...3. All elements in the set {u*, S(u*), S(S(u*)), S(S(S(u*))), S(S(S(S(u*)))), S(S(S(S(S(u*))))), ...} are different.

Uhm... how do you handle "nestedness" without a reference point? This is why when I think about natural numbers and the operations I get so adamant about trying to figure out how the heck a reference point comes into play (if it actually does). In my humble lowly view, I believe there just absolutely has to be a reference point in there no matter whether you are using some set-theoretic notation or encoding the reference point in the axioms themselves...

Also, thanks so much for contributing your information thus far!

I must say my head hurts after trying to read it... but it is not you- it is me!

 

[philiprdutton]

hacking

They work in any order. It would make sense to have axiom 1 come before axiom 8, but this is not strictly necessary.

Axiom 9 is important for proofs but if left off, many problems could still be stated.
I leave off 2-5, as these simply define equality. You may amuse yourself by removing one or more of these, which effectively replaces equality with a certain kind of (possibly equivalence) relation.

If #1 is removed, the system is either null, unchanged, or unchanged except with the addition of finitely many ur-elements, which don't actually change things at all from a set-theoretic point of view. (They don't give it more expressive power.) Essentially all proofs are either nonconstructive or conditional.

If #6 is removed, the system may be unchanged or have only finitely many natural numbers -- perhaps only one.

I'm not quite sure what the effects of removing #7 would be. Could S be multivalued, or is it defined as a function? This may lead to natural numbers as an incomparable web rather than a chain. Perhaps Matt will lend his talents here...?

If #8 is removed there may be only finitely many numbers. If so, they may either end at an element (call it "infinity") that is its own successor, or may loop at some point. In either case there would be a finite chain of natural numbers, then a ring that functions like the integers modulo a constant.

If #9 is removed there may be inaccessible natural numbers (numbers not in {1, S(1), S(S(1)), ...}). Proofs become difficult.

Thank you for your analysis. I have begun to see many people resort back to a set-theoretic notation as in your case of the #1 axiom quoted above. A few times, lately, I have seen the set-theoretic articulation of the natural numbers. Every time I see such an articulation, I get the "shivers" because it looks so nested. When I think about "nesting" I can not understand how "nesting" could ever exist without a reference point.

The rest I am not able to comment on due to lack of understanding. However, I am deftly grateful for the valiant list you put forth. Honestly, I would love a poster of "what happens if you remove the axioms" as opposed to the axioms themselves (not afraid to admit that I love math posters!).

 

[CRGreathouse]

A few times, lately, I have seen the set-theoretic articulation of the natural numbers. Every time I see such an articulation, I get the "shivers" because it looks so nested. When I think about "nesting" I can not understand how "nesting" could ever exist without a reference point.

In set theory, the natural reference point is the null set, because once you know how to form sets ("set-builder notation") you don't need any further axioms to form the null set. It provides a concrete starting point too -- unlike the Peano "1", which could be anything, the nukll set is easy to grasp.

The rest I am not able to comment on due to lack of understanding. However, I am deftly grateful for the valiant list you put forth. Honestly, I would love a poster of "what happens if you remove the axioms" as opposed to the axioms themselves (not afraid to admit that I love math posters!).

Heh, maybe I'll make one.

 

[philiprdutton]

null set = references point

In set theory, the natural reference point is the null set, because once you know how to form sets ("set-builder notation") you don't need any further axioms to form the null set. It provides a concrete starting point too -- unlike the Peano "1", which could be anything, the nukll set is easy to grasp.

So, the ability to talk of numbers and the operations on them, and the notion of prime, is essentially due to the power of NESTING? Is this all?

 

[phoenixthoth]

Uhm... how do you handle "nestedness" without a reference point? This is why when I think about natural numbers and the operations I get so adamant about trying to figure out how the heck a reference point comes into play (if it actually does). In my humble lowly view, I believe there just absolutely has to be a reference point in there no matter whether you are using some set-theoretic notation or encoding the reference point in the axioms themselves...

Also, thanks so much for contributing your information thus far!

I must say my head hurts after trying to read it... but it is not you- it is me!

I think I may be misunderstanding your main question here. If I do understand, then any selected element u* can be the reference point%, such as the set whose only element is the null set. That is a nice choice because its cardinality is what is "natural" to think of as "1."

As far as nestedness, I'm not sure what you mean so if it's basically the iterates of what I'm calling a successor function, they are no less "natural" than the first iterate.

Sorry if I misunderstood.

%so long as whatever function you're using for the successor does NOT have u*, the reference point, in its range, i.e., nothing's successor is u*.

btw, not that it matters much, my condition 3 on a successor function could be stated as something like no elements in the orbit of u* are periodic points of S (of any period). Or, perhaps not as compactly, as the following set is pairwise disjoint:
{{x} : x is in the orbit of u* under S}. Basically my three conditions are trying to generalize the essential characteristics a successor function would have. For example, u* could be the square root of 5, if U is taken to be the set of real numbers, and S(x) = x-1. What I'm thinking is the set
{sqrt(5), sqrt(5) -1, sqrt(5)-2, sqrt(5)-3, ...} is, in some sense, like the usual set of natural numbers (except in this case, the order R I defined would reverse the 'usual' order...I defined the order so that x <= y if y is in the orbit of the successor function applied to x.)

 

[philiprdutton]

nestedness in binary digit sequences

I think I may be misunderstanding your main question here. If I do understand, then any selected element u* can be the reference point%, such as the set whose only element is the null set. That is a nice choice because its cardinality is what is "natural" to think of as "1."

As far as nestedness, I'm not sure what you mean so if it's basically the iterates of what I'm calling a successor function, they are no less "natural" than the first iterate.

Sorry if I misunderstood.

%so long as whatever function you're using for the successor does NOT have u*, the reference point, in its range, i.e., nothing's successor is u*.

btw, not that it matters much, my condition 3 on a successor function could be stated as something like no elements in the orbit of u* are periodic points of S (of any period). Or, perhaps not as compactly, as the following set is pairwise disjoint:
{{x} : x is in the orbit of u* under S}. Basically my three conditions are trying to generalize the essential characteristics a successor function would have. For example, u* could be the square root of 5, if U is taken to be the set of real numbers, and S(x) = x-1. What I'm thinking is the set
{sqrt(5), sqrt(5) -1, sqrt(5)-2, sqrt(5)-3, ...} is, in some sense, like the usual set of natural numbers (except in this case, the order R I defined would reverse the 'usual' order...I defined the order so that x <= y if y is in the orbit of the successor function applied to x.)

What I meant by "nestedness" (or "nesting") is best described like:

linear: ...{}{}{}{}{}...
nested: nothing, then {}, then {{}}, then{ {}, {{}} } ... etc.A standard visualization of nesting can be seen from the output of, say, a Cellular Automaton like the "Rule 90":[/PLAIN]
http://mathworld.wolfram.com/Rule90.html[/URL]
Or, what can be seen with the bit sequences of successive binary numbers:
[URL="http://www.wolframscience.com/nksonline/page-117"]http://www.wolframscience.com/nksonline/page-117

 

[CRGreathouse]

So, the ability to talk of numbers and the operations on them, and the notion of prime, is essentially due to the power of NESTING?

No. Nesting is a convenient way to model the Peano successor function, but it isn't required -- another method could be used instead.

 

[philiprdutton]

No. Nesting is a convenient way to model the Peano successor function, but it isn't required -- another method could be used instead.

Just a clarification of my thoughts. Sure, there may be other methods besides "nesting" to model the Peano successor function. Actually, I was a bit more keen on the idea that there could be a successor function unlike the Peano successor function- one where there actually is not a reference point (like in the "counting/metronome" system I was trying to describe in earlier posts). Perhaps the thing that distinguishes the Peano successor function from some other successor function is that there might be a reference point in the Peano successor (as it is defined)? More precisely, are all successor functions based on a reference point? Is Peano's?