Let u be a structure and let s v a be an assignment

Question

Math Assignment Questions -

Part A -

Q1. In the proof of Lemma 3 from the handout on Boolean algebra, we used (without even mentioning) the following fact: if U is an ultrafilter, then a Λ b ∈ U if and only if both a ∈ U and b ∈ U. Prove this fact. (We saw a similar fact when discussing Compactness of propositional logic, as maximal sets of formulas had a similar property.)

Q2. Suppose h : B → 2 is a Boolean algebra homomorphism from some B to the two-element Boolean algebra 2. Consider the set U = {b ∈ B : h(b) = 1}. Show that U is an ultrafilter on B.

Part B -

Q3. Section 2.2, Ex. 6 from Enderton: Show that a formula θ is valid i? ∀xθ is valid.

Part C -

Q4. Section 2.2, Ex. 18 from Enderton. A universal (∀₁) formula is one of the form ∀x₁ . . . ∀x_nθ, where θ is quantfier-free. An existential (∃₁) formula is of the dual form ∃x₁ . . . ∃x_nθ. Let u be a substructure of B, and let s : V → |u|. (Recall, u being a substructure of B means that |u|⊆ |B|and all the non-logical parameters are interpreted appropriately; see Enderton, p. 90.)

(a) Show that if |=_u ψ [s] and ψ is existential, then |=_B ψ [s].

(b) Show that if |=_B  φ [s] and φ is universal, then |=_u φ [s].

(c) Using parts (a) and (b), explain why the sentence ∃_xP_x is not equivalent to any universal sentence, and why 8xPx is not equivalent to any existential sentence.

Q5. Section 2.2, Ex. 19 from Enderton. An ∃₂ formula is one of the form is one of the form ∃x₁, . . . ,x_nθ, where θ is universal (∀₁).

(a) Suppose φ is a ∃₂ sentence (no free variables) in a language with no constants or function symbols (thus only relations). Show that ' is true in a structure u, then it is true in a finite substructure of u.

(b) Explain why this shows that ∀_x∃_yP_xy is not equivalent to any ∃₂ sentence.

Part D -

Q6. To which axiom groups, if any, do each of the following formulas belong?

(a) [(∀xPx → ∀yPy) → Pz] → [∀xPx → (∀yPy → Pz)]

(b) ∀y[∀x(Px → Px) → (Pf(c) →∀ Pf(c))]

(c) ∀x(Qx → 8yPxy) → (Qy → ∀yPyy)

Q7. Section 2.4, Ex. 3 from Enderton. Recall the prime formulas are atomic formulas and those of the form ∀xψ, i.e., everything but those of the form (¬ψ) or (ψ → χ­).

(a) Let u be a structure and let s : V → |A| be an assignment function. Define a (propositional) truth assignment v on the set of prime formulas in the following way:

v(α) = T i? |=_u α [s].

That is, they receive value T if they are true in the model, F otherwise. Show that for all formulas φ (prime or not), we have

v^-(φ) = T i? |=_u φ [s].

(b) Explain why this shows that every instance of axiom scheme 1 (p. 112) is valid.

Q8. Section 2.4, Ex. 11 from Enderton. Give a deduction (again from ø) showing the provable transitivity of equality: ∀x∀y∀z(x = y → (y = z →∀ x = z)).

Textbook - A Mathematical Introduction to Logic, Second Edition by Herbert B. Enderton.