Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For n an integer greater than 2, Can one always get a complete theory over a finite language with exactly n models (up to isomorphism)?

There's a theorem that says that 2 is impossible.

My understanding is this should be doable in a finite language, but I don't know how.

If you switch to a countable language, then you can do it as follows. To get 3 models, take the theory of unbounded dense linear orderings together with a sequence of increase constants < ci: i < ω >. Then the ci's can either have no upper bound, an upper bound but no sup, or have a sup. This gives exactly 3 models. To get a number bigger than 3, we include a way to color all elements, and require that each color is unbounded and dense. (The ci's can be whatever color you like.) Then, we get one model for each color of the sup plus the two sup-less models.

share|improve this question
add comment

2 Answers

up vote 11 down vote accepted

You can refine Ehrenfeucht's example getting rid of the constants.

Here is what John Baldwin suggested:

Consider the theory in the language L={≤}, saying

  • ≤ is a preorder (transitive, reflexive, not necessarily anti-symmetric) without least or last element. (Notice that the binary relation defined by (x≤y ^ y≤x) is an equivalence relation. Call it E.)
  • For each n, E has exactly one class of size n. Call it C_n.
  • C_i≤C_j (for i≤j) setwise.
  • E-classes are densely ordered: For any two points there is a point ≤-between them and not E equivalent to any of them.

Check that this theory is complete.

Note that each finite equivalence class in this new theory plays the role of one of the constants in the classical example, so you get three countable models the same way.

share|improve this answer
    
excellent, thanks. –  Richard Dore Oct 26 '09 at 16:01
    
@Javier: there was no reason to make this post community wiki. I've added a section to the FAQ explaining community wiki mode: mathoverflow.net/faq#communitywiki –  Anton Geraschenko Oct 26 '09 at 16:31
    
Sorry, Anton. My mistake. –  Javier Moreno Oct 29 '09 at 18:10
add comment

See Vaught's theorem on wikipedia. It says:

Ehrenfeucht gave the following example of a theory with 3 countable models: the language has a relation ≥ and a countable number of constants c0, c1, ...with axioms stating that ≥ is a dense unbounded total order, and c0< c1

share|improve this answer
    
    
Yea. You can color the limit of the c's (if it exists) to get a higher number of models as well. But that isn't a finite language, just countably infinite. –  Richard Dore Oct 5 '09 at 23:28
add comment

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.