Logic and Proof Methods

Every mathematical theorem — from a simple divisibility fact to the deepest result in analysis — rests on a rigorous logical argument. This post gives you the complete toolkit: the precise language of propositions and quantifiers, and the four proof strategies that between them cover every mathematical argument you will ever need to write.

5Connectives

∀ ∃Quantifiers

4Proof Methods

4Solved Examples

CSIR/GATE/JAMExam Relevance

⇒

Propositions, Connectives & Quantifiers

📐 Proposition

A proposition is a declarative sentence that is either true (T) or false (F), but not both. Examples: "$2$ is prime" (T); "$\sqrt{2}\in\mathbb{Q}$" (F).

📐 The Five Logical Connectives

Symbol	Name	Read as	False exactly when
$\neg p$	Negation	not $p$	$p$ is true
$p\wedge q$	Conjunction	$p$ and $q$	at least one false
$p\vee q$	Disjunction	$p$ or $q$	both false
$p\Rightarrow q$	Implication	if $p$ then $q$	$p$ true, $q$ false
$p\Leftrightarrow q$	Biconditional	$p$ iff $q$	different truth values

Key equivalences: $\;p\Rightarrow q\equiv\neg q\Rightarrow\neg p\equiv\neg p\vee q\;$ | $\;\neg(p\Rightarrow q)\equiv p\wedge\neg q$

📐 Quantifiers and Their Negations

Let $P(x)$ be a predicate with domain $D$.

Universal: $\forall x\in D,\;P(x)$ — true when $P(x)$ holds for every $x\in D$.

Existential: $\exists\,x\in D,\;P(x)$ — true when $P(x)$ holds for at least one $x\in D$.

Negation rules (De Morgan for quantifiers):

$$\neg\bigl(\forall x\in D,\;P(x)\bigr)\equiv\exists\,x\in D,\;\neg P(x) \qquad \neg\bigl(\exists\,x\in D,\;P(x)\bigr)\equiv\forall x\in D,\;\neg P(x)$$

📖 Reference: Apostol, T.M., Mathematical Analysis, 2nd ed., Ch. 1, §1.1–1.2. Also: Rudin, W., Principles of Mathematical Analysis, 3rd ed., Ch. 1, §1.1.

🔗 Prerequisites

Quantifiers range over sets, so set notation is assumed. Read first: Sets and Basic Notation — A Foundation for Mathematics.

💡

Intuition — The Four Proof Methods

A proof is a watertight argument — every step must follow logically from what came before. These four strategies cover every theorem you will ever need to prove.

→ Direct Proof

Assume $p$, deduce $q$. The most natural approach — use when the hypothesis leads straight to the conclusion.

⇔ Contrapositive

Prove $\neg q\Rightarrow\neg p$ instead. Logically identical to direct proof, but sometimes $\neg q$ is an easier starting point.

⚡ Contradiction

Assume $\neg S$, derive absurdity. Best for irrationality proofs, infinitude arguments, or "X cannot exist."

🔁 Induction

Prove $P(1)$, then $P(k)\Rightarrow P(k+1)$. The standard method whenever the statement is indexed by $\mathbb{N}$.

🇮🇳 हिंदी में संक्षेप

कथन (Proposition) वह वाक्य है जो सत्य या असत्य हो। पाँच तार्किक संयोजक: $\neg$ (Negation), $\wedge$ (Conjunction), $\vee$ (Disjunction), $\Rightarrow$ (Implication), $\Leftrightarrow$ (Biconditional)। परिमाणक: $\forall$ (सार्वत्रिक — सभी के लिए) और $\exists$ (अस्तित्व — कम से कम एक के लिए)। निषेध नियम: $\neg(\forall x\;P)\equiv\exists x\;\neg P$। चार Proof विधियाँ — Direct, Contrapositive, Contradiction और Mathematical Induction — मिलकर गणित का पूर्ण तर्क-आधार बनाती हैं।

✏️

Solved Examples

Very Easy | Truth Table

Show $(p\Rightarrow q)\wedge(q\Rightarrow p)\equiv p\Leftrightarrow q$ via truth table

