What Makes Prime Numbers So Mysterious?

[philiprdutton]

ticking

I'm not sure of what you mean by "nested". I think you mean,

x, xx, xxx, xxxx... are numbers​

is "not nested", while

x is a number; also, if A is a number then Ax is a number​

is "nested". I think most people here would say both are one and the same.

But if the system is viewed as an algorithmic process, then how do you distinguish? Especially if we are talking about a system that only can only tick. How can we limit the expressiveness of an axiomatic system so that all you can do is "poke" it so that it "ticks". Can we have a one-to-one input/output system. Axiom systems like Peano have many ways to "input" your "statements" to make them "produce" an output. I do not know how the formal mathemticians talk about the "usage" of the axiomatic systems at this level of abstraction, but I see it with the input/output metaphor.

Nested counting is where at each step of the count, the process starts again from "one."

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

I had to put the numbers in there for visualization but I am saying that I just want a ticking system.

Anyway, Here is my focus:
I want to define a ticking system using the axiomatic method. But, I do not want the system to do anything except tick! No nesting. Can this be done with the axiomatic system or is it too flexible at it's core such that it can not make such limitations? This is a short side study on the nature of axiomatic systems.

 

[NeoDevin]

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

In this system, what differentiates 5 from 2? Other than the fact that they were created by different axioms? This system has no notion of order, unless you explicitly put it in, in which case you get nesting as you put it.

 

[dodo]

In other words, this ticking machine seems to have no internal state. When it ticks and says 'x', there is no way of telling if it is the first 'x', the 5th or the 625th. On the other hand, if it *does* have a state, then you should consider how the state is represented, and call this representation a 'number'.

 

[philiprdutton]

differentiating

In this system, what differentiates 5 from 2? Other than the fact that they were created by different axioms? This system has no notion of order, unless you explicitly put it in, in which case you get nesting as you put it.

Yes. It is my point. You cannot differentiate those numbers. I just put them in the post for sake of moving forth in the discussion. If you view the system as an algorithmic process, then it kind of does have order. Okay. So are you saying that using a formal axiomatic theory, I can not create a ticking system with order AND which does not provide notions of divisibility, prime, and anything else related to numbers or number bases? I am interested in the answer which is why all this time I am not concerned about cool stuff like addition or division.

 

[philiprdutton]

yes

In other words, this ticking machine seems to have no internal state. When it ticks and says 'x', there is no way of telling if it is the first 'x', the 5th or the 625th. On the other hand, if it *does* have a state, then you should consider how the state is represented, and call this representation a 'number'.

You are correct in saying you can not figure out if it is the first 'x' or the 5th 'x' or the 625th 'x'. I said already that I want the user of the system to worry about that. I don't want the user of the system to expect that the system to tell them via some particular feature of the system. They just use the ticking system like a metronome (a metaphor obviously).

Let me put it this way- can there be an axiomatic version of a metronome?

 

[philiprdutton]

internal state

In other words, this ticking machine seems to have no internal state. When it ticks and says 'x', there is no way of telling if it is the first 'x', the 5th or the 625th. On the other hand, if it *does* have a state, then you should consider how the state is represented, and call this representation a 'number'.

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

 

[dodo]

I fail to see how a system with no numbers fits in a number theory forum, but for the sake of the discussion let me provide an example. The boolean operator 'not' behaves as you want. Or, if you prefer, a function f(x) = 1 - x. But unless we begin counting time, or sequence steps, the only thing we produce is the set {0,1}, with no additional structure, operations or functionality.

 

[CRGreathouse]

Yes. It is my point. You cannot differentiate those numbers. I just put them in the post for sake of moving forth in the discussion. If you view the system as an algorithmic process, then it kind of does have order. Okay. So are you saying that using a formal axiomatic theory, I can not create a ticking system with order AND which does not provide notions of divisibility, prime, and anything else related to numbers or number bases? I am interested in the answer which is why all this time I am not concerned about cool stuff like addition or division.

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?

 

[philiprdutton]

building blocks

I fail to see how a system with no numbers fits in a number theory forum, but for the sake of the discussion let me provide an example. The boolean operator 'not' behaves as you want. Or, if you prefer, a function f(x) = 1 - x. But unless we begin counting time, or sequence steps, the only thing we produce is the set {0,1}, with no additional structure, operations or functionality.

The reason is not sake of discussion. The reason is of great importance. 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. So, whether or not you agree with what I am doing, I really need help trying to formalize the tick system without using something that already has notions of "number". Unfortunately, that math education imposed upon us does not even begin to get into these concepts.

Look at the peano system as one holistic system or look at the Peano system in terms of modular building blocks. If you take the modular building block approach then I am saying that before you can construct numbers you have to build on top of the tick system. Therefore, it has lots to do with the topic of Number Theory.

 

[CRGreathouse]

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

Internal state?

 

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