Homework Sheet 4
Exercise � (� points) We consider the vocabulary L = {P} without equality, where P is a binary
relation symbol. Let T be the following theory over L.
T = {∀x∃yP(x, y), ∀x∃y¬P(y, x)} .
Determine (with proof) whether the theory T is complete.
Exercise � (� points) We consider the vocabulary L = {∼, f , c} with equality, where ∼ is a binary
relation symbol and f , c are function symbols of arity, respectively,  and . Let T be the following
theory over L.
T = {x ∼ f (x), f 
(c) = c} .
Write down the canonical structure M for T. Show that ∼ really is the relation you claim it is.
Exercise � (� points) We consider the vocabularies L = {Q},L = {Q, P},L = {Q, f } with equality,
where Q is a binary relation symbol, P is a unary relation symbol,and f a unary function symbol. We
are given the following formulae over L (for an arbitrary n ∈ N).
ϑ ≡ ∀x∀y[Q(x, x) ∧ [Q(x, y) ↔ Q(y, x)]]
φn ≡ ∀y∃x⋯∃xn
n
⋀
i=
[Q(y, xi) ∧
n
⋀
j=i+
xi ≠ xj]
ψn ≡ ∃x⋯∃xn
n
⋀
i=
n
⋀
j=i+
[xi ≠ xj ∧ Q(xi, xj)]
ξn ≡ ∀x∃x⋯∃xn
n
⋀
i=
n
⋀
j=i+
[xi ≠ xj ∧ Q(xi, xj)]
Let M be an structure over the vocabulary L with universe M. We call a subset A ⊆ M a clique if
A × A ⊆ QM. A structure M is nice if there is an infinite clique A ⊆ M. We call a theory T over L
good if every model M of T is nice.
Given a structure M over a vocabulary L′
⊇ L, we denote by M L its L-reduct, i.e., we forget all
relations and function not in L. We call a theory T over a vocabulary L′
⊇ L great if a structure M
over L is nice if,and only if,it can be extended to a model of T,i.e.,there exists a model M′
of T such
that M′
L = M.
(a) (� point) Show that the theory R = { ϑ, φn n ∈ N} is not good.
(b) (� point) Show that the theory S = { ϑ, ψn n ∈ N} is not good.
(c) (�.� points) Give an example of a great theory T over the vocabulary L. Briefly explain why your
example is correct.
(d) (�.� points) Give an example of a finite great theory U over the vocabulary L. Briefly explain
why your example is correct.
(e) (� points) Determine (with proof) whether the theory V = { ϑ, ξn n ∈ N} is good.