What Makes Prime Numbers So Mysterious?

[CRGreathouse]

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?

I don't get it. I did explain that if you take away the starting point ("1" or "0") you get the same system, one with ur-elements, or an empty collection. Do you mean something distinct from this? Perhaps you mean a system like this:

1. For each number n, S(n) exists.
2. For each number n, P(n) exists.
3. For each number n, S(P(n)) = n.

which could be a model of the integers instead of the natural numbers?

 

[philiprdutton]

somehow

I don't get it. I did explain that if you take away the starting point ("1" or "0") you get the same system, one with ur-elements, or an empty collection. Do you mean something distinct from this? Perhaps you mean a system like this:

1. For each number n, S(n) exists.
2. For each number n, P(n) exists.
3. For each number n, S(P(n)) = n.

which could be a model of the integers instead of the natural numbers?

Actually, I did absorb your explanation about taking away the starting point ("1" or "0") and getting the same system. So, I am wondering where exactly the "reference point" is (in the Peano system).

Do you mean something distinct from this?

Yes, I did mean something distinct from the explicit Peano axiom. For the pseudo-description of the system you give above, I don't see how there is a reference point to "1" or "0" or whatever you call it that starts the natural numbers. So, perhaps that is a candidate of what I was talking about when I was was saying:

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?

 

[CRGreathouse]

For the pseudo-description of the system you give above, I don't see how there is a reference point to "1" or "0" or whatever you call it that starts the natural numbers. So, perhaps that is a candidate of what I was talking about when I was was saying:

Well that system isn't strong enough to prove that there are numbers, but if at least one exists than you effectively have the integers. In fact, you may have more than one mutually-disjoint 'number lines' -- it's possible that you have 0 and 0', where 0'≠0, 0'≠S(0), 0'≠P(0), 0'≠S(S(0)), 0'≠P(P(0)), etc. you may even have infinitely many disjoint 'number lines'.

 

[philiprdutton]

Well that system isn't strong enough to prove that there are numbers, but if at least one exists than you effectively have the integers. In fact, you may have more than one mutually-disjoint 'number lines' -- it's possible that you have 0 and 0', where 0'≠0, 0'≠S(0), 0'≠P(0), 0'≠S(S(0)), 0'≠P(P(0)), etc. you may even have infinitely many disjoint 'number lines'.

It may not be strong enough to have numbers. However, it's core structure has some similarity with the core structure (or form) of that which exists with a number system- specifically, that "philosophically" speaking, you can view a number as just a "thing" that happens to have a "successor" and a "predecessor" (and which is also a "successor" and a "predecessor"). If you think about numbers in terms of graph theory, a number is a node with two edges. The edges connect to other nodes... and so forth. Each edge is used by the successor and predecessor functions (whatever those are). So, in this case, should one define the number with an edge-centric definition or a node centric definition? It is hard to think about which way to define a number. Perhaps you define it in terms of BOTH.

This is kind of what I feel happens in number systems. Now, with this graph theory experiment, you can not define a number until you define a reference point.

still being resolved:

1) Are all successor functions based on a reference point? Is Peano's?
2) Can nesting exist without a reference point?
3) Do any alternate formalizations of the natural numbers effectively use nesting? (such as what might be considered a set-theoretric formalization where one attempts to use {},{{}},{{{}}},.. where {} is the empty set.)
4) What are some examples of formal systems which actually use a reference point (field,border,group,whatever)? Does Peano's system use a reference point?​

 

[CRGreathouse]

It may not be strong enough to have numbers. However, it's core structure has some similarity with the core structure (or form) of that which exists with a number system- specifically, that "philosophically" speaking, you can view a number as just a "thing" that happens to have a "successor" and a "predecessor" (and which is also a "successor" and a "predecessor").

You misunderstand. If there is "something" there, I'm calling it a number. (You may have another term for it.) The system isn't strong enough to show that there is anything there at all.

If you think about numbers in terms of graph theory, a number is a node with two edges. The edges connect to other nodes... and so forth. Each edge is used by the successor and predecessor functions (whatever those are). So, in this case, should one define the number with an edge-centric definition or a node centric definition? It is hard to think about which way to define a number. Perhaps you define it in terms of BOTH.

Of course this leads to the possibility of generalizing the concept of number my using multivalued functions for S and P, graph-theoretically allowing for more than two edges. (To keep the graph theory sound, remember that the underlying structure is a digraph not a graph.)

