Un-definability of graphs with bounded out-degree

Question

I want to solve the following question but has some difficulties:

Given a language L = ⟨R( , )⟩ where R is a two-place relation symbol. Prove that the set of graphs of bounded out-degree (graphs whose vertex with the highest out-degree still has a finite out-degree) is not definable in this language.

Intuitively this is obvious, since there's no way to specify that a vertex is in finitely many edges. However I don't have much clue on how to prove that this is the case. I tried to prove it by assume we can define it and get a contradiction, but I don't seem to get anywhere. I would appreciate if anyone can give suggestions on how to approach this.

Answer 1

here is the compactness argument @Noah alludes to. Suppose for contradiction that bounded out degree is definable by some P. Then consider the following for each n:

$d_n: \exists x_1,...,x_n [\bigwedge x_i \neq x_j \land \bigwedge R(y, x_i)]$

a graph G satifsies $d_n$ if G has a vertex y with outdegree at least n. Now consider the theory $T:= P \cup \{d_n(y/c) : n \in \mathbb{N}\}$ in the language L along with a fresh constant c. it is finitely satisfiable (why?) , hence admits a model M by compactness. In particular the interpration of c in M has outdegree greater than any finite n but M has bounded outdegree, contradiction.

for completeness, here is the argument from EF games as @Tom alludes to. fix $k \in \mathbb{N}$, let $A_k$ be the a wheel of size $\aleph_0$, ie a center node c surrounded by infinitely many nodes, whose only edges are spokes, that is, edges from the outer nodes to the center. Let $B_k$ be the wheel of size $k+1$. We will show that $A_k \equiv_k B_k$ with EF.

Pf: via induction. base: the empty function is a partial isomorphism p. inductive step, forth: suppose we have a partial isomorphism p of domain size n. let $a \in A$. a is either a center node or a outer node. case 1: a is a center node. if a center node, then pick p(a) = b's center node. This is a partial isomorphism of size n+1, suppose $A_k \models R(x,y)$ for $x,y \in dom(p)$. if x,y are from the n stage, we are done by inductive hypothesis. Otherwise, one of x or y is a. in fact, x must be a, in a directed graph. This holds iff $B_k \models R(p(a), p(y)$ by our strategy. case 2 when a is a outer node also holds (why?). the back condition is similar. so we are done.

This construction holds for arbitrary k. So consider P, with quantifier rank k. $B_k$ satisfies P, but $A_k$ does not, a contradiction.

Answer 2

So, I don't know the correct way to do this using compactness, but I do know a way to solve this using ultraproducts.

I'm going to assume that $R$ is the binary relation of a simple graph, i.e. $[\forall x](\lnot xRx)$ and $[\forall x y](xRy \to yRx)$ .

Let $\Gamma$ be the set of sentences that insist that $R$ has bounded degree.

Let $G_n$ for all $n \ge 1$ be $K_n$, the complete graph on $n$.

I construct a sequence of models $G_1, G_2, G_3, \cdots$.

Let $\mathcal{U}$ be an ultrafilter on the positive integers.

I define $G$ as $\prod_{k \ge 1} G_n / \mathcal{U}$ .

The following are all consequences of Łoś's theorem.

$G$ is a complete graph.

$|G|$ is infinite. More precisely, $G$ has at least $k$ elements for each finite $k$.

Additionally, for each $\gamma$ in $\Gamma$, it holds that $G \models \gamma$.

Therefore $\Gamma$ holds of a graph where $R$ does not have bounded out degree, which is a contradiction as desired.