Exercise � Prove that the set of even numbers is not first-order definable in ⟨Z, ≤⟩.
Exercise � We consider structures with the empty signature. Use a back-and-forth argument to show
that
A ≡m B iff A = B or A , B ≥ m .
Exercise � Prove that the set of all complete finite binary trees whose number of vertices is divisible
by  is not first-order definable.
Exercise � Which of the following languages (over {a, b}) are first-order definable?
(a) a∗
(bb)∗
(b) (ab)∗
(c) { an
n ∈ N}
(d) { an
bm
an
m, n ∈ N}
(e) The set of all palindromes.
Exercise � Which of the languages in Exercise 4 are monadic second-order definable?
Exercise � Which of the following graph classes are first-order definable? (We assume that all graphs
are finite and undirected.)
(a) graphs of degree at most 
(b) trees
(c) paths
(d) graphs of diameter at most 
(e) graphs of even diameter
(f) graphs with a Hamiltonian cycle
1