$p$	$q$	$p\Rightarrow q$	$q\Rightarrow p$	$(p\Rightarrow q)\wedge(q\Rightarrow p)$	$p\Leftrightarrow q$
T	T	T	T	T	T
T	F	F	T	F	F
F	T	T	F	F	F
F	F	T	T	T	T

Columns 5 and 6 are identical, confirming $(p\Rightarrow q)\wedge(q\Rightarrow p)\equiv p\Leftrightarrow q$. $\blacksquare$

Easy–Medium | Negating Quantifiers

Negate the $\varepsilon$–$\delta$ definition of a limit

Write the precise negation of: "For every $\varepsilon>0$ there exists $\delta>0$ such that $\lvert x-a\rvert<\delta\Rightarrow\lvert f(x)-L\rvert<\varepsilon$."

Original: $\forall\varepsilon>0\;\;\exists\,\delta>0\;\;P(\varepsilon,\delta)$.

Step 1 — swap quantifiers (De Morgan twice):
$\exists\,\varepsilon>0\;\;\forall\delta>0\;\;\neg P(\varepsilon,\delta)$.

Step 2 — negate implication $(\neg(A\Rightarrow B)\equiv A\wedge\neg B)$:
$\neg P\equiv\lvert x-a\rvert<\delta\;\wedge\;\lvert f(x)-L\rvert\geq\varepsilon$.

Full negation: "There exists $\varepsilon>0$ such that for every $\delta>0$, there is an $x$ with $\lvert x-a\rvert<\delta$ and $\lvert f(x)-L\rvert\geq\varepsilon$." (This is exactly $\lim_{x\to a}f(x)\neq L$.) $\blacksquare$

Medium–Hard | Mathematical Induction

Prove $\displaystyle\sum_{k=1}^{n}k^2=\dfrac{n(n+1)(2n+1)}{6}$ for all $n\in\mathbb{N}$

Base case $(n=1)$: LHS $=1$. RHS $=\dfrac{1\cdot2\cdot3}{6}=1$. $\checkmark$

Inductive step: Assume $\displaystyle\sum_{k=1}^{m}k^2=\dfrac{m(m+1)(2m+1)}{6}$. Then:

$$\sum_{k=1}^{m+1}k^2=\frac{m(m+1)(2m+1)}{6}+(m+1)^2 =\frac{(m+1)\bigl[m(2m+1)+6(m+1)\bigr]}{6}$$

$$=\frac{(m+1)(2m^2+7m+6)}{6}=\frac{(m+1)(m+2)(2m+3)}{6}$$

which is the formula for $n=m+1$. By induction the result holds for all $n\in\mathbb{N}$. $\blacksquare$

Hard | CSIR NET / GATE / IIT JAM Level

Prove $6\mid n^3-n$ for all $n\in\mathbb{N}$ — two independent proofs

Method (i) — Induction.

Base $(n=1)$: $1-1=0=6\cdot0$. $\checkmark$

Step: Assume $6\mid k^3-k$. Then $(k+1)^3-(k+1)=(k^3-k)+3k(k+1)$. By hypothesis $6\mid(k^3-k)$. Since one of $k,k+1$ is even, $2\mid k(k+1)$, so $6\mid3k(k+1)$. Hence $6\mid(k+1)^3-(k+1)$. $\checkmark$

Method (ii) — Direct factorisation.

$n^3-n=(n-1)\,n\,(n+1)$ — the product of three consecutive integers. Any three consecutive integers contain a multiple of $2$ and a multiple of $3$, so the product is divisible by $\text{lcm}(2,3)=6$. $\blacksquare$

⚡

Quick Revision Cards

📊 A — Key Symbols & Equivalences

$p\Rightarrow q\equiv\neg q\Rightarrow\neg p\equiv\neg p\vee q$
$\neg(p\Rightarrow q)\equiv p\wedge\neg q$
$p\Leftrightarrow q\equiv(p\Rightarrow q)\wedge(q\Rightarrow p)$
$\neg(\forall x\;P)\equiv\exists x\;\neg P$
$\neg(\exists x\;P)\equiv\forall x\;\neg P$
$p\Rightarrow q$ vacuously true when $p$ is false

⚙️ B — Proof Method Chooser

Direct: hypothesis → conclusion naturally
Contrapositive: easier to assume $\neg q$
Contradiction: irrationality, "cannot exist"
Induction: statement indexed by $\mathbb{N}$
Contrapositive ≠ Converse!
Induction requires BOTH base case AND step

