Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Reading my textbook, I came across exercises for nested quantifiers.

The question: Let $L(x, y)$ be the statement “$x$ loves $y$,” where the domain for both $x$ and $y$ consists of all people in the world. Use quantifiers to express each of these statements.

i) Everyone loves himself or herself.

Textbook answer: $$ \forall xL(x, x) $$

Is this equivalent to my answer? : $$ \forall x\forall y((x=y)\to L(x,y)) $$

share|improve this question
1  
How do you know that the question is trivial? A good rule of the thumb with the word trivial is that one should only use it on things one can do... otherwise, it is a bit silly. –  Mariano Suárez-Alvarez Feb 23 '13 at 19:29
    
I am sorry, I was using it in a self-deprecating manner. I am not so sure if my questions are dumb or not. –  Chase Feb 23 '13 at 19:32
    
@Chase Why don't you try to prove that both answers are equivalent? –  Git Gud Feb 23 '13 at 19:33
2  
Don't be self-deprecating then. –  Mariano Suárez-Alvarez Feb 23 '13 at 19:40

2 Answers 2

up vote 4 down vote accepted

They're equivalent.

Let's start with $(\forall x)(\forall y) ((x=y)\to L(x,y))$:

  1. Apply instantiation twice and set $x/x$ and $x/y$, getting $(x=x)\to L(x,x)$.
  2. $x=x$ is an axiom of reflexivity of equality.
  3. From these two infer $L(x,x)$ (modus ponens).
  4. Apply generalization to get $(\forall x) L(x,x)$.

And the other way around: Let's start with $(\forall x) L(x,x)$.

  1. Apply instantiation to get $L(x,x)$.
  2. Use substitution for formulas axiom to get $(x = y) \to (L(x,x) \to L(x,y))$.
  3. Exchange the antecendents to get $L(x,x) \to ((x = y) \to L(x,y))$ (we can do this because $\phi\to(\psi\to\rho) \equiv \psi\to(\phi\to\rho)$ is a tautology).
  4. Apply modus ponens on 3. and 1. to get $(x = y) \to L(x,y)$.
  5. Use generalization twice to get $(\forall x)(\forall y) (x = y) \to L(x,y)$
share|improve this answer

Petr Pudlák's answer is of course exactly right about the equivalence, and he gives a pair of proofs which shows why it holds. But it is worth remarking as a footnote that this equivalence is (of course!) only available if you are already using the language of first-order logic with identity.

Now, it is natural and indeed pretty standard first to (1) introduce the language of first-order logic first without identity and then (a later chapter!) (2) add the identity relation. Note, then, that "Everyone loves himself or herself" can already be perfectly well rendered into our formalism at stage (1): we do not have to have identity explicitly in the formal language do to the translation.

It is a good principle, when rendering English into the language of FOL, to only expose as much structure as we need (translating as simply as we can, without unnecessarily going round the houses -- as with any translation). That is why the simpler translation already available at level (1) would be preferred as a translation to the unnecessary circumlocution of the more complex (though provably equivalent) sentence that becomes available at level (2).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.