Prepare solutions to the following questions, and submit as a .pdf file to Coursys. Your solution must be submitted before the beginning of lecture time on Monday Nov. 23.

1. From the Axiomatizing Problems section of course notes, Exercise 1, Parts 2 and 5.
2. Write a FO formula, in a vocabulary that contains one binary relation symbol \(R\) (as well as =, which as usual is true equality or object identity), that is true in a structure \({\cal{A}}\) if and only if \(R^{{\cal A}}\) is a total order on the universe \(A\).
3. Let \(\sigma=(min,max;E,\lt,=)\) be a vocabulary with \(min,max\) being constant symbols, and the other three symbols binary relation symbols. Write a FO \(\sigma\)-formula, that is true in a structure \({\cal A}\) if and only if:
   1. \(\lt^{\cal A}\) is a total order on \(A\), and \(min^{\cal A}\) and \(max^{\cal A}\) are the first and last elements in that order;
   2. There is a closed walk in the graph \((A,E^{\cal A})\) that starts at \(min^{\cal A}\), follows the order \(\lt^{\cal A}\), and finally returns from \(max^{\cal A}\) to \(min^{\cal A}\).
   (Observe that the walk in question is a Hamiltonian cycle.)
4. Let \(\tau=(s,t;E,R,B,G)\) be a vocabulary with one binary relation symbol (\(E\)), three unary relation symbols, and two constant symbols. We can think of a structure for this vocabulary as a graph with vertices labelled with colours Red, Blue and Green, and two ``designated'' vertices s and t. Consider the case of such structures where the graph consists of a simple directed path and \(s\) and \(t\) denote the first and last vertices on the path. (Equivalently, where \(E\) is a total order on the domain, and \(s\) and \(t\) are the min and max elements.) We can think of the vertices as a sequence of states. Write a formula that is true of such a structure if and only if:
   1. Every state has exactly one colour;
   2. The starting state is not red;
   3. The end state is red;
   4. Every blue state is followed by a red state;
   5. A green state preceded by a red state is not followed by a blue state
5. A structure of size \(n\), for the vocabulary \(\tau=(g,h)\) where g and h are binary function symbols, can be thought of as a pair of \(n\times n\) game boards. Imagine a game where a move consists of swapping two pieces on the board. Write a formula that is true in exactly the \(\tau\)-structures where the two boards differ by exactly one such move.