Lecture notes · Math for Computer Science · Lecture 1

Introduction and Proofs

MIT 6.042J Mathematics for Computer Science, lecture 1, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part explains what a proof is, first in everyday terms and then as the mathematical idea of a chain of logical steps that starts from accepted assumptions.

Key ideas

A proof is a method for finding out whether something is true. The lecture says this idea applies across many fields, not just math. 1:12
People establish truth in many ways, such as observation, experiment, counterexamples, and judges or juries weighing evidence. Authority alone, like a boss or a professor saying so, does not make something true in math. 5:57
Saying 'I don't see why not' is not a proof. It shifts the job of proving to the person who disagrees with you. 7:06
In math, a proof is a chain of logical deductions, which are small steps that each follow from earlier statements, starting from a set of axioms, which are accepted starting points. The chain shows that a proposition is true. 7:28
A proposition is a statement that is either true or false. You may not know which one it is, but it must be one or the other. 8:24

Words to know

proposition: A statement that is either true or false. You might not know which, but it has to be one or the other.
axiom: A starting statement that we accept as given, so the proof can build on it.
logical deduction: A small step where something new follows necessarily from statements we already have.
counterexample: A single case that shows a claim is false.

Example

Think of a proof like a bridge built one plank at a time. Each new plank must rest securely on the one before it, and the first planks rest on ground everyone agrees is solid. If every plank holds, you can safely walk from the starting bank to the far bank, which is the conclusion.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

Checking a claim on many examples does not prove it is always true, and one clear counterexample can show it is false.

Key ideas

A proposition is a statement that is either true or false. A predicate is a proposition whose truth depends on a variable, such as n. 10:49
The claim that n squared plus n plus 41 is prime works for the first 40 values of n, but it fails at n = 40. So checking many cases does not prove a claim. 13:29
A quantifier tells you how many values a claim covers. 'For every' covers all of them, and 'there exists' says at least one exists. 16:23
Euler's conjecture about a to the fourth plus b to the fourth plus c to the fourth equals d to the fourth stood for over 200 years. Then Elkies found a solution, which showed it was false. 15:21

Words to know

predicate: A statement whose true or false answer changes depending on the value of a variable, like n.
proposition: A statement that is either true or false.
quantifier: A word or symbol that says how much a claim covers, such as 'for every' or 'there exists'.
universe of discourse: The set of all the things you are talking about, such as only the natural numbers.

Example

Imagine checking whether every apple in a barrel is ripe by tasting the first 40 apples, and all of them are ripe. You still cannot be sure, because the 41st apple could be rotten. The lesson works the same way: passing many tests does not prove a claim is always true.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part shows why trying a few examples doesn't prove a math claim, why picture proofs and computer proofs can be shaky, and how the word "implies" is defined.

Key ideas

Testing a claim on a few cases is not enough. A claim can work for many examples and still be false, so a real proof is needed. 20:00
Proofs by picture can look convincing but still be wrong. A picture shows only the cases you drew, and your brain can stop looking for other possibilities. 21:49
The four color theorem was finally proved with a computer checking thousands of cases. Many mathematicians found this unsatisfying because it is hard to know the computer made no mistakes. 22:34
Do not believe everything you read. A magazine example used 9 as a prime number, which is wrong, and that mistake would make Goldbach's conjecture look easy. 25:03
An implication, written p implies q, is true if p is false or if q is true. Only the case where p is true and q is false makes it false. 29:43

Words to know

conjecture: An educated guess that people believe may be true but have not proved yet.
prime: A whole number greater than 1 that can only be divided evenly by 1 and itself, such as 11 or 13.
integer: A whole number, which can be positive, negative, or zero, such as -2, 0, or 5.
implies: A word for an if-then link: p implies q means that if p holds, then q must also hold.

Example

Imagine a parent says, "If you finish your homework, you get dessert." The promise is kept if you don't finish your homework, because then the rule never applies. It is also kept if you finish and get dessert. The promise is only broken if you finish your homework and still get no dessert. This is how "p implies q" works.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part explains how true and false statements work in logic, what makes a sentence a proposition, and what axioms are.

Key ideas

An 'if p, then q' statement (p implies q) is true whenever p is false, no matter what q is. The lesson uses the joke 'If pigs could fly, I would be king' to show this. 30:40
'If and only if' means the statement works in both directions. To prove it, you must check that p leads to q and that q leads to p. 32:39
Not every sentence is a proposition. A proposition must be either true or false. 'This statement is false' is not a proposition, because it cannot be either one without causing a contradiction. 34:37
An axiom is a proposition that we assume is true without proof. You need axioms to start any math, because you cannot prove everything from nothing. 35:47
In math, the key is to state your assumptions clearly. Then anyone who accepts those assumptions can follow your proof and check your conclusion. 36:40

Words to know

proposition: A statement that is either true or false, but not both.
implies: A 'if this, then that' link between two statements. 'p implies q' means that if p is true, q has to be true too.
axiom: A statement that people agree to accept as true without proving it, used as a starting point for a proof.
if and only if: A link between two statements that says each one is true exactly when the other one is true. It has to work both ways.

Example

Think of the rules of a board game. Everyone agrees to the starting rules before playing, and nobody proves them first. Those agreed rules play the same role that axioms play in math: they are the starting point that everyone can see and check the rest of the game against.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–44:06

This part explains two wished-for traits of a set of starting rules (axioms), and how Kurt Gödel showed that having both is impossible.

Key ideas

A set of axioms is consistent if no statement can be proved both true and false. Without this, years of proof work could be wiped out by one contradiction. 40:15
A set of axioms is complete if it can be used to prove that every statement is either true or false. That means every problem can be settled. 41:26
In the 1930s, Kurt Gödel proved that no set of axioms can be both consistent and complete. Famous logicians like Russell and Whitehead had been searching for one and never found it. 42:34
Because consistency is a must, the lesson says there will always be true facts that cannot be proved. Some problems, like Goldbach's conjecture, may be like this. 43:18

Words to know

axiom: A starting rule or basic statement that we accept without proof, and then use to prove other things.
consistent: Never contradicting itself. A consistent set of rules never lets you prove something is both true and false.
complete: Leaving nothing out. A complete set of rules can settle every statement as either true or false.
conjecture: A statement that people believe may be true but have not yet proved.

Example

Think of a rule book for a board game. If one page says a move is allowed and another page says it is banned, the rule book is not consistent. If some moves are covered by no rule at all, the rule book is not complete. This is only a picture to help you see the idea, not part of the lesson.

3 checked practice questions for this part are in the app.

Lecture 2: Induction →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York