04 Proof Techniques Free Online FlashCards

What is a mathematical proof?

A logically valid argument showing that a conclusion follows from definitions, assumptions, and established results for every object covered by the statement.

What is the contrapositive of $P\implies Q$?

The contrapositive of $P\implies Q$ is $\neg Q\implies\neg P$. These implications are logically equivalent.

How does a direct proof establish $P\implies Q$?

Assume $P$, introduce arbitrary objects satisfying the hypotheses, apply definitions or known results, and derive $Q$.

How can you prove that the sum of two even integers is even?

Write $a=2m$ and $b=2n$ for integers $m,n$. Then $a+b=2(m+n)$, so the sum is even.

What is a proof by contrapositive?

Prove the logically equivalent statement $\neg Q\implies\neg P$ instead of proving $P\implies Q$ directly.

What is the structure of proof by contradiction?

Assume the statement is false, derive an impossibility, and conclude that the negation is impossible; therefore the original statement is true.

How does the contrapositive prove that odd $n^2$ implies odd $n$?

Assume $n$ is not odd, so $n=2k$. Then $n^2=4k^2=2(2k^2)$ is even, proving the contrapositive.

What requirement makes a proof by cases complete?

A proof by cases divides all possibilities into exhaustive cases and proves the conclusion separately within each case.

Why is $n^2-n$ even for every integer $n$?

For even $n$, write $n=2k$; for odd $n$, $n-1$ is even. Thus $n(n-1)=n^2-n$ is even in both exhaustive cases.

What is a counterexample?

A single valid example that shows a universal claim is false. For an implication, it must satisfy the hypothesis and fail the conclusion.

Give a counterexample to divisibility by $4$ implying divisibility by $8$.

The integer $4$ is divisible by $4$ but not by $8$, so it disproves the implication.

Why can examples not prove a universal claim?

A universal claim requires a general argument over arbitrary allowed objects; checking finitely many examples only shows that those tested cases work.