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, 2013 at 0:10

3 Answers 3

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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 0:24
  • $\begingroup$ Oh well, i meant a the "_" over it. But thats ok too. $\endgroup$
    – Wyvern666
    Jun 16, 2013 at 0:45
  • $\begingroup$ Eh? You mean $\overline {\exists x\,A}$? $\endgroup$
    – dfeuer
    Jun 16, 2013 at 4:41

You must log in to answer this question.

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