11
$\begingroup$

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 increasing constants $\langle c_i: i < \omega\rangle$. Then the $c_i$’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 $c_i$’s can be whatever color you like.) Then, we get one model for each color of the sup plus the two sup-less models.

$\endgroup$
14
$\begingroup$

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

Here is what John Baldwin suggested:

Consider the theory in the language $L=\{\le\}$, saying

  • $\le$ is a total preorder (transitive, total [hence reflexive], not necessarily anti-symmetric) without least or last element. (Notice that the binary relation defined by $x\le y \land y\le 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\le C_j$ (for $i\le j$) setwise.
  • $E$-classes are densely ordered: for any two points there is a point $\le$-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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

I think there is a problem with Baldwin's answer as cited above. There might be additional non-isomorphic models which have infinite equivalence classes $C_i$ which can have the order type of $\mathbb{Z}$ or of two disjoint copies of $\mathbb{Z}$ above each other or whatsoever. So one would have to make it as follows:

  • The ordering of the points (modulo equivalence) is a dense linear order $<$ without endpoints.

  • If $x < y$ and the equivalence class of $x$ has at least $n$ elements then the equivalence class of $y$ has also at least $n$ elements.

  • For each $n>1$ there is a least $x$, call it $c_n$, where the equivalence class has exactly $n$ elements.

  • The classes $c_n$ play the same role as the constants in Ehrenfeuchts example.

Frank Stephan (fstephan@comp.nus.edu.sg)

$\endgroup$
  • 1
    $\begingroup$ The set of infinite equivalence classes cannot have the order type of Z. They are densele ordered. $\endgroup$ – Emil Jeřábek Apr 9 at 8:03
  • 1
    $\begingroup$ To amplify Emil's comment: The linear order of all the $E$-classes was assumed to be dense, and therefore (in countable models) isomorphic to $\mathbb Q$. Among these, the finite classes are ordered like $\mathbb N$. For any copy of $\mathbb N$ in $\mathbb Q$, the difference $\mathbb Q-\mathbb N$ has order-type $\mathbb Q$. $\endgroup$ – Andreas Blass Apr 9 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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