Register to reply

Whole prime number

by philiprdutton
Tags: number, prime
Share this thread:
philiprdutton
#19
Jul28-07, 07:34 PM
P: 120
* 1 is a natural number
* For all x, Sx is a natural number
* For all x, Sx is not 1
* For all x and y, x = y iff Sx = Sy

Okay. So regarding the obscure number line that sort of exists before Peano touches the paper with his pencil, I imagine what would happen if Peano wrote the following:

* 32654 is a natural number
* For all x, Sx is a natural number
* For all x, Sx is not 32654
* For all x and y, x = y iff Sx = Sy

It would be totally cool with me. But it sort of points out that the number line is still there regardless of whether Peano writes the axioms down or not. Sure I take your point that it is a rather platonistic statement but I can not seperate out the platonisticism when talking about this stuff at this level.

In fact, just for fun, I will add a few more:

* 99 is a natural number
* For all x, Sx is a natural number
* For all x, Sx is not 99
* For all x and y, x = y iff Sx = Sy



* 10010001 is a natural number
* For all x, Sx is a natural number
* For all x, Sx is not 10010001
* For all x and y, x = y iff Sx = Sy




* 666 is a natural number
* For all x, Sx is a natural number
* For all x, Sx is not 666
* For all x and y, x = y iff Sx = Sy

(the above I could not resist!)
CRGreathouse
#20
Jul28-07, 07:42 PM
Sci Advisor
HW Helper
P: 3,684
"1" is just a label, it could be anything. Consider this model of Peano arithmetic:

"1" is a triangle. If x is a polygon, Sx is a polygon with one more side than x; otherwise, Sx is a pink unicorn. x = y iff x and y are polygons and x and y have the same number of sides. For example S(S(1)) (that is, "3") is a pentagon.

This works perfectly well -- all the Peano axioms can be made to hold in this system, even though the underlying objects are not "numbers" in any normal sense of the word. If we went through all the usual definition we would find that x + y would be defined as a polygon with two fewer sides than the total number of sides in x and y.
philiprdutton
#21
Jul28-07, 07:53 PM
P: 120
Yes I am in agreement with you about the labels. But, I am not convinced that Peano wrote that stuff without already having been biased by the notion of the number line.

Also, given

* 1 is a natural number
* For all x, Sx is a natural number
* For all x, Sx is not 1
* For all x and y, x = y iff Sx = Sy

I still maintain the early phrase "For all x" is unfortunate. It clearly can be interpreted as saying "for all the x that already exist." This is very much a problem in my opinion. It feels as if the system is riding on the edge of chicken and egg. I am sorry but it will take me some time to absorb that it is not a chicken and egg system (I will take the mathematicians word for it for now).

If, however, the numbers can exist without the successor function definition (example: in terms of counting only and not in terms of talking about where the counting stops) then clearly there is a problem with the definition of Prime. It refers not to the "position" where the counting stops UNTIL the operational axioms are applied.
CRGreathouse
#22
Jul28-07, 08:04 PM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by philiprdutton View Post
Yes I am in agreement with you about the labels. But, I am not convinced that Peano wrote that stuff without already having been biased by the notion of the number line.
I'm not entirely sure what you mean. I do think he gave examples of non-numbers as a basis for the Peano axioms, though.

Quote Quote by philiprdutton View Post
I still maintain the early phrase "For all x" is unfortunate. It clearly can be interpreted as saying "for all the x that already exist." This is very much a problem in my opinion. It feels as if the system is riding on the edge of chicken and egg. I am sorry but it will take me some time to absorb that it is not a chicken and egg system (I will take the mathematicians word for it for now).
Philosophically it may pose a problem, but as formally phrased (and I haven't used the formal phrasings or notations) it is mathematically airtight.

Quote Quote by philiprdutton View Post
If, however, the numbers can exist without the successor function definition (example: in terms of counting only and not in terms of talking about where the counting stops) then clearly there is a problem with the definition of Prime. It refers not to the "position" where the counting stops UNTIL the operational axioms are applied.
Hmm. I don't know what you mean, but this seems like philosophy again. If you would rephrase this in more detail perhaps I can say something. If it's meant to be mathematical I'll need to know the precise axioms you're using (if not successor) and how you define prime (and how you define everything you use to define prime). When modifying systems precision is very important.
philiprdutton
#23
Jul28-07, 08:30 PM
P: 120
Let us assume that there can be an axiomatic system which does not allow you to construct the natural numbers. Assume also that the axiomatic system just states all the would-be numbers in terms of "steps" in a counting process.

Obviously, why do this since the point of the axiomatic system is to be able to build numbers. Don't worry about that for now.

So here is the "foo" axiomatic system:

"foo" axioms:
"foo"
"foo,foo"
"foo,foo,foo"
"foo,foo,foo,foo"
"foo,foo,foo,foo,..."

That was my best attempt at defining a simple basic axiomatic system which just states the steps at each count of a counting process.

Obviously, to talk about each step in terms of a number one needs to have some structure about what it is that you are talking about. Once you add the structure you can finally say that "foo,foo,foo,foo,foo" is really 5. But until you have done so, the "foo,foo,foo,foo,foo" is not a prime even though it falls in the same position on the number line as the 5 from the other axiomatic system.

It is not a formal example but I am trying my best to get to that point. Any ideas how we can formally write an axiomatic system which just lists the "foo" ?? Perhaps we can call it the "counting axioms."
CRGreathouse
#24
Jul28-07, 08:38 PM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by philiprdutton View Post
It is not a formal example but I am trying my best to get to that point. Any ideas how we can formally write an axiomatic system which just lists the "foo" ?? Perhaps we can call it the "counting axioms."
I think you just did that -- mathematicians would use the term "axiom schema", that is, each number is its own axiom:

Axiom 1: 1 is a natural number.
Axiom 2: 2 is a natural number.
. . .

OK, so now you have a system where you cannot add or take the successor, but you have the natural numbers. (You can call them "foo, foo" and the like if you wish, but names are just labels to mathematicians so I'll just call them this for now.)

So in the context of this system containing your counting axiom schema, what is the definition of "prime"? Or is your point that you can't even define it here? (Mathematicians would say, informally, that they don't have the 'machinery' they need.)
philiprdutton
#25
Jul28-07, 09:00 PM
P: 120
Quote Quote by CRGreathouse View Post

So in the context of this system containing your counting axiom schema, what is the definition of "prime"? Or is your point that you can't even define it here? (Mathematicians would say, informally, that they don't have the 'machinery' they need.)