I can't see how defining numbers in terms of edges instead of points changes anything.

Does Peano's system use a reference point?

Huh? Of course it does, "1 is a natural number". Do I misunderstand the question?

3) Do any alternate formalizations of the natural numbers effectively use nesting? (such as what might be considered a set-theoretric formalization where one attempts to use {},{{}},{{{}}},.. where {} is the empty set.)

Hmm... I had a thought that might let you express yourself better with the mathematicians here. Perhaps by "nesting" you mean "recursion"? If not, explain what you mean by nesting again (and what its relationship is to recursion: is one a subset of the other or are they disjoint?).

 

[philiprdutton]

recursion = nesting?

Huh? Of course it does, "1 is a natural number". Do I misunderstand the question?

You are talking about the reference point in terms of the numbers that the system gives you. I am talking about the system's reference point in terms of the construction of the formal system. Where specifically is the reference point defined? Not, "how can I define the reference point in terms of the objects the system creates."

In other words, why is "1 is a natural number" the reference point? We pegged this question before and ended up in totally different formalizations of the natural numbers. This is why, when looking at the Peano axioms I do not see an explicit axiom that defines the reference point. You said already you can take out the "0/1 is a natural number" axiom and still have a working system. So, maybe the reference point is somehow already hardwired into the Peano successor function? This is why I asked what makes the Peano' successor function special in comparision to some other successor function? Is the Peano successor function equipped already with a reference point?

Can you tell me what the Peano successor function is seperately from the Peano axioms? Did Peano axioms create the successor function?

Also, yes it is possible that nesting and recursion are the same phenomenon. I will have to think about it a while longer however. Is the Peano successor function simply recursion? I can't understand what recursion would be if there was not a reference point.

 

[philiprdutton]

side note on graph theory

If you think about numbers in terms of graph theory, a number is a node with two edges. The edges connect to other nodes... and so forth. Each edge is used by the successor and predecessor functions (whatever those are). So, in this case, should one define the number with an edge-centric definition or a node centric definition? It is hard to think about which way to define a number. Perhaps you define it in terms of BOTH.

Of course this leads to the possibility of generalizing the concept of number my using multivalued functions for S and P, graph-theoretically allowing for more than two edges. (To keep the graph theory sound, remember that the underlying structure is a digraph not a graph.)

Using the graph theory construction you eventually have to have a reference node before you can begin to say anything about what node represents a given number. That is why I brought it up. So, somehow, a graph theoretician would specify this reference. Likewise, with the Peano axioms, when/where in the construction of the system is the reference defined? Or maybe it isn't because a reference point is already implicitly given in the successor function he was using. Is the Peano successor function recursion? Does raw and pure recursion have a reference point?

 

[CRGreathouse]

You are talking about the reference point in terms of the numbers that the system gives you. I am talking about the system's reference point in terms of the construction of the formal system. Where specifically is the reference point defined? Not, "how can I define the reference point in terms of the objects the system creates."

But "1" could be anything in the Peano axioms -- unlike, say, the standard set-theoretic "1", which is {{}}. The Peano "1" exists only because there's an axiom that says it does, which doesn't tell us anything about it.

In other words, why is "1 is a natural number" the reference point? We pegged this question before and ended up in totally different formalizations of the natural numbers.

Qua?

This is why, when looking at the Peano axioms I do not see an explicit axiom that defines the reference point. You said already you can take out the "0/1 is a natural number" axiom and still have a working system.

I don't know that I said that. Without that axiom you could easily have no numbers, in which case you can't use the successor operation (because it applies only to numbers) or induction (because it requires numbers, and specifically 1). In fact in that case no axiom has any meaning at all.

That is, in every system you can construct that has no numbers, the Peano axioms are true. *Any* numberless system at all.

Can you tell me what the Peano successor function is seperately from the Peano axioms?

Sure, it gives you the "next" number. The axioms define just what that means, but this is the philosophical meaning.

Also, yes it is possible that nesting and recursion are the same phenomenon. I will have to think about it a while longer however. Is the Peano successor function simply recursion? I can't understand what recursion would be if there was not a reference point.

The successor function can be applied to something that has the successor function applied to it, which is a recursive use of the function. Is "nesting" just any such use of a function, or is it specific in some way to the successor?

 

[CRGreathouse]

