This homework is due by Friday April 22.
Is Γ ⊭ φ equivalent to Γ ⊨ ~φ? Justify your answer.
In Homework 8 Problem 3 you showed that for a closed formula/sentence ψ, a model 𝓜 will either make ψ true for all assignment functions or for none. Similarly for making ψ false. So in such cases, for short I’ll just talk of whether 𝓜 makes ψ true or false.
For this problem, let φ be a formula with no free/unbound variables except (possibly) x.
Prove that ⊨ ∃x(φ ⊃ ∀xφ). Hint: Start a reductio by assuming there’s a model 𝓜 that makes ∃x(φ ⊃ ∀xφ) false.
For some choices of φ, there will be models that don’t make φ[x ← a] ⊃ ∀xφ true. Explain what those models are like.
Suppose we want to define ⊨ so as to apply to open formulas (as well as to closed formulas/sentences). Here are two strategies for doing so. Where Γ is a set of formulas, understand “⟦Γ⟧𝓜q is true” to mean “∀γ∈Γ(⟦γ⟧𝓜q is true).”
Γ ⊨A φ =def for all models 𝓜: for all assignment functions q: if ⟦Γ⟧𝓜q is true, then ⟦φ⟧𝓜q is true.
Γ ⊨B φ =def for all models 𝓜: if (for all assignment functions q: ⟦Γ⟧𝓜q is true), then (for all assignment functions q: ⟦φ⟧𝓜q is true).
Observe that when Γ is empty, these definitions turn out to be equivalent, so ⊨A φ iff ⊨B φ. In fact, there can only be a difference between them when Γ includes some open formulas, in which case it might happen that ⊨B φ but ⊭A φ.
x ≠ a ⊃ x = a for all assignment functions?Given what you showed in Problem 3, it’s not generally true that if φ ⊨B ψ then ⊨B φ ⊃ ψ. This problem will explore another example of that.
x ≠ a ⊃ ∀x x ≠ a for all assignment functions?x ≠ a for all assignment functions?Given the strange behavior of ⊨B exhibited in Problems 3 and 4, henceforth we’ll understand ⊨ to mean ⊨A.
x = a ⊭ ∀x x = a.⊨ φ then ⊨ ∀xφ. For simplicity, you can assume that φ is a formula with no free/unbound variables except (possibly) x.A set is “deductively complete” iff, for every ψ, either it contains ψ or it contains ~ψ. Assume that Σ is a deductively complete set of sentences, and that 𝓜 is a model of Σ. Show that for any sentence ψ, 𝓜 will make ψ true iff Σ ⊨ ψ.
Say that a set of sentences is “maximally consistent” iff it’s deductively consistent, and no further sentences can be consistently added (that is, for any φ ∉ Γ, Γ ∪ {φ} is deductively inconsistent).
~(φ ⊃ ψ), then it also contains φ and contains ~ψ.φ ⊃ ψ, then either it contains ~φ or it contains ψ.Compactness can be expressed in either of these ways:
Γ ⊨ φ, then for some finite Γ′ ⊆ Γ, Γ′ ⊨ φ.Σ′ ⊆ Σ, Σ′ is satisfiable, then Σ is satisfiable.Fill in the gaps in this proof that if some proof system S is semantically sound and complete, then Compactness holds.
Soundness for
Ssays that if some finite subset of a set of sentencesΓcan prove a contradiction, thenΓhas no model. (Why are we entitled to say “finite” here?) Completeness says the converse: that ifΓhas no model, then from some finite subset one can prove a contradiction. (Why are we entitled to say “finite” here?) Taken together, this gives us thatΓhas no model iff from some finite subset one can prove a contradiction. Any finite subset that has a model will be one that cannot prove a contradiction. (Why?) So if every finite subset ofΓhas a model, thenΓhas a model. (Why does this follow from what we’ve said?) That is what Compactness claims.
Here is a proof that given Compactness, there is no way to express “there are finitely many Fs.” For suppose that some sentence ψ did express that. We know we can express “there is at least one F,” namely as ∃xFx (where ∃xφ can be defined as ~∀x~φ). Let F₁ abbreviate that sentence. We also know we can express “there are at least two Fs,” namely as ∃x∃y(Fx ∧ Fy ∧ x ≠ y). Let F₂ abbreviate that sentence. We also know we can express “there are at least three Fs,” namely as ∃x∃y∃z(Fx ∧ Fy ∧ Fz ∧ x ≠ y ∧ x ≠ z ∧ y ≠ z). Let F₃ abbreviate that sentence. And so on. Now consider the infinite set of sentences Γ = {ψ, F₁, F₂, F₃, ...}. We can demonstrate that every finite subset of Γ is satisfiable. For every finite subset, there will be a largest n such that Fn belongs to that subset. Then any model that has at least n elements in the extension of F will satisfy the subset (this is true even if the subset also includes the alleged ψ). Then Compactness entails that Γ must also be satisfiable. But it cannot be, if ψ expresses what we said it does. For ψ would require that in any model, there is some n ∈ ℕ such that the extension of F contains exactly n elements. But Fn+1 will be an element of Γ, so would not then be satisfied by that model. So there cannot be any such ψ.
In second-order logic, Compactness no longer holds and there it is expressible that there are finitely many Fs.
This homework problem is to explain/reconcile the above proof with the following two observations:
We know how to write sentences that entail that there are finitely many objects. Give an example, and explain why an analogue of the above argument doesn’t show these sentences to be impossible.
Note that we can express “there are infinitely many Fs” iff we can express “there are finitely many Fs,” since one is the negation of the other. Now, we know how to write sentences that entail that there are infinitely many objects: such as the axioms of arithmetic that say that the functor S is injective and that Z is nothing’s successor. First, explain why these entail that there are infinitely many objects. Then explain why an analogue of the above argument doesn’t show these sentences to be impossible.
Fill in the gaps in this proof that if any two countable (that is, finite or countably infinite) models of a deductively closed theory Δ are isomorphic, then Δ is deductively complete.
Assume for reductio that
Δis not deductively complete. Then for some sentenceψ, bothΔ ∪ {ψ}andΔ ∪ {~ψ}are deductively consistent. So those two sets are satisfiable. (Why?) By Löwenheim-Skolem, these sets must have countable models𝓜₁and𝓜₂. These models must be isomorphic. (Why?) So they must make true all the same sentences. (Why?) SoΔmust be deductively complete after all. (Why?)