Logic B-Exam May 1997

There are 4 questions worth 10 points each for a total of 40 points.

1. For each of the following, confirm or refute the assertion. Justify your answer.

(a) If φ is unsatisfiable and ψ is valid, then (φ → ψ) is valid.

(b) If (φ → ψ) is valid, then φ is unsatisfiable or ψ is valid.

(c) If (φ → ψ) is unsatisfiable, then φ is valid and ψ is unsatisfiable.

2. Show that the sentence

(∃z)(∀x)(∀y)((f(x) = f(y) → x = y) ∧ f(x) ≠ z)

does not have any finite model.

3. Consider a countable vocabulary Σ, and let T be a theory over Σ (recall that a theory is a set of sentences closed under logical implication.) Recall that, by the Lowënheim-Skolem Theorem, if a set of sentences over Σ is satisfiable, then it has a countable model. T is complete if for every sentence φ we have that either φ ∈ T or ¬φ ∈ T. T is ω-categorical if all its countable models are isomorphic. Show that if T is ω-categorical and has no finite models, then it is complete.

4. Consider a vocabulary Σ for graphs, which consists of a single binary relation symbol E (the edge relation). A perfect matching of a directed graph G = (V, E) is a subset E′ ⊆ E of edges such that every node falls on some edge in E′ and no two edges in E′ share a node. Write a second-order sentence φ over Σ such that φ is true for a graph G = (V, E) precisely when G has a perfect matching. Explain why φ is a correct solution.