Using the graph theory construction you eventually have to have a reference node before you can begin to say anything about what node represents a given number. That is why I brought it up. So, somehow, a graph theoretician would specify this reference. Likewise, with the Peano axioms, when/where in the construction of the system is the reference defined? Or maybe it isn't because a reference point is already implicitly given in the successor function he was using. Is the Peano successor function recursion? Does raw and pure recursion have a reference point?

Recursion has to work on something, so if by reference point you mean "something", then yes. If you mean "a distinguished point that is the unique 'beginning' of the numbers" then no, you don't need that.

Why do you say the graph needs a reference point? Perhaps I simply don't understand your neologisms.

The Peano successor function isn't recursion, but you can use it recursively.

 

[philiprdutton]

graph reference point.

Why do you say the graph needs a reference point? Perhaps I simply don't understand your neologisms.

Well basically here is the graph we talked about:
(in vertical form- my horizontal ascii graph didn't work right.):

.
.
.
\
0 << node
/
0 << node
\
0 << node
/
0 << node
\
.
.
.It is a crude representation but anyway, where is the node which represents "zero" or "one" ? I was saying that you can not look at any nodes and talk about what they are (in terms of numbers) until after you define the reference point (or reference node).

 

[CRGreathouse]

It is a crude representation but anyway, where is the node which represents "zero" or "one" ? I was saying that you can not look at any nodes and talk about what they are (in terms of numbers) until after you define the reference point (or reference node).

But the same could be said for set theory, right?

{}
{{}}
{{}, {{}}}
{{}, {{}}, {{}, {{}}}}
{{}, {{}}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}}}
. . .
S(n) = n U {n}

 

[philiprdutton]

yes

But the same could be said for set theory, right?

{}
{{}}
{{}, {{}}}
{{}, {{}}, {{}, {{}}}}
{{}, {{}}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}}}
. . .
S(n) = {n, {n}}

I think the set theory version has a reference point: The empty set.

 

[CRGreathouse]

Yes. That is exactly my point.

In both cases, there's no need for a special element. *Any* element would suffice. Without the axiom "1 is a number", you don't know that there are any numbers (or nodes). If, instead, you have as an axiom "A number exists", then you have a nonconstructive system that may have non-numbers preceding numbers (unless you have a P operator). Without that nonconstructive axiom, you may have no numbers at all, a system with non-numbers that eventually become numbers with enough uses of the S operator, or a system just like the Peano one.

So, to answer your question about when the reference point is defined, I'll let you pick which of the three situations you'll allow.

 

[philiprdutton]

In both cases, there's no need for a special element. *Any* element would suffice. Without the axiom "1 is a number", you don't know that there are any numbers (or nodes). If, instead, you have as an axiom "A number exists", then you have a nonconstructive system that may have non-numbers preceding numbers (unless you have a P operator). Without that nonconstructive axiom, you may have no numbers at all, a system with non-numbers that eventually become numbers with enough uses of the S operator, or a system just like the Peano one.

So, to answer your question about when the reference point is defined, I'll let you pick which of the three situations you'll allow.

Actually I do think the set theory version has a reference point: the empty set. The "0" (or "1") of the set theory version is the empty set. All other sets include at least one empty set, therefore they are not empty. Just that first one. In this case, I am not required to speak of numbers at all in order to talk about this reference point.

 

[CRGreathouse]

Actually I do think the set theory version has a reference point: the empty set. The "0" (or "1") of the set theory version is the empty set. All other sets include at least one empty set, therefore they are not empty. Just that first one. In this case, I am not required to speak of numbers at all in order to talk about this reference point.

Yes, set theory has a special point you can pick. But it doesn't need to be that special element for the Peano axioms to hold -- you could even choose {{{}}} as your element "1", even though it's not on the standard list of ordinal sets. You just need somewhere to start.

 

[philiprdutton]

falling out

Yes, set theory has a special point you can pick. But it doesn't need to be that special element for the Peano axioms to hold -- you could even choose {{{}}} as your element "1", even though it's not on the standard list of ordinal sets. You just need somewhere to start.

I really think that the nested set theory version makes the reference point sort of fall out naturally. You don't need to pick. Think about it, if, as you suggested, you choose {{{}}} as your element "1", then were will you "store" this piece of information? With the nested set theory version, you don't even need to encode this information because the empty set is a natural boundry or reference point... all because of the nested nature of the setup. So, back to Peano, is the reference explicitly stated or is it implicitly defined? I have to go back through a few posts here to find the first attempt at this answer.

 

