Homework Sheet 3
Exercise � (� points) We consider the vocabulary L = {P, f } (with equality) where P is a unary
predicate symbol and f a unary function symbol. Define the following formulae.
φ = ∃x∀y[P(y) ↔ y = x] ,
ψ = ∀x[P(x) ↔ f (x) = x] ,
ξ = ∀x∃y[y ≠ x ∧ ∀z[f (z) = f (x) ↔ (z = x ∨ z = y)]] ,
ζ = ∃x¬P(f (f (f (x)))) .
For which n ∈ N does there exist a structure M over the vocabulary L such that M ⊧ φ ∧ ψ ∧ ξ ∧ ζ
and such that M has exactly n elements (no proof necessary)?
Exercise � (� points) We consider the vocabulary L = {P, Q, S} without equality consisting of three
relation symbols of arities, respectively, , , and . We call a structure M over this vocabulary nice if
it satisfies the following conditions.
• The domain M is the set N
of all subsets of the set of natural numbers.
• The relation SM is the proper subset relation: SM = {⟨A, B⟩ A ⊂ B }.
Find a formula φ(x, y, z) over the vocabulary L such that, given a nice structure M and a variable
assignment e, we have M ⊧ φ[e] if, and only if, the following condition holds.1
(a) (� point) e(x) = e(y)
(b) (� point) e(z) = e(x) ∩ e(y)
(c) (� point) e(z) = e(x) ∪ e(y)
(d) (� point) e(x) is the complement of e(y).
Briefly justify the correctness of your answer.
Consider the formulae
ψQ = ∀x∀y[Q(x, y) ↔ [S(x, y) ∧ ¬∃z[S(x, z) ∧ S(z, y)]]] ,
ψP = ∀x∀y[Q(x, y) → [P(x) ↔ P(y)]] .
(e) (� point) Note that there exists a unique relation Q ⊆ N
× N
such that Q = QM, for every nice
structure M satisfying ψQ. Describe this relation as explicitly as possible.
(f) (� points) Find as many sets P ⊆ N
as possible such that P = PM,for some nice structure M satisfying
ψQ ∧ψP. Or better,compute exactly how many2
such sets exist and prove the correctness
of your answer.
1
In (a) and (d), the variable z does not need to appear in φ.
2
Here we expect for the answer a cardinal number such as , , , ℵ, ℵ, ℵ
, ℵω, ℵωω
.