Logic and Proof Methods — The Language of Mathematics
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.
Propositions, Connectives & Quantifiers
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).
| 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$
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.
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
| $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$
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$
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$
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
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.
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.
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$.
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
← 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.
How did you find this post?
Tap a reaction — counts are saved permanently on our server.
Preparing for BSc, MSc, CSIR NET, GATE or IIT JAM?
Practise what you just read and learn it in Hindi, step by step.
Found this helpful?
This article is free and will always remain so. If it helped you understand a concept or prepare for your exam, a small token of appreciation keeps this resource going for the next student.
Have a question, doubt, or thought about this post? Choose how you want to join the discussion below.
💬 Comment on Telegram — No account needed