0
$\begingroup$

Hello I am having difficulty with this question, I am not even sure what strategy one would go about proving something like this:

Suppose $L$ is a language which includes an infinite list $c_1,c_2,\cdots$ of constant symbols. Let $\Gamma$ be a set of sentences $\Gamma = \{c_i \neq c_j \mid i,j\in N, i < j\}$. Let A be a sentence such that $\Gamma \Rightarrow A$. Prove that $A$ has a finite model.

I am not sure whether I would prove this via a contradiction (i.e., assume $A$ has an infinite model, or if I show a finite model that works or some how assume that we can have an infinite model and then use some sort of compactness to show it can be finite. I am a little all over the place with this question, please any help would be great!

$\endgroup$
  • 3
    $\begingroup$ (Possible) hint: $A$ can only refer to a finite number of constant symbols. $\endgroup$ – Dave Clarke Apr 24 '14 at 19:49
  • 1
    $\begingroup$ Showing that $A$ has an infinite model doesn't give a contradiction: it could have a finite model too. $\endgroup$ – David Richerby Apr 24 '14 at 19:59
2
$\begingroup$

Note that you're looking for a model of $\{A\}$, not of $\Gamma \cup \{A\}$ (which obviously has no finite model since all the constants need to be pairwise distinct).

Proof by contradiction would be “assume $A$ has only infinite models or no model at all”. This isn't likely to lead anywhere.

Compactness could let you find a model of some set of sentences but you'd still have to prove the existence of a finite model at some point. Anyway, there is an easy direct proof.

The smallest model of a set of sentences is the one that collapses all the ways in which the differences between elements don't matter. You don't have to go all the way to apply this intuition: you can find a smaller model by collapsing some elements that don't matter. Here, you have an infinite number of constants; to find a finite model, you'll have to map infinitely many to the same element of the model (possibly to several elements).

In particular, if some constants do not appear in your theory at all, they can all be mapped to the same model element.

The theory is $\{A\}$. This is a finite theory, consisting of (one) finite formula. Only a finite number of constants appear in this formula. Let $C(A)$ be the set of constants that appear in $A$. Define $\mathscr{M}: c \mapsto c$ if $c \in C(A)$, $c \mapsto c_1$ if $c \notin C(A)$. Then $\mathscr{M}$ satisfies $A$.

$\endgroup$

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.