🎯 C — Exam Tips

🔵 CSIR NET: Negate $\varepsilon$-$\delta$ def: swap quantifiers then negate implication
🟢 GATE: Always label "Base case" and "Inductive step" explicitly
🟠 IIT JAM: Contrapositive ≠ Converse — classic MCQ trap
🔴 B.Sc. Raj.: Write inductive hypothesis in full before the step

⚠️

Common Mistakes

❌ Errors to Avoid

Error 1: Contrapositive vs. Converse

Wrong: "$p\Rightarrow q\equiv q\Rightarrow p$." | Correct: The contrapositive $\neg q\Rightarrow\neg p$ is logically equivalent; the converse $q\Rightarrow p$ is NOT.

Error 2: Wrong negation of implication

Wrong: $\neg(p\Rightarrow q)\equiv\neg p\Rightarrow\neg q$. | Correct: $\neg(p\Rightarrow q)\equiv p\wedge\neg q$. Negating an implication gives a conjunction, never another implication.

Error 3: Omitting the base case in induction

Wrong: Proving only the inductive step. | Correct: Both parts are mandatory. Without the base case the chain never starts. Classic failure: the "proof" that all horses are the same colour breaks at $n=2$.

Error 4: Wrong negation of quantifiers

Wrong: $\neg(\forall x\;P(x))\equiv\forall x\;\neg P(x)$. | Correct: $\neg(\forall x\;P(x))\equiv\exists\,x\;\neg P(x)$. The quantifier flips AND the predicate is negated — both changes are required.

🌐

Real-World Applications

🖥️

Program Verification

Hoare logic formalises $\{P\}\;C\;\{Q\}$ — a direct implementation of implication. Loop invariant correctness proofs use mathematical induction.

🔒

Cryptography (RSA)

RSA decryption correctness uses contradiction and the Fundamental Theorem of Arithmetic. Every security proof in cryptography is a rigorous logical argument.

🤖

Automated Theorem Proving

Lean, Coq, and Isabelle encode exactly these connectives and quantifiers. Every proof step must cite an axiom or a previously verified lemma.

🗄️

Database Query Optimisation

Rewriting SQL NOT EXISTS as FOR ALL NOT is De Morgan's law for quantifiers applied algorithmically to relational algebra.

📋

Summary Table & Key Result

Concept	Statement / Formula	Condition	Reference
Implication	$p\Rightarrow q\equiv\neg p\vee q$	Any $p,q$	Apostol Ch. 1
Contrapositive	$p\Rightarrow q\equiv\neg q\Rightarrow\neg p$	Tautology	Apostol Ch. 1
Neg. Quantifier	$\neg(\forall x\;P)\equiv\exists\,x\;\neg P$	Any domain	Standard
Induction	Base $+$ Step $\Rightarrow\forall n\in\mathbb{N}$	$P(n)$ well-defined	Apostol §1.2
Contradiction	Assume $\neg S$, derive $r\wedge\neg r$	Any $S$	Standard
Sum of squares	$\sum_{k=1}^{n}k^2=\dfrac{n(n+1)(2n+1)}{6}$	$n\in\mathbb{N}$	By induction

The Four-Method Toolkit:

$$\text{Direct}\quad\big|\quad\text{Contrapositive}\quad\big|\quad\text{Contradiction}\quad\big|\quad\text{Induction}$$

Every theorem in analysis, algebra, and topology is proved by one — or a combination — of these four strategies.

🔗

Cross-References & Related Posts

📚 Prerequisites & Next Steps

← Prerequisite: Sets and Basic Notation — A Foundation for Mathematics — quantifiers range over sets; De Morgan's laws for sets and for quantifiers are parallel results built on the same logical foundation.

→ Next Topic: Relations and Functions — formally defined using set-builder notation and the logical quantifiers developed here.

📖 Further Reading: Apostol, Ch. 1, §§1.1–1.4; Rudin, Ch. 1, §§1.1–1.5; Bartle & Sherbert, Ch. 1 & Appendix.

📖 Download Academic PDF Notes Logic and Proof Methods — Fractal Frontier Maths

Logic and Proof Methods — The Language of Mathematics