Exploring the Mystery of Prime Numbers

[matt grime]

Eh? This is called a pathetic fallacy (no, that is not an ad hominem attack). What do you mean by 'a function knowing something'? What do you mean by a 'function stopping'. These phrases don't make sense. The successor function takes an integer and produces another one. That we call it the successor is because we're secretly thinking of this as a well ordered set.

 

[CRGreathouse]

He misspoke -- he meant that the finite ordinals are a model of Peano's axioms. Set theory was based on logic; a set, intuitively, is an object that represents the class of all "things" satisfying some condition.

Yes. I meant "the set-theoretic counting model based on the canonical finite ordinals" when I said "set theory".

 

[CRGreathouse]

In the Peano system the recursion seems to be progressing in what I call the "forward" direction on the number line.

Okay, if you like. In that case you're saying that a is "forward" of b iff a = S(b) or a = S(S(b)) or s = S(S(S(b))) or ... That's a definition (essentially, you just defined an ordering on the Peano numbers), and like all proper definitions, it doesn't increase the power of the underlying system.

How does the succession "stop?"

What do you mean? It "stops" immediately; it's an atomic operation. S(4) = 5: one step and it's done.

Are you asking about the behavior of a, S(a), S(S(a)), S(S(S(a))), ...?

 

[philiprdutton]

Okay, if you like. In that case you're saying that a is "forward" of b iff a = S(b) or a = S(S(b)) or s = S(S(S(b))) or ... That's a definition (essentially, you just defined an ordering on the Peano numbers), and like all proper definitions, it doesn't increase the power of the underlying system.
What do you mean? It "stops" immediately; it's an atomic operation. S(4) = 5: one step and it's done.

Are you asking about the behavior of a, S(a), S(S(a)), S(S(S(a))), ...?

If I say out loud, "5", then you have to interpret this in terms of successors (in the context of our discussion). So you say, "Oh yes, you mean S(4)." But actually, S(4) has to be interpreted as S(3)... and so forth till we get to the reference point. So, in this particular direction, things "Stop." I realize "stop" is not a mathematical term but, please relax people: This is a forum, not a mathematical archive of mathematical definitions,symbols, derivations, etc.

Now, clearly, the one "direction" stops, but in cases like recursively defined addition, I am not so clear which direction the recursion is working (on the number line so to speak). I hope this makes sense even though it is in human terms and not the angelic language of formal mathematics.

Does everything in Peano work in the "direction" toward the reference point?

Thanks :) - You gents have been a tremendous help thus far!

 

[CRGreathouse]

If I say out loud, "5", then you have to interpret this in terms of successors (in the context of our discussion). So you say, "Oh yes, you mean S(4)."

No. It's true that S(4) = 5, but 5 is just a symbol. If you're working with just the Peano axioms, you don't know what that symbol is -- it may be a graph, some sets, or whatever else -- but you *do* have something in your model. If you want to use it in your model, you will have some specialized way of doing so -- in the case of the set-theoretic model, S(x) = x U {x}.

Now granted, if you're just working with the axioms and not a model, all you can do with 5 is say that it's S(4) and S(S(3)) and so forth, but each of these does refer to a particular object/symbol/representation -- you just don't know what it is. There is no need to stop here; it really is an atomic operation.

So, in this particular direction, things "Stop." I realize "stop" is not a mathematical term but, please relax people: This is a forum, not a mathematical archive of mathematical definitions,symbols, derivations, etc.

Now, clearly, the one "direction" stops, but in cases like recursively defined addition, I am not so clear which direction the recursion is working (on the number line so to speak). I hope this makes sense even though it is in human terms and not the angelic language of formal mathematics.!

I think you mean that 3 has several representations (3, S(2), S(S(1))) but only the distinguished element "1" has no others -- it's not the successor of anything. But this is only because the axioms let us build the successors of numbers but not predecessors. You could define a system that went both ways, even without using a P symbol:

1. 1 is a number.
2. For every number x, S(x) is a number.
3. For every number x, there is a number y such that S(y) = x.

IDoes everything in Peano work in the "direction" toward the reference point?

As above, it could go both ways ("never stop" in your terminology, I think) except that the Peano axioms don't allow an x with S(x) = 1. Replace that axiom with axiom 3 above, and give a replacement axiom that shows that the elements are distinct, and you'll have a functioning number system.

 

[philiprdutton]

Fact: The Successor function can only move away from the reference point.
Question: Does any aspect of the Peano system utilize the direction toward the reference point?

 

[CRGreathouse]

