A formula that expresses a finite graph is connected in FO.

Question

Write a such senetence $\phi$ in the first order logic that: $$G \models \phi \text{ iff } G \text{ is connected} $$

We consider only finite graphs. When it comes to infinite graphs it is obvious that FO cannot express that fact.

$$\forall p_1 \, \forall p_2 \, p_1 \neq p_2 \implies \exists n \, \exists p_2 \, \cdots \, \exists p_{n-1} \bigwedge_{1 \le i < n} e(p_i, p_{i+1})$$

Is correct? Why, why not?

Answer 1

You made some basic errors. The question is whether or not the following holds:

There is a single first-order sentence $φ$ in the language of graphs such that every finite graph $G$ satisfies $φ$ iff $G$ is connected.

You cannot create $φ$ after being given $G$. Rather you must write one $φ$ down that works for every finite graph $G$. Secondly, quantifiers are interpreted (in any structure) to quantify over all objects in that structure, so you cannot quantify over natural numbers. Thirdly, you cannot have "$\cdots$" anywhere in your formula. In general "$\cdots$" is forbidden in any rigorous mathematics; if you cannot express it without ellipsis then it is not rigorous.

After you understand the above, then you can try your best to construct a desired $φ$, to get a feel for why it is impossible. Then carefully study the proof of the compactness theorem to see why. And you may wish to try the four problems in this question and the two answers.