This homework is due by the end of the day on Wed April 10.
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.
φ is validΓ is satisfiableφ and ψ are logically equivalent⊨ is effectively decidable⊨ is not decidable but only effectively enumerableSometimes “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.)
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.
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.
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.
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).
Prove that a set is maximally consistent iff it’s deductively consistent, deductively closed, and deductively complete.
Prove that if a maximally consistent set contains a sentence ¬(φ ⊃ ψ), then it also contains φ and contains ¬ψ.
Prove that if a maximally consistent set contains a sentence φ ⊃ ψ, then either it contains ¬φ or it contains ψ.