Cheap and Secure Web Hosting Provider : See Now

Finding a finite model

, , No Comments
Problem Detail: 

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!

Asked By : InsigMath

Answered By : Gilles

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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24085

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback