LEC LOG 2

definability of a class of structures

The set of all graphs with a vertex cover of size $k$:

$$\exists x_1\exists x_2\dots \exists x_k\left(\underset{i,j\in \{i,\dots ,k\}}{\bigwedge }{x}_i\ne x_j\right)\wedge \forall x\forall y(E(x,y)⟹{\vee }_{i\in \{1,\dots ,k\}}(x=x_i\vee y=x_i)).$$

Tried to FO-define connected graphs and failed; could not avoid recursive structures. Saw that it is “extended definable”, though.

---

homomorphisms

Let $\mathcal{A}$ and $\mathcal{B}$ be models over the same language $L$. A homomorphism from $\mathcal{A}$ to $\mathcal{B}$ is a map $h:|\mathcal{A}|\to |\mathcal{B}|$, where $|\mathcal{A}|$ is the underlying set or universe of discourse of $\mathcal{A}$, satisfying the following properties:

1. For all constant symbols $c$, $h(c^{\mathcal{A}})=h(c^{\mathcal{B}})$.
2. For all relational symbols $r$, $(a_1,\dots ,a_n)\in r^{\mathcal{A}}⟺(h(a_1),\dots ,h(a_n))\in r^{\mathcal{B}}$.