Translate the following sentences into predicate logic. Use Sx for “x is a student”, Px for “x is a professor”, Rxy for “x respects y”, and use the equality symbol “=” where relevant. You may assume that quantifiers range over people, so you don’t need any additional symbol for “x is a person.” [2 points each]
Any professor whom some students respect is respected by some professor.
There is someone who, although not him or herself a student, respects any student who respects no professor.
There is exactly one professor who respects only those students who respect him.
Prove the following sequents. You may use cut and/or replacement with any results, so long as you refer to a fully rigorous proof (e.g. in textbook or a previous pset). [4 points each]
(∀xFx→∀xGx) → ∀xFx ⊢ ∀xFx
Solution: This is just an instance of Peirce’s law, and its validity depends only on its propositional structure.
∀x∀y∀z(Rxy→¬Ryz) ⊢ ∃y∀x¬Rxy
Solution: As usual, there are several different ways that this result can be proven. For example: use excluded middle to infer ∃y∃xRxy∨¬∃y∃xRxy. The second disjunct implies ∀y∀x¬Rxy and hence ∃y∀x¬Rxy. The first disjunct says that there are two things, say a and b, such that Rab. The first premise then implies that, for arbitrary c, Rca→¬Rab. Therefore ¬Rca and it follows that ∃y∀x¬Rxy.
(I’m fairly confident that this result cannot be proven in intuitionistic logic, and so requires the use of EM or another result derived from the full power of DNE.)
Provide two interpretations to show that the following sentence is a contingency. [4 points]
∀x(Fx→Gx) ∨ ∀x(Gx→Fx)
Can there be a correctly written proof with the following line fragments? Justify your answer by reference to the existence (or non-existence) of relevant interpretations, and by citing soundness or completeness. [4 points]
1 (1) ∀y∃xRxy A
1 (n) ∃x∃y(Rxy∧Ryx)