Lecture on Proofs and Logical Deductions

Introduction

• MIT Open Courseware under Creative Commons license.
• Definitions and broader concepts of proofs.

Definitions of a Proof

• Mathematical Proof: A chain of statements each logically supported by the previous ones leading from assumptions to conclusions.
• General Proof: Method for ascertaining truth, verifying truth across various fields.

Methods of Ascertaining Truth

1. Observation and Experiment: Fundamental in physics; e.g., observing gravity.
2. Eliminating Falsehoods: Narrowing down the truth by elimination; e.g., counterexamples.
3. Judicial System: Truth established by evidence evaluated by juries and judges.
4. Religious Beliefs: Truth based on faith, interpretation by religious authorities.
5. Authority Figures: Truth determined by bosses, customers, or authoritative figures.
6. Inner Conviction: Belief without external proof; prevalent in programming, “no bugs” mantra.

Importance of Mathematical Proof

• Unique in allowing students to challenge even the most experienced professors.
• Mathematical dialogues are encouraged.

Fundamental Components of Mathematical Proofs

• Propositions: Statements that are either true or false.
• Logical Deductions: Based on logical reasoning from axioms.
• Axioms: Propositions assumed to be true without proof.

Propositions and Predicates

• Proposition Examples:
  • Simple: 2 + 3 = 5 (true).
  • Complex: For all natural numbers n, n^2 + n + 41 is a prime number (false).
• Predicate: Proposition whose truth depends on a variable, e.g., n^2 + n + 41.
• Universe of Discourse: Context, e.g., set of natural numbers.
• Quantifiers: For all (∀), There exists (∃).

Examples and Counterexamples

• Natural Numbers:
  • Example showing a proposition fails at n = 40.
• Historical Mathematical Conjectures:
  • Euler’s sum conjecture, disproved after 218 years.
  • Fermat’s Last Theorem (solved example).
  • Elliptic Curves and RSA Cryptography: Relevance to practical applications.

Challenges in Mathematical Proofs

• Exhaustive Checking Limitations: Not always practical for large numbers or infinite sets.
• Goldbach’s Conjecture: An example of an unsolved and unverified proposition.

Consequences of Misproofs

• Proof by Picture: Often misleading and incorrect.
• Four-Color Theorem: Initially false proofs, finally proved using a computer in 1977.
• Revisions and Verifications: Importance of detailed and human-verifiable proofs.

Logical Implications and Truth Tables

• Implication (P implies Q): P => Q is true if P is false or Q is true.
• If and Only If (P iff Q): P <=> Q requires both directions to be true.
• Examples: Implication Truth Table
  • P true, Q true; P => Q true.
  • P true, Q false; P => Q false.

Propositions vs. Non-Propositions

• Not every statement is a proposition (e.g., questions, commands).
• A proposition must be either true or false.

Axioms

• Definition: Propositions assumed to be true, basis for logical deductions.
• Consistency: No proposition can be both true and false.
• Completeness: Every proposition is either true or false.

Examples of Different Axioms in Various Geometries

• Euclidean Geometry: One line through a point parallel to given line.
• Spherical Geometry: No lines through a point parallel to given line.
• Hyperbolic Geometry: Infinitely many lines through a point parallel to given line.

Importance of Consistency and Completeness

• It’s essential for a set of axioms to be consistent to avoid contradictions.
• Gödel’s Incompleteness Theorems: Proved that no set of axioms can be both consistent and complete.
  • Revolutionary impact on mathematics and logic.

Conclusion

• Ongoing exploration and verification in mathematics.
• Limitations and challenges in proving theories and conjectures.