Exploring the Mystery of Prime Numbers

  • Thread starter philiprdutton
  • Start date
  • Tags
    Prime
In summary: Maybe...just maybe...we might find some new way to think about prime numbers and make some progress on the stubborn topic.
  • #106
philiprdutton said:
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"1 recursively (or inductively) requires but three axioms: an axiom stating that "one"2 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:
1The 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.

2Modern treatments start with zero rather than one so that addition and multiplication can be easily defined based on the Peano axioms.
 
Physics news on Phys.org
  • #107
philiprdutton said:
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.
 
  • #108
axiomatic systems

D H said:
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.

D H said:
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."


D H said:
In comparison, defining the "numbers"1 recursively (or inductively) requires but three axioms: an axiom stating that "one"2 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?
 
  • #109
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.
 
  • #110
cool

D H said:
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?
 
  • #111
D H said:
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. :tongue:
 
  • #112
philiprdutton said:
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.
 
  • #113
without addition

CRGreathouse said:
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".
 
  • #114
philiprdutton said:
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.

philiprdutton said:
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".
 
  • #115
addition is what?

CRGreathouse said:
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?


CRGreathouse said:
I don't understand your use of the term "metronome system".

Sorry. Earlier I attempted to switch from "counting system" to "metronome system."
 
  • #116
philiprdutton said:
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).
 
  • #117
short cutting

CRGreathouse said:
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.
 
  • #118
philiprdutton said:
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.
 
  • #119
defining numbers

CRGreathouse said:
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."
 
Last edited:
  • #120
philiprdutton said:
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.

philiprdutton said:
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.
 
  • #121
makes sense

CRGreathouse said:
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.

I think I am getting close to understanding my own confusion.

I still have a few misunderstandings. When Peano fully defined the successor function, did addition fall out automatically (I think this was a point in an earlier posting about recursion)? Looking at the axioms on wikipedia, I can't see an explicit definition of addition. Interestingly the wikipedia editor for the Peano axiom topic has written the following:

"The axioms are based on the successor operation, written Sa or S(a), which adds 1 to its argument."

From that statement, it seems as though the addition is indeed built into the successor function.

I think I finally understand the difference between the Peano axiomatic system and the counting system we talked about earlier. I propose the following thought experiment:

All the arithmetic operations of the Peano system (and hence the notion of prime) could not exist if there was not a reference "point" defined on the "number line." If you take that first axiom away from the Peano system then all you have is a system that acts like a "metronome" ( the "counting system" that we have been talking about).
 
  • #122
philiprdutton said:
When Peano fully defined the successor function, did addition fall out automatically (I think this was a point in an earlier posting about recursion)? Looking at the axioms on wikipedia, I can't see an explicit definition of addition.

Off the top of my head:

x + 0 = x
x + S(y) = S(x + y)

These two allow any two numbers to be added, since you just decrease one step by step until it is zero, increasing the sum likewise.

philiprdutton said:
From that statement, it seems as though the addition is indeed built into the successor function.

That was just terminology. The successor just picks the next number; addition is defined in terms of it. It's convenient to mention that once addition is defined x + 1 will be the same as S(x), but that just falls out of the above definition since S(0) = 1.

philiprdutton said:
All the arithmetic operations of the Peano system (and hence the notion of prime) could not exist if there was not a reference "point" defined on the "number line." If you take that first axiom away from the Peano system then all you have is a system that acts like a "metronome" (or the "counting system" that we have been talking about).

Which is the first axiom?
 
  • #123
oops

philiprdutton said:
All the arithmetic operations of the Peano system (and hence the notion of prime) could not exist if there was not a reference "point" defined on the "number line." If you take that first axiom away from the Peano system then all you have is a system that acts like a "metronome" ( the "counting system" that we have been talking about).

CRGreathouse said:
Which is the first axiom?

Ooops! Indeed, the axioms are not ordered! I mean the axiom which states: "1 is a natural number" Also, we might be looking at two different versions of the axioms. I am looking at the list on the wikipedia (which are slightly rephrased from the original perhaps). Anyway, take that out and you basically sever addition and multiplication. Perhaps you also have no way to say what a number is. However, the number line is still there. The form has not been changed, destroyed or altered in any way (this will be very profound to me if it is indeed true).
 
