Predicate logic: Equivalence between two formulas

490 Views Asked by At

Consider the following sentence:

(1) The last man on earth is the last man in the Universe.

I think that both (A) and (B) capture the form of (1) (I'm assuming Russell's theory of definite descriptions):

(A) ∃x(P(x)∧Q(x)∧∀y((P(y)∨Q(y))⊃x=y))

(B) ∃x∃y(P(x)∧∀z(P(z)→z=x)∧Q(y)∧∀z(Q(z)→z=y)∧x=y)

P = last man on earth Q = last man in the Universe

But I was asking myself if (A) and (B) really are logically equivalent. In particular, I'm worried about (A) being compatible with the existence of several last men on earth, or with several last men in the Universe. Are (A) and (B) logically equivalent? If not, why?

1

There are 1 best solutions below

8
On BEST ANSWER

Yes, they really are equivalent. With the identity in there the algebra to demonstrate equivalence is a bit hairy, and a formal proof also takes about 40-50 lines, but they really are equivalent.

And at the very least it is easy to demonstrate that a) does not allow for more than one last man on Earth or more than one last man in the Universe, because the $\forall y ((P(y) \lor Q(y)) \rightarrow x=y)$ part in a) will guarantee that anyone who is either the last man on Earth or the last man in the Universe will have to be identical to $x$. In fact, here is an equivalence that is easy to demonstrate that may help in seeing that:

$\forall y ((P(y) \lor Q(y)) \rightarrow x=y) \Leftrightarrow $ (Implication)

$\forall y (\neg (P(y) \lor Q(y)) \lor x=y) \Leftrightarrow$ (DeMorgan)

$\forall y((\neg P(y) \land \neg Q(y)) \lor x =y) \Leftrightarrow$ (Distribution)

$\forall y ((\neg P(y) \lor x=y) \land (\neg Q(y) \lor x=y)) \Leftrightarrow$ (Implication x2)

$\forall y (P(y) \rightarrow x=y) \land (Q(y) \rightarrow x=y))$ (Distribution $\forall$ over $\land$)

$\forall y (P(y) \rightarrow x=y) \land \forall y (Q(y) \rightarrow x=y)$

ADDENDUM

You asked for a tree .... here is a tree:

enter image description here