What Makes Prime Numbers So Mysterious?

[CRGreathouse]

we defined a "counting" style, infinite statement axiomatic system which you have no notion of multiplication nor successor function (as in the above posts). We have another system like Peano. Both systems produce something that lies on the same place on the number line. We use mapping to link the two systems through the "number line." Now, despite the mapping (if it is possible), you can not impose the notion of prime on the simpler system. Hence, the notion of "prime" is directly related to the mechanisms of addition/multiplication or other operations... NOT the actually position on the number line thing.

But of course. I can also set up a linking from the "counting" (on the left) to Peano Arithmetic (on the right) like so:

1 <--> 3
2 <--> 2
3 <--> 1
4 <--> 6
5 <--> 5
6 <--> 4
7 <--> 9
. . .

The mapping is perfectly reasonable, and all properties (i.e. none) that held in the counting system still hold in Peano arithmetic. The counting numbers that are prime in PA, though, are 1, 2, 5, and so on -- not at all the same.

 

[philiprdutton]

branches

But of course. I can also set up a linking from the "counting" (on the left) to Peano Arithmetic (on the right) like so:

1 <--> 3
2 <--> 2
3 <--> 1
4 <--> 6
5 <--> 5
6 <--> 4
7 <--> 9
. . .

The mapping is perfectly reasonable, and all properties (i.e. none) that held in the counting system still hold in Peano arithmetic. The counting numbers that are prime in PA, though, are 1, 2, 5, and so on -- not at all the same.

May I ask how you start with 3 and then get 2... 1,6,5,4,9?

Also, is the counting system single branch (of statements) as opposed to a multi-branch PA tree of types of statements? If each axiom in PA can produce a certain amount of statements then that set of statements is what I am informally calling a branch. Since the counting system only has one way to make statements it is single branch.

 

[dodo]

If you want to play "da da da da" for a while, stress one "da" of every N, as in "da da DA da da DA ..."; if you put them all together,

2 da DA da DA da DA da DA da DA da DA da ...
3 da da DA da da DA da da DA da da DA da da DA ...
4 da da da DA da da da DA da da da DA da da da DA ...
5 da da da da DA da da da da DA da da da da DA da da da da DA ...
6 da da da da da DA da da da da da DA da da da da da DA ...
7 da da da da da da DA da da da da da da DA da da da da da da DA ...

a prime number is one where the first stressed DA's won't coincide with any DA for all smaller numbers.

(Which of course is a re-edition of the [/PLAIN]
Sieve of Eratosthenes.)

 

[CRGreathouse]

May I ask how you start with 3 and then get 2... 1,6,5,4,9?

Yes, but that would be beside the point. They have no properties, so there's nothing making the counting "2" more or less like the Peano "2" than the Peano "7". I can put them in any order I want -- and in fact I could associate them with only the Peano primes, or only the Peano composites, or only the Peano powers of 2 that are squares.

Also, is the counting system single branch (of statements) as opposed to a multi-branch PA tree of types of statements? If each axiom in PA can produce a certain amount of statements then that set of statements is what I am informally calling a branch. Since the counting system only has one way to make statements it is single branch.

Terminology. Remember that both Peano arithmetic and your counting system have an infinite number of axioms -- you have one axiom schema, which actually has omega members (one for each natural number). So yes, each of your axioms has only one statement it can make, but you can make an infinite number of statements.

That aside, I'm still not sure I quite follow. What is the motivation behind the branch terminology?

 

[Hurkyl]

Incidentally, as far as formal logic is concerned, the axiomatic method is merely a convenient way for presenting formal theories. There is no inherent quality of a statement that determines whether or not it is an axiom -- it's simply an artifact of the way the formal theory is presented.

 

[philiprdutton]

creating a number system

If you want to play "da da da da" for a while, stress one "da" of every N, as in "da da DA da da DA ..."; if you put them all together,

2 da DA da DA da DA da DA da DA da DA da ...
3 da da DA da da DA da da DA da da DA da da DA ...
4 da da da DA da da da DA da da da DA da da da DA ...
5 da da da da DA da da da da DA da da da da DA da da da da DA ...
6 da da da da da DA da da da da da DA da da da da da DA ...
7 da da da da da da DA da da da da da da DA da da da da da da DA ...

