First order Logic. Compactness theorem. A task with solution.

Question

Prove that it is not possible in the FO logic to define that there exists a such connected component $G_0 \in G$ where $G$ undirected graph that for every $v \in G_0 P(v)$ where $P$ is any single-argument relation-symbol.

So we consider structures-graphs: $\mathbb{A} = (V, E, P) $.

1. From my intuition it's possible for finite graphs, yes?

2. My solution:

Let's assume that there exists a such set of sentences $\Delta$ that $G \models \Delta \iff \text{ There exists a such connected component } G_0$ that for every $v \in G_0 P(v)$

$V$ is a universum- it is a set of vertexes.

Let's assume that considered graph is countable. We don't lose a generality. So, every vertex can be labeled with natural number.

Let $\Delta' = \Delta \cup \Gamma, \Gamma = \{E(v_i, f) \mid i \in \mathbb{N}\}$ and $f$ is a constant (argumentless function) which we add to signature. $f$ points to a such vertex $v$ that $\neg P(v)$.

Let $\Delta_0 \subset \Delta' \text { and } \Delta_0 \text { is finite }$ Note, that $\Delta_0 $ is satisfable because it is easy to point a model.

From compactness theorem we have that $\Delta'$ is satisfable but it's impossible beacuse of $\Delta$

Is it ok?

---

What can you say about the larger theory $S=T\cup \{\phi_n : n\in \mathbb{N}\}$?

Why $S$ is finitely satisfable? $S = T \cup N = T \cup \{\phi_n | n \in \mathbb{N} \}$ Let's take a finite subset $\Delta$ of $S$. It is easy for me to show that there is a model for $N \cap \Delta$. But, I have a problem to show that $T \cap \Delta$. Certainly, the crucial fact is that it is finite. However, intuitively I imagine that model looks like:

From compactness theorem we get that $S$ is satisfable.

What can you say about the connected component of c in any model $M$ of $S$?

As we can see from the image.

Now suppose $M\models S$; let $H$ be the reduct of $M$ to $(E,P)$. What can you say about $H$ versus $G$? (HINT: look at their theories)

$H$ is not connected while $G$ is connected. Their theories are equal ( I am not convinced that it is a problem). Perhaps, the grap you've chosen is a special?

Answer 1

Let $G$ be the $(E, P)$-structure consisting of the usual graph structure on $\mathbb{Z}$ (with an edge between $a$ and $b$ iff $\vert a-b\vert=1$ - that is, edges=successivities), where $P$ holds everywhere except at $0$.

Now expand the language by a new constant symbol $c$, and let $\varphi_n$ say "$c$ is at least distance $n$ from any point where $P$ fails." And let $T$ be the $(E, P)$-theory of $G$.

• What can you say about the larger theory $S=T\cup\{\varphi_n: n\in\mathbb{N}\}$?

• What can you say about the connected component of $c$ in any model $M$ of $S$?

Now suppose $M\models S$; let $H$ be the reduct of $M$ to $(E, P)$. What can you say about $H$ versus $G$? (HINT: look at their theories . . .)

Answer 2

Suppose for a contradiction that $\phi$ is a sentence in the language $(E,P,=)$ such that every graph/predicate pair $(G, E, P,=)$ satisfies $\phi$ if and only if there is a connected component of $G$ for which all the nodes satisfy $P$.

Trivially, a graph $(G,E)$ is disconnected if and only if it has at least two connected components. This is equivalent, in turn, to saying there is some node $v_0 \in G$ such that $(G,E,P,=)$ satisfies $\phi$, when $P(w)$ is interpreted as "$w \not = v_0$".

We will obtain a contradiction using the following result.

Lemma. The property that a graph is connected is not definable in the signature $(E,=)$.

We can use $\phi$ to find a sentence $\phi'$ in the signature $(E,=)$ which is true about a graph $(G,E,=)$ if and only if $G$ is connected.

The sentence $\phi'$ can be taken to be $\lnot (\exists v) \phi[P(w)/(w \not= v)]$ where $\phi[P(w)/(w\not =v)]$ is the formula obtained from $\phi$ by replacing $P(w)$ with "$w \not = v$" everywhere. (We assume that $v$ is chosen to be a variable that does not occur in $\phi$).