[CRGreathouse]

I really think that the nested set theory version makes the reference point sort of fall out naturally. You don't need to pick. Think about it, if, as you suggested, you choose {{{}}} as your element "1", then were will you "store" this piece of information? With the nested set theory version, you don't even need to encode this information because the empty set is a natural boundry or reference point... all because of the nested nature of the setup. So, back to Peano, is the reference explicitly stated or is it implicitly defined? I have to go back through a few posts here to find the first attempt at this answer.

I agree that the empty set is natural; I just wanted to make clear that it isn't needed -- any set, even one that isn't an ordinal, will work.

If I understand correctly, it is impossible to answer your question for Peano. I can answer for set theory because it is a model of Peano arithmetic, but I can only answer for this and other models -- in some models of Peano arithmetic it's explicitly defined, while in others it's "natural".

 

[philiprdutton]

I agree that the empty set is natural; I just wanted to make clear that it isn't needed -- any set, even one that isn't an ordinal, will work.

If I understand correctly, it is impossible to answer your question for Peano. I can answer for set theory because it is a model of Peano arithmetic, but I can only answer for this and other models -- in some models of Peano arithmetic it's explicitly defined, while in others it's "natural".

So, Uhm, are we essentially saying that there are no models of Peano arithmetic that do not have said reference point?



PS: I had no idea that set theory was based on Peano arithmetic. I guess Cantor created it after the Peano axioms?

 

[Hurkyl]

So, Uhm, are we essentially saying that there are no models of Peano arithmetic that do not have said reference point?

Yes -- the existence of an initial element is explicitly stated as an axiom.

 

[Hurkyl]

PS: I had no idea that set theory was based on Peano arithmetic. I guess Cantor created it after the Peano axioms?

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.

 

[philiprdutton]

initial element

Yes -- the existence of an initial element is explicitly stated as an axiom.

Is there a particular "word" in the literature that refers to this "initial element" (or reference point)?? I feel it is so crucial yet so hard to talk about.

 

[Hurkyl]

Is there a particular "word" in the literature that refers to this "initial element" (or reference point)?? I feel it is so crucial yet so hard to talk about.

Yes: typically, one goes so far as to choose a single character to represent it. '0' and '1' are common choices, though I'm sure I've seen authors use other symbols like 'a', 'i', 'e', or even '\epsilon' if they are worried about a conflict of notation, or simply to reduce the possibility of confusing the reader.

For flavor, I will use the symbol 'v' in this post. I will use 'S' for the successor function.

One of Peano's axioms states that v \neq Sx, no matter what x is.

Incidentally, a minimalist might not even give the initial element a name -- they would adjust the above axiom to assert that there exists some object with that property.


The reason one might call v the 'initial element' is that it's traditional to define a total ordering on the natural numbers (traditionally called '<') such that x < Sx for any x. One can then prove that v is, in fact, the smallest element relative to this particular total ordering.

 

[philiprdutton]

ahh i see

Yes: typically, one goes so far as to choose a single character to represent it. '0' and '1' are common choices, though I'm sure I've seen authors use other symbols like 'a', 'i', 'e', or even '\epsilon' if they are worried about a conflict of notation, or simply to reduce the possibility of confusing the reader.

For flavor, I will use the symbol 'v' in this post. I will use 'S' for the successor function.

One of Peano's axioms states that v \neq Sx, no matter what x is.

Incidentally, a minimalist might not even give the initial element a name -- they would adjust the above axiom to assert that there exists some object with that property.The reason one might call v the 'initial element' is that it's traditional to define a total ordering on the natural numbers (traditionally called '<') such that x < Sx for any x. One can then prove that v is, in fact, the smallest element relative to this particular total ordering.

Thank you for the clear explanation. This very feature of number systems is what I have been thinking about much lately. In particular, I wanted to explore the idea that "primality" can perhaps alternatively be studied from the perspective of the "reference" feature in a system. The majority of people tend to study primes in terms of well defined arithmetic operations or distribution properties, etc. What I am saying is that the whole "family" of systems which use a reference point quite possibly exhibit similar behavior. Perhaps that "family" of systems will be very broad. This I do not know because I am not a professional mathematician and I have not properly surveyed the systems.

