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)?
Solution For n = , we have a model M with universe M = {, , , , , }, PM = {}, and
fM = {⟨, ⟩, ⟨, ⟩, ⟨, ⟩, ⟨, ⟩, ⟨, ⟩, ⟨, ⟩} .
For every even n ≥ , we have a model M with universe M = {, , . . . , n − }, PM = {}, and
fM = {⟨, ⟩, ⟨, ⟩} ∪ {⟨k + , k⟩, ⟨k + , k⟩ k ≤ n/ − } .
For other values of n there is no model with n-elements. As an example, let us draw the models for
n =  and n = . The red circle denotes the element in PM and the arrows describe the function fM.








 
 
 
 
n = 
n = 
Let us explain why models of other sizes do not exist. The formula ξ states that, for every element
a ∈ M, there is exactly one other element b ∈ M with f (a) = f (b). Consequently, every element
of M has either exactly two preimages under f or none. If we add the number of these preimages for
all element of M, we get the number of elements of M (since f is a function).
It follows that the size of M is even. Furthermore, by definition of a structure, M cannot be empty.
To exclude the remaining cases n =  and n = , it is sufficient to prove that the above formulae
imply that M has at least  elements. By φ, there exists a (unique) element a ∈ PM. By ψ, we have
fM(a) = a, and by ξ a has a second preimage b. BY ζ, there is some element c with f 
M(c) ∉ PM. We
have c ≠ a and c ≠ b since fM(a), fM(b) ∈ PM. Furthermore, d = fM(c) is different from a and b
(since fM(d) ∉ PM) and also from c (by φ). By ξ, d must have a second preimage e under fM. This
makes  different elements a, b, c, d, e.
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.
Solution Let M be a nice structure and e a variable assignment.
(a) A first try would be to take the formula
ψ = ∀u[S(u, x) ↔ S(u, y)] .
Clearly,ψ is true if e(x) = e(y). Conversely,suppose that e(x) ≠ e(y). Then there is some n ∈ N with
n ∈ e(x) and n ∉ e(y) (or the other way round). Hence, {n} ⊆ e(x), but {n} ⊈ e(y). If e(x) ≠ {n},
it follows that
M ⊭ ψ[e] .
But if e(x) = {n}, the only proper subset of e(x) is ∅. So, if e(y) = {k} for k ≠ n, the only proper
subset of e(y) is also ∅ and it follows that
M ⊧ ψ[e] .
Consequently, the formula ψ above does not quite work.
If we take the dual formula
ξ = ∀u[S(x, u) ↔ S(y, u)]
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 , , , ℵ, ℵ, ℵ
, ℵω, ℵωω
.
instead, we have a similar problem that ξ holds if e(x) = N ∖ {n} and e(y) = N ∖ {k}, for n ≠ k.
Since the cases where the two formulae ψ and ξ fail are disjoint, we can combine these formulae to
get
φa = ψ ∧ ξ .
(b) Note that the intersection is the infimum with respect to the inclusion ordering. Hence, we can
set
φb = z ⊆ x ∧ z ⊆ y ∧ ∀t[(t ⊆ x ∧ t ⊆ y) → t ⊆ z] .
(c) Dually to (b), we can use
φc = x ⊆ z ∧ y ⊆ z ∧ ∀t[(x ⊆ t ∧ y ⊆ t) → z ⊆ t] .
(d) It is sufficient to state that the sets x and y are disjoint and that their union is all of N. Guessing
the sets t = ∅ and u = N and using the formulae from (b) and (c), we can write
φd = ∃t∃u[∀v(t ⊆ v ∧ v ⊆ u) ∧ φb(x, y, t) ∧ φc(x, y, z)] .
A different solution to (b)–(d) works with singleton sets. The formula J(x) = ∃y∀z[S(z, x) ↔
φa(z, y)] states that x is a singleton.
φb = ∀t[J(t) → [t ⊆ z ↔ (t ⊆ x ∧ t ⊆ y)]] ,
φc = ∀t[J(t) → [t ⊆ z ↔ (t ⊆ x ∨ t ⊆ y)]] ,
φd = ∀t[J(t) → ¬(t ⊆ x ↔ t ⊆ y)] .
(e) Clearly, Q must include all pairs ⟨A, B⟩ such that A ⊂ B and B ∖ A = . Conversely, if A ⊂ B
and B∖A contains more than one element,we have A ⊂ A∪{n} ⊂ B,for any n ∈ B∖A. Hence,⟨A, B⟩
does not belong to Q. Therefore,
Q = {⟨A, A ∪ {n}⟩ A ⊂ N, n ∈ N ∖ A} .
(f) Clearly, the equivalence P(x) ↔ P(y) always holds if P is true for all sets, or if it is true for no
set. So we have at least these  choices for P.
The formula ψP only requires that P(x) ↔ P(y) holds for all ⟨x, y⟩ ∈ Q, that is, for all pairs where
y contains exactly one more element that x. By induction on the difference y ∖ x it follows that
P(x) ↔ P(y) must hold for all pairs that differ by a finite number of elements. This condition is also
sufficient for the validity of φP. Thus, we can choose P to be true for all finite sets and false for all
infinite ones, or vice versa. This gives already  choices.
Next we can distinguish between infinite sets whose complement is finite and those where the
complement is infinite. This gives a total of 
=  choices.
For the general statement, consider the relation
E = {⟨A, B⟩ ∈ N
× N
A ⊕ B is finite} .
(⊕ denotes the symmetric difference.) Note that E is an equivalence relation: reflexivity holds since
A ⊕ A = ∅ is finite; symmetry holds since A ⊕ B = B ⊕ A; and transitivity holds since, if A ⊕ B and
B ⊕ C are finite, then A ⊕ C = (A ⊕ B) ⊕ (B ⊕ C) is the symmetric difference of two finite sets and,
therefore, also finite.
Let R = N
/E be the quotient. We have argued above that the predicate P satisfies our formula if,
and only if, it respects E, i.e., if, and only if, it either contains all elements of a given E-class, or none
of them. This gives  R
choices for P.
To conclude our argument,we show that R = ℵ
(which means that there are ℵ
possible choices
for P). Clearly,
R ≤  N
= ℵ
.
For the converse inequality, we find an injection N
→ R, i.e., a function f N
→ N
such that
f (A) and f (B) are not E-equivalent for A ≠ B. To do so, we fix an injection g N × N → N. For
instance, we can set
g(a, b) = pb+
a , where p, p, . . . is an enumeration of all prime numbers.
Then we can set
f (A) = { g(a, b) a ∈ A, b ∈ N} .
(Intuitively, for each a ∈ A, we include in f (A) the entire row of the table for g (see below).)
If A ≠ B, then f (A) ⊕ f (B) contains all numbers g(a, b) with a ∈ A ⊕ B and b ∈ N. In particular,
the symmetric difference is infinite.
g(a,b) b = 0 b = 1 b = 2 b = 3 b = 4 b = 5 ⋯
a = 0 2 4 8 16 32 64 ⋯
a = 1 3 9 27 81 243 729 ⋯
a = 2 5 25 125 625 3125 15625 ⋯
a = 3 7 49 343 2401 18087 117649 ⋯
a = 4 11 121 1331 14641 161051 1771561 ⋯