prove whether two quantifier logic statement are logic

227 Views Asked by At

I want to know how to transform the logic statment to another.

Let L(x,y) be the statement"x loves y," where the domain for both x and y consist of all people in the world.

There is someone who loves no one besides himself.

original answer:∃x∀y(L(x,y)↔x=y)

my solution:∃x(L(x,x)∧∀y((y≠x)⇒¬L(x,y)))

My thought:It exists a person x that love himself/herself,for every people y which is not equal to x,person x will not love,so there is someone who loves no one besides himself.

It seem logic equivalent literally.

However,if there are logic equivalent ,they can transform into same form. which means ∃x(L(x,x)∧∀y((y≠x)⇒¬L(x,y))) can transform to ∃x∀y(L(x,y)↔x=y).

My work:

∃x(L(x,x)∧∀y((y≠x)⇒¬L(x,y)))

∃x(L(x,x)∧∀y(L(x,y)⇒(y=x))) (reversing implication)

∃x(L(x,x)∧(∀yL(x,y)⇒∀y(y=x))) (∀ distribute ⇒)

∃x(L(x,x)∧(¬∀yL(x,y)∨∀y(y=x))) (rewrite implication)

∃xL(x,x)∧∃x(¬∀yL(x,y)∨∀y(y=x)) (since ∃x(P(x) ∧ Q(x)) → (∃xP(x) ∧ ∃xQ(x)))

∃xL(x,x)∧(∃x¬∀yL(x,y)∨∃x∀y(y=x))

Then i am stuck with these mess.

1

There are 1 best solutions below

2
On BEST ANSWER

The problem you are running into is the fact that the 'standard' set of equivalences for statements involving quantifiers is not complete. That is, certain first-order equivalences (such as this one) cannot be demonstrated by a series of applications of this 'standard' set of equivalences, and so you'll need to prove the equivalence using rules of inference ... for which the 'standard' set is complete.

Now, with your problem, you can actually get pretty far. Starting with the other statement, you can do:

$\exists x \forall y (L(x,y) \leftrightarrow x=y)$

$\exists x \forall y ((L(x,y) \to x=y) \land (x=y \to L(x,y))$

$\exists x (\forall y (L(x,y) \to x=y) \land \forall y (x=y \to L(x,y)))$

Now, from here, you of course want to go to

$\exists x \forall y (L(x,y) \to x=y) \land \exists x \forall y (x=y \to L(x,y))$

But while this statement is in fact equivalent to the previous one, this is only so in virtue of the fact that in order for the latter statement to be true, the $\exists x$ actually has to be the very same object, but this is something specific to this statement: in general, the statements $\exists x (P(x) \land Q(x))$ and $\exists x (P(x)) \land \exists x (Q(x))$ are not equivalent, and so while there is an equivalence principle to distribute a universal over a conjunction, you clearly cannot do this for an existential ... and there is no equivalence principle that states iñ which special cases (like this one) where in fact you can.

Now, if we can get to the latter statement, we can continue with:

$\exists x \forall y (x \neq y \to \neg L(x,y)) \land \exists x \forall y (L(x,y) \to x =y)$

And now we're pretty close! Indeed, $\exists x \forall y (x=y \to L(x,y))$ and $\exists x \ L(x,x)$ are equivalent, but once again, the 'usual' set of equivalence principles does not allow you to demonstrate this.