Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Up to isomorphism.

For instance, the group axioms are verified by an infinite number of non-isomorphic algebraic structures. But the Peano axioms, I think (my proof may lack some formality due to my lack of in depth knowledge of logic and foundations, but I think it's rigorous enough that someone more knowledgeable could make it into a formal proof) uniquely determine $\mathbb{N}$: any two structures that satisfy the Peano axioms must be isomorphic.

One thing I noted is that the axioms for standard classes of structures (rings, groups etc - all of which have many non-isomorphic instances) are always of the form:

$$(\forall a_1...a_n\in A)\ \phi(a_1...a_n) = \psi(a_1...a_n)$$

Where $\phi$ and $\psi$ are functions "defined in terms of" the structure operations. On the other hand, the Peano axioms include axioms of other forms, notably the ones governing the successor operations. Could this be relevant?

Are there any results describing the relationship between an axiom set, and the number of non-isomorphic structures verifying it?

share|improve this question
    
the Peano axioms, and in fact no first order axioms can uniquely determine the natural numbers. This is very strange result. –  user58512 Feb 18 '13 at 17:00
3  
It is (or ought to be) a familiar theorem that first-order Peano Arithmetic is not categorical. It isn't even countably categorical -- i.e. it can have non-isomorphic models with countable domains. It is also (or ought to be) a familiar theorem that second-order Peano Arithmetic is categorical (assuming that the second-order quantifiers are constrained to run over the full power set of the numbers). Which do you mean? –  Peter Smith Feb 18 '13 at 17:19
    
I have no idea. My proof assumes that 0, S(0), S(S(0))... are the only elements in the structure, and that a sentence "For all $a \in \mathbb{N}$: $P(a, b) \implies P(a, S(b))$ can be used as an inductive step, is that enough information? And what do you mean by categorical? I have little background in metamathematics and none in category theory, but I'll try to keep up if you could give me some hints as to what to look up. –  Jack M Feb 18 '13 at 17:45
    
To get that $\mathbb{N}$ is uniquely determined, you have to assume that induction works. That is, you must take as an axiom (but not a first order axiom) that if a subset $P$ contains 0 and $n\in P$ implies $n+1\in P$, then $P=\mathbb{N}$. –  Francis Adams Feb 18 '13 at 18:08
1  
The Peano axioms in first-order logic do not uniquely define $\mathbb{N}$; the induction rule is not strong enough to rule out certain (quite strange) models of the Peano axioms. However, if you interpret the Peano axioms in second-order logic with the full semantics, then they uniquely define $\mathbb{N}$. In addition, if I remember correctly, there do exist uncomputable sets of first-order axioms that uniquely determine $\mathbb{N}$; for example, you could say that the axioms of your system are exactly the statements about $\mathbb{N}$ that are true. –  Tanner Swett Feb 18 '13 at 18:33

3 Answers 3

up vote 5 down vote accepted

If there is a sentence specifying the cardinality of the model to be a finite $n$ then you can write an axiom schema which ensures its uniqueness.

But it a [consistent] first-order theory does not have finite models then it has models in every cardinality. This follows from the Lowenheim-Skolem theorems. Clearly, then, those models are not isomorphic.

Sometimes, though, a theory has a unique model in a particular cardinality, this is called categoricity. There are several tests whether or not a theory is categorical in any cardinality, but those usually require some more knowledge in model theory.

It is not a coincidence that model theory and algebra have a large intersection in modern mathematics.

share|improve this answer
    
Thanks for the pointer on "categoricity". –  Jack M Feb 18 '13 at 17:50
    
Perhaps it should be specified here at "theory" means first-order theory. –  Henning Makholm Feb 18 '13 at 18:15
    
@Henning, thanks! –  Asaf Karagila Feb 18 '13 at 18:18

Actually, Peano Arithmetic does not uniquely determine $\mathbb{N}$, even if you fix the cardinality of the structure you want (also called a model). These are the so-called "non-standard" models of PA, and there are a lot of them: $2^{\aleph_0}$ to be more precise. They all look like "end-extensions" of $\mathbb{N}$. That is, $\mathbb{N}$ plus a bunch of stuff at the end. There are some things you can say about what such a model looks like and how its arithmetic behaves. Read more about that here.

That link also shows how to show that such models exist, but let me outline a construction here using Godel's incompleteness theorem. Godel proved, among other things, that there is a logical sentence $G$ that is true in $\mathbb{N}$, but cannot be proved or disproved from the axioms of PA. Thus if we consider the axioms PA $+ \neg G$, Peano Arithmetic plus the the negation of $G$, this is consistent, and hence has a model by standard results in logic. Of course, any model of PA $+ \neg G$ also satisfies PA, but this model disagrees with $\mathbb{N}$ on the truth of $G$, so they cannot be isomorphic.


To go into a little more detail about your question as a whole, let me explain what Peter Smith brought up in the comments. There is a notion of a "countably categorical" or "$\omega$ - categorical" theory. This is a collection of axioms where every countable model is isomorphic. You can think of this as uniquely determining a (countable) structure. Given a collection of axioms (which we will call a theory), it is of interest to determine when it is or is not $\omega$-categorial, how many models there are, and perhaps how much "variation" there can be. There are many equivalent conditions for $\omega$-categoricity outlined here, but I will try to give you some context before sending you to read Wikipedia.

You can think of a theory as the basic operating system behind your model. The theory tells you what axioms you must satisfy. However, there are all sorts of possible extra software packages you can install. These extra packages are called "types". Some of these types are not compatible with your operating system, so you give up on them immediately. Some software packages are compatible with your operating system, but not with each other. Each "type" promises you the existence of a collection of special objects in your model. A $1$-type gives you one special element, whereas a general $n$-type gives you a collection of $n$ elements satisfying certain properties with respect to each other, and the model in general. Unless I'm mistaken, I don't think that types are the final word on the issue of non-isomorphic models, but they are certainly important to that end. Understanding what sort of types are compatible with our theory, and in what combination, tells us a lot about the sorts of models our theory can have.

share|improve this answer
1  
Note that some people distinguish between "Peano Arithmetic" and "Peano's axioms". The former is a first-order theory (with an axiom schema for induction with infinitely many instances). The latter include a single second-order induction axiom and do determine the model up to isomorphism, at least under the standard semantics for higher-order logic. –  Henning Makholm Feb 18 '13 at 18:14
    
@HenningMakholm Thanks for pointing that out, I'd not heard of that convention. To the OP: Everything I have said above is about first-order theories. –  Isaac Solomon Feb 18 '13 at 18:17
    
When you say at the end of paragraph 2 that "therefore they cannot be isomorphic", do you mean isomorphic in the sense of a bijection f with f(a + b) = f(a) + f(b)? –  Jack M Feb 18 '13 at 20:03
    
Here the isomorphism is understood to preserve the arithmetic structure which is based on the successor symbol. So there is no bijection $f$ for which $S(a) = b$ is true iff $S(f(a)) = f(b)$. –  Isaac Solomon Feb 18 '13 at 20:17

A footnote. The OP says in his comments that his putative proof that any two structures that satisfy the Peano axioms must be isomorphic assumes that $0$, $S(0)$, $S(S(0))$, ... are the only elements in the structure.

Suppose $T$ is a theory of arithmetic which contains at least Robinson Arithmetic (i.e. the usual axioms for successor, and recursion axioms for addition and multiplication). Say that a model of $T$ is slim iff the only elements of its domain are the denotations of '$\mathsf{0}$', '$\mathsf{S(0)}$', '$\mathsf{S(S(0))}$'. It is easily shown that all the 'slim' models of $T$ are isomorphic. So a fortiori, the slim models of first-order PA are all isomorphic, and so are slim models of second-order PA.

So yes, IF the OP is entitled to the assumption that his version of PA only has slim models, then his conclusion the theory is categorical is correct.

BUT: if we dealing with first-order PA, then the assumption is illegitimate. There can be non-slim models that verify all the first-order axioms (as other answers have noted).

On the other hand, if we are dealing with second-order PA, then the assumption is correct. In fact, Dedekind's categoricity proof proceeds by showing that all the models of second-order PA are slim.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.