Continued from a question I asked here, since I believed this question deserves its own thread.
When taking the contrapositive, I was taught to negate the quantifiers as well. For example, if we have the statement $$\forall x \in S, \exists y \in S, P(x) \implies P(y),$$ where $P$ is a statement over the domain $S$. Taking the contrapositive of the above statement would give us:
$$\exists y \in S, \forall y \in S, \neg P(y) \implies \neg P(x),$$ correct? The logic behind this makes sense to me. Consider the simple example:
If every car has wheels, then there is a car with at least one wheel.
The contrapositive of this would be:
If there is a car which does not have at least one wheel, then not every car has wheels.
Symbolically, we could say that the original statement is:
$\forall c, \exists d, c \implies d$, and the contrapositive as $\exists c, \forall d, \neg d \implies \neg c.$
However, recently I've found out that this is not always the case. If we have something along the lines of:
If $a$ is a real number, such that $a < b$ for every positive real number $b$, then $a = 0$.
Expressing this symbolically, I would think we have that $$\exists a \in \mathbb{R}, \forall b \in \mathbb{R}^+, a < b \implies a = 0.$$
However, when we take the contrapositive of this statement, we get $$\exists a \in \mathbb{R}, \forall b \in \mathbb{R}^+, a \neq 0 \implies a \ge b,$$ and not $$\forall a \in \mathbb{R}, \exists b \in \mathbb{R}^+, a \neq 0 \implies a \ge b.$$
How can I know when to negate quantifiers, and when not to?
Best Answer
You aren't considering the quantifiers' scope, partly due to your insertion of commas after every quantifier, which is obscuring not just your analysis but also your intended meaning.
Some authors insert a comma/colon/period after a quantifier to delimit that its scope extends as far right as possible; others use commas/colons/periods, like in $(\exists x,P(x)),$ with no particular meaning; others import from natural language commas as punctuation and the colons as abbreviation of ‘such that’; these usages conflict with one another; How to grammatically formalise mathematical statements?
Reading your question, I had to frequently pause to guess whether you mean something like $$∀x \;(Px\implies Q)$$ or something like $$(∀x \:Px)\implies Q;$$ they aren't equivalent formulae!
$$\forall x {\in} S \;\exists y {\in} S\; (P(x) \implies P(y)).$$ Since the goal when taking contrapositive is for the old and new sentences to be logically equivalent, and the conditional here conveniently contains no quantifiers, the contrapositive is simply $$\forall x {\in} S \;\exists y {\in} S\; (¬P(y) \implies ¬P(z)).$$
$$(∀x{∈}C\:Wx)⟹∃y{∈}C\:Wy.$$ Here, each side of the conditional has a quantifier, so they need to be negated, and the contrapositive is $$(∀y{∈}C\:¬Wy)⟹∃x{∈}C\:¬Wx.$$ If no car has a wheel, then some car has no wheel.
$$\forall a{\in}\mathbb R\;\Big((\forall b{\in}\mathbb R^+\;a<b)\implies a=0\Big).\tag1$$ Here, there's only one quantifier to negate, and the contrapositive is $$\forall a{\in}\mathbb R\;\Big(a\ne0\implies \exists b{\in}\mathbb R^+\;a\ge b \Big).\tag2$$
Note that $(1)$ and $(2)$ are, respectively, logically equivalent to: $$\forall a{\in}\mathbb R\;\exists b{\in}\mathbb R^+\;\Big(a<b\implies a=0\Big);\tag1$$$$\forall a{\in}\mathbb R\;\exists b{\in}\mathbb R^+\;\Big(a\ne0\implies a\ge b \Big).\tag2$$ So, had we initially pulled out those quantifiers, the contrapositive work itself would, like in case #1 above, have required no quantifier negation.