Phase 1 - Lesson 1.2

Logic, Quantifiers, and Necessary vs Sufficient Conditions

How to read and write mathematical statements without ambiguity: connectives, quantifier order, and the difference between ‘if’ and ‘only if’.

⏱ 45 min● Beginner🔗 Prereqs: 1.1

↖ Phase 1 hub

Builds on: 1.1 gave sets and functions; logic is how we make and negate claims about them.
Leads to: Epsilon-delta limits (1.5, Phase 2) and measure theory (Phase 6) are built from nested quantifiers you must parse precisely.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Translate English mathematical statements into symbolic logic using connectives and quantifiers.
Negate compound and quantified statements mechanically, swapping ∀ and ∃.
Distinguish necessary from sufficient conditions and match them to the direction of an implication.
Explain why a statement and its contrapositive are equivalent while a converse is not.

Key Vocabulary

Proposition: A statement that is definitely true or false (not both).

Implication: ‘P ⇒ Q’ (if P then Q); false only when P is true and Q is false.

Converse / contrapositive: Of P⇒Q: converse is Q⇒P; contrapositive is ¬Q⇒¬P (logically equivalent to the original).

Universal / existential quantifier: ∀ (for all) and ∃ (there exists); binds a variable over a domain.

Necessary condition: Q is necessary for P when P ⇒ Q: P cannot hold unless Q does.

Sufficient condition: P is sufficient for Q when P ⇒ Q: P alone guarantees Q.

Connectives and the truth of an implication

A proposition is a statement with a definite truth value. We combine propositions with ∧ (and), ∨ (or), ¬ (not), ⇒ (implies) and ⇔ (if and only if). The one that trips people up is implication:

\[P\Rightarrow Q \ \text{is false in exactly one case: } P\ \text{true and }Q\ \text{false.}\] (1.2)

So ‘if it rains I bring an umbrella’ is only broken on a rainy day with no umbrella; a dry day never breaks the promise. This ‘vacuously true’ behavior is not a quirk - it is what makes proofs by cases and by contradiction work.

Contrapositive vs converse

The contrapositive \(\neg Q\Rightarrow\neg P\) is logically identical to \(P\Rightarrow Q\) - proving either proves both. The converse \(Q\Rightarrow P\) is a genuinely different claim. Confusing them is the single most common logical error.

Statement	Symbol	Equivalent to original?
Original	P ⇒ Q	-
Converse	Q ⇒ P	No
Contrapositive	¬Q ⇒ ¬P	Yes
Inverse	¬P ⇒ ¬Q	No (it equals the converse)

Quantifiers and the danger of order

Nested quantifiers do not commute. Compare over the reals: \(\forall x\,\exists y\,(y\gt x)\) (true: pick \(y=x+1\)) versus \(\exists y\,\forall x\,(y\gt x)\) (false: no single \(y\) beats every \(x\)). To negate, flip every quantifier and negate the core:

\[\neg\big(\forall x\,\exists y\,P(x,y)\big)=\exists x\,\forall y\,\neg P(x,y)\] (1.3)

Necessary vs sufficient

If \(P\Rightarrow Q\), then \(P\) is sufficient for \(Q\) (having P is enough) and \(Q\) is necessary for \(P\) (without Q you cannot have P). They coincide only when \(P\Leftrightarrow Q\).

Worked Example - Differentiable vs continuous

Theorem: differentiable \(\Rightarrow\) continuous. So differentiability is sufficient for continuity.

Equivalently, continuity is necessary for differentiability: a function with a jump cannot be differentiable there.

The converse fails: \(f(x)=|x|\) is continuous at 0 but not differentiable. Necessary does not imply sufficient.

Contrapositive restatement: ‘not continuous \(\Rightarrow\) not differentiable’ - a handy quick test.

Interactive: predict the negation

Predict first: The definition of a bounded sequence is ‘∃M ∀n, |a_n| ≤ M’. What is the precise negation (i.e. what it means to be UNbounded)?

Common Mistakes to Avoid

Proving the converse Q⇒P when the task asked for P⇒Q. Always check which direction you owe.
Reading ‘P is necessary for Q’ as P⇒Q. It is the reverse: Q⇒P.
Swapping the order of ∀ and ∃ and assuming the meaning is unchanged.
Negating ‘P and Q’ as ‘not P and not Q’ instead of the correct ‘not P or not Q’ (De Morgan).

Quant Practitioner Tips

Rewrite every ‘only if’ sentence as an explicit implication before working with it.
To negate a definition, walk left to right flipping ∀↔∃ and negating the inequality at the end.
When a direct proof stalls, try the contrapositive - it is free and often easier.
In finance models, ‘no-arbitrage’ theorems are chains of necessary/sufficient conditions; parsing them is exactly this skill.

Knowledge Check

Q1 Medium

‘A function is integrable only if it is bounded (on a closed interval).’ This tells us:

boundedness is sufficient for integrability

boundedness is necessary for integrability

integrability is sufficient for boundedness

boundedness and integrability are equivalent

Q2 Easy

The contrapositive of ‘if n² is even then n is even’ is:

if n is even then n² is even

if n is odd then n² is odd

if n² is odd then n is odd

if n is not even then n² is even

Q3 Hard

Negate: ‘∀ε>0 ∃δ>0 such that P(ε,δ)’.

∀ε>0 ∀δ>0, ¬P

∃ε>0 ∀δ>0, ¬P

∃ε>0 ∃δ>0, ¬P

∀ε>0 ∃δ>0, ¬P

Practical Exercise

Consider the claim: ‘For every real x, if \(x^2\lt x\) then \(0\lt x\lt 1\).’ (a) State the contrapositive. (b) Prove the claim by proving the contrapositive. (c) Is the converse true?

▶ Show full solution

(a) Contrapositive: if \(x\le 0\) or \(x\ge 1\), then \(x^2\ge x\).

(b) If \(x\le 0\), then \(x^2\ge 0\ge x\). If \(x\ge 1\), then multiplying \(x\ge 1\) by the positive number \(x\) gives \(x^2\ge x\). Either way \(x^2\ge x\), so the contrapositive holds, hence so does the original.

(c) Converse: ‘if \(0\lt x\lt 1\) then \(x^2\lt x\)’. True - for such \(x\), multiplying \(x\lt 1\) by \(x\gt 0\) gives \(x^2\lt x\). Here converse and original are both true, so the statement is in fact an equivalence.

After the reveal, answer for yourself: Notice how the contrapositive turned a strict-inequality hypothesis into an easier case split. That reframing is the whole point of the technique.

Lesson Summary

Mathematical writing is precise because its logic is: an implication P⇒Q fails only when P is true and Q false, its contrapositive ¬Q⇒¬P is equivalent while its converse is not, and quantifiers must not be reordered. ‘Sufficient’ matches the arrow’s tail and ‘necessary’ its head. Negating a statement is mechanical: flip every quantifier and negate the core.

Error Log Checklist

Which direction of implication does the problem actually ask for?
Did I read ‘necessary’/‘sufficient’ in the correct arrow direction?
When negating, did I flip ∀↔∃ everywhere?
Did I apply De Morgan correctly to ‘and’/‘or’?

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers

Q: Why are a statement and its contrapositive equivalent but a statement and its converse are not?
A: P⇒Q and ¬Q⇒¬P have identical truth tables, so proving one proves the other; the converse Q⇒P can differ in truth value, as ‘continuous does not imply differentiable’ shows.

Q: Give the rule for negating ∀x ∃y P(x,y).
A: It becomes ∃x ∀y ¬P(x,y): flip each quantifier and negate the inner predicate.

Q: If P is sufficient for Q, which of P, Q is necessary for the other?
A: P sufficient for Q means P⇒Q, so Q is necessary for P: P cannot occur without Q.

Completion Checklist

I can explain the core ideas in my own words
I worked the derivations/examples by hand
I completed the interactive workbench(es)
I passed the knowledge check

Confidence / mastery rating

Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

Calculus, Vol. I (Tom Apostol, 2nd ed., 1967) foundational - Vol. I, Ch. 1-3 rigor - Mathematical rigor, implication and quantified statements underlying the limit definitions.
A Mind for Numbers (Barbara Oakley, 2014) foundational - chunking & understanding - Reframing hard logical statements and using contrast (necessary vs sufficient) to build durable understanding.

← 1.1 Next: 1.3 →