Please do at least 5 problems in total, including one from each section. If
you do more than 5, please indicate the 5 you would like us to grade first; if
one of those 5 is badly wrong, we will replace it with another from the same
section.
1 Models
Recall this definition from the practice exam:
Definition 1. If A is a σ-structure, we say B ⊆ A is a substructure if:
• For each constant c ∈ Cσ, cA ∈ B
• For each n-ary function f ∈ Fσ and b1, . . . , bn ∈ B, fA(b1, . . . , bn) ∈ B
In this case, we make B is a σ-structure B, interpreting functions and relations like in A. Explicitly:
• For c ∈ Cσ, cB = cA
• For f ∈ Fσ, fB(b1, . . . , bn) = fA(b1, . . . , bn)
• For R ∈ Rσ, RB = {(b1, . . . , bn) ∈ Bn
|(b1, . . . , bn) ∈ RA}
1. Let B ⊆ A be a substructure, and s: V → B be a B-valued assignment
function. Since B ⊆ A, we can view s as an A-valued assignment function
as well, which we will call s
′
(formally, s
′ = ι ◦ s, where ι is the inclusion
function from B to A).
Show that for any σ-term τ , s(τ ) = s
′
(τ )
2. Suppose σ is algebraic, T is an equational theory, and A |= T. Let B be
a substructure of A. Show that B |= T (you may assume problem 1)
Recall that a signature is algebraic if it contains no relations, and a
theory is equational if every φ in T looks like:
∀xi1 ∀xi2
. . . ∀xin
(τ1 = τ2)
for some σ-terms τ1 and τ2.
2 Deductions
3. Let σ be the signature with one unary relation P. Give a formal deduction to show ∀xP x ⊢ ¬∀y¬P y (do not quote meta-theorems)
Remark: To avoid a problem some of you pointed out previously, I recall
that our deductive system always assumes structures are non-empty to
avoid pathologies.
4. Let σ = (a, b, ·), where a and b are constants, and · is a binary function.
Let T be the theory asserting a and b are left and right identities for ·:
1. ∀x(x · a = x)
2. ∀x(a · x = x)
3. ∀x(x · b = x)
4. ∀x(b · x = x)
Show that T ⊢ a = b. This one is a bit longer, to so you can quote
meta-theorems or results from class if you’d like.
3 Soundness and Completeness
To avoid repitition, let σpart = (P, Q), two unary relations, and Tpart is
the theory of a set partitioned into disjoint sets P and Q; that is,
Tpart = {∀x(P x ∨ Qx), ∀x¬(P x ∧ Qx)}
5. Consider the σpart theory T defined as follows:
Let αn be the statement ∃x1∃x2 . . . ∃xn(P x1∧· · ·∧P xn∧[no two xi
’s are equal])
Let βn be the statement ∃x1∃x2 . . . ∃xn(Qx1∧· · ·∧Qxn∧[no two xi
’s are equal])
Finally, let T = Tpart ∪

S
n∈N
{αn, βn}

(a) Show that T is consistent
(b) Show that T is complete
Page 2
(c) Let ω1 be the smallest uncountable cardinal (that is, for any infinite
A ⊆ ω1, |A| = |N| or |A| = |ω1|). Up to isomorphism, how many
models does T have of cardinality ω1?
6. Let σ = (P, Q, ≤). Consider the following theory:
T = Tpart ∪
Tdlo ∪
{∀x∃y∃z(P y ∧ P z ∧ y < x ∧ x < z)} ∪
{∀x∃y∃z(Qy ∧ Qz ∧ y < x ∧ x < z)}
(where x < y is shorthand for x ≤ y ∧ ¬(x = y))
(a) Show T is consistent
(b) Show T is not complete
Hint: Show the statement
∀x∀y((x < y ∧ P x ∧ P y) → ∃z(P z ∧ x < z ∧ z < y))
can’t be proved or disproved
(c) (Hard and optional) Find some axioms you can add to T to make
T complete and consistent
7. The goal of this problem is to show connected graphs are not axiomatizable (in the signature with one binary edge relation). I don’t care
how you do this, but I’ll suggest two methods. Use whichever one makes
more sense to you.
(a) Let G be the graph with verticies N and edges {n, n + 1} (so, an
infinite stick in one direction)
i. Let T be the complete theory of G (that is, the set of true
statements in G). Show T has a model other than G (use compactness to add a new element)
ii. Show that any model of T other than G is disconnected (show
that any new elements don’t have a path connecting them to 0)
iii. If Σ axiomatized connected groups, show Σ ⊆ T, and therefore
Σ has a disconnected model
(b) Let σ
+ be the signature (E, a, b), where a and b are constants
i. Give a σ
+ theory T axiomatizing “graphs with no path connecting a and b”
Page 3
ii. Show that every finite subset of T is satisfiable in a connected
graph.
iii. If Σ axiomatized connected graphs, show that every finite subset
of Σ ∪T has a model. Conclude by compactness that Σ ∪T has
a model, which is both connected and disconnected.
Page 4

Midterm_2

CITATION