In a sense, going from 2 to S(1) to show that 1 does not equal 2 is going back. Is that what you mean?

 

[philiprdutton]

peano reverse

In a sense, going from 2 to S(1) to show that 1 does not equal 2 is going back. Is that what you mean?

Yes, perhaps that is an example. Now, if the successor function is not used for that, then what is the mechanism that allows this directional procession? What allows you to go back like that? There is no other function defined and it does not appear to be coming from some feature "underneath" the formal framework of axiomatic systems. So, my guess is that the expressive capabilities of the axioms is what is being used to move backwards in such a case?

(If "moving backward" is not a notion you want to entertain, then perhaps an alternate view is that moving from "2" to S(1) is a symbol decoding function- something that decodes a symbol into it's appropriate parameterized successor-function "call". If so, then are the axioms creating this decoding function?)Thanks for input.

 

[CRGreathouse]

If "moving backward" is not a notion you want to entertain, then perhaps an alternate view is that moving from "2" to S(1) is a symbol decoding function- something that decodes a symbol into it's appropriate parameterized successor-function "call". If so, then are the axioms creating this decoding function?

But in general there is no decoding function, because there is no x where S(x) = 1.

 

[philiprdutton]

something

But in general there is no decoding function, because there is no x where S(x) = 1.

If you can specify in the axioms that there is no x where S(x) = 1, then perhaps you can specify in the axioms a way to "go backward" (toward the reference point). Without a doubt, "Something" is going backward in the Peano system. What exactly is this called?

 

[CRGreathouse]

If you can specify in the axioms that there is no x where S(x) = 1, then perhaps you can specify in the axioms a way to "go backward" (toward the reference point).

Of course this is one of the Peano axioms, yes?

 

[philiprdutton]

What feature of the Peano system "repeatedly" applies the "step" in direction towards the reference point?

 

[CRGreathouse]

What feature of the Peano system "repeatedly" applies the "step" in direction towards the reference point?

Huh? I don't follow. You have the full list of the axioms; why don't you give an example?

 

[philiprdutton]

example

Huh? I don't follow. You have the full list of the axioms; why don't you give an example?

I tried to give a clear example a few posts back. One might say the system is capable of "moving" from "23" to S(22). So, what might you call it when the system keeps on doing this towards the reference point? Is this recursion again? If so, are we correct in saying that the Peano system uses recursion in both directions?

As far as the Peano system is concerned, there can only be 3 possible ways to utilize recursion:

1) always toward the reference point
2) always away from the reference point
3) both directions are utilized.

My question is simply which "scheme" is employed?

 

[CRGreathouse]

I tried to give a clear example a few posts back. One might say the system is capable of "moving" from "23" to S(22). So, what might you call it when the system keeps on doing this towards the reference point? Is this recursion again? If so, are we correct in saying that the Peano system uses recursion in both directions?

As far as the Peano system is concerned, there can only be 3 possible ways to utilize recursion:

1) always toward the reference point
2) always away from the reference point
3) both directions are utilized.

My question is simply which "scheme" is employed?

I think that even in your example the axioms only let you 'move' forward -- you pick 22 because you can then 'move' to S(22) which equals 23.

Going through the axioms, using your order:

1. Has no obvious recursive use; applying repeatedly does not 'move' in either direction.
2. Has no obvious recursive use; applying repeatedly does not 'move' in either direction.
3. Applying repeatedly does not 'move' in either direction.
4. Applying repeatedly does not 'move' in either direction.
5. Has no obvious recursive use; applying repeatedly does not 'move' in either direction.
6. 'Moves' forward.
7. If anything 'moves' backward, this onw dows. what do you think? 'Move' is your term, not mine.
8. Has no obvious recursive use; applying repeatedly does not 'move' in either direction.
9. Either 'move' forward of not at all, your call.

 

[philiprdutton]

cool list

I think that even in your example the axioms only let you 'move' forward -- you pick 22 because you can then 'move' to S(22) which equals 23.

Going through the axioms, using your order:

1. Has no obvious recursive use; applying repeatedly does not 'move' in either direction.
2. Has no obvious recursive use; applying repeatedly does not 'move' in either direction.
3. Applying repeatedly does not 'move' in either direction.
4. Applying repeatedly does not 'move' in either direction.
5. Has no obvious recursive use; applying repeatedly does not 'move' in either direction.
6. 'Moves' forward.
7. If anything 'moves' backward, this onw dows. what do you think? 'Move' is your term, not mine.
8. Has no obvious recursive use; applying repeatedly does not 'move' in either direction.
9. Either 'move' forward of not at all, your call.

