Non standard number theories

I’m currently reading “Godel, Escher, Bach: An Golden Braid” by Hofstadter. On paqge 100, he claims that, just like in geometry, as a result of Godel’s theorem there are nonstandard number theories, in fact he claims there are an infiinite number.

It appears that what he claims are nonstandard geometries (i.e. not Euclidean) are defined by 4 core postulates laid out by Euclid, and seperated from each other by a fifth, the straight line intersection postulate.

My questions are: is my understanding of the situation correct, or do I need to reread? What postulates define a number theory, and which postulates are “redefined” so to speak, to create the differing number theories?

I’m really not sure. I need to read that again, probably after taking a few more math classes. But you missed Eternal. An Eternal Golden Braid.

Ahh, thanks for correcting.

There’s a certain amount we can learn about geometry using only 4 postulates. One thing we can’t learn though is: given a line and a point not on the line, how many lines through the point are parallel to the original line? There are three possible answers (0, 1 and infinity) and all three are logically consistent with the original 4 postulates but they are, of course, incompatible with each other.

For centuries, starting with Euclid, geometers have assumed that one of the possible answers (1) is “right” and the others “wrong” but since the nineteenth century they have known that it was not possible to derive the “right” answer from the other four postulates. If it couldn’t be proven, the only solution was to add the “right” answer as a fifth postulate or basic assumption.

Non-Euclidian geometry began when geometers, in a somewhat paradigmatic move, gave up worrying about which possible parallel postulate was “right” and allowed geometry to branch into three parts. Each part was logically self-consistent so while no two could be “right” at the same time, there was no reason to pick one and call it “right” and the other two “wrong.”

This happened because there was a question in geometry that could not be answered by logical deduction starting with the original four postulates. Could the same situation occur in number theory? Is there some proposition about numbers that is undecidable from the basic axioms? Well dog my cats, there is! And it was discovered by Kurt Godel who proved that there exists some proposition about numbers (call it G) that can neither be proved nor disproved using the basic axioms of arithmetic. In other words, both G and its negation (~G) are logically consistent with the other axioms.

Proceeding as geometers have done we could add G to our list of axioms (call the list of axioms N.) For that matter we could also add ~G. Now, like in geometry, there are two formulations: a “standard” one (N+G) and a “nonstandard” one (N+~G). The problem is that, unlike geometry, we aren’t done because Godel’s method for finding undecidable propositions still works for N+G and for N+~G. I.e. we know that both of these systems still contain an undecidable propostion. In “standard” number theory (N+G) there is a proposition (G’) that can not be decided by deducing from the list of axioms N+G so we can add either G’ or ~G’ as axioms creating another pair of number theories and each of those branches into another pair and so on and so on and so on… We end up with a binary tree of number theories that extends out infinitely.

To get back to your questions, the postulates that define number theory are listed in the book as the definition of TNT. Sadly, I seem to have temporarily misplaced my copy but they include the peano postulates, the definitions of addition and multiplication and the logical rules of inference. None of these basic axioms are redefined to make non-standard number theories. Instead, as undecidable propositions are found, they (or their negations) are added as new axioms. And yes, I’m afraid you might have to re-read the book because Hofstadter’s explaination was a thousand times clearer than mine could hope to be :slight_smile:

The Axiom of Choice is one that there’s some difference of opinion on. It hasn’t been proven to be provable from the other axioms, so many people work with the working assumption that it’s independent, like Euclid’s straight line intersection one. (If this were to ever lead to a clear contradiction, that would be a great discovery.)

Therefore, you can have a few number theories based on taking AC as an axiom, or it’s denial as an axiom, and wind up with some theories that are workable, differing in some subtle and esoteric ways. Typically, the differences are going to be in the handling of transfinites – nothing that will change your basic arithmetic, or it would quickly be an inconsistent theory.

74westy’s explanation is basically good. It’d be tough to expand on it without getting into the details.

Here is Wikipedia’s article on Peano Arithmetic. It has nice links to articles relating to axioms and other theories. Note that Peano Arithmetic is just one of a multiude of known interesting formulations of numeric systems. It is considered a very basic system that has just enough to state some key theorems. Most importantly, it allows basic proofs by induction. But it is hardly powerful enough to represent all interesting proofs about numbers, e.g., real numbers for example.

In Computer Science, there has been a lot of interest in limited number theories: ones that can be used to express basic concepts but not too powerful that automatic proofs are impossible. (Although every system I’ve dealt with, the complexity of theorem proving is always at least exponential time, with double exponential or more being by far the most common.) Many people, including my thesis advisor, went thru the most famous decidable theories and worked out their complexities decades ago. Charlie Rackoff collected a lot of these results in a Springer-Verlag monograph. The definite reference if you want to know a lot about only the decidable logics.

At one point, I knew more about Presburger Arithmetic than anyone here could imagine. (Note that the article’s statement that it is “one of the few” problems that provably require exponential time is a laughable understatement. Obviously the author never read Rackoff’s book or any advanced text on complexity theory. “Few” indeed!)

Just to give some history to this:

Nikolai Ivanovich Lobachewsky* (1793-1856) “On the Principles of Geometry” (1829) is the one to whom credit is usually given for the geometry that uses the infinite number of parallel lines. As that site also notes, a great number of people were thinking along the same lines even before him.

Georg Friedrich Bernhard Riemann developed the other case in which no parallels can be found.

Here’s a better Non-Euclidian Geometry page with a few diagrams, lots of names, and millions of links.

  • You get more hits if you spell it Lobachevsky.

We got taught to read the book as part of my CS/AI degree. After reading the first few chapters, I was pretty mystified as to why, seeing as they deal with Bach mostly.

I wonder if Peppermint Patty ever blamed all of her D-minuses on her ongoing exploration of non-standard number theories in her homework and on the tests.

Reading the Peano and Presburger articles was a depressing experience. I’ve accepted the fact that there are areas of higher mathematics I will never understand, but I thought arithmetic was firmly in my grasp.