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 3 is not first-order definable.
Exercise � Which of the following languages (over {a,b}) are definable in first-order logic? Which
of them are definable in monadic second-order logic?
(a) a∗
(bb)∗
(b) (ab)∗
(c) { an2
n ∈ N}
(d) { an
bm
an
m,n ∈ N}
(e) The set of all palindromes.
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 3
(b) paths
(c) trees
(d) graphs of diameter at most 3
(e) graphs of even diameter
(f) graphs with a Hamiltonian cycle
Exercise � (optional) Prove that the set of even numbers is not first-order definable in ⟨Z,≤⟩.