This is a nice list. I agree #7 is tricky. More thought required.

In the mean time, I am very curious now about something. When humans speak to each other about numbers we have a few things at our disposal:

1) 10 symbols (in example of decimal)
2) ordered positional data

These allow us to say, "I scored 450,201 points." We can "decode" these symbols and get a precise notion of what the value is that someone is talking about. Now, the Peano system within the confines of formal systems, use "internally" (during a 'move' operation), how many symbols? I first thought, well it has 2 symbols, then I thought, well it has 1 symbol and a successor relation, then I thought, well maybe it just has no symbols. Symbols are just "storage" mechanisms so I started to feel like there should be no need for storage in the abstract systems. So, the symbols that appear in the Peano axioms are just for the convenience of the user and they give the user the ability to temporarily make statements about the system. In other words they are just interface artifacts.

So, my basic novice question is:
Is it true that the Peano system yields no specific functionality for the explicit purpose of encoding a number into some language other than a single symbol language like "A".

In other words if during the middle of some particular Peano system "movement" or operation, if one could say "STOP" and then peek into the system to see what number it is on, then all you see is "A". It just has one symbol and no positions.

 

[CRGreathouse]

Now, the Peano system within the confines of formal systems, use "internally" (during a 'move' operation), how many symbols?

You can answer this question for models of the Peano axioms, but not for the Peano axioms themselves. The set-theoretic model uses braces, commas, and the set membership symbol, for a total of four native symbols. Other systems could be constructed with fewer symbols. The Peano system itself uses symbols like "=" and "1", but these could be written in various ways in the models themselves. For example, set equality could be defined as a = b <==> a in {b} and b in {a}.

In other words if during the middle of some particular Peano system "movement" or operation, if one could say "STOP" and then peek into the system to see what number it is on, then all you see is "A". It just has one symbol and no positions.

Again, this is a question about models and not axiomatic systems.

 

[philiprdutton]

talking

You can answer this question for models of the Peano axioms, but not for the Peano axioms themselves. The set-theoretic model uses braces, commas, and the set membership symbol, for a total of four native symbols. Other systems could be constructed with fewer symbols. The Peano system itself uses symbols like "=" and "1", but these could be written in various ways in the models themselves. For example, set equality could be defined as a = b <==> a in {b} and b in {a}.



Again, this is a question about models and not axiomatic systems.

Okay I think I am starting to get it : )

Basically (correct me if I am wrong) the Peano system defines the numbers in terms of recursion, it let's you "do stuff" with the numbers, BUT it does not equate a symbol (or combination of symbols) to each unique number. I'm guessing the latter part is up to those people who design "numbering systems".

If I am interested in designing a numbering system like "binary" or "hex" or base 60 then I don't even need the Peano axioms. I just need to have a good intuitive notion of a metronome.

Finally, what do mathematicians call the "gray" area in between "numbering systems" and the Peano system? What is it called when you "connect" the two?

 

[CRGreathouse]

Basically (correct me if I am wrong) the Peano system defines the numbers in terms of recursion, it let's you "do stuff" with the numbers, BUT it does not equate a symbol (or combination of symbols) to each unique number. I'm guessing the latter part is up to those people who design "numbering systems".

The axioms are a list of properties any model must have. The particulars of the model can vary, as long as they have everything required.

If you stick only to things specified in the axioms, you don't need a model -- you can show things that hold in all models. Of course you will also find things that can be neither proven nor disproven.

If I am interested in designing a numbering system like "binary" or "hex" or base 60 then I don't even need the Peano axioms. I just need to have a good intuitive notion of a metronome.

At the moment I'm reading your term "metronome" as "recursion", so I agree you need some kind of recursion to produce infinitely many numbers with only finitely many axioms. If you're looking for a way to make decimal numerals, you could do it with a successor mapping function that works on strings of symbols.

Finally, what do mathematicians call the "gray" area in between "numbering systems" and the Peano system? What is it called when you "connect" the two?

I don't know of any such gray area. There are axiom systems like Peano arithmetic and there are their models, which I think is what you mean by "numbering systems". You may mean something else, I don't know.

 

[philiprdutton]

not seeing it

...
...
...
I don't know of any such gray area. There are axiom systems like Peano arithmetic and there are their models, which I think is what you mean by "numbering systems". You may mean something else, I don't know.

Well, I just do not see how a numbering system has anything to do with an axiomatic system. Binary numbering for example is totally independent of the Peano axioms. So, I don't see how it can be considered a model of Peano.

