Existence of an embedding?

Question

Let $\mathcal{L}=\{R\}$ a language of the first order. We consider the set of graphs (which are irreflixive and symmetric). Then we define for a graph $G$ the following property $P$ : for $S_1$ and $S_2$ finite and disjoint $\subseteq G$, there exists $z\in G$ such that for all $x\in S_1$, $y\in S_2$ we have $R(x,z)$ and $\neg R(y,z)$. We denote $T$ the first order theory which satisfies these three properties.

First, I proved that there exists a countable model. Then I must prove that for a countable graph $K$ and a model $\mathcal{H}=(H,R)$ of $T$ (not necessary countable) I can find an embedding between $K$ and $H$.

Here is my attempt : I think that if $K$ could satisfy $P$, I could find an embedding between $K$ (which would become a countable model of $T$) and $\mathcal{H}$ by Lowenheim-Skolem. That means that every countable graph satisfies $P$.

First thing I noticed is that if $K$ is a countable graph with the property of irreflexivity I can find a least $2$ elements in $K$ such that $R(x_1,x_2)$. After, maybe I can use the fact that I can find an injective map $\iota$ between $\{x_1\}$ and a bigger finite set $\{\iota(x_1),...,\iota(x_k)\}$ which respects $\bigwedge_{1\le j\le k} R(\iota(x_j),x_2)$ (I'm not sure for $x_2$) . How can I arrive to the second part of the property $P$. Or maybe it's not the right way to proceed.

Thanks in advance !

Answer 1

First, a minor comment: the first line of your last paragraph is incorrect - a countable irreflexive graph might have no edges at all!

OK, now the real answer: work in stages. (This is an intuition similar to that behind the back-and-forth method for building an isomorphism between appropriate countable structures, if you've seen that before.) Specifically, what you want is an embedding $f: K\rightarrow H$. $K$ is countable, so let $K=\{k_0, k_1, k_2, . . .\}$ (I'm assuming WLOG that $K$ is infinite, for notational simplicity). So let's build $f$ in stages!

Let $G_n$ be the subgraph of $K$ consisting of $\{k_0, k_1, . . . , k_n\}$. A stage $n$ embedding will be an embedding $f_n$ of $G_n$ into $H$. In order to build $f$, what do we need? Well,

• for each $n$, a stage $n$ embedding $f_n$

would be nice. But we want to be able to "glue" the $f_n$s together, so we also want

• $f_n(k_i)=f_m(k_i)$ whenever $i\le m, n$.

Do you see why if we have such a set of $f_n$s, the map $\bigcup f_n$ is an embedding from $K$ into $H$?

OK, now let's build our $f_n$s. On the face of it, this might seem hard; however, the point of $T$ is that any model of $T$ "looks the same everywhere," so no matter how we've defined $f_n$, it will always be possible to extend it to $f_{n+1}$.

Here's a sketch of why: suppose I've defined $f_{17}$ - so I have an embedding from $G_{17}$ to $H$. Now I want to extend this to also include $k_{18}$. Bad news: I have to be careful where I send $k_{18}$! Maybe $k_{18}$ is connected to $k_1, k_3, k_{11},$ and $k_{16}$, and not connected to all the other $k_i$s (for $i<18$).

Why is there some $h\in H$ such that $h$ is connected to $f_{17}(k_1), f_{17}(k_3), f_{17}(k_{11})$, and $f_{17}(k_{16})$, and not connected to $f_{17}(k_i)$ for any other $i<18$?

Do you see how to use this to define $f_{18}$?

Answer 2

HINT: Enumerate the vertices of $K$. Then use the extension property (property $P$) to embed $K$ in $H$ one vertex at a time: if $f$ is the embedding map, when you embed vertex $v_n$, there is a vertex $v$ in $H$ such that for all $k<n$, $R(f(v_k),v)$ if and only if $R_K(v_k,v_n)$.