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)) $$

  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 23, 2013 at 19:29
  • $\begingroup$ I am sorry, I was using it in a self-deprecating manner. I am not so sure if my questions are dumb or not. $\endgroup$
    – Ishmael
    Commented Feb 23, 2013 at 19:32
  • $\begingroup$ @Chase Why don't you try to prove that both answers are equivalent? $\endgroup$
    – Git Gud
    Commented Feb 23, 2013 at 19:33
  • 2
    $\begingroup$ Don't be self-deprecating then. $\endgroup$ Commented Feb 23, 2013 at 19:40

2 Answers 2


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)$

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).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .