Phil 455: Homework 8 (on Concepts and Proof Systems)

This homework is due by Friday April 8. Communicate with me if you need assistance or more time to complete the homework.

  1. Prove (using informal semantic reasoning, as you used in Homework 7, Problems 7–13), that φ ∨ ψ ⊨ χ iff φ ⊨ χ and ψ ⊨ χ.

  2. Prove by induction on the structure/complexity of φ (see hint below for what this looks like) that for any formula φ, model 𝓜, and assignment functions f and g that agree on all variables free in φ, ⟦phi⟧𝓜f = ⟦phi⟧𝓜g. To keep things simpler, you can assume that the language has no functors or =, and that the only quantifier is ∀ and connectives are ⊃ and ~.

    Hint: as a base case, prove the thesis for all atomic φ, that is, ones of the form Rαβγ..., where α,β,γ,... are each either a variable or a term constant. Then for the inductive step, assume the thesis holds for some formulas φ and ψ, and prove then it must also hold for each of: (a) ~φ, (b) φ ⊃ ψ, and (c) ∀ξφ, where ξ is some variable (which may or may not be free in φ).

    If you need more help, compare Goldrei’s Theorem 4.1 (which he states on p. 156 and proves on pp. 159–160). To understand some of his notation, you may need to refer to pp. 151–2. Essentially, what he writes as x̅/a̅ is what I’d write as “an assignment q that maps each of the variables x̅ to the corresponding object in a̅,” and what he writes as x̅/a̅[xi/b] is what I’d write as q[xi:=b]. There are enough differences between Goldrei’s notation and ours, and his assumptions and ours (he is considering functors and =), that I expect you’ll probably have the easiest time just attempting this proof on your own. But I’ve given you references to his discussion in case it might be helpful.

  3. Prove that if φ is a closed formula, then a model 𝓜 will satisfy it either on all assignment functions or none. (Hint: use what you proved in the previous problem.)

  4. Define what the following concepts mean. Don’t use any of this vocabulary: “implies”, “follows”, “entails” (with no prefix, or prefixed by “logical”), “equivalent” (with no prefix, or prefixed by “logical”). Acceptable vocabulary: “semantically entails,” “semantic consequent,” “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.

    1. proof system S is sound
    2. proof system S is complete
    3. sentence φ is valid
    4. set of sentences Γ is satisfiable
    5. sentences φ and ψ are semantically equivalent
    6. a theory (set of sentences closed under semantic consequence) is complete (sometimes called “maximally consistent”)
    7. a set of arbitrary strings is effectively decidable
    8. a set of arbitrary strings is not decidable but only effectively enumerable
    9. a theory is effectively decidable
    10. a theory is not decidable but only effectively enumerable
    11. a semantic entailment/consequence relation ⊨ is effectively decidable
    12. a semantic entailment/consequence relation ⊨ is not decidable but only effectively enumerable

  5. Which of the following claims are equivalent?

    1. {φ} is satisfiable
    2. {φ} is unsatisfiable
    3. {~φ} is satisfiable
    4. {~φ} is unsatisfiable
    5. φ is semantically valid
    6. no model makes φ true
    7. some model makes φ true
    8. every model makes φ true

  6. Which of the following claims are equivalent?

    1. Γ ∪ {φ} is satisfiable
    2. Γ ∪ {φ} is unsatisfiable
    3. Γ ∪ {~φ} is satisfiable
    4. Γ ∪ {~φ} is unsatisfiable
    5. φ is a semantic consequence of Γ

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

  8. 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?

    If Γ ∪ {~φ} is satisfiable, then Γ ∪ {~φ} is deductively consistent in proof system S.

    updated This should be understood as a claim about all sentences φ and sets of sentences Γ.

  9. 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 follows from steps already written by the system’s rules. Consider an axiomatic proof system that has the single 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.

    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.

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