Homework 8

Which of the following claims are equivalent?

{φ} is satisfiable
{φ} is unsatisfiable
{¬φ} is satisfiable
{¬φ} is unsatisfiable
φ is a logical truth / valid formula
no interpretation/structure/model makes φ true
some interpretation makes φ true
every interpretation makes φ true

(a) and (g) are equivalent. (b) and (f) are equivalent. (d) and (e) and (h) are equivalent.

Which of the following claims are equivalent?

Γ ∪ {φ} is satisfiable
Γ ∪ {φ} is unsatisfiable
Γ ∪ {¬φ} is satisfiable
Γ ∪ {¬φ} is unsatisfiable
φ is a logical (or “semantic”) consequence of Γ

(d) and (e) are equivalent.

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

No. Let φ be a sentence like P or a = b, which is true on some interpretations but false on others. Γ can be, for example, the empty set. Neither φ nor ¬φ will be a consequence of no premises.

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:

(P ⊃ Q) ∨ (Q ⊃ P)
P ∨ (P ⊃ Q)
((P ⊃ Q) ⊃ P) ⊃ P

Assume for reductio that some interpretation makes the whole sentence false. Then by the semantic rule for ∨, it has to make both disjuncts false. By the rule for ⊃, to make the first disjunct false it has to make P true and Q false. But then by the rule for ⊃, it can’t make the second disjunct false. So our assumption fails.
Assume for reductio that some interpretation makes the whole sentence false. Then by the semantic rule for ∨, it has to make both disjuncts false. But if it makes the first disjunct false, then by the rule for ⊃, it has to make the second disjunct true. So our assumption fails.
Assume for reductio that some interpretation makes the whole sentence false. Then by the semantic rule for ⊃, it has to make (P ⊃ Q) ⊃ P true and P false. But if P is false then by the rule for ⊃, P ⊃ Q will be true, and so (P ⊃ Q) ⊃ P will have a true antecedent and a false consequent, so must be false. But we said it had to be true. So our assumption fails.

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:

P ⊃ (Q ∨ R) versus (P ⊃ Q) ∨ (P ⊃ R)
(Q ∨ R) ⊃ P versus (Q ⊃ P) ∧ (R ⊃ P)
P ⊃ (Q ⊃ R) versus Q ⊃ (P ⊃ R)
P ⊃ ¬Q versus Q ⊃ ¬P

If an interpretation makes (P ⊃ Q) ∨ (P ⊃ R) true, it has to make one of the disjuncts true, so it cannot make P true and both of Q and R false. So it cannot make P ⊃ (Q ∨ R) false, either. This shows that if it makes the first (rhs) true, it makes the second (lhs) true. If an interpretation makes (P ⊃ Q) ∨ (P ⊃ R) false, it must make both disjuncts false. So it must make P true and both of Q and R false. So it will make Q ∨ R false, and P ⊃ (Q ∨ R) also false. This shows that if it makes the first false, it makes the second false. So an interpretation always gives these formulas the same truth-value.
If an interpretation makes (Q ∨ R) ⊃ P true, it cannot make P false and either of Q and R true. So it cannot make either of Q ⊃ P or R ⊃ P false. This shows that if it makes the first (lhs) true, it makes the second (rhs) true. If an interpretation makes (Q ∨ R) ⊃ P false, it must make P false and either of Q and R true. So it will make at least one of Q ⊃ P or R ⊃ P false. This shows that if it makes the first false, it makes the second false. So an interpretation always gives these formulas the same truth-value.
If an interpretation makes P ⊃ (Q ⊃ R) false, it must make P true and Q ⊃ R false, which it turn means it must make Q true and R false. But then it will make P ⊃ R also false, and so Q ⊃ (P ⊃ R) also false. Analogous reasoning shows that if an interpretation makes Q ⊃ (P ⊃ R) false, it must also make P ⊃ (Q ⊃ R) false. So an interpretation makes the one formula false iff it makes the other false.
If an interpretation makes P ⊃ ¬Q false, it must make P true and ¬Q false, and so make Q true. But then it will make Q ⊃ ¬P false. Analogous reasoning shows that if an interpretation makes Q ⊃ ¬P false, it must also make P ⊃ ¬Q false. So an interpretation makes the one formula false iff it makes the other false.

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 Γ ⊨ ψ.

Let φ be the sentence constant P and ψ be ¬P. Γ can just be the empty set. Neither of φ nor ψ will be semantically valid (that is, consequences of zero premises), because on some interpretations P will be true and on others P will be false. But on every interpretation P ∨ ¬P will be true. So the left-to-right (“only if”) direction fails.

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

Proof of the “only if” (left-to-right) direction: Assume every interpretation satisfying φ ∨ ψ also satisfies χ. Any interpretation satisfying φ has to satisfy φ ∨ ψ, so will also satisfy χ; thus φ ⊨ χ. Same for any interpretation satisfying ψ.

Proof of the “if” (right-to-left) direction: Assume every interpretation satisfying φ also satisfies χ, and that every interpretation satisfying ψ also satisfies χ. Consider any interpretation that satisfies φ ∨ ψ, then it either must satisfy φ or it must satisfy ψ (it may of course do both). Either way, by our assumptions it must also satisfy χ. Since this is true for any interpretation that satisfies φ ∨ ψ, φ ∨ ψ ⊨ χ.

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.

