Phil 455: Homework 8

This homework is due by the end of the day on Mon April 1. (No, really.)

  1. Which of the following claims are equivalent?

    1. {φ} is satisfiable
    2. {φ} is unsatisfiable
    3. {¬φ} is satisfiable
    4. {¬φ} is unsatisfiable
    5. φ is a logical truth / valid formula
    6. no interpretation/structure/model makes φ true
    7. some interpretation makes φ true
    8. every interpretation makes φ true

  2. Which of the following claims are equivalent?

    1. Γ ∪ {φ} is satisfiable
    2. Γ ∪ {φ} is unsatisfiable
    3. Γ ∪ {¬φ} is satisfiable
    4. Γ ∪ {¬φ} is unsatisfiable
    5. φ is a logical (or “semantic”) consequence of Γ

  3. Is Γ ⊭ φ equivalent to Γ ⊨ ¬φ? Justify your answer.

  4. Here is a sample demonstration that P ⊃ (Q ⊃ P) is logically true, that is, that it’ll be true given any interpretation of the sentence letters:

    Terminology: I’ll say “interpretation” to mean, if we’re dealing with sentential/propositional logic, then every valuation/truth-assignment; if we’re dealing with predicate logic, then every structure/model and assignment. (I’ll only talk this way when it doesn’t matter what the assignment is.)

    Assume for reductio that some interpretation makes the whole sentence false. Then by the semantic rule for ⊃ (that is, the way that the truth-value of φ ⊃ ψ is determined by the value of φ and the value of ψ), the interpretation must make P true and Q ⊃ P false. But to achieve the latter, again by the rule for ⊃, it must make Q true and P false. But no interpretation can make P both true and false. So our assumption fails: there must be no interpretation that makes the whole sentence false.

    Show that these others are also logically valid:

    1. (P ⊃ Q) ∨ (Q ⊃ P)
    2. P ∨ (P ⊃ Q)
    3. ((P ⊃ Q) ⊃ P) ⊃ P

  5. Here is a sample demonstration that P ∨ Q and (P ⊃ Q) ⊃ Q are logically equivalent, that is, that they’ll have the same truth-value on any interpretation:

    Assume for reductio that some interpretation gives these sentences different truth-values. Either (i) it makes P ∨ Q false or (ii) it makes P ∨ Q true. In case (i), by the semantic rule for ∨ the interpretation must make both P and Q false; but then by the rule for ⊃ it must make P ⊃ Q true, giving (P ⊃ Q) ⊃ Q a true antecedent and false consequent, thus making it false. This is contrary to our assumption that the interpretation gives (P ⊃ Q) ⊃ Q a different truth-value than P ∨ Q. In case (ii), for the interpretation to make (P ⊃ Q) ⊃ Q false, it must make P ⊃ Q true and Q false, but then it can only do the former by making P false along with Q. But then it cannot make P ∨ Q true as claimed in the description of case (ii). So our assumption fails: there must be no interpretation that gives these sentences different truth-values.

    Show that these others are also logically equivalent:

    1. P ⊃ (Q ∨ R) versus (P ⊃ Q) ∨ (P ⊃ R)
    2. (Q ∨ R) ⊃ P versus (Q ⊃ P) ∧ (R ⊃ P)
    3. P ⊃ (Q ⊃ R) versus Q ⊃ (P ⊃ R)
    4. P ⊃ ¬Q versus Q ⊃ ¬P

  6. Let ℐ be a single interpretation. For sentential logic, these just have the job settling the truth-values of sentence letters like P, Q, and so on; and in that context they’re usually called “truth-assignments” or “valuations.” We talk about ℐ “satisfying” or “making true” some formula φ (which might be more complex than just P or Q). I like to write that like this: ⟦φ⟧ℐ = true, but you will see it written in a variety of ways, including: φℐ = true and ℐ ⊨ φ. The last notation can be very confusing, as we’ll see in this problem, because the ⊨ symbol is also used to express a relation between a set of sentences Γ and a formula φ, like this: Γ ⊨ φ. That expresses the claim that φ is a logical (or “semantic”) consequence of the premises in set Γ. You have to rely on context to determine which of these ways the ⊨ symbol is being used. If what occurs on the left-hand side is the name of a interpretation, ⊨ means the satisfies/makes-true relation. If what occurs on the left-hand side is a set of sentences, including a single sentence or no sentences, it means the logical consequence relation. (When ψ is a single sentence, ψ ⊨ φ is shorthand for {ψ} ⊨ φ; and Γ, ψ ⊨ φ is shorthand for Γ ∪ {ψ} ⊨ φ; and ⊨ φ with nothing on the left-hand side is shorthand for {} ⊨ φ.)

    The way we explain the semantics of ∨ and the satisfying/making-true relation, it follows that an interpretation ℐ makes the disjunctive sentence φ ∨ ψ true iff it makes φ true or it makes ψ true. You could write that like this: ℐ ⊨ φ ∨ ψ iff ℐ ⊨ φ or ℐ ⊨ ψ. (Note that only φ and ψ designate expressions of our formal/logical language. The other notation and words are claims in the metalanguage about the formal/logical language. I recommend only using spelled-out words like “iff” and “or” in the metalanguage, and only using symbols like ⊂⊃ and ∨ in the logical language you’re talking about. This helps keeps some things clearer.) Although you could express the satisying/making-true claim we just stated in that way, it’s easily confused with claims about consequence. The corresponding claim about consequence is not true, as you’ll now demonstrate.

    Show it to be false that: Γ ⊨ φ ∨ ψ iff Γ ⊨ φ or Γ ⊨ ψ.

  7. Prove (using informal reasoning about interpretations, as you did in Problems 88 and 89 — not by using a formal deduction or proof system like you learned in Intro Logic), that φ ∨ ψ ⊨ χ iff φ ⊨ χ and ψ ⊨ χ. (Yes, “and.” This is related to Problem 89b.)

  8. The rest of the problems specifically concern predicate logic, so now our formulas will be interpreted by “structures/models” like ℳ and “assignment functions” like q. Explain the difference between ⟦φ[x ← a]⟧ℳ q and ⟦φ⟧ℳ q[x:=a]. Hint: a is not being used in the same way in these two bits of symbolism. Your explanation should include what the difference is.

  9. Prove by induction on the 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 φ, ⟦φ⟧ℳf = ⟦φ⟧ℳ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 any 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.

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

  11. In Problem 94 you showed that for a closed formula/sentence ψ, a model ℳ will either make ψ true for all assignment functions or for none. Similarly for making ψ false. So in such cases, for short I’ll just talk of whether ℳ makes ψ true or false — suppressing mention of the assignment when any assignment will do.

    For this problem, let φ be a formula with no free/unbound variables except (possibly) x. Prove that ⊨ ∃x(φ ⊃ ∀xφ). Hint: Start a reductio by assuming there’s a model ℳ that makes ∃x(φ ⊃ ∀xφ) false.

  12. Here is a proof that ∀x(Fx ⊃ P) and ∃xFx ⊃ P are logically equivalent:

    If model ℳ makes ∀x(Fx ⊃ P) false (on any assignment), there must be some element of the domain that can be assigned to x in such a way that Fx ⊃ P is false on ℳ and that (variant) assignment. I’ll call this assignment q. But then ℳ and q must make P false, and make Fx true. But if ℳ and q make Fx true, then ℳ (and any assignment) must make ∃xFx also true; and assignments make no difference to the interpretation of P. So ℳ (and any assignment) will make ∃xFx ⊃ P also false. On the other hand, if model ℳ makes ∃xFx ⊃ P false (on any assignment), it must make ∃xFx true and P false. Then there must be some element of the domain where ℳ and an assignment of that element to x make Fx true. But then on ℳ and that (variant) assignment, Fx ⊃ P will be false. But then ℳ (and any assignment) cannot make ∀x(Fx ⊃ P) true. So a model (and assignment) make the one formula false iff it makes the other false.

    Show that the following are logically equivalent.

    1. P ⊃ ∀xFx versus ∀x(P ⊃ Fx)
    2. ∀x(Fx ∧ Gx) versus ∀xFx ∧ ∀xGx

  13. Show that these are not logically equivalent: ∀x(Fx ∨ Gx) versus ∀xFx ∨ ∀xGx.

  14. Show that (a) ∃x∀yRxy ⊨ ∀y∃xRxy, but that (b) ∀y∃xRxy ⊭ ∃x∀yRxy.

  15. Some authors restrict ⊨ to apply only to closed formulas; others like us and Goldrei allow it to apply to open formulas too. We say that Γ ⊨ φ when for every model ℳ and assignment q that make all the formulas in Γ true, that ℳ and q also make φ true. (Sometimes this may be because every ℳ and q at all make φ true; sometimes it may be because no ℳ and q make all the formulas in Γ true…)

    1. Show that if ⊨ φ then ⊨ ∀xφ. For simplicity, you can assume that φ is a formula with no free/unbound variables except (possibly) x.

    2. However, here is example that shows that it’s not generally true that φ ⊨ ∀xφ. Show that x = c ⊭ ∀x x = c.

    Given (b), we can’t say that formulas with free variables in them, like x = c, have the same meaning or are logically equivalent to their universal generalizations.