What Makes Prime Numbers So Mysterious?

[philiprdutton]

makes sense

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

 

[CRGreathouse]

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.

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.

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?

 

[philiprdutton]

oops

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

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

 

[CRGreathouse]

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.

 

[dodo]

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

 

[philiprdutton]

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.

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.

 

[philiprdutton]

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

 

[CRGreathouse]

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.

 

[philiprdutton]

reference point

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)?

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

 

[matt grime]

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.

 

[philiprdutton]

notational model

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

 

[CRGreathouse]

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.

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.

 

[CRGreathouse]

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.

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.

 

[philiprdutton]

no meaning

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... : )

 

[Hurkyl]

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.

 

[philiprdutton]

the basics

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

 

[CRGreathouse]

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.

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

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.

 

[CRGreathouse]

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.

 

[phoenixthoth]

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.

 

[Hurkyl]

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!

 

[matt grime]

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... : )

You can't answer them because it is purely a formal opinion of whether they are true or false. Your T/F questions seem purely ontological, if that's the word. In what sense do any mathematical objects exist?

 

[CRGreathouse]

You can't answer them because it is purely a formal opinion of whether they are true or false. Your T/F questions seem purely ontological, if that's the word. In what sense do any mathematical objects exist?

Heh. The only branch of philosophy I did ever get deeply into was ontology... maybe that's why I can take this discussion. As far as that goes, Matt, you're a formalist, yes?

 

[philiprdutton]

nesting

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

Uhm... how do you handle "nestedness" without a reference point? This is why when I think about natural numbers and the operations I get so adamant about trying to figure out how the heck a reference point comes into play (if it actually does). In my humble lowly view, I believe there just absolutely has to be a reference point in there no matter whether you are using some set-theoretic notation or encoding the reference point in the axioms themselves...

Also, thanks so much for contributing your information thus far!

I must say my head hurts after trying to read it... but it is not you- it is me!

 

[philiprdutton]

hacking

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

Thank you for your analysis. I have begun to see many people resort back to a set-theoretic notation as in your case of the #1 axiom quoted above. A few times, lately, I have seen the set-theoretic articulation of the natural numbers. Every time I see such an articulation, I get the "shivers" because it looks so nested. When I think about "nesting" I can not understand how "nesting" could ever exist without a reference point.

The rest I am not able to comment on due to lack of understanding. However, I am deftly grateful for the valiant list you put forth. Honestly, I would love a poster of "what happens if you remove the axioms" as opposed to the axioms themselves (not afraid to admit that I love math posters!).

 

[CRGreathouse]

A few times, lately, I have seen the set-theoretic articulation of the natural numbers. Every time I see such an articulation, I get the "shivers" because it looks so nested. When I think about "nesting" I can not understand how "nesting" could ever exist without a reference point.

In set theory, the natural reference point is the null set, because once you know how to form sets ("set-builder notation") you don't need any further axioms to form the null set. It provides a concrete starting point too -- unlike the Peano "1", which could be anything, the nukll set is easy to grasp.

The rest I am not able to comment on due to lack of understanding. However, I am deftly grateful for the valiant list you put forth. Honestly, I would love a poster of "what happens if you remove the axioms" as opposed to the axioms themselves (not afraid to admit that I love math posters!).

Heh, maybe I'll make one.

 

[philiprdutton]

null set = references point

In set theory, the natural reference point is the null set, because once you know how to form sets ("set-builder notation") you don't need any further axioms to form the null set. It provides a concrete starting point too -- unlike the Peano "1", which could be anything, the nukll set is easy to grasp.

So, the ability to talk of numbers and the operations on them, and the notion of prime, is essentially due to the power of NESTING? Is this all?

 

[phoenixthoth]

Uhm... how do you handle "nestedness" without a reference point? This is why when I think about natural numbers and the operations I get so adamant about trying to figure out how the heck a reference point comes into play (if it actually does). In my humble lowly view, I believe there just absolutely has to be a reference point in there no matter whether you are using some set-theoretic notation or encoding the reference point in the axioms themselves...