I feel that primes have been so clearly defined (for thousands of years perhaps). The definition in the literature is so clear. The idea that numbers can be broken down into various primes is also clear. Do not forget that everything that can be done with the Peano system is in terms of the reference point. Therefore, if "prime" is such a basic feature, then it probably shows up in other mathematic systems which use a reference point (possibly in combination with "nesting"/recursion). If those systems do not define numbers, then we must view the "primality notion" without traditional "institutionalization" of numbers. I am quite ambitious and confident that the "effect" is going to be there in many systems.

The reason one might call v the 'initial element' is that it's traditional to define a total ordering on the natural numbers (traditionally called '<') such that x < Sx for any x. One can then prove that v is, in fact, the smallest element relative to this particular total ordering.

I clearly see now that any attempt to define the natural numbers with some particular formal system will require the ordering to be "installed" (hence the reference point). Would I be correct in asserting that the set theoretic version of the natural numbers just encodes the ordering into the nesting (recursion- where {} is the reference point). My understanding is that a set's elements can not be ordered. But, if a set can contain a set, then you can take advantage of that and place your "ordering" in that feature.

Anyway, some questions:

-Do most of the standard formal systems use a reference point?
-What standard systems do not?
-Where does the set theoretic version of Peano encode the impose the ordering? (or by what feature of set theory)? I just want to make sure I totally understand this.Thanks a million!

 

[Hurkyl]

There is something called a pointed set. It is simply a set with a 'distinguished' element. Such an object has no structure whatsoever, aside from the fact that one of its elements is 'distinguished'. The simplest way to define such a thing is

A pointed set is a pair (S, x), where S is a set and x is an element of S.

If you wanted a formal system instead, then the theory of a pointed set is presented simply by specifying that the language has a constant symbol. (usually, '*' is used) In particular, no axioms are given -- this theory consists only of tautologies.

Pointed topological spaces are a useful object for some purposes. As the name suggests, it's simply a topological space with a distinguished point. A familiar example would be a Euclidean line or plane with a specified origin.

But these things don't really have a notion of "primeness".



Incidentally, Peano's axioms don't yield a notion of primeness either -- there are lots of ways to put an ordering or an algebraic structure on an object satisfying Peano's axioms. For example, one can define addition recursively by:

a + v = v
a + S(b) = S(a + b)

(often, one would use the symbol '0' instead of 'v' if one intends to use this definition of addition)

or, one might define addition by

a + v = S(v)
a + S(b) = S(a + b)

(and one would typically use the symbol '1' instead of 'v')

One could even define addition so that v+v is undefined, and

S(a) + v = a
v + S(b) = b
a + S(b) = S(a + b)

(one might use the symbol '-1' instead of 'v' if one were to adopt this definition)

For the above examples I was using S as if it were an "add one" operation -- but one could define an addition operation in an entirely different way, if one so desires!

The point is that primeness doesn't automatically make sense -- it is only meaningful relative to an algebraic structure.



The (usual) ordering on the ordinal numbers is indeed given by containment: \alpha &lt; \beta if and only if \alpha \subseteq \beta. And for the usual set-theoretic model of the natural numbers, this ordering does agree with the usual ordering on the natural numbers.

Incidentally, the main practical reason for studying ordinal numbers is that they are very useful for analyzing and proving things -- the practical content of the fact the finite ordinals model the natural numbers is that it allows us to transfer our expertise with natural numbers into a set-theoretic context.



Probably the most pervasive notion of "primeness" in mathematics is that of a prime element in a lattice. For example, the notion of primeness you're familiar with -- primeness of integers -- is a special case of this. You can organize the positive integers into a lattice by defining a \leq b if and only if a divides b. Or equivalently, by defining a \vee b = lcm(a, b) and a \wedge b = gcd(a, b).

 

[philiprdutton]

okay

Thanks for the quick information. I am grateful.

The point is that primeness doesn't automatically make sense -- it is only meaningful relative to an algebraic structure.

Yes, I agree.

I had one more question about natural number systems which use a reference point and recursion("or nesting"). In the Peano system the recursion seems to be progressing in what I call the "forward" direction on the number line. This seems pretty obvious due to the fact that their is a function which happens to be called "successor" function. Now, this question is a bit hard to verbalize but I will give it a shot:

How does the succession "stop?"

I can see how in each step of the succession, the system might just start over at the reference object and start to step again using the successor function. But I do not see how it can know to stop as might be required when performing operations like addition/multiplication.

 

[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.