logic pset10


Represent the form of the following sentences in predicate logic using the = symbol where necessary.

  1. There is one and only one Princeton University. (Use Px for “x is a Princeton University”)

  2. There is at most one Ivy League university in New Jersey. (Use Ix for “x is an Ivy League university”, and use Nx for “x is in New Jersey.”)

  3. The smallest prime number is even. (Px, Ex, x < y, variables are restricted to numbers.)


Prove the following sequents using any of the rules, including the = intro and elim rules. You may write proofs in “sloppy mode”, i.e. you may combine steps, cut in results proved elsewhere, etc., as long as you explain clearly and convincingly how the proof works.

  1. x(Px∧∀y(Pyx=y)) ⊢ ∀xy((PxPy)→x=y)

  2. ⊢ ∀xy((x=y)→(y=x))


Let Rxy be a binary relation symbol that satisfies the transitivity axiom (page 126). Suppose that Rxy satisfies two other axioms: serial xyRxy and irreflexive x¬Rxx. Show that there are at least three distinct things. (Your proof need not be fully formal, but it needs to be clear that you understand why the moves you make are licensed by our system.)