Yes. It is my point. In that system there is no way to define prime. Hence, primality is not a feature until more machinery is added.
Hurkyl
#26
Jul28-07, 09:29 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,098
From the point of view of formal logic, having a multiplication operation makes a rather large difference.

If we use first-order logic, and we omit general multiplication, we have the theory of Presburger arithmetic. This theory is known to be logically complete. But if we use Peano arithmetic... or even if we omit the induction axiom and use Robinson arithmetic, then we are working with an incomplete theory.

In other words, if we stick only to addition, every (first-order) proposition we can state about the natural numbers can either be proven or disproven. But if we allow multiplication, then there exist statements that can neither be proven or disproven. (And furthermore, it remains incomplete, even if we adopt finitely more axiom schema)


I don't know much about what happens when you allow higher-order logic.
Hurkyl
#27
Jul28-07, 09:43 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,098
Quote Quote by philiprdutton View Post
But, I am not convinced that Peano wrote that stuff without already having been biased by the notion of the number line.
Well, of course Peano was thinking about the "number line". His goal (I presume) was to write down a list of axioms that characterized the intuitive notion of "natural number" that he and other mathematicians had.

The modern approach to mathematics prefers to have explicit foundations -- these days, one often defines that anything satisfying the Peano axioms is a "set of natural numbers", or similar. Then, if we turn to metamathematics, we argue that the counting process does, in fact, satisfy the Peano axioms, and so we are justified in saying that when we count, we are using the natural numbers.
CRGreathouse
#28
Jul28-07, 10:27 PM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by Hurkyl View Post
If we use first-order logic, and we omit general multiplication, we have the theory of Presburger arithmetic. This theory is known to be logically complete.
Presburger arithmetic may be of interest to philiprdutton because it's just 'on the edge' of being able to define primes. It can't define the concept of being prime in general, let alone prove statements about them, but it can (I think) show that particular numbers are prime:

[tex]\neg\exists x : x + x = 5[/tex]
[tex]\neg\exists x : x + x + x = 5[/tex]
[tex]\neg\exists x : x + x + x + x = 5[/tex]
philiprdutton
#29
Jul28-07, 10:55 PM
P: 120
Quote Quote by CRGreathouse View Post
I think you just did that -- mathematicians would use the term "axiom schema", that is, each number is its own axiom:

Axiom 1: 1 is a natural number.
Axiom 2: 2 is a natural number.
. . .

OK, so now you have a system where you cannot add or take the successor, but you have the natural numbers. ....

Finally I had one last important thought. Given the system described where you have the natural numbers but you can not add or take the successor, we should be able to map the system to the system where by you can build the natural numbers. If such a mapping is "formalized" then the problem appears. On the one hand you have a system where "prime" is not defined and on the other hand you have a system where "prime" can be defined. They are mapped to each other and so now is there a paradox?

I am thinking about the utility of mapping similar to what is used by Godel in his famous proof.

Again for clarity: 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.
philiprdutton
#30
Jul28-07, 11:03 PM
P: 120
"The idea of a prime number is loads of fun for the guy with all the numbers AND the bag of tools with which he can do things to those numbers. The guy with only all the numbers is simply bored out of his mind." - Philip Ronald Dutton

(sorry! I am exploiting the utility of writing hoping it will sharpen my understanding of all this)
CRGreathouse
#31
Jul28-07, 11:07 PM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by philiprdutton View Post
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
#32
Jul28-07, 11:12 PM
P: 120
Quote Quote by CRGreathouse View Post
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
#33
Jul29-07, 01:07 AM
P: 688
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
Sieve of Eratosthenes
.)
CRGreathouse
#34
Jul29-07, 09:15 AM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by philiprdutton View Post
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.

Quote Quote by philiprdutton View Post
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
#35
Jul29-07, 12:30 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,098
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
#36
Jul29-07, 01:44 PM
P: 120
Quote Quote by Dodo View Post
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
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.


Register to reply