structures of first-order logic (задачи)

[gefest_md]

Проверьте, пожалуйста несколько задач.

К первой задачи: Множество всех $\left(b_1,\,b_2,\,\dots\,b_n\right)\in\left(U_M\right)^n$ для которых $M\models\varphi\left(b_1,\,b_2,\,\dots\,b_n\right)$ называется "definable subset of $M$ (by $\varphi$)".

Цитата:

2.12. Let $U_M$ be the underlying set for structure $M$. Suppose that $A\subset\left(U_M\right)^3$ and $B\subset\left(U_M\right)^3$ are definable subsets of $M.$
(a) Show that $A\times B\subset\left(U_M\right)^6.$
(b) Suppose we rearrange the order of the $n-$tuples. Consider the set of all $(z,\,x,\,y)$ such that $(x,\,y,\,z)$ is in A. Show that this set is definable.
(c) Show that $C\subset\left(U_M\right)^2$ is definable where $C$ is the set of ordered pairs $(x,\,y)$ such that $(x,\,y,\,z)$ is in $A$ for some $z.$
(d) Show that $D\subset\left(U_M\right)^2$ is definable where $D$ is the set of ordered pairs $(x,\,y)$ such that both $(x,\,y,\,z)\in A$ for some $z$ and $(x,\,y,\,z)\in B$ for some $z.$
(e) Show that $E\subset\left(U_M\right)^2$ is definable where $E$ is the set of ordered pairs $(x,\,y)$ such that. for some $z$, $(x,\,y,\,z)$ is in both $A$ and $B.$

Пусть $\varphi$ и $\psi$ формулы определяющие $A$ и $B$, соответсвенно. Тогда мои ответы такие:
(a) $\varphi\wedge\psi$
(b) $\bigvee_i\left(x_1=a_{i{3}}\wedge x_2=a_{i{1}}\wedge x_3=a_{i{2}}\right)$, где $\left(a_{i{1}},\,a_{i{2}},\,a_{i{3}}\right)\in A$
(c) $\exists z\varphi(x,\,y,\,z)$
(d) $\exists z\varphi(x,\,y,\,z)\wedge\exists z\psi(x,\,y,\,z)$
(e) $\exists z\left(\varphi(x,\,y,\,z)\wedge\psi(x,\,y,\,z)\right)$

Цитата:

2.13. We define the distance $d(a,\,b)$ between two vertices $a$ and $b$ of a graph as the least number of edges in a path from $a$ to $b.$ If no such path exists, then $d(a,\,b)=\infty$. Recall that $\nu_G$ is the vocabulary of graphs.
(a) Show that, for any $n\in\mathbb{N}$, there exists a $\nu_G-$ formula $\delta_n(x,\,y)$ so that, for any graph $G$, $G\models\delta_n(a,\,b)$ if and only if $d(a,\,b)=n.$ (Define the formulas $\delta_n(x,\,y)$ by induction on $n.$)

$\delta_1(x,\,y)$: $R(x,\,y)$
$\delta_2(x,\,y)$: $\neg\delta_1(x,\,y)\wedge\exists x_1\left(R\left(x,\,x_1\right)\wedge R\left(x_1,\,y\right)\right)$

$\dots$

$\delta_n(x,\,y)$: $\neg\delta_1(x,\,y)\wedge\neg\delta_2(x,\,y)\wedge\dots\wedge\neg\delta_{n-1}(x,\,y)\wedge\exists x_1\exists x_2\dots\exists x_{n-1}\left(R\left(x,\,x_1\right)\wedge R\left(x_1,\,x_2\right)\wedge\dots\wedge R\left(x_{n-1},\,y\right)\right)$

Цитата:

2.14. (a) Define a $\nu_G-$sentence $\varphi$ such that $\varphi$ has arbitrarily large finite models and, for any model $G$, $G$ is a connected graph.

$\exists x\forall y\left(\neg(x=y)\to R(x,\,y)\right)$.

Цитата:

2.15. (a) Define a $\nu_G-$sentence $\varphi$ such that $\neg\varphi$ has arbitrarily large finite models and, $G\models\varphi$ for any connected graph $G$.

$\forall x\exists y R(x,\,y)$

Цитата:

2.16. (a) Define a $\nu_G-$sentence $\varphi$ such that $\varphi$ has arbitrarily large finite models and, for any finite model $G$ of $\varphi$, $|G|$ is even.

$\forall x\exists!yR(x,y)$