Prove that for every finite structure $\mathfrak{A} $ where a signature is finite there exists such set of first order logic formulas $\Delta$ that $ \mathfrak{A} \models \Delta $ and for every structure $\mathfrak{B} \models \Delta $ there exists a homomorphism $h: \mathfrak{B} \to \mathfrak{A}$

I don't know how to start. Please hint me.

My idea: $\mathfrak{A} = (A,\Sigma^f_A, \Sigma^R_A), \mathfrak{B} = (B,\Sigma^f_B, \Sigma^R_B), A = \{a_1, .. , a_n\}, v: A \to Z \text{ where } Z = \{z_1, .., z_n\} \text{ is a set of variables }, v(a_i) = z_i $

Now, my formula is: $$\Delta_r \exists a_1, ..\exists a_i \bigwedge_{1 \le i \le n, r \in \Sigma^r_A} r(z_1, .., z_i)$$

$$\Delta_f \exists a_1, ..\exists a_i \bigwedge_{0 \le i \le n, f \in \Sigma^f_A} f(z_1, .., z_n) = v(f(v^{-1}(z_1), .., f(v^{-1}(z_i))$$

$$\phi_n = \exists_{z_1}, ...\exists_{z_n} \forall_{z_n+1} \bigwedge_{1 \le k,l \le n } \neg(z_k = z_l) \wedge \bigvee_{1 \le k \le n} (z_{n+1}= z_k)$$

$$\Delta = \Delta_r \wedge \Delta_f \wedge \phi_n$$

$\phi_n$ just ensures that a structure S satisfying $|S|=n$ It can be easy proved that $\mathfrak{A} \models \Delta$. Let's skip it.

So, let any $(\mathfrak{B}, \delta) \models \Delta $ Let $h$ be a function $h: A \to B, h(v^{-1}(z_i)) = \delta(z_i) $. Let's show that $h$ is an isomorphism.

1) So, $h$ must be a bijection. I cannot deal with that but my intuition says me that it is possible.

2) For $n \ge 0, f \in \Sigma_n^f, \{a_1, ..., a_n\} \subseteq A, h(f^A(a_1, .., a_n)) = f^B(h(a_1), ..., h(a_n))$ Let $$(\mathfrak{B}, \delta) \models \Delta $$ Let $$f^B \in \Sigma^f_B, f^B( \delta(z_1), .., \delta(z_n)) = \delta(v(f^A(v^{-1}(z_1), .., v^{-1}(z_n)))$$ is true because of the $(\mathfrak{B}, \delta) \models \Delta $

$$ f^B( \delta(z_1), .., \delta(z_n)) = f^B(h(v^{-1})z_1)),..,h(v^{-1}(z_n))) = f^B(h(a_1), .., h_(a_n) = \delta(v(f^A(v^{-1}(z_1), .., v^{-1}(z_n))) = \delta (v(f_A(a_1,..,a_n)) = h(f^A(a_1, .., a_n))$$ so 2) is true.

3) For $n \ge 1, r \in \Sigma_n^R, \{a_1, .., a_n \} \subseteq A, r^A(a_1,..,a_n) \iff r^B(h(a_1),..,h(a_n))$. Let $r^A \in \Sigma^R_A $ Let $\{a_1, .., a_n\} $ is satisfied. Because of $(\mathfrak{B}, \delta) \models \Delta_r$ Therefore, $r^A(\delta(v(a_1)), .., \delta(v(a_n))) = r^A(h(a_1), .., h(a_n)) = \gamma$. And such $\gamma \in \Sigma^R_B $ because $(\mathfrak{B}, \delta) \models \Delta_r$ The $\Leftarrow$ is similar to $\Rightarrow$

Please mark my solution and help me with 1).


This is a slightly odd question - as far as I can tell, it's actually easier to prove the following stronger result:

For every finite structure $\mathfrak{A}$ in a finite signature, there is a single sentence $\delta$ such that for every $\mathfrak{B}\models \delta$ we have $\mathfrak{B}\cong\mathfrak{A}$.

To do this, you need to find a way to "describe $\mathfrak{A}$ completely". HINT: Think about a sentence of the form "$\exists x_1\exists x_2 . . .\exists x_n\theta(x_1,x_2, . . ., x_n)$" (where $n$ is the cardinality of $\mathfrak{A}$). Do you see a way to choose an appropriate $\theta$ so that this sentence completely describes $\mathfrak{A}$? Subhint: Think in analogy with Cayley tables for groups - do you see why the Cayley table of a group determines it up to isomorphism? Do you see how to use this idea here?

  • $\begingroup$ I edited. Please glance at it :) $\endgroup$ – user376326 Oct 21 '16 at 15:36

Your Answer

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