1
$\begingroup$

I have to prove the following:

If a theory with equality $K$ has arbitrarily large finite normal models, then it has a denumerable normal model.

The setting is first-order logic. My attempt:

Assume $K$ has arbitrary large finite normal models $M_1, M_2,...$ with finite domains $D_1, D_2,..$, resepectively. Define $$D^* = \bigcup_{i=1}^\infty D_i.$$ Let the interpretations $M^*$ of $K$ have domain $D^*$. $M^*$ is again a normal model but it is infinite. The extension of the Skolem-Löwenheim Theorem says that any theory with equality that has an infinite normal model has a denumerable normal model. Hence, $K$ has a denumerable normal model.

I have the feeling that what I am doing is not really correct: I do not know that $K$ has infinitely many finite normal models. Also, how would I define $M^*$ such that it is again a normal model. Can someone help me with this proof?

EDIT

(Normal model in my book means the relation corresponding to the predicate = is an identitiy relation in the domain of the model).

Let $K$ be a theory with equality in the language $\mathcal{L}$. We add denumerably many new constant symbols $c_n$ for $n\in \mathbb{N}$ to $\mathcal{L}$. We also add denumerably many axioms $c_n \neq c_m$ for $n \neq m$. We call this new theory $K^*$. A normal model of $K^*$ is also a normal model of $K$, since each axiom of $K$ is also in $K^*$. Let $\Gamma$ be an arbitrary finite subset of axioms of $K^*$. We can write $\Gamma$ as the union of finitely many old axioms from $K$ and finitely many new axioms in $K^*$. Since $K$ has arbitrarily large finite normal models, we know there is an interpretation $M$ such that the finitely many old axioms are true. But how do I know the finitely many new axioms are true in $M$?

I do understand that if we have a normal model for $\Gamma$, by the compactness theorem there is a normal model $M^*$, which is denumerable, for $K^*$ and hence for $K$.

$\endgroup$

1 Answer 1

3
$\begingroup$

I am not sure what you mean by a "normal model", but you are correct in thinking that you aren't on the right track. The trick is to use the compactness theorem with a (cleverly chosen) new language.

As a hint, you might take your old language and add a constant symbol $c_n$ for each natural number. Then you can take $K$ and add axioms saying that $c_m \neq c_n$.

  • Do you see why a model of this theory must be an infinite model of $K$?

  • Do you see why this theory should be finitely satisfiable? (This is where you will use "arbitrarily large finite models", since any finite subset of your axioms can only refer to finitely many of the new constants $c_n$)

  • Can you use the compactness theorem to finish the proof?


Edit:

you're on the right track! You have a finite subset of $K^*$. You are correct in thinking that this finite subset can be written as $K_0 \cup N_0$ where $K_0$ is some finite subset of the "old" axioms, and $N_0$ is a finite subset of the "new" axioms.

Now you want to find a model of $K_0 \cup N_0$. You know how to find models of $K$, and any model of $K$ is also a model of $K_0$. So all you have to do is find a model of $K$ which is also a model of $N_0$. Remember every axiom in $N_0$ is of the form $c_m \neq c_n$ for some constant symbols, so your task becomes this:

  • Find a model of $K$
  • Assign each $c_n$ to some element of your model
  • Ensure that $c_n \neq c_m$ exactly when $N_0$ tells you they must be different.

Of course, if $N_0$ says the first $100$ constant symbols are all different, you will not be able to do this in a model with $< 100$ elements. Since you are assuming you have arbitrarily large finite models of $K$, though, you can always find a big enough model to do what you want.


I hope this helps ^_^

$\endgroup$
3
  • 2
    $\begingroup$ I’d not seen the term before, but I found a set of lecture notes online in which a normal model is one in which the relation $=$ is interpreted as real equality. (I’d take the ultraproduct, but I like to see the machinery. :-)) $\endgroup$ Oct 12, 2020 at 19:08
  • 1
    $\begingroup$ @BrianM.Scott - Good to know! Also, taking ultraproducts would probably be more in line with OP's original idea of somehow "gluing" the finite models together. I opted for compactness because I figured every model theory class has to teach compactness, whereas some (like my first model theory class) never get to ultraproducts at all (regrettably) $\endgroup$ Oct 12, 2020 at 19:14
  • $\begingroup$ Hi @HallaSurvivor, I edited my post where I try to write down the proof you suggest. :) I think your second bullet point is still not clear to me. $\endgroup$
    – Ruby
    Oct 12, 2020 at 19:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .