Double Negation Introduction in Predicate Logic

Double negation introduction also holds in predicate logic. That is, from any formula \(A\), we may derive its double negation \(\lnot\lnot A\).

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.

Proposition (Double Negation Introduction)
For any formula \(A\), \[
A\ \models\ \lnot\lnot A
\]holds.
Proof

Members-Only Content
【Log In】【Sign Up】

Example (Double Negation Introduction)
For an arbitrary propositional function \(P\left( x\right) \), double negation introduction gives \[
P\left( x\right) \ \models\ \lnot\lnot P\left( x\right) .
\]
Example (Double Negation Introduction)
Consider the following inference:
\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.
Example (Double Negation Introduction)
Consider the following inference concerning formulas \(A,B\): \[
\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.

Proposition (Generalization of Double Negation Introduction)
Choose an arbitrary formula
\(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.
\]
Proof

Members-Only Content
【Log In】【Sign Up】

Example (Double Negation Introduction)
Consider the following inference concerning formulas \(A,B\): \[
\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

Problem (Validity of Inference)
Show that the following inference concerning formula \(A\) is valid: \[
A\ \therefore\ \lnot\lnot\left( A\wedge A\right) .
\]
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Validity of Inference)
Show that the following inference concerning formulas \(A,B\) is valid: \[
A\rightarrow B,\ A\ \therefore\ \lnot\lnot B.
\]
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Validity of Inference)
Show that the following inference concerning formulas \(A,B,C\) is valid: \[
A,\ B\rightarrow C\ \therefore\ \lnot\lnot A\wedge\left( B\rightarrow C\right) .
\]
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Double Negation Introduction and Implication Elimination)
For formulas \(A,B,C\), show that the following inference is valid: \[
A\rightarrow B,\ B\rightarrow C,\ A\ \therefore\ \lnot\lnot C
\]
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Double Negation Introduction and Implication Introduction)
For formulas \(A,B,C\), show that the following inference is valid: \[
A\rightarrow B\ \models\ A\rightarrow\lnot\lnot B
\]
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Double Negation Introduction and Universal Quantification)
Let the domain of the variable \(x\) be \(X\). Show that the following inference is valid: \[
\forall x\in X:P\left( x\right) \ \therefore\ \forall x\in X:\lnot\lnot P\left( x\right) .
\]
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Double Negation Introduction and Existential Quantification)
Let the domain of the variable \(x\) be \(X\). Show that the following inference is valid: \[
\exists x\in X:P\left( x\right) \ \therefore\ \exists x\in X:\lnot\lnot P\left( x\right) .
\]
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Multiple Negations)
For formula \(A\), show that the following inference is valid: \[
\lnot A\ \therefore\ \lnot^{9}A
\]
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Double Negation Introduction, Disjunction Introduction, and Conjunction Introduction)
For formulas \(A,B,C,D\), show that the following inference is valid: \[
A,\ B\ \therefore\ \lnot\lnot\left( A\vee C\right) \wedge\lnot\lnot\left(
B\vee D\right) .
\]
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Validity of Inference)
For formulas \(A,B\), determine whether the following inference is valid: \[
\lnot\lnot A\ \therefore\ \lnot\lnot B.
\]
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Quantifiers and Double Negation)
Let the domain of the variable \(x\) be \(X\). Show that each of the following two inferences is valid: \begin{align*}
& \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*}

View Solution

Members-Only Content
【Log In】【Sign Up】

Discussion

To ask questions about this material or discuss it with other learners, you need to register as a member and log in.

  • Members can post comments
  • You can reply to other users
  • You can search and view past discussions
  • You can edit your posts later

At WIIS, we believe that all users are equal as learners, regardless of age, gender, educational background, occupation, or social status.

This is not a place to compete over knowledge, but a space to deepen understanding while respecting one another’s ideas. Questions and opinions are welcome, and you are also encouraged to ask openly about anything you do not understand.

To help maintain a constructive and welcoming learning environment, please review the guidelines before posting.

If you find a typo, broken link, or error in the content, please let us know using the form below.

User Posts Related to This Lesson

Table of Contents

MEMBERSHIP

Take your learning further.

Join WIIS to access
members-only content,
downloadable PDF textbooks,
AI Tutor, forums,
and other member benefits.

MEMBERS-ONLY CONTENT

Access exclusive materials designed for deeper learning.

PDF TEXTBOOKS

Download textbooks and study them anywhere.

AI Tutor

Use AI-powered support to deepen your understanding.

COMMUNITY FEATURES

Connect with other learners and join discussions and research.

ログイン

アカウントにログインして、学習ノートやブックマーク、投稿記事などを管理できます。

Recently Viewed Pages