CS2050 L05 Introduction to Proof

Overview

Abrahim Ladha introduces proof writing as a readable, high-level form of formal logic: every step must be valid, but writers can omit details a mathematically prepared reader can readily reconstruct. Using integer parity, counterexamples, contraposition, and biconditionals, he develops practical proof techniques and explains why examples can suggest a conjecture but cannot establish a universal claim.

Key takeaways

A direct proof of P → Q assumes P and derives Q; for parity, writing an even integer as 2k turns the definition into an algebraic tool.
Proof writing balances rigor with readability: every deduction must be valid, but familiar facts such as equality substitution and multiplication associativity need not always be expanded.
A universal claim cannot be established by checking examples; one counterexample is enough to disprove it, as 2^(2^5) + 1 is divisible by 641.
Contraposition can make an awkward implication manageable: to prove oddness of 5n + 4 implies oddness of n, assume n is even and show 5n + 4 is even.
The factor bound for n = ab follows by contradiction: if both positive factors exceed √n, their product exceeds n.
An if-and-only-if proof requires both implications, and each direction can use a different strategy, as in the proof that n² is even exactly when n is even.

Chapters

0:00 Proofs as Readable Pseudocode for Formal Logic

Ladha compares a written proof to pseudocode: a reader should be able to expand its reasoning into formal rules of inference.
Unlike a line-by-line inference derivation, a proof uses prose while retaining an objective standard of correctness.
An elegant proof also has explanatory value, much like a literary form, while remaining either correct or incorrect.

3:00 Number Domains and What Counts as Established Truth

The course treats the natural numbers as 0, 1, 2, and onward, and integers as positive and negative naturals.
A rational number is a ratio of integers with a nonzero denominator; real and complex numbers require more careful construction.
Claims such as the irrationality of π or √2 need demonstrations, not just observed decimal patterns.

8:00 Axioms, Theorems, Corollaries, Conjectures, and Lemmas

An axiom is a truth accepted without proof, providing a starting foundation for deductions.
A theorem is an established truth; a corollary is a consequence that follows readily from a theorem.
A conjecture is an unproved candidate claim, while a lemma is a helper result used to prove a larger theorem.

11:00 Direct Proof: The Product of Two Even Integers Is Even

Ladha defines an even integer n by the existence of an integer k such that n = 2k.
For even a and b, write a = 2k and b = 2l, then calculate ab = 2(2kl).
Because 2kl is an integer, the product satisfies the definition of evenness.

14:00 Proof Style, Substitution, and Reader Expectations

A proof proceeds top to bottom, with each sentence serving as a premise or a deduction from earlier sentences.
The even-product proof relies on equality substitution and associativity of multiplication without spelling out every formal inference.
Using distinct witnesses k and l avoids accidentally asserting that two unrelated even numbers are equal.

22:00 Corollaries from the Even-Product Theorem

If n is even, the theorem immediately gives that n² is even by taking both factors to be n.
The proof also reveals a stronger fact: the product of two even integers is a multiple of four.
A stronger observation can be stated as a corollary, but it should be identified and explained rather than silently substituted for the original theorem.

30:00 Direct Proof: An Even Integer Times an Odd Integer

Ladha defines an odd integer b by b = 2l + 1 for some integer l, alongside an even integer a = 2k.
Expanding gives ab = 4kl + 2k = 2(2kl + k), which matches the definition of even.
The proof may omit intermediate arithmetic if the reader can follow it, but beginners are encouraged to show enough steps.

39:00 Why Examples Cannot Prove Universal Claims

A few successful calculations can suggest a conjecture, but they cannot establish that a statement holds for every integer.
Fermat's proposed pattern 2^(2^n) + 1 produces prime values for early cases, including 3, 5, 17, 257, and 65537.
The next case is composite, with 2^(2^5) + 1 divisible by 641, illustrating why a pattern of examples is not a proof.

44:00 Direct Proof: The Product of Two Odd Integers Is Odd

Write odd integers as a = 2k + 1 and b = 2l + 1.
Their product simplifies to 2(2kl + k + l) + 1.
Since the expression inside the parentheses is an integer, the product satisfies the definition of oddness.

46:00 Counterexamples Disprove Universal Claims

To refute a statement that claims a property holds for all inputs, it is enough to find one input where it fails.
Exponentiation is not associative: 4^(3^2) = 4^9 = 262144, while (4^3)^2 = 64^2 = 4096.
The counterexample establishes the negation of the universal claim by demonstrating a specific failure.

51:00 Contraposition: Proving the Negated Conclusion Implies the Negated Premise

The implication P → Q is logically equivalent to its contrapositive, not Q → not P.
For the claim that oddness of 5n + 4 implies oddness of n, Ladha instead assumes n is even.
Writing n = 2k gives 5n + 4 = 2(5k + 2), which is even and proves the contrapositive.

56:00 A Square-Root Bound for Factors of a Composite Integer

For positive integers n, a, and b with n = ab, at least one factor must be at most √n.
The contrapositive assumes both a > √n and b > √n, then multiplies the inequalities to get ab > n.
Since ab = n, that result is a contradiction; the bound helps limit how far a factor search must go.

1:02:00 An If-and-Only-If Requires Two Implications

To establish P if and only if Q, prove both P → Q and Q → P.
Either implication can be proved directly or replaced by its contrapositive when that direction is easier.
Ladha recommends readable phrases such as “there exists” over dense symbolic shorthand in written proofs.

1:05:00 Proving That n² Is Even Exactly When n Is Even

For the direction from n² even to n even, Ladha proves the contrapositive: if n is odd, then n² is odd.
With n = 2k + 1, expansion gives n² = 2(2k² + 2k) + 1, an odd integer.
For the reverse direction, n = 2k gives n² = 2(2k²), which is even.

1:10:00 A Creative Direct Proof That Even n² Forces Even n

Assume n² = 2k for an integer k, then rewrite n as n(n + 1) − 2k.
Consecutive integers n and n + 1 include an even number, so n(n + 1) is even; 2k is also even.
The difference of these even quantities is even, establishing n even without using the simpler contrapositive route.

Transcript excerpt

0:03 All right. Um let's get started. So today's topic uh CS 2050 is introduction to proof. Uh so what is a proof? What does that mean to prove something? So really abstractly we're sort of we've done a lot of logic and we've shown you how to do inference and uh inference is done in a fully formal fully syntactic method in the sense that there are a system of rules that exist the rules of inference and that these could be applied perhaps by a computer program and in the 70s people did play around with like trying to do automated deduction and things right so it's this great thing that we have because it's pure and it's like perfect and we spent a lot of time doing this really formally so But then when we relax, we're still confident that we haven't made an error. And so that's kind of what we're going

0:50 to do today is we're we're going to relax. Um so logic is this great foundation for mathematics because it's completely objective. However, um a lot of really basic statements require a lot and are lengthy to formalize. So what a proof really is and this is sort of a boring definition is that it is analogous to the difference between a proof and a logical argument as we've done uh fully formally from the rules of inference. [clears throat] The difference between those two is analogous to uh assembly and pseudo code in the sense that if you outline pseudo code to someone if it's correct in theory they could like compile it and get down to something that's very machine executable. The same analogy exists here where proof is sort of a

1:36 highlevel argument that's done um to a specific level of rigor with the

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Abrahim Ladha.