Lesson 4

Optional Problems.

1. (20 points) Prove the transitivity property of equality, \(\vdash (x = y \land y = z) \Rightarrow x = z\).
2. (20 points) Suppose that \(\Delta \cup \{\phi\} \vdash \psi\). Then \(\Delta \vdash \phi \Rightarrow \psi\).
3. (20 points) Prove the following theorems:
   1. (5 points) \(\vdash \forall x \ \forall y \ \phi \Rightarrow \forall y \ \forall x \ \phi\)
   2. (5 points) \(\vdash \forall x \ \phi \Rightarrow \exists x \ \phi\)
   3. (10 points) Suppose that \(\phi, \psi\) are two expressions that are identical, except for the following difference: \(\phi\) has free occurrences of \(x\) exactly at those positions that \(\psi\) has free occurrences of \(y\). Then \(\vdash \forall x \ \phi \Rightarrow \forall y \ \psi\).
4. (20 points) Consider a model for finite Graph Theory. That is, the universe \(\Gamma\) is the set of nodes and the only relation \(G^{\Gamma}(x, y)\) is true if there is an edge from \(x\) to \(y\) in the graph. For example, to check whether the graph is symmetric, one can use the following sentence: \[\forall x \ \forall y \ G^{\Gamma}(x, y) \Rightarrow G^{\Gamma}(y, x).\] Prove that for every fixed expression \(\phi\) over alphabet \(\Sigma_{G}\), checking whether a given graph \(G\) satisfies property \(\phi\) can be done in polynomial time.
5. (20 points) Show that the first form of the completeness theorem derives the second. That is, prove that if it is true that \(\Delta \models \phi\) implies \(\Delta \vdash \phi\), then it follows that if \(\Delta\) is consistent, then \(\Delta\) has a model.
6. (20 points) Suppose that \(\phi\) is an expression, and \(M\) and \(M'\) are two models appropriate to \(\phi\)'s vocabulary such that \(M\) and \(M'\) agree on everything except for the values they assign to the variables that are not free in \(\phi\). Then \(M \models \phi\) if and only if \(M' \models \phi\).
7. (20 points) If \(\Delta\) is a set of first-order sentences such that \(\mathbb{N}\models \Delta\), then there is a model \(\mathbb{N}'\) such that \(\mathbb{N}' \models \Delta\), and the universe of \(\mathbb{N}'\) is a proper superset of the universe of \(\mathbb{N}\).
8. (25 points) Recall the model for Graph Theory. Consider the REACHABILITY problem, given a graph \(G\) and two nodes \(x, y \in V\). Is there a path from \(x\) to \(y\)? Prove that there is no first-order expression \(\phi\) with two free variables \(x\) and \(y\) such that, for every graph \(G\) and vertices \(u,v\), we have \(G_{x=u,y=v}\models\phi\) if and only if there is a path from \(u\) to \(v\).