Graphs and first-order logic.

**andrei** · January 7th 2013, 02:27 AM

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?

**emakarov** · January 7th 2013, 04:54 AM

I agree. And connectedness is not expressible in first-order logic by compactness argument.

Thread: Graphs and first-order logic.

LinkBack

Thread Tools

Display

Graphs and first-order logic.

Re: Graphs and first-order logic.

Similar Math Help Forum Discussions

Complexity of SAT in First-order logic

First order logic

First order logic

First order Logic

First order Logic!

Search Tags