Last edited:
  • #124
philiprdutton said:
Ooops! Indeed, the axioms are not ordered! I mean the axiom which states: "1 is a natural number" Also, we might be looking at two different versions of the axioms. I am looking at the list on the wikipedia (which are slightly rephrased from the original perhaps). Anyway, take that out and you basically sever addition and multiplication. Perhaps you also have no way to say what a number is. However, the number line is still there. The form has not been changed, destroyed or altered in any way (this will be very profound to me if it is indeed true).

Without the axiom "1 is a natural number" (which in modern terms is "0 is a natural number") you can't prove the existence of numbers at all.
 
  • #125
philiprdutton said:
... if there was not a reference "point" defined on the "number line."
Actually that number 1 is not an arbitrary reference point. In informal terms, it is "the step of the successor": when defining addition, we started by a + 1 = S(a). Similarly, when extending the axioms with S(0)=1, the number 0 turns out to be the neutral element of addition, a + 0 = a, all as a consequence of the initial axioms and the definition of addition.

More formally, if you define a function f: N* x N* -> N* (N* being the numbers including 0) as
d(a,b) = the number 's' such that, for a <= b, we have a + s = b;
and for a > b, the number d(b,a)​
then I'd say the function d(a,b) passes the requisites to be considered a metric (non-negativity, identity of elements with distance 0, symmetry and triangular identity), so that N* plus the function d() is now a metric space. So now we can speak of distance: and the distance d(a,S(a)) is exactly 1.
 
Last edited:
  • #126
true

CRGreathouse said:
Without the axiom "1 is a natural number" (which in modern terms is "0 is a natural number") you can't prove the existence of numbers at all.

Yes. I am in agreement with you on that. But I still believe the underlying "form" of what was once called a "number line" would still remain completely the same. Peano, by stating that "1 is a natural number" has basically "encoded" the reference point into the system. However, without the axiom, a user could just define their own reference point outside of the system and just use what is left in the Peano axiom set as a "metronome." The combination of "reference" point and "metronome system" is basically enough to completely build all the numbers. In other words, from an algorithmic perspective if you have memory (for the reference point) and metronome, you can get all the numbers, addition, multiplication, "prime", etc. all in one complete magical "poof!".

Okay. I might be getting the picture now (finally). Peano's axioms just give the user a way to input things into a recursive blackbox which then turns around and spits out a number. It is essentially an interface to recursion. It is a system which, once the recursion is kicked into gear, there is nothing you can do except wait until the answer comes back. You can't peer into the recursive "machinery" to glean or use "internal" information. If you take the "1 is a natural number" axiom out then the black box remains but is basically "disoriented". So:
*Recursion without a reference point is basically a metronome.
*Recursion without a reference point is just unary "counting/ticking."
*Recursion can only be used to define numbers when given a seed.
*Recursion is a powerful thing (mystery) which requires an interface to be used; hence, Peano defined his axioms.
*Pure recursion does not have a reference point.
 
  • #127
Dodo said:
Actually that number 1 is not an arbitrary reference point. In informal terms, it is "the step of the successor": when defining addition, we started by a + 1 = S(a). Similarly, when extending the axioms with S(0)=1, the number 0 turns out to be the neutral element of addition, a + 0 = a, all as a consequence of the initial axioms and the definition of addition.

More formally, if you define a function f: N* x N* -> N* (N* being the numbers including 0) as
d(a,b) = the number 's' such that, for a <= b, we have a + s = b;
and for a > b, the number d(b,a)​
then I'd say the function d(a,b) passes the requisites to be considered a metric (non-negativity, identity of elements with distance 0, symmetry and triangular identity), so that N* plus the function d() is now a metric space. So now we can speak of distance: and the distance d(a,S(a)) is exactly 1.

