This homework is due by the end of the day on Wed April 10.
Sample answers in purple.
Define what the following concepts mean. Don’t use any of this vocabulary: “implies”, “follows”, “entails” (with no prefix), “equivalent” (with no prefix). Acceptable vocabulary: “logically or semantically entails,” “logical or semantic consequence,” “derivable in proof system so-and-so from premises such-and-such,” “model.” I’ll understand “true in a model” (without any specification of an assignment function) to mean true on that model and any/every assignment function. I’ll understand “intepretation” to mean a pair of some model and some assignment of variables to that model’s domain.
Γ and formula φ, if Γ ⊢ φ in S (that is, there is some derivation in system S of φ from premises Γ) then Γ ⊨ φ (that is, φ does logically follow from Γ — or in other words, every interpretation that makes all the formulas in Γ true also makes φ true).Γ and formula φ, if Γ ⊨ φ then Γ ⊢ φ in S. (There are also “weaker” forms of completeness that only make this claim for the case where Γ is empty.)φ is valid It is true on every model (and any/every assignment function — see Problem 95 in previous homework).Γ is satisfiable There is at least one interpretation on which they are all true.φ and ψ are logically equivalent They have the same truth value on every model (and any/every assignment function). Equivalently, φ ⊨ ψ and ψ ⊨ φ.⊨ is effectively decidable For any set of sentences/formulas Γ, the set of sentences/formulas that are their logical consequences is effectively decidable, as in (f).⊨ is not decidable but only effectively enumerable For any set of sentences/formulas Γ, the set of sentences/formulas that are their logical consequences aren’t decidable but only effectively enumerable, as in (g).Sometimes “consistent” is used to express the same (semantic) concept as “satisfiable.” Other times it’s used to express a proof-theoretic notion. For clarity, I’ll try to always say “deductively consistent” to capture this latter usage. Since we’re working with proof systems that are known to be sound and complete for the family of semantic relations (logical consequence, satisfiability and so on) that we’re working with, we can move between the semantic and proof-theoretic ways of understanding “consistent.”
Give one of the ways that we said the notion of deductive consistency can be defined. (You can assume you’re talking about a property of a finite set. An infinite set is counted as deductively consistent iff all of its finite subsets are.)
Any of the following say that Γ is deductively inconsistent (in the proof system that ⊢ is understood to be about).
Γ ⊢ ⊥φ) Γ ⊢ φφ) Γ ⊢ φ and Γ ⊢ ¬φChoose one of them. Then claim that Γ is deductively consistent if that that does not hold.
Here is an alternative formulation of one of the important logical facts/properties we’ve discussed the past weeks. What is the short name of that fact/property? (Don’t just guess; I want you to justify your answer.)
For all sets of formulas Γ and formulas φ, if Γ ∪ {¬φ} is satisfiable, then Γ ∪ {¬φ} is deductively consistent in proof system S.
The contrapositive of the displayed claim is:
(For all Γ and φ) If Γ ∪ {¬φ} is deductively inconsistent in proof system S, then Γ ∪ {¬φ} is not satisfiable.
which is equivalent to:
(For all Γ and φ) If Γ ⊢ φ in proof system S, then Γ ⊨ φ.
which is a statement that proof system S is sound.
In an axiomatic proof system, you are allowed to write as a step any of: (a) any substitution instance of some axiom schema, (b) anything given as a premise, (c) anything that the system’s rules license given the steps that have already been written. Consider an axiomatic proof system that includes the rule of Modus Ponens; and whose axioms include these two:
(Axiom K) φ ⊃ (ψ ⊃ φ)
(Axiom S) (φ ⊃ (ψ ⊃ χ)) ⊃ ((φ ⊃ ψ) ⊃ (φ ⊃ χ))
If the proof system is going to be for classical sentential or predicate logic, it will need more axioms and/or rules than this, but this is all we need for this problem.
Use this proof system to derive from the two premises P ⊃ Q and Q ⊃ R the conclusion P ⊃ R.
As I said in class, officially a “proof” in these systems is just a list of formulas that obey the system’s rules, but when I ask you to give one, I want you also to annotate each entry/step in the list with an explanation for why it’s allowed.
Hint: first use your premises and an instance of Axiom K, to derive by Modus Ponens P ⊃ (Q ⊃ R). Then use an instance of Axiom S to derive by Modus Ponens your desired conclusion.
P ⊃ Q (Premise)Q ⊃ R (Premise)(Q ⊃ R) ⊃ (P ⊃ (Q ⊃ R)) (Axiom K)P ⊃ (Q ⊃ R) (MP from 2,3)(P ⊃ (Q ⊃ R)) ⊃ ((P ⊃ Q) ⊃ (P ⊃ R)) (Axiom S)(P ⊃ Q) ⊃ (P ⊃ R) (MP from 4,5)P ⊃ R (MP from 1,6)Using the same proof system from the previous problem, derive from the premise P ⊃ (P ⊃ Q) the conclusion P ⊃ Q.
Hint: in class we talked about how to derive P ⊃ P in a system like this, using one instance of Axiom S, two instances of Axiom K, and two applications of Modus Ponens. Begin by reconstructing that proof. (You can consult pp. 91-92 of the Goldrei book I posted a link to if you forget how we did it in class.) Then use an instance of Axiom S, together with your premise, to derive (P ⊃ P) ⊃ (P ⊃ Q). Then use the step P ⊃ P that you’ve reconstructed a proof of (from no premises) to derive by Modus Ponens your desired conclusion.
(P ⊃ ((Q ⊃ P) ⊃ P)) ⊃ ((P ⊃ (Q ⊃ P)) ⊃ (P ⊃ P)) (Axiom S)(P ⊃ ((Q ⊃ P) ⊃ P)) (Axiom K)(P ⊃ (Q ⊃ P)) ⊃ (P ⊃ P) (MP from 1,2)P ⊃ (Q ⊃ P) (Axiom K)P ⊃ P (MP from 3,4)(P ⊃ (P ⊃ Q)) ⊃ ((P ⊃ P) ⊃ (P ⊃ Q)) (Axiom S)P ⊃ (P ⊃ Q) (Premise)(P ⊃ P) ⊃ (P ⊃ Q) (MP from 6,7)P ⊃ Q (MP from 5,8)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 Σ ⊨ ψ.
Left-to-right: By assumption, either (i) Σ contains ψ so every model of Σ is a model of ψ (that is, Σ ⊨ ψ) or (ii) Σ contains ¬ψ so every model of Σ is a model of ¬ψ. Nothing can both be a model of ψ and ¬ψ; so if any model ℳ of Σ is a model of ψ, as the lhs of our underlined claims says, then we’re in case (i), which as we said involves Σ ⊨ ψ.
Right-to-left: if Σ ⊨ ψ then every model of Σ, including ℳ, makes ψ true.
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).
Prove that a set is maximally consistent iff it’s deductively consistent, deductively closed, and deductively complete.
Let our set be Γ.
Right-to-left: Γ is consistent. Now suppose some φ ∉ Γ. By closure it follows that Γ ⊬ φ. By completeness it follows that Γ ⊢ ¬φ. We can add extra premises without destroying derivability, so Γ, φ ⊢ ¬φ. So Γ ∪ {φ} is not consistent. This was shown for an arbitrary φ ∉ Γ; hence Γ counts as “maximally consistent.”
Left-to-right, for consistent: obvious.
Left-to-right, for closed: Suppose for reductio that Γ ⊢ φ but φ ∉ Γ. Then by our assumption (the lhs of what we’re proving) that Γ is maximally consistent it follows that Γ ∪ {φ} is inconsistent. But then Γ ⊢ ¬φ. Since we’re supposing that Γ also proves φ, this violates Γ’s being (maximally) consistent. Hence our reductio supposition fails.
Left-to-right, for complete: Suppose for argument’s sake that Γ ⊬ φ. Then Γ ∪ {¬φ} will be consistent; but since we’re assuming that Γ is maximally consistent, ¬φ must therefore ∈ Γ. Hence Γ ⊢ ¬φ. Discharging our supposition, we can conclude that either Γ ⊢ φ or Γ ⊢ ¬φ.
Prove that if a maximally consistent set contains a sentence ¬(φ ⊃ ψ), then it also contains φ and contains ¬ψ.
By its being maximally consistent, it must contain either φ or ¬φ; but by its being maximally consistent it can’t contain ¬(φ ⊃ ψ) and also contain ¬φ. So it contains φ. The argument for ¬ψ is similar.
Prove that if a maximally consistent set contains a sentence φ ⊃ ψ, then either it contains ¬φ or it contains ψ.
Suppose for reductio that it contains neither. Then by maximal consistency it must contain φ and also contain ¬ψ. Then since we showed in Problem 106a that a maximally consistent set is deductively closed, it contains ¬(φ ⊃ ψ). But then this violates the assumption that the set is consistent and contains φ ⊃ ψ. So our reductio supposition fails.