First order logic: Formulating sentences for graph properties

first-order-logiclogic

Let $\sigma = \{ E \}$ be a signature with a binary relational symbol $E$. Give for each of the following statements a sentence $\varphi \in FO[\sigma]$, such that for a $\sigma$-strucutre $\mathcal{A}$, $\mathcal{A} \models \varphi$ iff the statement is true for $\mathcal{A}$.

$i$) $E^\mathcal{A}$ is an equivalence relation and $E^\mathcal{A}$ has at most three equivalence classes.

$ii$) $\mathcal{A}$ is a $\sigma$-structure $\mathcal{G}$, which is un undirected graph and there exists for its universe $U$ a bipartition $A \cup B = U$ in two disjoint, non-empty sets, such that $(A \times B) \cup (B \times A) = E^{\mathcal{G}}$.

For $i$), I divided $\varphi$ in two parts: $\varphi = \varphi' \land \varphi''$ where
$\varphi'$ describes the equivalence relation: $$ \varphi' = \forall x E(x, x) \land \forall x \forall y \forall z (E(x, y) \land E(y, z) \rightarrow E(x, z)) \land (\forall x \forall y E(x, y) \rightarrow E(y, x))$$

$\varphi''$ should describe the property of having at most three equivalence classes, but I'm not sure how I can write it. What I understand:

If the graph only has one equivalence class, then we must have a complete graph (since the relation is reflexive, transitive and symmetric) that is connected. If we have two equivalence classes, then we must have two complete and disconnected subgraphs within the original graph. And for three equivalence classes, we must have three complete and disconnected complete subgraphs. Is my understanding correct? How can I formulate this property mathematically?

For $ii$), my understanding is that $\mathcal{A}$ should be a bipartit graph with non-empty color classes. Again, I'm not sure how I can formulate this. Any help would be much appreciated.

Best Answer

First, let's focus on $(1)$.

The trick to writing $\phi''$ out is to shift from second-order to first-order thinking, via representatives.

Specifically, "The structure is the disjoint union of three complete graphs" is really a second-order statement as phrased, since it essentially quantifies over sets ("There exist three sets which partition the universe and such that ..."). However, I don't really need to think about the whole "pieces" of the universe: every equivalence class is determined by any of its members.

For example, "There are at least five equivalence classes" can be expressed as "There are at least five elements whose equivalence classes are different," and - granting that we've already written down $\phi'$, so we know that $E$ is an equivalence relation in the first place - this is really just a first-order claim:

$\exists x_1,x_2,x_3,x_4,x_5(\bigwedge_{1\le i<j\le 5}\neg x_iEx_j)$.

Now do you see how to write "There are exactly three equivalence classes" in a first-order way (again, taking $\phi'$ for granted)?

The sentence $$\exists x_1,x_2,x_3[(\bigwedge_{1\le i<j\le 3}\neg x_iEx_j)\wedge\forall y(\bigvee_{1\le k\le 3}yEx_k)]$$ will do the job. I've chosen to use "big-connective" notation here, namely $\bigwedge$ and $\bigvee$, since this emphasizes how the solution generalizes if we replace $3$ with any larger number.

OK, now what about $(2)$?

Well, here the challenge is the same: the statement as written involves quantification over sets, so we need a way to think about representatives somehow.

The obvious notion of "representative" is "member of each 'side,'" i.e., we're looking for a sentence beginning "$\exists x_1,x_2$" where intuitively $x_1$ and $x_2$ lie in the two parts of our bipartite graph. Here the trouble is that we need to figure out a way to identify each "side." So:

Suppose $\mathcal{G}$ is a bipartite graph with domain $U$ and $A,B$ are nonempty sets partitioning $U$ such that $E^\mathcal{G}=(A\times B)\cup(B\times A)$. How can I tell whether two elements of $U$ lie in the same "piece" (= either both in $A$ or both in $B$)?

Now do you see how to use this to solve your problem?

Related Question