In the first, a is a term constant of the language, and we substitute it in for any free variables x in formula φ. Then we interpret the resulting formula using model ℳ and assignment function q. In the second, a is a metalanguage expression picking out some element of the domain. Here we interpret the original formula φ using using model ℳ and a variant assignment function q′, which is like q except that it maps x to a (if q already does so, then q′ is just q).

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̅[x_i/b] is what I’d write as q[x_i:=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.

Base case: φ is an atomic formula, of the form Rαβγ…, where α,β,γ,… are each either a variable or a term constant. For each term that’s a term constant, their intepretation will depend only on ℳ and not on the assignment function. For each term that’s a variable, the variable will here be free (the formula in question is atomic, so has no quantifiers) and by hypothesis f and g will give them the same interpretation. Since the whole formula depends only on the interpretation of R, which is given by ℳ, and the interpretation of each of R’s argument terms, which we just showed f and g agree on, the interpretation of the whole formula will also agree.

Inductive step: we assume that the thesis holds for φ and ψ, and have to show it holds for each of:

¬φ: The interpretation of this on a model ℳ and each of f, g depends only on the interpretation of φ on each of f and g. Our inductive assumption tells us that the interpretation of φ can be trusted to be the same when f and g agree on all free variables in φ. Since that’s the same constraint as agreeing on all free variables in ¬φ, our inductive assumption gives us what we need.
φ ⊃ ψ: The interpretation of this depends only on the interpretation of φ and ψ on each of f and g. Our inductive assumption tells us that the interpretation of φ can be trusted to be the same when f and g agree on all free variables in φ; and the interpretation of ψ can be trusted to be the same when f and g agree on all free variables in ψ. Since the free variables in φ ⊃ ψ are the union of the free variables in φ and ψ, and the thesis we’re arguing for concerns f and g that agree on all those, they will agree on all the variables needed for the inductive assumption to give us what we need.
∀ξφ: This is the harder case, because the thesis we’re arguing for concerns assignments f and g that agree on all the free variables in ∀ξφ, which won’t include ξ, but the subformula φ usually will have ξ free. So our inductive assumption will only tell us that the interpretation of φ can be trusted to be the same when f and g additionally agree on ξ — which we’re not given that they do. The solution to this obstacle is that ∀ξφ will only be true on assignment f if the interpretation of φ comes out true no matter what object from the domain is assigned to ξ. Given that, plus our inductive assumption that any other differences between f and g don’t matter to the interpretation of φ, guarantee that ∀ξφ will be true on assignment g as well. We can reason in the same way that if ∀ξφ is true on assignment g, that plus our inductive assumption guarantee that ∀ξφ will be true on assignment f as well.

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

Since φ has no free variables, using what we showed in Problem 93: for any model ℳ, and assignment functions f and g, ⟦φ⟧_ℳf = ⟦φ⟧_ℳg.

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.

Suppose for reductio there’s a model ℳ that makes ∃x(φ ⊃ ∀xφ) false. Then for every object a in ℳ’s domain, φ ⊃ ∀xφ has to be false on an assignment that maps x to a. That means that φ has to be true on ℳ paired with any such assignment, and ∀xφ has to be false. But for the latter to be the case, there has to be some object b in ℳ’s domain where φ is false on ℳ and an assignment that maps x to b. In that case, φ cannot be true on ℳ and every assignment of objects in the domain to x. Hence our reductio supposition that there’s a model that makes ∃x(φ ⊃ ∀xφ) false fails. In other words, every model must make that sentence true.

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.

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

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

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

Consider a model whose domain has exactly two objects 0 and 1, with only 0 being in the extension of F and only 1 being in the extension of G. Then ∀xFx and ∀xGx will both be false on this model. But ∀x(Fx ∨ Gx) will be true.

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

Suppose a model makes ∃x∀yRxy true (on any assignment). Then there has to be some element of the domain, m, that can be assigned to x in such a way that the model makes ∀yRxy true on that assignment. That means that for every element n of the domain, the pair (m,n) has to be in the extension this model assigns to R. But then there will be an element that can be assigned to x, namely m, such that no element can be assigned to y in such a way to make Rxy false on that assignment. So this model has to make ∃xRxy true for every assignment to y, and so make ∀y∃xRxy true.
Consider a model whose domain has exactly two objects 0 and 1, and that assigns to R the extension {(0,1),(1,0)}. No element of the domain can be assigned to x in such a way that this model makes ∀yRxy true on that assignment. So the model makes ∃x∀yRxy false (on any assignment). But if y is assigned 0, there is an assignment to x (namely, 1) that makes Rxy true on this model, and if y is assigned 1, there is also an assignment to x (namely 0) that makes Rxy true. So for every assignment to y, this model makes ∃xRxy true, and thus it makes ∀y∃xRxy true.

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

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

Suppose that ⊨ φ; then on every model and assignment, φ will be true. But then no model will have an object in its domain where an assignment can map x to that object and thereby make φ false on that model and assignment. But in that case, no model and assignment can make ∀xφ false.
However, here is example that shows that it’s not generally true that φ ⊨ ∀xφ. Show that x = c ⊭ ∀x x = c.

Consider a model with two objects in its domain, Carly and Bob, where the model interprets constant c to mean Carly. Consider an assignment that maps x to Carly. On that model and assignment, x = c is true, but ∀x x = c is false.

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.