Thanks for this extra information. I am trying to understand the notion of "the step of the successor" as you called it. But it will require some mind bending. Are you saying that the axiom "0 is a natural number" combined with possibly one of the other axioms were written by Peano specifically to set up some kind of "unit space?" or "unit distance". You seem to be speaking of a kind of unit space when you say things like "the distance d(a,S(a)) is exactly 1." and "N* plus the function d() is now a metric space".
 
  • #128
philiprdutton said:
Yes. I am in agreement with you on that. But I still believe the underlying "form" of what was once called a "number line" would still remain completely the same. Peano,` by stating that "1 is a natural number" has basically "encoded" the reference point into the system.

I'm not sure I agree. 1 isn't given any properties, so the axioms would remain unchanged in meaning if you replaced all instances of "1" with "0" or "2007" or "foo".

Now the induction axiom, that's a powerful one. I could understand if you wanted to take that one out. But if you kept it in (considering that it does mention "1") while still taking out the "1 is a natural number" axiom, you'd have one of two situations:
* There are no natural numbers. This is a pretty boring situation, since the other axioms don't tell you much of anything, since they all have to do with numbers.
* 1 isn't a natural number. We'll call it an "ur-element", borrowing from set theory. But apply the successor operation to it enough times and you eventually get a natural number. From then on, the natural numbers operate just like normal -- call the first natural number 1' and define addition (multiplication, etc.) as normal but with 1' instead of 1.

So I don't think taking out the 1 does anything -- either you have a system with literally nothing in it, or you have one just like the ordinary natural numbers.
 
  • #129
reference point

CRGreathouse said:
I'm not sure I agree. 1 isn't given any properties, so the axioms would remain unchanged in meaning if you replaced all instances of "1" with "0" or "2007" or "foo".

Now the induction axiom, that's a powerful one. I could understand if you wanted to take that one out. But if you kept it in (considering that it does mention "1") while still taking out the "1 is a natural number" axiom, you'd have one of two situations:
* There are no natural numbers. This is a pretty boring situation, since the other axioms don't tell you much of anything, since they all have to do with numbers.
* 1 isn't a natural number. We'll call it an "ur-element", borrowing from set theory. But apply the successor operation to it enough times and you eventually get a natural number. From then on, the natural numbers operate just like normal -- call the first natural number 1' and define addition (multiplication, etc.) as normal but with 1' instead of 1.

So I don't think taking out the 1 does anything -- either you have a system with literally nothing in it, or you have one just like the ordinary natural numbers.

So, are you saying that in order for us to apply the definition of "natural number" one must have already "built" support for a reference point in a particular system (like Peano)?
CRGreathouse said:
,... you'd have one of two situations:
* There are no natural numbers. This is a pretty boring situation, since the other axioms don't tell you much of anything, since they all have to do with numbers.

True it is boring if you are only interested in numbers. One of the things I am interested in is the system "mechanics" of axiomatic theory. Perhaps it would be helpful if someone could explain the true order of creation of the set of Peano axioms. In other words, what is the first axiom that must be stated? What is the second? What is the third? ... what is the last?

It would be helpful for the sake of stepping through the recreation of the Peano system. With such a list, I am assuming I can hack off the last axiom without even thinking about it and still be able to have "natural numbers". What axioms can be hacked off in this sense?

Also, if there is not one Peano axiom (I am typically looking at the list given on wikipedia) which can not be deleted without affecting the existence of "natural numbers" then it is clearly a system which is describing an existing "thing" as opposed to actually creating the "thing." (here, "thing" is the number line). If is only describing the "thing" then it is clearly only an interface to it.
 
Last edited:
  • #130
philiprdutton said:
Peano, by stating that "1 is a natural number" has basically "encoded" the reference point into the system. However, without the axiom, a user could just define their own reference point outside of the system and just use what is left in the Peano axiom set as a "metronome."
I think you're missing a standard result in set theory. If we remove the axiom - there is some natural number (which we call 1), then we're getting to the point where the empty set will satisfy the definition of the natural numbers since the precedent in any remaining axiom is false, thus things are automatically true.

I presume you don't wish to have a set of natural numbers that has no elements.

It isn't that he has declared 1 to be a natural number, just that there is such a thing. I.e. whatever notional model we choose for our axioms must be a non-empty set.
 
  • #131
notational model

matt grime said:
I think you're missing a standard result in set theory. If we remove the axiom - there is some natural number (which we call 1), then we're getting to the point where the empty set will satisfy the definition of the natural numbers since the precedent in any remaining axiom is false, thus things are automatically true.

I presume you don't wish to have a set of natural numbers that has no elements.

It isn't that he has declared 1 to be a natural number, just that there is such a thing. I.e. whatever notional model we choose for our axioms must be a non-empty set.

Interesting result you mentioned.

I am still interested in the properties of the system (what can it do? how can I use it?) even when there is no longer the ability to recognize, talk about, or define "natural numbers." On the one hand it sounds like I am philosophizing everything to death. However, I am working out my understanding of what I consider a practical problem. I will re-iterate it here: I am simply wondering what is the basic core "feature" of an axiomatic system. I am starting to think that the basic core feature is a metronome type "feature." This is what I am exploring. So, I can tolerate a system that does not necessarily have the ability to "internalize" the notion of a "natural number."
 
Last edited:
  • #132
philiprdutton said:
So, are you saying that in order for us to apply the definition of "natural number" one must have already "built" support for a reference point in a particular system (like Peano)?

I understood no part of that.

philiprdutton said:
True it is boring if you are only interested in numbers.

No. Either the system is just like the system with the "1" axiom (possibly with a few ur-elements, but they don't change anything) or it's a list of properties that apply to nothing. Consider this system:

1. All unicorns are four-legged.
2. All unicorns have a single horn.
3. All unicorns are pink.
4. All unicorns are good-hearted.
5. Unicorns only allow maidens to ride on them.

It could be an interesting system, in that it gives several properties to the set U of unicorns. But if you know (perhaps as an additional axiom) that there are no unicorns, suddenly 1-5 mean nothing -- they don't add or subtract from the possible properties of any object or creature.

Similarly, using the Wikipedia axioms you use:
2. Every natural number is equal to itself (equality is reflexive).
3. For all natural numbers a and b, a = b if and only if b = a (equality is symmetric).
4. For all natural numbers a, b, and c, if a = b and b = c then a = c (equality is transitive).
5. If a = b and b is a natural number then a is a natural number.
6. If a is a natural number then Sa is a natural number.
7. If a and b are natural numbers then a = b if and only if Sa = Sb.
8. If a is a natural number then Sa is not equal to 1.
9. For every set K, if 1 is in K, and Sx is in K for every natural number x in K, then every natural number is in K.

Literally none of the axioms 2-9 have any meaning whatever if there are no natural numbers. Axioms 2-8 are in that case of the form "False --> x" which is always true, and axiom 9 is of the form "x --> {} is in the set X" which is true for any set X.
 
  • #133
philiprdutton said:
One of the things I am interested in is the system "mechanics" of axiomatic theory. Perhaps it would be helpful if someone could explain the true order of creation of the set of Peano axioms. In other words, what is the first axiom that must be stated? What is the second? What is the third? ... what is the last?

They work in any order. It would make sense to have axiom 1 come before axiom 8, but this is not strictly necessary.

Axiom 9 is important for proofs but if left off, many problems could still be stated.

philiprdutton said:
It would be helpful for the sake of stepping through the recreation of the Peano system. With such a list, I am assuming I can hack off the last axiom without even thinking about it and still be able to have "natural numbers". What axioms can be hacked off in this sense?

I leave off 2-5, as these simply define equality. You may amuse yourself by removing one or more of these, which effectively replaces equality with a certain kind of (possibly equivalence) relation.

If #1 is removed, the system is either null, unchanged, or unchanged except with the addition of finitely many ur-elements, which don't actually change things at all from a set-theoretic point of view. (They don't give it more expressive power.) Essentially all proofs are either nonconstructive or conditional.

If #6 is removed, the system may be unchanged or have only finitely many natural numbers -- perhaps only one.

I'm not quite sure what the effects of removing #7 would be. Could S be multivalued, or is it defined as a function? This may lead to natural numbers as an incomparable web rather than a chain. Perhaps Matt will lend his talents here...?

If #8 is removed there may be only finitely many numbers. If so, they may either end at an element (call it "infinity") that is its own successor, or may loop at some point. In either case there would be a finite chain of natural numbers, then a ring that functions like the integers modulo a constant.

If #9 is removed there may be inaccessible natural numbers (numbers not in {1, S(1), S(S(1)), ...}). Proofs become difficult.
 
  • #134
no meaning

CRGreathouse said:
I understood no part of that.
No. Either the system is just like the system with the "1" axiom (possibly with a few ur-elements, but they don't change anything) or it's a list of properties that apply to nothing. Consider this system:

1. All unicorns are four-legged.
2. All unicorns have a single horn.
3. All unicorns are pink.
4. All unicorns are good-hearted.
5. Unicorns only allow maidens to ride on them.

It could be an interesting system, in that it gives several properties to the set U of unicorns. But if you know (perhaps as an additional axiom) that there are no unicorns, suddenly 1-5 mean nothing -- they don't add or subtract from the possible properties of any object or creature.

Similarly, using the Wikipedia axioms you use:
2. Every natural number is equal to itself (equality is reflexive).
3. For all natural numbers a and b, a = b if and only if b = a (equality is symmetric).
4. For all natural numbers a, b, and c, if a = b and b = c then a = c (equality is transitive).
5. If a = b and b is a natural number then a is a natural number.
6. If a is a natural number then Sa is a natural number.
7. If a and b are natural numbers then a = b if and only if Sa = Sb.
8. If a is a natural number then Sa is not equal to 1.
9. For every set K, if 1 is in K, and Sx is in K for every natural number x in K, then every natural number is in K.

Literally none of the axioms 2-9 have any meaning whatever if there are no natural numbers. Axioms 2-8 are in that case of the form "False --> x" which is always true, and axiom 9 is of the form "x --> {} is in the set X" which is true for any set X.

Thanks for the input. So, it sounds as if the axiomatic Peano system basically builds the "structure" that we find in the "number line."

[T or F] The number line doesn't exist until after an axiomatic system is written to create the structure.

[T or F] You can't have a number without the ability to know what it is in terms of it's successor and/or it's predecessor.

[T or F] You can't have a the notion of a "number" separated from operations like addition/multiplication EVEN if you do not define those operations in your axioms.

[T or F] A system that can give us, in order, "1,2,3,4,5,6..." can also be modified to only give us, "blip,blip,blip,blip,..." However, given the modified system, we do not know if "the tape is moving or the tape is not moving". (I am making a play on the Turing machine when I use the word "tape")Thanks for the input. If someone can help me with the above T/F statements then I would be very grateful and will be ready to close this thread (much to everyone's relief I am sure!). Obviously, I need to go study... : )
 
Last edited:
  • #135
In the practice of formal logic, one considers syntax, and semantics.

Syntax is essentially just formal manipulation of symbols. You define a "language" and "rules of inference", and you can start proving "theorems" and all sorts of interesting stuff.

A "theory" is a collection of statements that you make in the language.

One convenient way to specify a theory is by selecting a collection of statements, which we call "axioms", which have the property that the entire language (and nothing else) can be derived from those axioms by applying the rules of inference.

(Incidentally, this is by no means the only way to specify a theory)



When we try to "interpret" a language, that's semantics. A typical interpretation is to supply a set of "objects", and for each function symbol, relation symbol and constant symbol in the language, one supplies a function, relation, or element on the set of objects.

If a collection of statements are true in this interpretation, then we call it a "model" of those statements.

Note that if a set of axioms generate a theory, then a model of those axioms is the same thing as a model of that theory.

For common theories, we give the models special names. e.g. a model of group theory would be called a "group" -- equivalently, a model of the group axioms would be called a "group". Similarly, a model of Hilbert's axioms would be called a "Euclidean geometry", and a model of Peano's axioms would be called a "set of natural numbers".

Remember -- a model of Peano's axioms is the same thing as a model of the theory it generates. The theory is the important thing here; if we picked a different set of axioms that generated the same theory, we would still call it a "set of natural numbers".

We do this, even if the set of objects doesn't obviously resemble our intuitive notion of a "plane" or a "set of numbers" ought to be. As a practical matter, this is fine, precisely because we tend to design theories so that they capture the essense of our intuitive notions. So, I can still apply all of my geometric intuition, even if I'm working with something that doesn't manifestly appear to have any geometric form at all!



Sometimes, one might step outside of pure mathematics. e.g. we might assert that the numbers we really use to count with in real life are a model of Peano's axioms, or that reality is a model of quantum mechanics.

There is a mathematical theorem that says any consistent theory using elementary Boolean logic has a set-theoretic model. If you want to talk about the possible existence of models in "reality" or in some world of "Platonic ideals", or whatever, then you are no longer talking about mathematics.
 
Last edited:
  • #136
the basics

Hurkyl said:
In the practice of formal logic, one considers syntax, and semantics.

Syntax is essentially just formal manipulation of symbols. You define a "language" and "rules of inference", and you can start proving "theorems" and all sorts of interesting stuff.

A "theory" is a collection of statements that you make in the language.

One convenient way to specify a theory is by selecting a collection of statements, which we call "axioms", which have the property that the entire language (and nothing else) can be derived from those axioms by applying the rules of inference.

(Incidentally, this is by no means the only way to specify a theory)



When we try to "interpret" a language, that's semantics. A typical interpretation is to supply a set of "objects", and for each function symbol, relation symbol and constant symbol in the language, one supplies a function, relation, or element on the set of objects.

If a collection of statements are true in this interpretation, then we call it a "model" of those statements.

Note that if a set of axioms generate a theory, then a model of those axioms is the same thing as a model of that theory.

For common theories, we give the models special names. e.g. a model of group theory would be called a "group" -- equivalently, a model of the group axioms would be called a "group". Similarly, a model of Hilbert's axioms would be called a "Euclidean geometry", and a model of Peano's axioms would be called a "set of natural numbers".

Remember -- a model of Peano's axioms is the same thing as a model of the theory it generates. The theory is the important thing here; if we picked a different set of axioms that generated the same theory, we would still call it a "set of natural numbers".

We do this, even if the set of objects doesn't obviously resemble our intuitive notion of a "plane" or a "set of numbers" ought to be. As a practical matter, this is fine, precisely because we tend to design theories so that they capture the essense of our intuitive notions. So, I can still apply all of my geometric intuition, even if I'm working with something that doesn't manifestly appear to have any geometric form at all!



Sometimes, one might step outside of pure mathematics. e.g. we might assert that the numbers we really use to count with in real life are a model of Peano's axioms, or that reality is a model of quantum mechanics.

There is a mathematical theorem that says any consistent theory using elementary Boolean logic has a set-theoretic model. If you want to talk about the possible existence of models in "reality" or in some world of "Platonic ideals", or whatever, then you are no longer talking about mathematics.


Thanks for supplying this summary. I am afraid I am not going to be able to absorb it all without spending a lot of time "doing" the math. I figure I will need to start with an understanding of mathematical logic (which is why I posted a question already about "rule of inference" in the logic discussion area).
 
  • #137
What did you think of my list of changes by omitting axioms (#133)? I'm curious to see what you think, since this may be ther only place we're properly connecting now. :biggrin:

I'm going to number your questions in bold below.

philiprdutton said:
Thanks for the input. (0) So, it sounds as if the axiomatic Peano system basically builds the "structure" that we find in the "number line."

(1) [T or F] The number line doesn't exist until after an axiomatic system is written to create the structure.

(2) [T or F] You can't have a number without the ability to know what it is in terms of it's successor and/or it's predecessor.

(3) [T or F] You can't have a the notion of a "number" separated from operations like addition/multiplication EVEN if you do not define those operations in your axioms.

(4) [T or F] A system that can give us, in order, "1,2,3,4,5,6..." can also be modified to only give us, "blip,blip,blip,blip,..." (5) However, given the modified system, we do not know if "the tape is moving or the tape is not moving". (I am making a play on the Turing machine when I use the word "tape")

0. I don't understand.
1. I think this statement is essentially "Is mathematical Platonism correct?". If so, it's highly subjective -- but as I said before, I'm something of a Platonist but few mathematicians are.
2. What's a number? There's no reason you can't have objects without successors or predecessors. Still, I'll take a crack at this one. A member of the extended reals should probably be considered a number under a sensible definition of same, and in that system +/- infty could be defined without successor or predecessor.
3. What's a number? In any case definitions don't matter; they're "conservative extensions" of the theory.
4. I don't understand.
5. There are lots of ways to represent numbers on (binary) Turing machines, but unary is most popular: a 0-terminated string of 1s. I don't know what this has to do with the tape moving or your other philosophical questions.
 
  • #138
philiprdutton said:
Thanks for supplying this summary. I am afraid I am not going to be able to absorb it all without spending a lot of time "doing" the math. I figure I will need to start with an understanding of mathematical logic (which is why I posted a question already about "rule of inference" in the logic discussion area).

Hurkyl's post was explaining what was meant by the term "model". It's worth a second read -- and if that doesn't do it for you, look it up elsewhere.

Here, since you're already using Wikipedia, let me find you a link there.

Hmm, that's not good. I found http://en.wikipedia.org/wiki/Model_theory but it's considerably more technical than the post.
 
  • #139
philiprdutton said:
Thanks for the input. So, it sounds as if the axiomatic Peano system basically builds the "structure" that we find in the "number line."

[T or F] The number line doesn't exist until after an axiomatic system is written to create the structure.

[T or F] You can't have a number without the ability to know what it is in terms of it's successor and/or it's predecessor.

[T or F] You can't have a the notion of a "number" separated from operations like addition/multiplication EVEN if you do not define those operations in your axioms.

[T or F] A system that can give us, in order, "1,2,3,4,5,6..." can also be modified to only give us, "blip,blip,blip,blip,..." However, given the modified system, we do not know if "the tape is moving or the tape is not moving". (I am making a play on the Turing machine when I use the word "tape")


Thanks for the input. If someone can help me with the above T/F statements then I would be very grateful and will be ready to close this thread (much to everyone's relief I am sure!). Obviously, I need to go study... : )

Maybe you can define something structurally equivalent to the set of natural numbers this way...
Let U be any infinite set (which could mean, for instance, that there is a one-to-one correspondence between U and at least one of its proper subsets). Such a set exists in ZF by the axiom of infinity.

Pick out any element of U. Let's call it u*. Now let S be any function with domain U and range contained in U with the following conditions:
1. u* is not in the range of S
2. S has no fixed points (i.e., for all u in U, S(u) is not u)

(u* is going to behave like the number 1 and S like the successor function.)

Now for another definition. A subset A of U is called inductive (or S-inductive because it depends on S) iff the following conditions hold:
1. u* is in A and
2. for all a in A, S(a) is in A.

Let N* be the intersection of all inductive subsets of U. This is going to be what behaves like the set of natural numbers. I think N* will just be the orbit of u*:
{u*, S(u*), S(S(u*)), S(S(S(u*))), S(S(S(S(u*)))), S(S(S(S(S(u*))))), ...}.

N* certainly won't be like N at all if the orbit of u* is finite, so let's add a third condition to S:
1. u* is not in the range of S
2. S has no fixed points (i.e., for all u in U, S(u) is not u)
3. All elements in the set {u*, S(u*), S(S(u*)), S(S(S(u*))), S(S(S(S(u*)))), S(S(S(S(S(u*))))), ...} are different.

Now define a relation on N*, call it R, which will behave like less than or equal to:
(x,y) is in R iff y is in the orbit of x. In other words, (x,y) is in R iff either y=x or y=S(x) or y=S(S(x)) or y=S(S(S(x))) or ... .

I think then that (N, <=) is structurally like (N*, R) in that if we define a function from N to N*, called f, as f(n) is the (n-1)st iterate of u* under S, then f would be a one-to-one correspondence and "relation preserving," i.e., for all n1 and n2 in N, then n1 <= n2 iff R( f(n1), f(n2) ).

If this is true, then for any given U, S with the stated properties on U, then the intersection of all inductive sets would behave like the set of natural numbers.


Incidentally, when the axiom says 1 is a natural number, I'm wondering what 1 is. One way to make that work is to define 1 to be the set whose element is the empty set and for all sets a, define the successor of a to be the union of a with the set whose element is a.
 
  • #140
philiprdutton said:
Thanks for supplying this summary. I am afraid I am not going to be able to absorb it all without spending a lot of time "doing" the math. I figure I will need to start with an understanding of mathematical logic (which is why I posted a question already about "rule of inference" in the logic discussion area).
The main thing I was trying to say is that there is a separation between syntax and semantics. Theories and proofs are syntactic; they do not come pre-equipped with any sort of "meaning".

It is true that a mathematician often has a particular meaning in mind when 'e creates a theory, and 'e designs it so that the theory can be given the interpretation 'e desires. But once the theory is created, it is a purely syntactic, and if one desires, it can be used with other meanings, or with no meaning attached to it at all!
 
<h2>1. What are prime numbers?</h2><p>Prime numbers are positive integers that are only divisible by 1 and themselves. They have exactly two factors, making them unique and important in mathematics.</p><h2>2. How many prime numbers are there?</h2><p>There are infinitely many prime numbers. As of now, the largest known prime number has over 24 million digits.</p><h2>3. How can I determine if a number is prime?</h2><p>There are a few methods for determining if a number is prime, including trial division and the Sieve of Eratosthenes. These methods involve checking if the number is divisible by any smaller numbers. However, there is no known formula or algorithm to generate all prime numbers.</p><h2>4. Why are prime numbers important?</h2><p>Prime numbers have many applications in mathematics and computer science. They are used in cryptography, data encryption, and coding theory. They also play a crucial role in the distribution of prime numbers, which is a fundamental problem in number theory.</p><h2>5. Are there any patterns or relationships between prime numbers?</h2><p>While there are some patterns and relationships between prime numbers, they are not fully understood. For example, there are infinitely many pairs of prime numbers that differ by 2, such as 3 and 5, 5 and 7, 11 and 13, etc. This is known as the twin prime conjecture, which has not yet been proven or disproven.</p>

1. What are prime numbers?

Prime numbers are positive integers that are only divisible by 1 and themselves. They have exactly two factors, making them unique and important in mathematics.

2. How many prime numbers are there?

There are infinitely many prime numbers. As of now, the largest known prime number has over 24 million digits.

3. How can I determine if a number is prime?

There are a few methods for determining if a number is prime, including trial division and the Sieve of Eratosthenes. These methods involve checking if the number is divisible by any smaller numbers. However, there is no known formula or algorithm to generate all prime numbers.

4. Why are prime numbers important?

Prime numbers have many applications in mathematics and computer science. They are used in cryptography, data encryption, and coding theory. They also play a crucial role in the distribution of prime numbers, which is a fundamental problem in number theory.

5. Are there any patterns or relationships between prime numbers?

While there are some patterns and relationships between prime numbers, they are not fully understood. For example, there are infinitely many pairs of prime numbers that differ by 2, such as 3 and 5, 5 and 7, 11 and 13, etc. This is known as the twin prime conjecture, which has not yet been proven or disproven.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
759
  • Linear and Abstract Algebra
Replies
2
Views
1K
Replies
35
Views
3K
Replies
8
Views
1K
  • Linear and Abstract Algebra
Replies
4
Views
5K
Replies
11
Views
3K
  • Math Proof Training and Practice
Replies
9
Views
2K
  • Linear and Abstract Algebra
Replies
6
Views
6K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Linear and Abstract Algebra
Replies
6
Views
4K
Back
Top