Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 37 · Getting Started

Logic and Proof Techniques

Learn statements, quantifiers, negation, contrapositive, contradiction and direct proof, the logical toolkit every real analysis proof relies on.

Every definition in analysis is a sentence full of "for every" and "there exists". To read such sentences, negate them, and prove them, you need a small amount of logic. This lesson gives you that toolkit with plenty of worked examples. Master it now and the epsilon proofs later will feel like routine steps instead of magic.

Statements and connectives

A statement is a sentence that is either true or false. From statements P and Q we build:

Symbol Read as True when
¬P not P P is false
P ∧ Q P and Q both are true
P ∨ Q P or Q at least one is true
P ⇒ Q if P then Q not (P true and Q false)

The implication P ⇒ Q is false in exactly one case: P true and Q false. If P is false the implication is true ("vacuously"). For example, "if 2 = 3 then the moon is cheese" is a true statement.

Python Truth tables for implication

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The third column and the fourth column always agree: P ⇒ Q is equivalent to its contrapositive ¬Q ⇒ ¬P. The last column (the converse) differs, so an implication and its converse are different claims.

Quantifiers

  • ∀x ∈ S, P(x) means "for every x in S, P holds".
  • ∃x ∈ S, P(x) means "there is at least one x in S with P".

Order matters. Over the real numbers:

  • ∀x ∃y, y > x is true: given any x, take y = x + 1.
  • ∃y ∀x, y > x is false: no real number is bigger than all real numbers.

Negating quantifiers

To negate, swap ∀ with ∃ and negate the inside:

  • ¬(∀x, P(x)) is ∃x, ¬P(x).
  • ¬(∃x, P(x)) is ∀x, ¬P(x).

Example. The statement "every sequence term is below 5" is ∀n, a_n < 5. Its negation is ∃n, a_n ≥ 5: some term is at least 5. Note that the negation of < is ≥, not >.

Later you will negate "for every ε > 0 there is N such that for all n ≥ N, |a_n - L| < ε". Following the rule step by step gives: "there is ε > 0 such that for every N there is n ≥ N with |a_n - L| ≥ ε". This is how you prove a sequence does not converge to L.

Python Test a quantified claim on finite data

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line is true here only because we restricted x to a finite range. Over all real numbers it is false. That is a reminder that finite experiments can mislead.

Proof techniques

Direct proof

Assume P, apply definitions and known facts, and arrive at Q.

Claim. If n is even, then n² is even.

Proof. Let n = 2k for an integer k. Then n² = 4k² = 2(2k²), which is twice an integer. ∎

Contrapositive

To prove P ⇒ Q, prove ¬Q ⇒ ¬P instead.

Claim. If n² is even, then n is even.

Proof. Suppose n is odd, n = 2k + 1. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1 is odd. So if n is not even, n² is not even. ∎

Contradiction

Assume the claim is false and derive an impossibility.

Claim. √2 is irrational.

Proof. Suppose √2 = p/q in lowest terms with integers p, q, q ≠ 0. Squaring gives p² = 2q², so p² is even, hence p is even (previous claim), say p = 2m. Then 4m² = 2q², so q² = 2m² and q is even. Both p and q are even, contradicting lowest terms. ∎

Proving "there exists" and "for all"

  • To prove ∃x, P(x): exhibit one x (or argue that one must exist).
  • To prove ∀x, P(x): let x be arbitrary, and prove P(x) using only what you know about every x.
  • To disprove ∀x, P(x): give a single counterexample.

Checking examples never proves a "for all" statement. One example is enough only to prove "there exists" or to disprove "for all".

Check your understanding

Quick check · 3 questions

of 3 answered You scored / 3 · perfect!

  1. 1. Which statement is equivalent to P ⇒ Q?

    An implication is equivalent to its contrapositive. The converse and the inverse are different statements.
  2. 2. What is the negation of: for every x there is y with y > x?

    Swap each quantifier and negate the inner claim: ∃x ∀y, y ≤ x.
  3. 3. How do you disprove the claim 'every prime is odd'?

    A single counterexample disproves a universal statement, and 2 is an even prime.

Summary

  • An implication is equivalent to its contrapositive, not to its converse.
  • Negate a quantified statement by swapping ∀ and ∃ and negating the inside.
  • Order of quantifiers matters: ∀x ∃y is different from ∃y ∀x.
  • Standard proof styles are direct, contrapositive and contradiction.
  • Examples never prove a universal claim; counterexamples disprove one.

Next: Sets, Functions and Countability