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:

enter image description here

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?

  • $\begingroup$ It is not clear to me if you are asking about "The set of nodes satisfying $P$ is connected" or "there is a connected component for which every node satisfies $P$". The former is a much more common kind of exercise. $\endgroup$ Jan 21 '17 at 13:59
  • $\begingroup$ In the solution, could you explain the set $V$? I am not sure how to form $\Gamma$ without knowing the set $V$ first. $\endgroup$ Jan 21 '17 at 14:02
  • $\begingroup$ I am asking about: "there is a connected component for which every node satisfies $P$." $\endgroup$
    – user376326
    Jan 21 '17 at 14:02
  • $\begingroup$ @Carl Mummert, I edited $\endgroup$
    – user376326
    Jan 21 '17 at 14:03
  • $\begingroup$ Because $\Gamma$ only refers to vertices in $V$, it feels like I can make a model of $\Delta'$ by just making a graph that has one more vertex $w$, not in $V$, not connected to any other vertex, and with $P(w)$. Then $\{w\}$ is a component satisfying $P$, so $\Delta'$ is satisfiable. I am afraid, though, that I don't understand the idea you are trying to use to make the answer. $\endgroup$ Jan 21 '17 at 14:09

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 . . .)

  • $\begingroup$ thanks for questions make me to think. But, I have to ask you: 1. What is a reduct? 2. " the connected component of c ". I cannot understand what does it mean connected component of c. 3. I have doubts: We have just one constant $c$ and we have a lot of sentences $\phi_n$ saying something else about $c$. For example: $\phi_1$ says $c$ equals 1, $\phi_2$ says $c$ equals 2 and so on. $\endgroup$
    – user376326
    Jan 21 '17 at 22:48
  • $\begingroup$ Re: question 1: Suppose I have a structure $S$ in some big language $L$, and I have a sublanguage $L_0\subset L$ that I'm interested in. Then I can also view $S$ as an $L_0$-structure: just "forget" about the symbols in $L$ not in $L_0$! For instance, the underlying group of a ring is the reduct of the ring (a $\{+, \times\}$-structure) to the language $\{+\}$. Similarly, if I take one of the structures you're interested in (an $\{E, P\}$-structure) and "forget" the $P$-part, this is the underlying graph. When I view $S$ as an $L_0$-structure, I'm taking the reduct of $S$ to $L_0$. (contd) $\endgroup$ Jan 21 '17 at 22:58
  • $\begingroup$ Re: question 2: $c$ is a constant symbol. So in any $\{E, P, c\}$-structure, $c$ names an element of that structure (that is, a vertex). So the "connected component of $c$" is the connected component of that vertex. Re: question 3, I'm not really sure what your doubts are. $\varphi_n$ says that there is no vertex distance $\le n$ from $c$ which is not in $P$ (remember, the thing named by $c$ is a vertex!); it doesn't say "$c$ equals $n$" (and I'm not sure what that would mean anyways). For example, $\varphi_1$ is the sentence "$\forall x(E(c, x)\implies P(x))$". Does that make sense? $\endgroup$ Jan 21 '17 at 22:59
  • $\begingroup$ Yes, it makes sense- thanks. Now- I am trying to answer your questions. $\endgroup$
    – user376326
    Jan 21 '17 at 23:22
  • $\begingroup$ "What can you say about the larger theory $S=T\cup\{\phi_n:n\in \mathbb{N}\}$?". It is not satisfable because T enforces that there exists an edge between $0$ and $1$ and $\phi_1$ forbids it. $\endgroup$
    – user376326
    Jan 21 '17 at 23:51

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$).

  • $\begingroup$ Ok, I grasp it! :). I understand that $v_0$ is a constant which points to any vertex, yeah? $\endgroup$
    – user376326
    Jan 21 '17 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy