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

← 1.1 Next: 1.3 →