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

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_r' = \bigwedge_{r^A \in \Sigma^r_A} \forall a_1, ..., a_i r^A(a_1, .., a_i) \Rightarrow r^B(v(a_1), .., v(a_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).

  • $\begingroup$ What about 2)? Can I repair my solution? $\endgroup$ – user376326 Oct 21 '16 at 19:56
  • $\begingroup$ I added $\Delta_r'$ Is it better? $\endgroup$ – user376326 Oct 21 '16 at 20:02
  • $\begingroup$ I edited my post. $\endgroup$ – user376326 Oct 21 '16 at 20:09
  • $\begingroup$ Can I improve my solution or not? $\endgroup$ – user376326 Oct 21 '16 at 20:17
  • $\begingroup$ In your statement of the problem, where you said "there exists a homomorphism", did you mean "isomorphism"? $\endgroup$ – bof Oct 21 '16 at 22:43

Suppose the structure $\mathfrak{A}$ has domain $A$ with $n$ distinct elements $a_1,\dots,a_n.$

Let $\Gamma$ be the set of all $\varphi$ such that:

  1. $\varphi$ is an atomic formula or the negation of an atomic formula (in our language) with free variables exactly $x_1,\dots,x_n,$


  1. $\mathfrak{A}\models\varphi(a_1,\dots,a_n).$

$\Gamma$ is a finite set of formulas, since the language has a finite signature (and $A$ is finite).

Now use the sentence

\begin{align} (\exists x_1)\dots(\exists x_n)\left((\forall x)\big(\bigvee_{k=1}^nx=x_k\big)\,\land\, \bigwedge \Gamma\right). \end{align}

  • $\begingroup$ Still negation missing, take A={p(0,0),p(1,1)} and B={p(0,0),p(0,1),p(1,1)}, the formula for A will be more or less p(0,0) & p(1,1). Which is also satisified by B. But you cannot find a homorphism, if you map h(0)=0 and h(1)=0 you will render p(1,0) true although it is not. if you map h(0)=0 and h(1)=1 you will render p(0,1) false although it is not. $\endgroup$ – Transfinite Numbers Oct 21 '16 at 20:28
  • $\begingroup$ Thank you, I added the negations in -- you're right, that was an oversight. $\endgroup$ – Mitchell Spector Oct 21 '16 at 20:30
  • $\begingroup$ What do you mean when you say 'language'? Please refer me somewhere. $\endgroup$ – user376326 Oct 21 '16 at 20:42
  • $\begingroup$ When I said "formula in our language", I just meant a formula built from the constant symbols, function symbols, and relation symbols in the signature, and the equality symbol. There are only finitely many symbols in the signature, so there are only finitely many atomic formulas (and only finitely many negations of atomic formulas) in that language. $\endgroup$ – Mitchell Spector Oct 21 '16 at 22:21

$\newcommand{\rdiag}{\operatorname{rdiag}}$If you allow for each element $d$ of the domain $D_M$ a constant $c_d$, and if we ignore functions for the moment, you can construct the relational diagram:

$$\rdiag^+_M = \{ r(c_{d_1}, \ldots, c_{d_n}) \mid d_1,\ldots,d_n \in D_M, \langle d_1,\ldots,d_n\rangle \in r_M \}$$

$$\rdiag^-_M = \{ ¬r(c_{d_1}, \ldots, c_{d_n}) \mid d_1,\ldots,d_n \in D_M, \langle d_1,\ldots,d_n\rangle \notin r_M \}$$

$$\rdiag_M = \rdiag^+_M ∪ \rdiag^-_M$$

Since $D_M$ and $r_M$ are finite, $\rdiag_M$ is finite and can be represented as a single conjunction. For another model $N$ the constants $c_d$ will be interpreted again, and when this other model satisfies $\rdiag_M$, then $h(\{c_d\}_N) := \{c_d\}_M$ is a homomorphism.

  • $\begingroup$ I don't understand what do you mean by diagram. What do you think about my solution/ $\endgroup$ – user376326 Oct 21 '16 at 19:48
  • $\begingroup$ modeltheory.wikia.com/wiki/Diagram $\endgroup$ – Transfinite Numbers Oct 21 '16 at 19:56
  • $\begingroup$ Please note that I edited ( I added $ \Delta_r'$ ) and please look at comments below my post. $\endgroup$ – user376326 Oct 21 '16 at 20:02
  • $\begingroup$ Please note that correct notation is $\langle d_1,\ldots,d_n\rangle$, not $<d_1,\ldots,d_n>$. And I did some other copy-editing as well. $\qquad$ $\endgroup$ – Michael Hardy Oct 21 '16 at 22:38

Your Answer

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