If anyone knows the rules of the numbering system then they can create all the binary numbers mechanically. Likewise, they can also interpret a binary encoding (ex: a number written down on paper) just by following the rules of the binary numbering scheme. I don't see how any of this is related to the Peano axioms at all.

So, when I asked about the "gray area", I should have been more correct in asking, "is there one?" Indeed your answered "I don' think so." This I am now inclined to believe as well. However, you explicitly linked the two systems by saying that a numbering system is a model of Peano. At this point I disagree completely. Perhaps I am missing something?


Thanks.

 

[CRGreathouse]

Well, I just do not see how a numbering system has anything to do with an axiomatic system. Binary numbering for example is totally independent of the Peano axioms. So, I don't see how it can be considered a model of Peano.

Here's a model of the Peano axioms which generally corresponds to binary numbers. I'm quoting terms that come from the axioms. (This way you won't confuse "1", the number from the Peano axioms, with 1, the glyph from the binary numbers,)

A "natural number" is a finite sequence of glyphs, all of which are 0 or 1, and has a 1 in the leftmost position.

"1" is the unique "natural number" with only one glyph. (This meets axiom 1.)

Two "natural numbers" are equal iff they have the same number of glyphs and each corresponding glyph is the same. (This meets axioms 2, 3, 4, and 5.)

The "successor function" flips the last glyph. If it was a 1, move left and repeat the process. If the leftmost digit is flipped and it was a 1, add a 1 glyph to the left. (This meets axioms 6, 7, 8, and 9.)

 

[CRGreathouse]

If anyone knows the rules of the numbering system then they can create all the binary numbers mechanically. Likewise, they can also interpret a binary encoding (ex: a number written down on paper) just by following the rules of the binary numbering scheme. I don't see how any of this is related to the Peano axioms at all.

Sure, and someone can do the same with the Peano axioms, yes? Or are you saying that there's meaning to the binary number "1001010" that the Peano 74 = S(S(S(...(1)...))) lacks?

However, you explicitly linked the two systems by saying that a numbering system is a model of Peano. At this point I disagree completely. Perhaps I am missing something?

Look at my 'binary Peano model' and tell me what you think.

 

[philiprdutton]

meaning

... Or are you saying that there's meaning to the binary number "1001010" that the Peano 74 = S(S(S(...(1)...))) lacks?

I think they have an "equivalence" of sorts. The binary number definitely has meaning: "10001010". It has meaning if you known the numbering scheme. That is to say, it has positional data, and it has an imposed "order" due to the positional data. Actually, the positional data is also due to the reference point (the zero position).

Anyway, this is all very interesting. These two "systems" are so "equivalent." The numbering system requires a way to encode the rules if you want to formalize it (thats a wild guess). So, what do mathematicians call the attempt to link the two systems (or prove they are "equivalent")?

I just see them as two different systems mainly due to the fact that they are "formalized" in different ways. Specifically, I think they are separate entities... one can not be a model of another.

 

[HallsofIvy]

Okay I think I am starting to get it : )

Basically (correct me if I am wrong) the Peano system defines the numbers in terms of recursion, it let's you "do stuff" with the numbers, BUT it does not equate a symbol (or combination of symbols) to each unique number. I'm guessing the latter part is up to those people who design "numbering systems".

If I am interested in designing a numbering system like "binary" or "hex" or base 60 then I don't even need the Peano axioms. I just need to have a good intuitive notion of a metronome.

Finally, what do mathematicians call the "gray" area in between "numbering systems" and the Peano system? What is it called when you "connect" the two?

Do you mean numeration system? You need the Peano Axioms to have NUMBERS- regardless of what base or Roman numerals or other numeration system you use for them. Numeration systems are just symbols you use for the numbers.

 

[CRGreathouse]

So, what do mathematicians call the attempt to link the two systems (or prove they are "equivalent")?

The literal answer to your question, I think, is equiconsistency -- the idea that for systems A, B, we have A + cons(A) ==> cons(B) and B + cons(B) ==> A, where cons(X) means that system X is consistent. (Would someone check my informal definition here?)

This doesn't apply to my model and the Peano axioms, because my model is just a model (not a system). You may have a system in mind based on or similar to my model, and that might be equiconsistent with Peano arithmetic, though; you'd have to be more explicit before I could comment.

I just see them as two different systems mainly due to the fact that they are "formalized" in different ways. Specifically, I think they are separate entities... one can not be a model of another.

It's easy to construct a model of a weak system in a strong one. ZFC can model Peano arithmetic.

 

[mathwonk]

why do these flaky threads get so many hits? or for that matter, why does the national enquirer sell more copies than the ny times?

 

