5

I am trying to figure out the negation of $\forall xT(x) \implies \exists y L(y)$

I have two choices in mind

  1. $\exists x T(x) \land \forall y \neg L(y)$

  2. $\forall x T(x) \land \forall y \neg L(y)$

Not sure which is correct. I know in general the negation of $p \implies q$ is $p \land \neg q$ but here how to handle the quantifiers is confusing me.

For instance if the bracketing was $\forall x(T(x) \implies \exists y L(y))$, then I believe the negation would be $\exists x T(x) \land \forall y \neg L(y)$, but in this case since $\forall x T(x)$ is a premise, I think that $2$ is correct.

IntegrateThis
  • 3,778
  • 3
    It's 2. ${}{}{}$ – Shaun Mar 13 '21 at 00:15
  • 1
    The traditional convention is that quantifiers bind tighter than the binary connectives: so you should read your formula as $(\forall x T(x)) \implies (\exists y(L(y))$, which makes your proposed answer 2 the correct one. (Your idea about $\forall x(T(x) \implies \exists y(L(y))$ isn't right: $\implies$ should still turn into $\land$ when you negate it.) – Rob Arthan Mar 13 '21 at 00:24
  • @RobArthan ok thank you. You can post this as an answer if you'd like. – IntegrateThis Mar 13 '21 at 00:28
  • Thanks for the suggestion - done. – Rob Arthan Mar 13 '21 at 00:29

2 Answers2

1

You're nearly there. Just note that $$\lnot\exists yLy\equiv \forall y\lnot Ly.$$

Shaun
  • 44,997
  • The issue is really the confusion over in the original statement, notationwise, are we saying that when there exists an $x$ such that $T(x)$ then $\exists y $ with $L(y)$. Or rather is the statement that when $\forall x T(x)$ is true, then $\exists y$ with $L(y)$? I think we have answered it is the latter. – IntegrateThis Mar 13 '21 at 00:25
1

The traditional convention is that quantifiers bind tighter than the binary connectives: so you should read your formula as $(\forall x T(x)) \implies (\exists y(L(y))$, which makes your proposed answer 2 the correct one. (Your idea about $\forall x(T(x) \implies \exists y(L(y))$ isn't right: $\implies$ should still turn into $\land$ when you negate it. This would lead to answer 1.)

Rob Arthan
  • 48,577