Introduction to Analysis · Chapter 02

Logic and proofs

Statements, connectives and quantifiers, then the four things you can do with them: prove directly, negate, argue indirectly, and climb the natural numbers one step at a time.

P \Rightarrow Q

\forall x \in X

\exists x \in X

P \land Q

\neg P

P \lor Q

P (n) \Rightarrow P (n + 1)

\neg Q \Rightarrow \neg P

Lessons

Build the foundation

01Statements and truthA mathematical statement is a sentence that is either true or false, with nothing in between. Questions, instructions and opinions are not statements. Neither is a sentence holding a variable nobody has fixed: it has no truth value until the variable is given a value.Read lesson →
02And, or, notThree words build every compound statement: and, or, not. You already met them as set operations. Intersection is "and", union is "or", and complement is "not". The one word that behaves differently from everyday speech is "or", which in mathematics never excludes the case where both parts hold.Read lesson →
03ImplicationAn implication is a promise: if the first statement holds, the second one does too. A promise is broken only when its condition is met and its conclusion fails. When the condition never arises, the promise was never tested, and mathematics counts an untested promise as kept.Read lesson →
04QuantifiersAn open sentence becomes a statement in a second way: instead of fixing the variable, say how many values satisfy it. "For every" claims the sentence never fails; "there exists" claims it succeeds at least once. When two quantifiers appear together their order decides the meaning, and swapping them usually changes the claim entirely.Read lesson →
05Negating quantified statementsEvery definition in the rest of this course is a chain of quantifiers, and half the work is saying precisely what it would mean for one to fail. Denying such a statement is mechanical rather than creative: walk along the chain from the outside in, turn each "for every" into "there is" and each "there is" into "for every", and finally deny the sentence at the end. Nothing is reordered, and nothing is dropped.

Read lesson →

06Direct proof and counterexampleTo prove that something always happens, assume the hypothesis for an unnamed case and reason to the conclusion using only what the assumption gives. Because the case was never named, the argument covers all of them at once. To disprove such a claim you need only one case where it fails.Read lesson →

07Contradiction and contrapositiveSome claims resist a direct attack, and two indirect routes are available. A proof by contradiction assumes the claim is false and derives an impossibility, so the assumption cannot stand. A proof by contrapositive assumes the conclusion fails and derives that the hypothesis fails too, which says the same thing as the original.Read lesson →

08Mathematical inductionA claim about every natural number cannot be checked case by case, because the cases never end. Induction replaces the endless checking with two finite jobs: show the claim at the first number, and show that whenever it holds at one number it holds at the next. Those two together reach every number, because any particular number is only finitely many steps from the start.Read lesson →

09Chapter practiceThis lesson mixes everything from the chapter without announcing which idea each question is testing. Deciding what a question is about is part of the work, and it is the part that transfers to reading mathematics written by other people.Read lesson →

Mapping the lesson.

Logic and proofs

Build the foundation