[HallsofIvy]

But I am confused as to why all the peano axioms start out with "if b is a natural number"... Am I missing something? I read Peano and feel as if he assumes all the natural numbers are set into position on the number line even before he finishes all the axioms. I figured his successor function was just a means of getting around. It gets confusing like the chicken and egg dilemma.

Primes, squares, addition, fractions, etc. all have to do with permitted "operations." But I still believe the natural numbers are still implicitly defined and do sit in place on the number line whether the operational axioms are defined yet or not.

?? The Peano axioms do not start out with "if b is a natural number" nor does Peano "assume all the natural numbers are set into position on the number line" (I have never seen any mention of "number line" in anything to do with Peano axioms). Peano's axioms DEFINE the natural numbers: the natural numbers are any set of things, together with a "successor function" that satisfies the Peano axioms.

 

[philiprdutton]

kind of my point

?? The Peano axioms do not start out with "if b is a natural number" nor does Peano "assume all the natural numbers are set into position on the number line" (I have never seen any mention of "number line" in anything to do with Peano axioms). Peano's axioms DEFINE the natural numbers: the natural numbers are any set of things, together with a "successor function" that satisfies the Peano axioms.

Sure Peano does not mention the number line. The problem that I have is that the "structure"... or shall I say "Scaffolding" of the traditional number line and the peano system are so so so so so so so close. I wanted to explore the link- try to build the common baseline structure between the two systems and see what you have. Then explore what it means to add in the additional "structure" which give you the two unique systems. I just can't help but want to explore the "intersecting scaffolding." I tried to explore this idea in earlier posts but it was a little bit of a challenge in terms of communication.

 

[HallsofIvy]

So basically what you are saying is that you do not understand what Peano's axioms are and how they give the natural numbers.

 

[phoenixthoth]

It seems odd that a definition of natural numbers would start with 1 is a natural number. (Or 0 if you like.) It seems simultaneously circular and a bit unclear (what is 1?).

The word structure is a bit vague to me, but if we're talking about orderings, then they aren't a part of the Peano axioms. After defining the natural numbers with the Peano axioms, one could then define various orders on the set, including the usual order which would say that n < m iff m is in the orbit of n under the successor function (i.e., there is a kth iterate of the successor function that when applied to n yields m). If one defines 1 to be the singleton containing the empty set, then the usual order does not have to be defined in this way: n < m iff n is an element of m. (That would work if the successor function is defined so that the successor of z is the union of z and the singleton containing z.) Anyway, order (which is what I think is meant by structure) is not a part of the definition but can be developed using the same tools used in the definition. One advantage of not inserting an order in the definition is to allow one to use unusual orders, if one so desires.

 

[CRGreathouse]

why do these flaky threads get so many hits? or for that matter, why does the national enquirer sell more copies than the ny times?

It's amusing to find order in chaos.

 

[CRGreathouse]

It seems odd that a definition of natural numbers would start with 1 is a natural number. (Or 0 if you like.) It seems simultaneously circular and a bit unclear (what is 1?).

1 is anything you like, as long as it performs as the axioms require. That's the strength of the axiomatic system.

 

[mathwonk]

found any lately?

 

[dodo]

I wanted to explore the link- try to build the common baseline structure between the two systems ...

I believe the idea of the Peano axioms is to BE that common baseline - for the integer numbers, as well as for strings of xxxx, or for other artifices that satisfy the axioms.

 

[philiprdutton]

orderings are there

It seems odd that a definition of natural numbers would start with 1 is a natural number. (Or 0 if you like.) It seems simultaneously circular and a bit unclear (what is 1?).

The word structure is a bit vague to me, but if we're talking about orderings, then they aren't a part of the Peano axioms. After defining the natural numbers with the Peano axioms, one could then define various orders on the set, including the usual order which would say that n < m iff m is in the orbit of n under the successor function (i.e., there is a kth iterate of the successor function that when applied to n yields m). If one defines 1 to be the singleton containing the empty set, then the usual order does not have to be defined in this way: n < m iff n is an element of m. (That would work if the successor function is defined so that the successor of z is the union of z and the singleton containing z.) Anyway, order (which is what I think is meant by structure) is not a part of the definition but can be developed using the same tools used in the definition. One advantage of not inserting an order in the definition is to allow one to use unusual orders, if one so desires.

Actually, I disagree with you when you say that "oderings are not part of the Peano axioms." The problem is that recursion uses an ordering whether you like it or not. It does not "look" like our standard notion of "ordering" but I believe it is there.