(related to Part: Methods of Mathematical Proving)
When proving mathematical theorems, one has quite often to negate different kind of propositions. The logic of negating propositions is not hard to follow and depends on the type of proposition to negate. The following list gives some examples of propositions types and provides rules to follow when negating them.
A conditional proposition is a proposition of the type $P\Rightarrow Q$, where $P,Q$ are themselves propositions.
Example 1: $P:=$"It is raining", $Q:=$"The roads are wet.", $P\Rightarrow Q:$"If it is raining, then the roads are wet."
Example 2: $P:=$"$a$ is even", $Q:=$"$a\cdot b$ is even for all $b\in\mathbb N$", $P\Rightarrow Q:$"If $a$ is even, then $a\cdot b$ is even for all $b\in\mathbb N$."
The correct negation of such statements is proven here and follows these steps:
Negated example 1: $P:=$"It is raining", $\neg Q:=$"The roads are dry.", $\neg (P\Rightarrow Q)=(P\wedge \neg Q):$"It is raining and the roads are dry."
Negated example 2: $P:=$"$a$ is even", $\neg Q:=$"there exists a $b\in\mathbb N$, for which $a\cdot b$ is odd"^{1}, $\neg (P\Rightarrow Q)=(P\wedge \neg Q):$"$a$ is even and there exists a $b\in\mathbb N$, for which $a\cdot b$ is odd."
Many statements use the existential and universal quantifiers $\exists$ ("there exists") and $\forall$ ("for all"). For instance, consider the following examples:
Example 3: $P:=$"All cars have their own maximal velocity, but you can find a suitable trailer which can be pulled by them."
Example 4: $P:=$"There exists a real number $y$ such that for all $\epsilon > 0$ there exists $\delta > 0$ such that for every $x$ with $0 < |x-a| < \delta$ implies $|f(x)-y| < \epsilon.$"
The correct negation of such statements follows these rules:
Negated example 3: $\neg P:=$"There is at least one car with a maximal velocity, such that, whatever trailer you take, you cannot pull it by the car."
Negated example 4: $\neg P:=$"For all real numbers $y$ there exists $\epsilon > 0$ such that for all $\delta > 0$ there exists $x$ with $0 < |x-a| < \delta$ and $|f(x)-y| \ge \epsilon.$"[^2]
Note the negation of the implication "$0 < |x-a| < \delta$ implies $|f(x)-y| \ge \epsilon$", as explained in examples 1 and 2. ↩