6
$\begingroup$

I need equivalent expressions for: $\lnot (\forall x)\exists y A$

  1. $\exists x \lnot (\exists y A)$

  2. $\exists x \lnot (\exists y) A$ The same as (1) I think

  3. $\exists x \exists y \lnot A $

Which one is OK? And what would be the result for the negation: $\lnot(\lnot (\forall x)\exists y A)$?

  1. $\forall x \lnot (\exists y A) $

Is that OK?

In fact, what I want is $\lnot (\forall x)\exists y A$ without any negated quantifier, if this is possible.

$\endgroup$
1
  • 2
    $\begingroup$ The difference between 1 and 2 appears to be purely notational. Different texts/teachers use different notation for quantified expressions. You should use the notation expected in your class. $\endgroup$ – dfeuer Jun 16 '13 at 0:10
6
$\begingroup$

The first two work. Not the third.

  1. $\lnot (\forall x)\exists y A \equiv \exists x \lnot (\exists y A)\quad$ YES!

  2. $\lnot (\forall x)\exists y A \equiv \exists x \lnot (\exists y) A \quad ?\quad$ The same as (1): More or less, but stick with $(1)$

  3. $\lnot (\forall x)\exists y A \not\equiv \exists x \exists y \lnot A $

Then we have from $(1)$: $$\lnot (\forall x)\,\exists y\, A \quad \equiv \quad\exists x \,\lnot (\exists y \,A) \quad \equiv \quad \exists x \,\forall y \,(\lnot A)$$

Now: $$\lnot\,(\,\lnot (\forall \,x)\exists y\, A ) \quad \equiv \quad\forall x\, \exists y\,A\,$$

$\endgroup$
14
  • $\begingroup$ Nice, i like more the $\equiv$ symbol, maybe im more familiar with it in this cases. $\endgroup$ – Wyvern666 Jun 16 '13 at 0:21
  • 2
    $\begingroup$ Your confusion is based on the fact that you are not grouping the expression properly in your head, because of your somewhat inconsistent notation. Let me rewrite it for you: $\lnot(\lnot(\forall x\,\exists y\,A))$. The expression $\forall x\,\exists y\,A$ is all one unit. So reducing $\lnot(\lnot(\forall x\,\exists y\,A))$ to $\forall x\,\exists y\,A$ is the same as reducing $\lnot(\lnot p)$ to $p$. $\endgroup$ – dfeuer Jun 16 '13 at 4:49
  • 1
    $\begingroup$ If it's false that it's false that you are the worst barber in the world, then you are the worst barber in the world. If you are the worst barber in the world, then it's false that it's false that you are the worst barber in the world. At least, that's how it works in classical logic. In intuitionistic logic, the situation is rather more complicated, but it would probably be best to avoid that for now (or forever). $\endgroup$ – dfeuer Jun 16 '13 at 4:49
  • 1
    $\begingroup$ Wyvern666 We, in fact, have a double negation: $\;\lnot\,(\,\lnot (\forall \,x)\exists y\, A )\;\equiv \lnot(\lnot \forall x\,\exists y\,A)\; \equiv \;\lnot\lnot (\forall \,x \exists y\, A ) \equiv \forall\,x\exists y\, A$ $\endgroup$ – amWhy Jun 16 '13 at 14:16
  • 1
    $\begingroup$ No: $\lnot(\forall x \lnot \exists y A) \equiv \lnot(\lnot \exists x \exists y A) = \exists x\exists y A$ or we get the same by pushing negation in: $\lnot(\forall x \lnot \exists y A) \equiv \lnot \forall x \lnot \exists y A \equiv \exists x \lnot\lnot \exists y A \equiv \exists x \exists y A$ $\endgroup$ – amWhy Jun 19 '13 at 19:01
3
$\begingroup$

Since this appears to be homework, I will offer an approach to the solution, rather than a solution. You should consider two questions:

  1. How can you rewrite $\lnot \forall x\,A$ in terms of $\exists$?
  2. How can you rewrite $\lnot \exists x\,A$ in terms of $\forall$?
$\endgroup$
2
  • 1
    $\begingroup$ Sorry, not homework. I have already done this but not with different cuantifiers, it just gets tricky sometimes. But im learning. $\endgroup$ – Wyvern666 Jun 16 '13 at 0:16
  • 1
    $\begingroup$ Break it down, one layer at a time. Try to answer the questions I pose. Think about what they mean. If I say "It's false that every bird is red", how can you rephrase that as "There exists a bird ..."? If I say "There does not exist a bird larger than my house", how can you rephrase that as "All birds ..."? $\endgroup$ – dfeuer Jun 16 '13 at 0:33
1
$\begingroup$

(1) and (2) in your answer are the same and are the answer.

You can also write $\lnot\exists$ as $\nexists$.

If you pin down $A$ as a relation from domain $X$ to range $Y$, so that $A\colon X \to Y$, then you can write $A=\{\}$.

$\endgroup$
3
  • $\begingroup$ Oh yes, in fact i use the backslash over everytime, no the $\lnot$ thing wich confuses me when dealing large formulas. $\endgroup$ – Wyvern666 Jun 16 '13 at 0:24
  • $\begingroup$ Oh well, i meant a the "_" over it. But thats ok too. $\endgroup$ – Wyvern666 Jun 16 '13 at 0:45
  • $\begingroup$ Eh? You mean $\overline {\exists x\,A}$? $\endgroup$ – dfeuer Jun 16 '13 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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