Assessment exercises 4

Show that there is a formal proof in the first-order language $L$ with non-logical symbols $f,0,1$ (where $f$ is a unary function and $0,1$ are constants) of $\exists x \exists y (\neg (x=u)\wedge (f\left(x\right)=f\left(y\right)\left)\right)$ from $\forall x \left(\right(f\left(x\right)=0)\vee (f\left(x\right)=1\left)\right)$ and $\exists x \exists y \exists z (\neg (x=y)\wedge (\neg (y=z)\wedge \neg (z=x)\left)\right)$.

(Hint: first make an informal argument in the way you might for some other mathematics course you are studying. Then try to tighten up the arguments and write all the cases down. Then rewrite your proof in first order logic.)

Let $L_E$ be the first order language with single non-logical symbol $\sim$ (a binary relation).

(a) Write down statements of $L$ saying that $\sim$ is an equivalence relation.

(b) Write down a single statement of $L$ saying that there are exactly three $\sim$-equivalence classes.

(c) Show how to write down infinitely many statements of $L$ that when taken together say that there are infinitely many $\sim$-equivalence classes.

Let $L_G$ be the first order language with a single non-logical symbol $E$ (a binary relation). A simple graph is a nonempty set $V$ of vertices and a set $E$ of unordered pairs of vertices.

(a) Explain how an $L_G$-structure might be regarded as a graph, and vice versa. What two extra conditions on $L_G$-structures must be true for this graph to be a simple graph?

(b) Write down statements of $L_G$ saying that:

(i) the graph is complete (has every possible edge);

(ii) the graph has no cycle of length $n$;

(iii) vertices $x,y$ of $V$ are not connected by any path. (You will need to give infinitely many sentences for this one.)

A simple graph $(V,E)$ is bipartite if there is a partition $V=V_0\cup V_1$ into two disjoint sets such that all edges in $E$ join a vertex in $V_0$ with a vertex in $V_1$. If $G=(V,E)$ is a simple graph and $\sim$ is an equivalence relation on $V$ then we define a graph $G/\sim =(V/\sim ,E/\sim )$ by: for $v\in V$ the $\sim$-equivalence class of $v$ is denoted $v/\sim$ and $V/\sim$ is the set of $\sim$-equivalence classes $v/\sim$ of $V$; and $(v/\sim ,w/\sim )\in E/\sim$ if and only if $(x,y)\in E$ for some $x\in v/\sim$ and $y\in w/\sim$. (Note that this construction may create loops, i.e. edges from a vertex to itself, which is also a cycle of length 1.) Suppose $G$ is a simple graph with no cycles of odd length i.e. no sequence of vertices $v_0,v_1,\dots ,v_{2k}$ with $(v_i,v_{i+1})\in E$ for all $i$ and also $(v_{2k},v_0)\in E$.

(a) Let $X$ be the set of equivalence relations on $V$ such that $G/\sim$ has no cycles of odd length. Show that $X$ is nonempty.

(b) Define $⩽$ on $X$ by letting ${\sim }_1⩽{\sim }_2$ if and only if $x{\sim }_{1}y$ implies $x{\sim }_{2}y$ for all $x,y\in V$. Show that $(X,⩽)$ is a poset with the Zorn property.

(c) Let $\sim \in X$ be maximal. Show that $\sim$ divides $V$ into either one or two equivalence classes and the case of only one class is only possible is the original graph had no edges. (Hint: two equivalence classes $C,D$ can be merged provided (a) there is no path of odd length between them and (b) provided there is no third class $E$ with paths of from $C$ to $E$ and from $D$ to $E$ of different parity. It follows that any two classes with an even length path between them can be merged, and if two classes cannot be merged but have no path between, then there is another class with an even length path from one of them.)

(d) Deduce that any graph with no odd cycles is bipartite. Prova a converse too, and hence explain how to write down infinitely many sentences of $L_G$ saying that a graph is bipartite.