Call/WhatsApp/Text +1(838)201-9170

Call/WhatsApp/Text +1(838)201-9170

Call/WhatsApp/Text +1(838)201-9170

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

Question?