3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Are you familiar with Ehrenfeucht-Fraisse games? $\endgroup$
    – TomKern
    Dec 7, 2023 at 16:46
  • $\begingroup$ @TomKern I'm not familiar with that but I did a quick search on Wikipedia. Is it basically choosing 2 graphs, one with bounded out-degree and the other unbounded, and play the game to show that they are equivalent? I sort of get the idea but I'm not familiar with game semantics and how I can relate the game to the language. $\endgroup$
    – haha
    Dec 7, 2023 at 17:12
  • $\begingroup$ It's a bit trickier than that: assuming there is a defining formula, the EF game between a bounded out-degree graph and an unbounded out-degree graph can always be won in (quantifier depth of formula) turns. However the number of turns this takes can get larger and larger the larger the bound on out-degree. Are there other tools you're more familiar with for showing that a property can't be expressed by a formula? Is this for a class, and if so, what has been covered recently? $\endgroup$
    – TomKern
    Dec 7, 2023 at 19:14
  • $\begingroup$ @TomKern I'm just familiar with the basic things that you typically learn in a basic logic course. Basic syntactic and semantic definitions like wff, sentence, structure, model, etc. as well as basic theorems like compactness, completeness, soundness, etc. Something covered that be related to this question is how to describe the size of structures in theories. It's nothing complicated though, like using $$∃x_1∃x_2…∃x_n (x_1≠x_2∧ x_1≠x_3…∧x_1≠x_n∧x_2≠x_3∧x_2≠x_4…∧x_2≠x_n…∧x_{n-1}≠x_n )$$ to describe structures with size greater than n, and using a set of all such formulas for infinite structure $\endgroup$
    – haha
    Dec 7, 2023 at 20:48
  • 6
    $\begingroup$ EF-games, love them though I do, are overkill; this is a quick application of the compactness theorem. Suppose $\Gamma$ is a set of sentences true in every bounded-out-degree graph; can you use compactness show that there is a graph of non-bounded-out-degree which still satisfies $\Gamma$? $\endgroup$ Dec 7, 2023 at 21:08

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks a lot for giving explanations for both approaches! So T is finitely satisfiable because for any finite subset of $\{d_n(y/c):n∈N\}$ there is a largest n and we can find some graphs with bounded out-degree of n+1? And the case for a being outer node is just R(p(x),p(a)), flipping sides? $\endgroup$
    – haha
    Dec 10, 2023 at 19:12
  • $\begingroup$ yes in both cases $\endgroup$
    – emesupap
    Dec 11, 2023 at 18:53
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .