Double Negation Introduction
For an arbitrary formula \(A\), the following rule of inference holds: \[
A\ \models\ \lnot\lnot A
\]That is, under every interpretation in which \(A\) is true, \(\lnot\lnot A\) is also true. This rule of inference is called double negation introduction.
A\ \models\ \lnot\lnot A
\]holds.
P\left( x\right) \ \models\ \lnot\lnot P\left( x\right) .
\]
\begin{align*}
& \text{Every even integer is divisible by }2.\\
& \text{Therefore, it is not the case that any even integer is not divisible by }2.
\end{align*}Let the domain \(X\) of the variable \(x\) be the set of all even integers, and define the propositional function \[
P\left( x\right) :x\text{ is divisible by }2.
\]Then the preceding inference can be formalized as
\[
\forall x\in X:P\left( x\right) \ \therefore\ \forall x\in X:\lnot\lnot P\left( x\right) .
\]Applying universal elimination to the premise gives
\[
P\left( c\right) .
\]Applying double negation introduction gives
\[
\lnot\lnot P\left( c\right) .
\]Applying universal introduction then gives
\[
\forall x\in X:\lnot\lnot P\left( x\right) .
\]Therefore, the inference is valid.
\lnot A\ \therefore\ A\vee B\rightarrow\lnot\lnot B.
\]By implication introduction, instead of proving the validity of the preceding inference directly, it is sufficient to prove the validity of
\[
\lnot A,\ A\vee B\ \therefore\ \lnot\lnot B.
\]Suppose that both \(\lnot A\) and \(A\vee B\) are true. If \(\lnot A\) is true, then \(A\) is false. Since \(A\vee B\) is true, at least one of \(A\) and \(B\) must be true. Therefore, \(B\) is true. By double negation introduction, \(\lnot\lnot B\) is true. Hence, the preceding inference is valid. That is,
\[
\lnot A\ \models\ A\vee B\rightarrow\lnot\lnot B
\]holds.
Generalization of Double Negation Introduction
By double negation introduction, for any formula \(A\), \[
A\ \models\ \lnot\lnot A
\]holds. If we take \(\lnot A\) in place of \(A\), then \[
\lnot A\ \models\ \lnot\lnot\lnot A
\]is obtained. The same argument applies repeatedly.
\(A\) and an arbitrary number \(n\in\mathbb{N} \), and denote the \(n\)-fold negation of \(A\) by \[
\lnot^{n}A.
\]Then the following rules of inference hold:
\[
\left\{
\begin{array}
[c]{cc}\lnot A\ \models\ \lnot^{n}A & \left( if\ n\text{ is odd}\right) \\
A\ \models\ \lnot^{n}A & \left( if\ n\text{ is even}\right) .
\end{array}
\right.
\]
\lnot A\ \therefore\ \lnot\left( \lnot\left( A\vee B\right) \right)
\rightarrow\lnot\lnot\lnot\lnot B.
\]By implication introduction, instead of proving the validity of the preceding inference directly, it is sufficient to prove the validity of
\[
\lnot A,\ \lnot\left( \lnot\left( A\vee B\right) \right) \ \therefore
\ \lnot\lnot\lnot\lnot B.
\]Suppose that both \(\lnot A\) and \(\lnot\left( \lnot\left( A\vee B\right) \right) \) are true. By De Morgan’s law, \begin{align*}
\lnot\left( \lnot\left( A\vee B\right) \right) & \Leftrightarrow
\lnot\left( \lnot A\wedge\lnot B\right) \\
& \Leftrightarrow\lnot\lnot A\vee\lnot\lnot B
\end{align*}is an equivalent transformation. Hence, if \(\lnot\left( \lnot\left( A\vee B\right) \right) \) is true, then at least one of \(\lnot\lnot A\) and \(\lnot\lnot B\) is true. However, if \(\lnot A\) is true, then its negation \(\lnot\lnot A\) is false. Therefore, \(\lnot\lnot B\) is true, and by double negation introduction, \(\lnot\lnot\lnot\lnot B\) is true. Thus, the original inference is valid. That is, \[
\lnot A\ \models\ \lnot\left( \lnot\left( A\vee B\right) \right)
\rightarrow\lnot\lnot\lnot\lnot B
\]holds.
Exercises
A\ \therefore\ \lnot\lnot\left( A\wedge A\right) .
\]
A\rightarrow B,\ A\ \therefore\ \lnot\lnot B.
\]
A,\ B\rightarrow C\ \therefore\ \lnot\lnot A\wedge\left( B\rightarrow C\right) .
\]
A\rightarrow B,\ B\rightarrow C,\ A\ \therefore\ \lnot\lnot C
\]
A\rightarrow B\ \models\ A\rightarrow\lnot\lnot B
\]
\forall x\in X:P\left( x\right) \ \therefore\ \forall x\in X:\lnot\lnot P\left( x\right) .
\]
\exists x\in X:P\left( x\right) \ \therefore\ \exists x\in X:\lnot\lnot P\left( x\right) .
\]
\lnot A\ \therefore\ \lnot^{9}A
\]
A,\ B\ \therefore\ \lnot\lnot\left( A\vee C\right) \wedge\lnot\lnot\left(
B\vee D\right) .
\]
\lnot\lnot A\ \therefore\ \lnot\lnot B.
\]
& \left( a\right) \quad\forall x\in X:P\left( x\right) \ \therefore
\ \lnot\lnot\left( \forall x\in X:P\left( x\right) \right) \\
& \left( b\right) \quad\forall x\in X:P\left( x\right) \ \therefore
\ \forall x\in X:\lnot\lnot P\left( x\right) .
\end{align*}