a prime number is one where the first stressed DA's won't coincide with any DA for all smaller numbers.

(Which of course is a re-edition of the [/PLAIN]
Sieve of Eratosthenes.)

Okay, so basically you just created a numbering system. Given the counting system you just added some machinery to give you the ability to talk about where you stopped counting. Once you do this you can start looking at the patterns produced and start theorizing and start writing conjectures. But all that you discover is not related to the place on the number line. It is related to the nature of the extra machinery.

 

[philiprdutton]

a race

Yes, but that would be beside the point. They have no properties, so there's nothing making the counting "2" more or less like the Peano "2" than the Peano "7". I can put them in any order I want -- and in fact I could associate them with only the Peano primes, or only the Peano composites, or only the Peano powers of 2 that are squares.



Terminology. Remember that both Peano arithmetic and your counting system have an infinite number of axioms -- you have one axiom schema, which actually has omega members (one for each natural number). So yes, each of your axioms has only one statement it can make, but you can make an infinite number of statements.

That aside, I'm still not sure I quite follow. What is the motivation behind the branch terminology?

Basically, I meant to say that you "start" the counting system. You also "start" to count USING the Peano system. Now, for each step, there will be a result for each system. Let's say that there is a set of results for the counting system and a set of results for the Peano system WHEN USED as a counting system. Now, just map the two systems formally with these results in mind. If this could be done, then I guess you can say the two systems are equivalent in the sense of those sets of results. However, you can not impose the notion of prime from the Peano set of results back over to the counting system. That is all I am wanting to do. And I want to know what it means for the notion of primality. Just trying to open up discussion about all this in layman's terms.

 

[CRGreathouse]

But all that you discover is not related to the place on the number line. It is related to the nature of the extra machinery.

Of course some could argue -- and I think I would -- that this extra machinery is the number line, not the counting axiom schema. So far that's not even strong enough to tell us that "2" comes after "1".

 

[dodo]

I don't think there was too much extra machinery. I just replaced his notation (da da da <end> for the number 3) for another more easy to type (da da DA for 3), and defined addition as the concatenation of sequences, which is only natural when counting "da da da".

The prime definition, on the old notation, would not change the concept. It would say, "a prime is a number where the first 'da<end>' do not coincide with any 'da<end>' for smaller numbers". I merely replaced 'da<end>' by 'DA', and defined addition. The fact that you don't explicitly mention the <end> at the end does not make the concept of 'end' disappear.

 

[philiprdutton]

strong enough

Of course some could argue -- and I think I would -- that this extra machinery is the number line, not the counting axiom schema. So far that's not even strong enough to tell us that "2" comes after "1".

So, if the extra machinery is the number line, then Peano might possibly might not have been biased by an intuitive notion of a number line? Given Peano axioms (we just happen to be using Peano axioms for sake of discussion) what do they do (in context of discussion)? Do they:

A) create the number line?
-- or --
B) create the facility to "talk" about the number line?

 

[philiprdutton]

primes: what is it?

I don't think there was too much extra machinery. I just replaced his notation (da da da <end> for the number 3) for another more easy to type (da da DA for 3), and defined addition as the concatenation of sequences, which is only natural when counting "da da da".

The prime definition, on the old notation, would not change the concept. It would say, "a prime is a number where the first 'da<end>' do not coincide with any 'da<end>' for smaller numbers". I merely replaced 'da<end>' by 'DA', and defined addition. The fact that you don't explicitly mention the <end> at the end does not make the concept of 'end' disappear.

Are you saying that you are in agreement that the notion of prime is not due to a strict position on the "number line" (whatever the hell a number line is) and instead it is due to structure of the 'meta-data" you are adding when you change the appearance from "da" to "DA"?

 

[CRGreathouse]

Are you saying that you are in agreement that the notion of prime is not due to a strict position on the "number line" (whatever the hell a number line is) and instead it is due to structure of the 'meta-data" you are adding when you change the appearance from "da" to "DA"?