Also, thanks so much for contributing your information thus far!

I must say my head hurts after trying to read it... but it is not you- it is me!

I think I may be misunderstanding your main question here. If I do understand, then any selected element u* can be the reference point%, such as the set whose only element is the null set. That is a nice choice because its cardinality is what is "natural" to think of as "1."

As far as nestedness, I'm not sure what you mean so if it's basically the iterates of what I'm calling a successor function, they are no less "natural" than the first iterate.

Sorry if I misunderstood.

%so long as whatever function you're using for the successor does NOT have u*, the reference point, in its range, i.e., nothing's successor is u*.

btw, not that it matters much, my condition 3 on a successor function could be stated as something like no elements in the orbit of u* are periodic points of S (of any period). Or, perhaps not as compactly, as the following set is pairwise disjoint:
{{x} : x is in the orbit of u* under S}. Basically my three conditions are trying to generalize the essential characteristics a successor function would have. For example, u* could be the square root of 5, if U is taken to be the set of real numbers, and S(x) = x-1. What I'm thinking is the set
{sqrt(5), sqrt(5) -1, sqrt(5)-2, sqrt(5)-3, ...} is, in some sense, like the usual set of natural numbers (except in this case, the order R I defined would reverse the 'usual' order...I defined the order so that x <= y if y is in the orbit of the successor function applied to x.)

 

[philiprdutton]

nestedness in binary digit sequences

I think I may be misunderstanding your main question here. If I do understand, then any selected element u* can be the reference point%, such as the set whose only element is the null set. That is a nice choice because its cardinality is what is "natural" to think of as "1."

As far as nestedness, I'm not sure what you mean so if it's basically the iterates of what I'm calling a successor function, they are no less "natural" than the first iterate.

Sorry if I misunderstood.

%so long as whatever function you're using for the successor does NOT have u*, the reference point, in its range, i.e., nothing's successor is u*.

btw, not that it matters much, my condition 3 on a successor function could be stated as something like no elements in the orbit of u* are periodic points of S (of any period). Or, perhaps not as compactly, as the following set is pairwise disjoint:
{{x} : x is in the orbit of u* under S}. Basically my three conditions are trying to generalize the essential characteristics a successor function would have. For example, u* could be the square root of 5, if U is taken to be the set of real numbers, and S(x) = x-1. What I'm thinking is the set
{sqrt(5), sqrt(5) -1, sqrt(5)-2, sqrt(5)-3, ...} is, in some sense, like the usual set of natural numbers (except in this case, the order R I defined would reverse the 'usual' order...I defined the order so that x <= y if y is in the orbit of the successor function applied to x.)

What I meant by "nestedness" (or "nesting") is best described like:

linear: ...{}{}{}{}{}...
nested: nothing, then {}, then {{}}, then{ {}, {{}} } ... etc.A standard visualization of nesting can be seen from the output of, say, a Cellular Automaton like the "Rule 90":[/PLAIN]
http://mathworld.wolfram.com/Rule90.html[/URL]
Or, what can be seen with the bit sequences of successive binary numbers:
[URL="http://www.wolframscience.com/nksonline/page-117"]http://www.wolframscience.com/nksonline/page-117

 

[CRGreathouse]

So, the ability to talk of numbers and the operations on them, and the notion of prime, is essentially due to the power of NESTING?

No. Nesting is a convenient way to model the Peano successor function, but it isn't required -- another method could be used instead.

 

[philiprdutton]

No. Nesting is a convenient way to model the Peano successor function, but it isn't required -- another method could be used instead.

Just a clarification of my thoughts. Sure, there may be other methods besides "nesting" to model the Peano successor function. Actually, I was a bit more keen on the idea that there could be a successor function unlike the Peano successor function- one where there actually is not a reference point (like in the "counting/metronome" system I was trying to describe in earlier posts). Perhaps the thing that distinguishes the Peano successor function from some other successor function is that there might be a reference point in the Peano successor (as it is defined)? More precisely, are all successor functions based on a reference point? Is Peano's?