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作业君