MATH 150 FALL 2020 SAMPLE FINAL EXAM
INSTRUCTIONS.
A. Please show your work, unless explicitly stated that showing your work is
not required. Remember that it is your reasoning and writing that is primarily
evaluated. Explain your work clearly and carefully, as if you were explaining
it to someone who does not know anything about it.
B. Do problems you find easier first. If you have spare time, check on correct-
ness.
C. You are encouraged to use any result we proved in the lecture. If you use such
a result, do not prove it; just quote it. It is OK to use the lecture text and other
course materials posted on Canvas Math 150 course site during the exam. But be
cautious not to lose too much time browsing throughout those materials.
D. Smaller number of complete solutions is preferred before many unsuccessful
attempts and partial solutions.
E. Please do not use symbols ∵ and ∴ but instead write everything in words.
F. Recall that our convention is that N does include 0.
Student Name:
Student Id Number:
The problems are on the next page.
1
2SAMPLE FINAL EXAM PROBLEMS
1. (3+3+4pt) Write a formula ϕ in the respective formal language L expressing
the fact that should hold in the given L-structure(s).
(a) L is Lgraph and ϕ(u) expresses that there exists exactly one triangle which
passes through the node denoted by variable u. This should hold in any
graph viewed as an Lgraph-structure.
(b) L is Lpo and ϕ(u) expresses that there are exactly two minimal elements
below the element denoted by variable u. This should hold in any strict
partial ordering viewed as an Lpo-structure.
(c) L is Larith and ϕ(u, v, w, z) expresses that the numbers denoted by variables
u, v, w, z constitute a geomertic progression of squares. The structure is the
standard model of arithmetic N.
Terminology. A triangle in a graph is a circle of length 3. See Homework 5
assignment for the definition of a circle in a graph of length n.
An element p of a strict partial ordering P = (P,<) is minimal iff there is no
element of P below p, that is, there does not exist any q ∈ P such that q < p.
2. (10pt) Let L be a language with a unary relation symbol A. Assume t and t′
are L-terms and ϕ is the following L-formula:
t =˙ t′ → (A(t) ∨ ¬A(t′) )
Prove that for every L-structure M and every evaluation s of variables in M,
M |= ϕ[s]
3. (10pt) Assume L is a first order language such that CL 6= ∅ and Σ is a set of
L-sentences. Assume further that R ∈ RL is a binary relation symbol and e ∈ CL
is a constant symbol such that
Σ |= (∀u)(¬u =˙ e→ R(u, e))
Define a binary relation R∗ on CL by
〈c, d〉 ∈ R∗ iff Σ |= R(c, d)
Prove that for any c ∈ CL such that Σ |= ¬ c =˙ e we have 〈c, e〉 ∈ R∗.
4. (5+5pt) Prove that the following are elementary classes of L-structures for the
respective languages.
(a) The class of all graphs viewed as Lgraph-structures which have, for each
n ∈ N, infinitely many nodes of degree exactly n.
(b) Given a fixed n ∈ N r {0}, the class of all equivalence relations, viewed
as Leqrc1,...,cn-structures, which have at least n infinite equivalence classes.
Here Leqrc1,...,cn is the language obtained by adding new constant symbols
c1, . . . , cn to L
eqr, see the sample solution below.
5. (10pt) Use the Compactness Theorem I to prove that the class of all strict
partial orderings which have finitely many minimal elements, viewed as a class of
Lpo-structures, is not elementary.
3SAMPLE SOLUTIONS.
Problem 1. Coming soon. Please check back.
Problem 2. Coming soon. Please check back.
Problem 3. Coming soon. Please check back.
Problem 4(a). The first step is to write down an Lgraph-formula ϕn(v) expressing
that the node denoted by variable u has degree exactly n. That the degree is exactly
n means that there are exactly n neighbors.
Consider the following Lgraph-formulas.
ψ′n(u,w1, . . . , wn) :
∧
1≤i≤n
E(u,wi)
ψ′′n(w1, . . . , wn) :
∧
1≤i≤n
i6=j
¬ wi =˙wj
ψ′′′n (w1, . . . , wn) : (∀w)((E(u,w) →
∨
1≤i≤n
w =˙wi)
The first formula expresses that the nodes denoted by variables w1, . . . , wn are
all neighbors of the node denoted by variable u. The second formula expresses
that the nodes denoted by variables w1, . . . , wn are pairwise distinct, and the third
formula expresses that every neighbor of the node denoted by variable u is one
of the nodes denoted by variables w1, . . . , wn. It follows that the L
graph-formula
ψ¯n(u,w1, . . . , wn) defined by
ψ¯n(u,w1, . . . , wn) : ψ
′
n(u,w1, . . . , wn) ∧ ψ
′′
n(w1, . . . , wn) ∧ ψ
′′′
n (u,w1, . . . , wn)
expresses that the nodes denoted by variables w1, . . . , wn are precisely all n distinct
neighbors of the node denoted by variable u. Thus, the formula
ψ˜n(u) : (∃w1) . . . (∃wn)ψ¯n(u,w1, . . . , wn)
expresses that the node denoted by variable u has precisely n distinct neighbors,
or in other words, its degree is n.
Next we need to say that there are infinitely many nodes of degree n. Because
formulas are finite, we will use an infinite set Σ = {ψℓ | ℓ ∈ N} of L
graph-sentences
for this. Each sentence ψℓ will express that there are at least ℓ distinct nodes with
degree precisely n. Then the set Σ will express that for each ℓ ∈ N that there are
at least ℓ distinct nodes with degree n, which means that there are infinitely many
nodes of degree n. The Lgraph-sentence ψℓ can be taken to be the following:
ψℓ : (∃u1) . . . (∃uℓ)


∧
1≤i≤ℓ
ψ˜n(ui) ∧
∧
1≤i,j≤ℓ
i6=j
¬ui =˙ uj


It expresses that there exist at least ℓ distinct nodes with degree exactly n. More
precisely, for every Lgraph-structure G the following are equivalent for a graph G
which is viewed as an Lgraph-structure:
• G |= {ψℓ} ∪ {σ
graph}
4• G is a graph which has at least ℓ distinct nodes with degree exactly n.
It follows that the following are equivalent for an Lgraph-structure G:
• G |= Σ ∪ {σgraph}
• G is a graph which has ininitely many distinct nodes with degree exactly n.
Problem 4(b). We first need to find a way of expressing, using a formal language,
that an equivalence class is infinite. An Leqr-formula
ϕ′′ℓ (u,w1, . . . , wℓ) :
∧
1≤i≤ℓ
E(u,wi) ∧
∧
1≤i≤ℓ
i6=j
¬ wi =˙wj
expresses that the objects denoted by variables w1, . . . , wℓ are distinct elements
of the equivalence class denoted by variable u. Thus, to say that the equivalence
class of the object denoted by u has at least ℓ distinct elements, we may use the
Leqr-formula
ϕ′ℓ(u) : (∃w1) . . . (∃wℓ)ϕ
′′
n(u,w1, . . . , wℓ)
Now the Leqr-sentence
ϕ¯ℓ : (∃u)ϕ
′
ℓ(u)
mandates the existence of an equivalence class with at least ℓ elements, but the re-
quirement that all sentences ϕ¯ℓ are satisfied does not guarantee that an equivalence
relation has an infinite equivalence class, as for each ℓ, the quantifier (∃u) may be
witnessed by a different element. So an equivalence relation which has only finite
equivalence classes, but arbitrarily large, would also satisfy all sentences ϕ¯ℓ.
To guarantee that for all ℓ the object denoted by variable u in the above formulas
is the same, we use a new constant symbol instead of a quantifier. So consider
a constant symbol c such that c /∈ CL, and add it to CL, thus obtaining a new
language Leqrc . We thus have:
• CL
eqr
c = CL
eqr
∪ {c} (= {c})
• FL
eqr
c = FL
eqr
(= ∅)
• RL
eqr
c = RL
eqr
(= {E})
Let
ϕcℓ be the formula obtained by replacing variable u in ϕ
′
ℓ(u) above
with the constant symbol c.
Notice that ϕcℓ is an L
eqr
c -sentence. Then by the same reasoning as above, we get
the following for every Leqrc -structure E:
• E |= {ϕcℓ, σ
eqr}
• E is an equivalence relation such that the equivalence class of cE has at
least ℓ elements.
Thus, for every Leqrc -structure E the following are equivalent:
• E |= {ϕcℓ | ℓ ∈ N r {0}} ∪ {σ
eqr}
• E is an equivalence relation such that the equivalence class of cE has at
least ℓ elements for every ℓ ∈ N.
• E is an equivalence relation such that the equivalence class of cE has infin-
itely many elements.
Now to say that that we have n distinct elementary classes, we add n distinct
constant symbols c1, . . . , cn to C
L, thus obtaining languageLeqrc1,...,cn . More precisely:
• CL
eqr
c1,...,cn = CL
eqr
∪ {c1, . . . , cn} (= {c1, . . . , cn})
5• FL
eqr
c1,...,cn = FL
eqr
(= ∅)
• RL
eqr
c1,...,cn = RL
eqr
(= {E})
Notice that the interpratations of ci, cj are in different equvalence classes iff they
are not in the relation, and this can be expressed by the sentence ¬ ci =˙ cj . We can
now write down our set of Leqrc1,...,cn-senetnces:
Σ =
n⋃
i=1
Σi ∪ {¬ ci =˙ cj | i, j ∈ {1, . . . , n} and i 6= j} ∪ {σ
eqr}
where
Σi = {ϕ
ci
ℓ | ℓ ∈ Nr {0}}
Here σeqr guarantees that E is an equivalence relation, Σi guarantees that the
equivalence class cEi is infinite, and the sentences ¬ ci =˙ cj guarantee that the
equivalence classes cEi and c
E
j are different for i 6= j.
Problem 5. Coming soon. Please check back.

欢迎咨询51作业君