I think that once you put connections in between the numbers (so that "3" is right between "2" and "4", where in your axiom schema right now there's nothing special connecting the three) you can form the concept of primes.

 

[philiprdutton]

positions

I think that once you put connections in between the numbers (so that "3" is right between "2" and "4", where in your axiom schema right now there's nothing special connecting the three) you can form the concept of primes.

Actually I do not want to be able to have the concept of primes. That is why I left it as a counting system. Leaving it that way, I want to map the bare counting system to the Peano system's version of the counting system. After all, I am assuming that the Peano system can indeed "simulate" the bare counting system. Is this possible? Yes I think it is. Why do it? For the sake of understanding the notion of "prime" separate from the notion of the position of the "item" on the "number line."

 

[CRGreathouse]

Actually I do not want to be able to have the concept of primes. That is why I left it as a counting system. Leaving it that way, I want to map the bare counting system to the Peano system's version of the counting system. After all, I am assuming that the Peano system can indeed "simulate" the bare counting system. Is this possible? Yes I think it is. Why do it? For the sake of understanding the notion of "prime" separate from the notion of the position of the "item" on the "number line."

But your line doesn't have position right now. "7" is just as close to "1048576000000000" as it is to "6".

 

[philiprdutton]

Algorithmically speaking... I can just as easily interpret the Peano axioms algorithmically since Peano successor function is very "algorithmic." Yes my counting system does not have position in terms that you speak of. It only has algorithmic position. Can we map this notion of algorithmic position (or step of execution - comp. sci. terms) to the "positional" stuff that we get out of the Peano axioms?

 

[CRGreathouse]

What do you mean by algorithmic position?

 

[philiprdutton]

mapping retake

But your line doesn't have position right now. "7" is just as close to "1048576000000000" as it is to "6".

I was referring to the positional "stuff" that you get out of the Peano system.

Let try this: Just ignore positional stuff in the Peano system and try to get it to produce what we are calling a "counting system." Let us say the Peano system can do many things. One of the things it can do (we hope) is just simulate the basic counting system. we have been talking about. Now, equate these two systems Once you map them, then allow the positional stuff to come back into view on the Peano side. With it comes the notion of prime but you can not impose that notion of prime back onto the basic counting system that was mapped to the peano counting system.

 

[philiprdutton]

steps

What do you mean by algorithmic position?

Steps. How does the peano successor function produce the successor? In zero time? Does the framework allow one to talk about the successor function in terms of "steps." How does the successor function "compute" the successor of x? Is it a magical filter that pumps out numbers but does not let you look into it ?

Obviously, time is not a factor in the "ether of mathematics and abstractness" but what is preventing me from saying there are 2 steps from S(4) to S(6) ?

 

[philiprdutton]

successor

Steps. How does the peano successor function produce the successor? In zero time? Does the framework allow one to talk about the successor function in terms of "steps." How does the successor function "compute" the successor of x? Is it a magical filter that pumps out numbers but does not let you look into it ?

Obviously, time is not a factor in the "ether of mathematics and abstractness" but what is preventing me from saying there are 2 steps from S(4) to S(6) ?

Actually, I think about it more and I am convinced that the Peano system definitely allows you to look at what is happening in terms of algorithm. Algorithm implies steps. Perhaps Peano wanted an algorithmic viewpoint, I don't know.

 

[philiprdutton]

Time for some side question:

Is there a way to map one axiomatic system to another? Has it been done for systems that are similar? Can it be done from one simple system to a system that is more feature rich but which still simulates the simpler system?

What exactly does it mean to map a formal axiomatic system to SOMETHING ELSE. Is this the technique employed by Godel in his most excellent work?

 

[CRGreathouse]

I was referring to the positional "stuff" that you get out of the Peano system.

Let try this: Just ignore positional stuff in the Peano system and try to get it to produce what we are calling a "counting system." Let us say the Peano system can do many things. One of the things it can do (we hope) is just simulate the basic counting system. we have been talking about. Now, equate these two systems Once you map them, then allow the positional stuff to come back into view on the Peano side. With it comes the notion of prime but you can not impose that notion of prime back onto the basic counting system that was mapped to the peano counting system.

Still not following. What do you mean when you say you "equate the two systems"?

Steps. How does the peano successor function produce the successor? In zero time? Does the framework allow one to talk about the successor function in terms of "steps." How does the successor function "compute" the successor of x? Is it a magical filter that pumps out numbers but does not let you look into it ?

Obviously, time is not a factor in the "ether of mathematics and abstractness" but what is preventing me from saying there are 2 steps from S(4) to S(6) ?

When you're working with the pure Peano axioms, there's noting you can say about time, space, or other complexity. If you choose a particular model of the Peano axioms, then you can talk about it.

 

[CRGreathouse]

Is there a way to map one axiomatic system to another? Has it been done for systems that are similar? Can it be done from one simple system to a system that is more feature rich but which still simulates the simpler system?

It's done a lot, sure. A system A can be shown to be consistent relative to a (stronger) system B by constructing a model of A inside B. Kelley-Morse set theory can model ZFC (and prove its consistency too, showing that KM is actually stronger).

What exactly does it mean to map a formal axiomatic system to SOMETHING ELSE. Is this the technique employed by Godel in his most excellent work?

Which work? Godel made several major contributions to mathematics... do you mean his Incompleteness Theorem, or perhaps his earlier Completeness Theorem?

 

[philiprdutton]

Godel's proof

Which work? Godel made several major contributions to mathematics... do you mean his Incompleteness Theorem, or perhaps his earlier Completeness Theorem?

I was referring to the one which states that "for any self-consistent recursive axiomatic system powerful enough to describe the arithmetic of the natural numbers (Peano arithmetic), there are true propositions about the naturals that cannot be proved from the axioms." (copied from wikipedia)

 

[CRGreathouse]

I was referring to the one which states that "for any self-consistent recursive axiomatic system powerful enough to describe the arithmetic of the natural numbers (Peano arithmetic), there are true propositions about the naturals that cannot be proved from the axioms." (copied from wikipedia)

That's the Incompleteness Theorem. I don't think his proof used the mapping technique you mention.

 

[philiprdutton]

question about mapping

It's done a lot, sure. A system A can be shown to be consistent relative to a (stronger) system B by constructing a model of A inside B. Kelley-Morse set theory can model ZFC (and prove its consistency too, showing that KM is actually stronger).

You said "consistent"... does that mean "equivalent?"

 

[philiprdutton]

godel mapping

That's the Incompleteness Theorem. I don't think his proof used the mapping technique you mention.

Well he used some kind of mathematical mapping.

 

[philiprdutton]

which proof?

That's the Incompleteness Theorem. I don't think his proof used the mapping technique you mention.

Sorry I am talking about the more famous of the two.

I think maybe his Godel number function is the "mapping" I am referring to. I thought it was a generic mathematics technique.

 

[CRGreathouse]

You said "consistent"... does that mean "equivalent?"

No. In fact those two are inequivalent -- and you should know the reason, since you just posted it: the Incompleteness Theorem. No sufficiently strong theory* can prove its own consistency, so since KM proves ZFC to be consistent the two can't be equal (unless one is inconsistent, in which case they're both equal to the theory "for all p, p" in which everything is true).

* Any theory containing Peano arithmetic is strong enough.

 

[CRGreathouse]

Sorry I am talking about the more famous of the two.

The Incompleteness Theorem is the more famous of the two, and it's the one you quoted. The Completeness Theorem is the one that essentially says that in first-order logic, provability <--> truth.

 

[philiprdutton]

Godel encoding

Godel encoding was used by Godel as follows: "Gödel used a system of Gödel numbering based on prime factorization. He first assigned a unique natural number to each basic symbol in the formal language of arithmetic he was dealing with."

Can I assign each natural number from the Peano system to the counting systems' statements which we have been talking about here? I want each step of the counting algorithm output to be assigned the associated natural number.

(sorry human language is making it difficult to be formal and to keep all my terms in proper context. Obviously, there is no existing association when I said "associated natural number" but you know what I mean...)