Note that when a problem asks you to “explain/justify” something, that is not asking for an answer as rigorous as when you are asked to “show/prove” something. And as we’ve discussed in class, when you are asked to prove something, we don’t expect it to be in a strict formal proof calculus, unless/until that’s what we specifically request. The kinds of proofs we’ve been doing on the board (with the steps made explicit enough), or that you’d submit for homework in a math class, are usually adequate.
Also, if two sentences are ever equivalent as a matter of propositional logic, you can simply say that. We don’t expect you to provide any further justification. Just be sure you’ve verified it for yourself.
Let S1 be a set, and let:
S2 = {S1}
S3 = {{S1}}
S4 = {S1, {S1}}
Questions:
S2 ∩ S4?S1 through S4 are members of S4?S1 through S4 are subsets of S4?For each of the following, true or false?
Α ⊆ Β and Β ⊆ Γ then Α ⊆ Γ.Α ⊆ Β and Β ⊆ Α then Α = Β.a ∈ Α and Α ⊆ Β then a ∈ Β.a ∈ Α iff {a} ⊆ Α.a ∈ Α and b ∈ Α iff {a,b} ⊆ Α.Let Α = {"a","b","c"}, Γ = {"c","d"}, and Δ = {"d","e","f"}. Then:
Α).Α – Γ?Α ∩ Γ?Α ∪ Γ?∅ ∪ Γ?Α ∪ (Γ ∩ Δ)?Α ∩ (Γ ∩ Δ)?List all elements of {0,1,2}².
Prove that Α ⨯ (Β ∩ Γ) = (Α ⨯ Β) ∩ (Α ⨯ Γ).
To prove that two sets are equal, first we prove that the left-hand set ⊆ the right-hand one, then we prove the converse (which I’ll describe as the left-hand set being ⊇ the right-hand one).
Here is a proof of the ⊆ direction: Suppose e ∈ Α ⨯ (Β ∩ Γ). Then by def of ⨯, e = (a,d) where (i) a ∈ Α and (ii) d ∈ Β ∩ Γ. From (ii) and def of ∩, it follows that (iii) d ∈ Β and (iv) d ∈ Γ. From (i) and (iii) and def of ⨯, it follows that (v) (a,d) ∈ Α ⨯ Β. From (i) and (iv) and def of ⨯, it follows that (vi) (a,d) ∈ Α ⨯ Γ. From (v) and (vi) and def of ∩, it follows that (a,d) ∈ (Α ⨯ Β) ∩ (Α ⨯ Γ). So by def of ⊆, Α ⨯ (Β ∩ Γ) ⊆ (Α ⨯ Β) ∩ (Α ⨯ Γ).
You supply a proof of the other direction.
Consider the functions described below, understood as applying for all x ∈ Χ and y ∈ Ψ. Is the function injective? (If “it depends,” what does it depend on?)
f(x,y) = (y,x)f(x,y) = xf(x) = y₀, for some fixed y₀ ∈ ΨProve that for any accessibility relation that’s symmetric, the relation will be transitive iff it’s right-Euclidean.
Prove that for any accessibility relation that’s symmetric, transitive, and right-Euclidean, the relation will be serial iff it’s reflexive.
Using a universe of {0,1,2}, give examples of a binary relation having the following features. (You can specify the relations by their graph.)
Is the relation “is a brother of” symmetric?
Give an example of an equivalence relation on the set of all pairs of living human beings (describe the relation in a short English phrase, please — don’t try to enumerate its graph!). Explain why it’s an equivalence relation.
Is the relation “is at least as old as” symmetric, anti-symmetric, or asymmetric?
Show it to be false that: If ⊨ φ ∨ ψ then ⊨ φ or ⊨ ψ.
Prove (using informal semantic reasoning) that φ ∨ ψ ⊨ χ iff φ ⊨ χ and ψ ⊨ χ.
Here is a proof of the “only if” (left-to-right) direction: Assume every model satisfying φ ∨ ψ also satisfies χ. Any model satisfying φ has to satisfy φ ∨ ψ, so will also satisfy χ; thus φ ⊨ χ. Same for any model satisfying ψ.
You supply of a proof of the other direction.
The following problems exercise material we’ve already gone through in class, so they should be ones you’re already in a position to handle. However, they won’t be assigned until the second homework assignment (along with some more problems on material we’ll be discussing in the next weeks). We give them to you now so that you have more opportunity to think about them and ask questions about them; but you aren’t expected to submit solutions of them until later.
Prove that if □ obeys a normal modal logic including axioms D and 4, then the “omissive Moore sentence” p ∧ ¬□p cannot be necessary (i.e. believed).
Prove that in any normal modal logic containing Axiom 5, from the premise □(q ⊃ □q), it follows that ◊q ⊃ □q. Hints: Show that the premise is true iff □(¬□q ⊃ ¬q). Help yourself to the propositional tautology that □q ∨ ¬□q. Work from there to establising □q ∨ □¬q. Work from there to the conclusion. This problem comes from reconstructions of Anselm’s “ontological proof” that God exists.
We explained in class that some premises are counted as entailing a conclusion in a normal modal logic just in case for every model and every world in that model, if the premises are all true then so too is the conclusion. So to disprove an entailment, we find a model and world where the premises are all true but the conclusion is false. Disprove the following entailments:
□p ⊨ p (it should be clear from our discussions that the accessibility relation in your model will have to fail to be reflexive)
p ⊨ □p
q ⊃ □q ⊨ ◊q ⊃ □q (if your counter-model has a right-Euclidean accessibility relation, it will show that the initial □ was essential to the proof in Problem 16)
Your neighbor sees your solution to Problem 17b and says “Wait a minute, I thought it’s a rule for all normal modal logics that when you’ve got p as a theorem, you could then infer □p as another theorem. How is that compatible with what you just did?” How would you answer their question and resolve their confusion?
Axiom D states □p ⊃ ¬□¬p, or equivalently, ¬(□p ∧ □¬p). A related sentence sometimes called “Axiom P” says ¬□⊥ (where ⊥ is a sentence logically guaranteed to be false). Prove that any normal modal logic contains Axiom D iff it contains Axiom P.
Cheryl’s Birthday. Albert and Bernard just met Cheryl. “When’s your birthday?” Albert asks her. Cheryl thinks a moment and says, “I’m not going to tell you, but I’ll give you some clues.” She writes down a list of ten dates: May 15, May 16, May 19, June 17, June 18, July 14, July 16, August 14, August 15, August 17. She says “My birthday is one of these dates.” Then Cheryl says she’ll whisper in Albert’s ear the month — and only the month — of her birthday, and she does so. Then Cheryl says she’ll whisper in Bernard’s ear the day — and only the day — of her birthday, and she does so.
“Can you figure it out now?” Cheryl asks Albert.
Albert answers, “I don’t know when your birthday is, but I know Bernard doesn’t know either.”
Bernard says, “I didn’t know originally, but now I do.”
Abert says, “Well, then now I know too!”
When is Cheryl’s birthday? Justify and explain your answer.