Prove that there exists a sentence $\phi$ such that for every model $\beta \models \phi $ iff $ \beta \cong \alpha $

111 Views Asked by At

Let's say the model $\alpha$ consists of $(A, a(R_1), a(R_2)...a(R_n))$, where A is a finite set, and all $R_i$ are relation symbols, $a$ denotes their interpretation in the model. I need to prove that a sentence $\phi_a$ exists, which satisfies the following for any model $\beta$:

$$\beta \models \phi_a \iff \beta \cong \alpha $$

Also, let's denote the elements of A as $a_o, a_1... a_n$

The guide says to start by constructing a formula $\psi$, telling which relation each string of elements belongs to (using free variables $v_o... v_n$ and quantifiers). But I am not exactly sure how to do this and how it relates to the question.

1

There are 1 best solutions below

4
On BEST ANSWER

Write down a sentence that says: there are $n$ objects and only $n$ objects, and those objects fulfill the relation $R_1$ in this particular way, and $R_2$ in that particular way, and so on.

One can write a sentence like that without too much effort. It will start like this $$\exists x_1\ \exists x_2\ \cdots\ \exists x_n [\ \ \dots\dots\dots\dots \ \ ],$$ where inside the brackets we say, first that every $z$ is equal to one of the $x_i$'s, and all the $x_i$'s are different, and then we also say things like $R_1(x_2,x_5)$ and $R_1(x_3,x_2)$ and so on, for all the instances that hold in the original model, and then we say things like $\neg R_1(x_4,x_7)$ and so on for the instances that don't hold. Do you see how it goes?

The thing to notice is that any model of this sentence will look just like your given model (except that I used $n$ instead of $n+1$), and they will be isomorphic. The way that the model $\beta$ realizes the existential quantifiers will provide the isomorphism.