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.

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.

share|improve this question
2  
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. –  dfeuer Jun 16 '13 at 0:10

3 Answers 3

up vote 6 down vote accepted

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\,$$

share|improve this answer
    
Nice, i like more the $\equiv$ symbol, maybe im more familiar with it in this cases. –  Wyvern666 Jun 16 '13 at 0:21
2  
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$. –  dfeuer Jun 16 '13 at 4:49
1  
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). –  dfeuer Jun 16 '13 at 4:49
1  
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$ –  amWhy Jun 16 '13 at 14:16
1  
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$ –  amWhy Jun 19 '13 at 19:01

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$?
share|improve this answer
1  
Sorry, not homework. I have already done this but not with different cuantifiers, it just gets tricky sometimes. But im learning. –  Wyvern666 Jun 16 '13 at 0:16
1  
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 ..."? –  dfeuer Jun 16 '13 at 0:33

(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=\{\}$.

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

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.