1
$\begingroup$

I am trying to rewrite the following propositions so that the negation acts on 𝑃 directly.

  1. ¬∃𝑥 ∃𝑦 𝑃(𝑥, 𝑦)
  2. ∃𝑥 ¬∀𝑦 ∃𝑧 ∀𝑤 𝑃 (𝑥, 𝑦, 𝑧, w)

Told by my prof that:

Whenever there is negation of a quantification, the negation is "pushed" through the quantifier to change the quantifier (from ∃ to ∀ or from ∀ to ∃) and then negates what the quantifier binds This is repeated until all quantifiers have been alternated.

From what I understand you only negate the quantifier that the negation is directly in front of such as:

  1. ∀𝑥 ∃𝑦 𝑃(𝑥, 𝑦)
  2. ∃𝑥 ∃𝑦 ∃𝑧 ∀𝑤 𝑃 (𝑥, 𝑦, 𝑧, w)

Is this correct or is the negation sign applied to every quantifier after as well since there is no negation on the P, like it asked.

My other solution would then be:

  1. ∀𝑥 ∀𝑦 ¬𝑃(𝑥, 𝑦)
  2. ∃𝑥 ∃𝑦 ∀𝑧 ∃𝑤 ¬𝑃 (𝑥, 𝑦, 𝑧, w)

Which solution, if either, are correct and why?

$\endgroup$

1 Answer 1

2
$\begingroup$

You have to change the negated quantifier and negate what it was quantifying. So from $\lnot \exists x \exists y P(x,y)$ you would go to $\forall x \lnot \exists y P(x,y)$ and then to $\forall x \forall y \lnot P(x,y)$

$\endgroup$
2
  • $\begingroup$ So would ∃𝑥 ∃𝑦 ∀𝑧 ∃𝑤 ¬ð‘ƒ (𝑥, 𝑦, 𝑧, w) be correct as well? $\endgroup$ Feb 8, 2018 at 1:07
  • $\begingroup$ Yes, it would... $\endgroup$ Feb 8, 2018 at 1:13

You must log in to answer this question.

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