This homework is due by the end of the day on Mon Apr 22.
Sample answers in purple.
Define what the following concepts mean.
A theory is deductively complete.
For every sentence φ in the theory’s language, the theory either includes φ or includes ¬φ. (If the theory is inconsistent, it will contain both.)
A theory is effectively decidable.
You already explained in Problem 100f what it is for a set of strings to be effectively decidable. A theory is just one kind of set of strings.
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?
If the axioms can be effectively enumerated, then we can enumerate all possible proofs from those axioms. If the theory is deductively complete, then eventually we will either get a proof of φ or a proof of ¬φ. (If the theory is inconsistent, we’ll get proofs of both.)
Let machine 1 work like this: Whichever of φ and ¬φ we get a proof of first, we stop and report that as belonging to the theory, and its negation as not belonging to the theory.
Let machine 2 work like this: Whenever we get a well-formed formula, we always report it as belonging to the theory.
If the theory is consistent, then machine 1 effectively decides membership within it. If the theory is inconsistent, then machine 1 gives incorrect answers, but for those theories machine 2 effectively decides membership within them.
If I don’t know whether the theory is consistent or not, I won’t know which of these machines decides membership within it. But for the theory to be decidable, it’s only required that there in fact be some machine that effectively decides membership within it, not that anyone know which machine that is, or be prepared to write out the machine’s full description, or know how to prove that the machine exists, or anything else of that sort.
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.
The set of logical consequences of the empty set will be one example. This will not contain Fb and neither will it contain ¬Fb.
Another example will be the set of logical consequences of Fa. This too will not contain Fb and neither will it contain ¬Fb.
Another example will be the set of logical consequences of Fa ∨ Fb… Or the set of logical consequences of ∃xFx… And so on.
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? Because proofs by definition are finite and so can only make use of a finite set of premises.) 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? Again because proofs are always finite.) 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? This is a version of soundness: if a set is satisfiable/has a model then it will be consistent/won’t prove a contradiction.) So if every finite subset ofΔhas a model, thenΔhas a model. (Why does this follow from what we’ve said? Every finite subset ofΔhas a model⟹(by previous sentence) from every finite subset ofΔone cannot prove a contradiction⟹(contraposing the biconditional beginning “taken together…”)Δhas a model.) That is what Compactness claims.
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:
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.
Sentences like ∀x x = a entail that there are only one, and so finitely many, objects. An important component of the above argument is that ψ be compatible with every finite subset of the Fn sentences. But sentences like the one described here will be incompatible with many of those subsets.
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.
If Z designates nothing’s successor, then what it designates must satisfy ≠ SZ, and also ≠ SSZ, and also ≠ SSSZ, and so on. So there are at least two objects. (We haven’t yet ruled out that SZ, SSZ, and SSSZ designate a single object.) But now by injectivity and Z ≠ SZ it follows that SZ ≠ SSZ, and by injectivity and Z ≠ SSZ it follows that SZ ≠ SSSZ, and so on. So there are at least three objects: Z, SZ, and whatever objects the rest of the numerals designate. Repeating the argument, we get that there are at least n objects for arbitrarily large n.
So the conjunction of those two axioms is incompatible with the existence of finitely many objects.
That conjunction would not be vulnerable to issues with Compactness like the ones described above, for its negation would still be compatible with the existence of infinitely many objects.
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? Semantic completeness for our proof system tells us that unsatisfiable sets are inconsistent.) 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? If they are countable models ofΔ ∪ {ψ}and Δ ∪ {¬ψ}, they are also countable models ofΔ, and so by our premise, must be isomorphic.) So they must make true all the same sentences. (Why? Isomorphic models always do this. Isomorphism for models is defined in such a way that the models make true all the same sentences.) SoΔmust be deductively complete after all. (Why?ℳ₂makes¬ψtrue, so nowℳ₁will have to do so too; butℳ₁also makes trueψ. But no model can make true bothψand¬ψ, so our reductio supposition fails.)