Phil 455: Homework 10

This homework is due by the end of the day on Mon Apr 22.

  1. Define what the following concepts mean.

    1. A theory is deductively complete.

    2. A theory is effectively decidable.

  2. If a theory is deductively complete and consistent, and its axioms can be effectively enumerated, then the theory will be effectively decidable. Explain why. What difference would it make if we took away the constraint that the theory is consistent?

  3. Despite what you showed in Problem 108, it is possible for theories to be effectively decidable without being deductively complete. Take as given the fact that entailment within monadic predicate logic — that is, first-order predicate logic where the non-logical signature is restricted to contain only monadic predicates and no functors — is decidable. Consider a signature consisting of just a single monadic predicate F and two term constants a and b. Give an example of a theory in that language that fails to be deductively complete.

  4. Compactness can be expressed in either of these ways:

    Fill in the gaps in this proof that if some proof system S is semantically sound and complete, then Compactness holds.

    Soundness for S says 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.

  5. Here is a proof that given Compactness, there is no way to express “there are finitely many Fs” (we are understanding F as a monadic predicate). 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 ψ, so long as there are still finitely many Fs). 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:

    1. 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.

    2. 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.

  6. Fill in the gaps in this proof that if any two countable (that is, finite or countably infinite) models of a theory Δ are isomorphic, then Δ is deductively complete.

    We take as a premise that any two countable models of theory Δ are isomorphic. Suppose 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, if these sets have any models, they must have countable models, let ℳ₁ be a countable model of Δ ∪ {ψ} and ℳ₂ be a countable model of Δ ∪ {¬ψ}. These models must be isomorphic. (Why?) So they must make true all the same sentences. (Why?) So Δ must be deductively complete after all. (Why?)