6-120 – First Lecture: Course Logistics & Foundations of Proof
Course Schedule & Structure
• Lecture sessions
• Tuesdays & Thursdays, 2:30 PM – 4:00 PM (room/time you are physically attending)
• Recitations
• Wednesdays & Fridays
• Attendance recorded → 10 % of final grade
• Format: small-group problem solving with a TA present
• Described by instructor as “some of the most useful time you’ll have this semester.”
• Warm-Up Problems (a.k.a. “warm-ups”)
• Quick multiple-choice questions on Canvas released before every recitation
• Purpose
• Nudge you to think about lecture material in advance
• Avoid the “What are we covering today?” situation at recitation
• Mechanics
• Unlimited retries until the deadline
• Instant feedback
• Full credit as long as you eventually pick the correct answer
• You could brute-force click every option, but you are encouraged to reason it out so the exercise is actually preparatory (and faster!).
Weekly Problem Sets
• Release & due cycle
• Released every Tuesday
• Due the following Monday at 11:59 PM (i.e., as late into Monday night as possible)
• Collaboration philosophy
• Strongly encouraged to work with peers, attend office hours, ask questions on Piazza, etc.
• “P-set Partner” matching tool
• Opens shortly after each set is released
• Pairs you with students who have overlapping schedules
• If you miss the first matching round, a second round will open
• Acceptable collaboration modes: dorm study groups, office-hour impromptu groups, your own friends, etc.
• Two-step workflow emphasized by the instructor
1. Solve together – brainstorm, discuss strategies, crack the puzzles collectively.
2. Write alone – set group notes aside, then write your final solutions in your own words.
• Goal: develop the separate skill of articulating mathematically rigorous, readable proofs.
• Prevents the “P vs NP fallacy”: understanding someone else’s proof (easy/Polynomial-time) ≠ creating the proof from scratch (hard/NP-complete).
Proof-Writing as a Learning Outcome
• Major export of 6-120: the ability to write precise, concise, correct proofs.
• Reading/comprehending proofs and evaluating their correctness is also part of the skill set.
• Instructor’s mantra: “Solve collaboratively, write individually.”
Late-Submission Policy for Problem Sets
• Accepted all the way until the last day of classes.
• Rationale: P-sets are intellectually valuable; the department wants you to learn from them even if life happens.
• Grading formula
• From on-time (0 h late) to 50 h late → linear drop from 100 % to 50 %.
• Penalty = 1 % per hour for the first 50 hours.
• After 50 h → flat 50 % credit until term ends.
• Practical advice
• If it’s 11:45 PM and you need an extra hour to polish a final proof, take it. Losing 1 point is worth the reduced stress and improved submission.
Where to Find More Logistics
• All details in the “Course Information & Policies” PDF on Canvas.
Introduction to Proofs
Big Question: What is a proof?
• Initial definition written on the board: “A proof is how you show that something is true.”
• Comparison to other human truth-seeking methods
• Experiments, observation, the scientific method
• Random sampling (election polling)
• Legal trials
• Investigation/evidence gathering
• Authority (“Professor said so.”) — discouraged in math
• Religion / divine revelation
• Inner conviction / intuition (“came to me in a dream”)
• Mathematics has its own procedure: the mathematical proof.
Formal Definition
• “A mathematical proof is a verification of a proposition by a chain of logical deductions from a base set of axioms.”
• Three highlighted terms to unpack (today and next lecture): proposition, logical deductions, axioms.
Propositions & Predicates
Proposition (Definition)
• “A statement that is true or false.”
• Examples
• “Today is Tuesday.” (True on Tue, false otherwise.)
• (2+3=5) (True.)
• (2+3=4) (False.)
Predicate (Definition)
• “A proposition whose truth depends on variables.” (Instructor noted wording will be refined.)
• After concrete values are substituted, it becomes a proposition.
• Example: “p is prime.” — Not a proposition until you specify the value of p.
Example Analysis: \forall n\in\mathbb N\;\big(n^2 + n + 41 \text{ is prime}\big)
• Breakdown of notation
• \forall = “for all.”
• \mathbb N = set {0,1,2,\dots} (zero is a natural number in this course).
• Inside predicate: n^2 + n + 41 is prime.
• Testing small n values
• n=0 \;\Rightarrow\; 41 (prime)
• n=1 \;\Rightarrow\; 43 (prime)
• n=2 \;\Rightarrow\; 47 (prime)
• \vdots
• n=39 \;\Rightarrow\; 1601 (prime)
• Counterexample search
• n=40 \;\Rightarrow\; 41^2 (composite)
• n=41 \;\Rightarrow\; 41\times43 (composite)
• A single false instance disproves the universal claim ⇒ proposition is false.
Example: Goldbach’s Conjecture
• Statement: “Every even integer >2 can be written as the sum of two primes.”
• Current status: unknown (open problem in number theory).
• 1995 Boston Globe featured it as one of mathematics’ major mysteries.
• Sample checks
• 12 = 7 + 5 (works)
• 20 = 17 + 3 (works after correcting 9+11 error)
• Key lesson: Some deceptively simple-looking propositions lie beyond present-day mathematical reach.
Boolean Operators & Truth Tables
Unary operator: NOT
• Symbols: \lnot A, \overline A, or \neg A.
• Truth table
| A | \lnot A |
|---|---|
| T | F |
| F | T |
Binary operators
• Consider propositions A,B (four possible truth combinations).
AND (conjunction)
• Symbols: A\;\text{and}\;B or A \wedge B
• True iff both A and B are true.
• Truth table
| A | B | A\wedge B |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
OR (inclusive disjunction)
• Symbols: A\;\text{or}\;B or A \vee B
• True if at least one of A,B is true.
• Truth table
| A | B | A\vee B | |
|---|---|---|---|
| T | T | T | |
| T | F | T | |
| F | T | T | |
| F | F | F |
Linguistic Pitfalls: “OR” in Everyday English
• Natural language is context-dependent, unlike strict logical symbols.
Wedding dinner example — “Chicken or pasta?”
• Expected responses: only one of the two.
• Logical type: exclusive or (XOR).Post-dinner beverage — “Coffee or tea?”
• Allowed: coffee, tea, or neither.
• Logical equivalent: “NOT (coffee AND tea)” → NAND.Condiment choice — “Cream or sugar?” for coffee.
• Any combination acceptable: cream, sugar, both, or neither.
• No single neat logical connective; essentially listing options.
• Bottom line: In mathematics, always interpret “OR” as inclusive \vee unless explicitly stated otherwise.
Key Take-Home Messages
• Attend recitation; it is graded and pedagogically valuable.
• Warm-ups are easy points and ensure you arrive prepared.
• Collaboration ≠ copying; coexistence of communal problem-solving and individual proof-writing hones both understanding and exposition skills.
• Late P-sets are accepted with a gentle sliding-scale penalty — prioritize learning and mental health.
• Proofs are math’s distinctive mechanism for certifying truth — different from science, law, or intuition.
• Master the vocabulary: propositions, predicates, logical operators.
• Beware the ambiguity of ordinary language; in proofs, precision reigns.