# Graphs and first-order logic.

• Jan 7th 2013, 02:27 AM
andrei
Graphs and first-order logic.
Quote:

We define the distance $d(a,\,b)$ between two vertices $a$ and $b$ of a graph as the least number of edges in a path from $a$ to $b.$ If no such path exists, then $d(a,\,b)=\infty.$ ... $\nu_G$ is the vocabulary of graphs.
...
(b) Does there exist a $\nu_G-$formula $\delta_{\infty}(a,\,b)$ so that, for any graph $G$, $G\models\delta_{\infty}(a,\,b)$ if and only if $d(a,\,b)=\infty$? Explain your answer.
I said no, because if there were such a formula, then there would be a formula saying that a graph is connected. What is your opinion?
• Jan 7th 2013, 04:54 AM
emakarov
Re: Graphs and first-order logic.
I agree. And connectedness is not expressible in first-order logic by compactness argument.