Isomorphism between two structures.

Question

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

Answer 1

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

Answer 2

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

and

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