Less Common Proof Strategies
When writing mathematical proofs, it's common to follow three general argument structures: construction,
contradiction, and induction.
And while these are great, they can pollute the problem-solving mind with oversaturated
suppose-for-the-sake-of-argument's and now-consider-when-n=k+1's.
These three argument structures are, of course, useful, but it poses as an interesting problem to be more
creative when it comes to proof-writing.
Here, I will provide a serious survey of unique and useful strategies you can deploy on problem sets to
break out of the monotonous cycle of
cookie-cutter proofs, and hopefully provide a unique perspective on problem-solving.
Proof by Contra-contradiction
We're able to prove via contradiction by the law of excluded middle, which says that either p or
not p holds.
It follows that either not p or not not p holds. So, we should want to prove that
contradicting the argument
poses a contradiction.
Example:
Prove that if \(p \in \mathbb{Z}_+\) is a prime and \(a \in \mathbb{Z}\), then \(a^p \equiv a \mod{p}\).
Suppose for the sake of contradiction that we could suppose for the sake of contradiction that this isn't true. Then Euler's Theorem wouldn't hold. \(\Box\)
Prove that if \(p \in \mathbb{Z}_+\) is a prime and \(a \in \mathbb{Z}\), then \(a^p \equiv a \mod{p}\).
Suppose for the sake of contradiction that we could suppose for the sake of contradiction that this isn't true. Then Euler's Theorem wouldn't hold. \(\Box\)
Proof by WLOG Spamming
By repeatedly declaring no loss in generality, one is bound to converge to a state of generality of the
highest degree,
and thus prove their goal.
Example:
Prove that any graph embedded in a surface of genus 1 is at worst 7-colorable.
WLOG suppose you have a graph with a vertex of degree 6. WLOG call that vertex \(v\). WLOG say we color that vertex blue, and WLOG take one of the vertices connected to \(v\). WLOG that vertex has to be a new color, WLOG say red, and WLOG... \(\Box\)
Prove that any graph embedded in a surface of genus 1 is at worst 7-colorable.
WLOG suppose you have a graph with a vertex of degree 6. WLOG call that vertex \(v\). WLOG say we color that vertex blue, and WLOG take one of the vertices connected to \(v\). WLOG that vertex has to be a new color, WLOG say red, and WLOG... \(\Box\)
Proof by Condescension
The point of this is to convince the professor that you're smarter than the problem.
Example:
Let \(a \in \mathbb{Z}\) be odd, \(e \geq 3\), and consider \(x^n \equiv a \mod{2^e}\). If \(n\) is odd, then a solution exists and is unique. Show further that if \(n\) is even, a solution exists if and only if \(a \equiv 1 \mod{4}\), and \(a^{2^{e-2}/d} \equiv 1 \mod 2^e\), where \(d = (n, 2^{e-2})\), and when a solution exists, there are exactly \(2d\) solutions.
Come on, Professor. You call this a capstone? \(\Box\)
Let \(a \in \mathbb{Z}\) be odd, \(e \geq 3\), and consider \(x^n \equiv a \mod{2^e}\). If \(n\) is odd, then a solution exists and is unique. Show further that if \(n\) is even, a solution exists if and only if \(a \equiv 1 \mod{4}\), and \(a^{2^{e-2}/d} \equiv 1 \mod 2^e\), where \(d = (n, 2^{e-2})\), and when a solution exists, there are exactly \(2d\) solutions.
Come on, Professor. You call this a capstone? \(\Box\)
Proof by Restatement
The goal of this strategy is to subtly restate the goal as a hypothesis.
Example:
Show that the Lagendre Symbol is completely multiplicative over the numerator.
Let \(a\) and \(b\) be positive integers \(_{\text{that are completely multiplicative as the numerator of a Legendre Symbol over some prime}}\). Then clearly \((a/p)(b/p) = (ab/p)\). \(\Box\)
Show that the Lagendre Symbol is completely multiplicative over the numerator.
Let \(a\) and \(b\) be positive integers \(_{\text{that are completely multiplicative as the numerator of a Legendre Symbol over some prime}}\). Then clearly \((a/p)(b/p) = (ab/p)\). \(\Box\)
Proof by Completion
This proof technique takes a bit of strategizing. You need to predict which problems will be graded for
completion. Prove these by copy-and-pasting a solution
to a previous problem. It might also help to attach a random diagram with lots of unlabeled arrows.
Example:
Show that the image of a continuous function from the circle to some curve in the plane divides the plane in exactly two components.
Suppose for the sake of contradiction that we could suppose for the sake of contradiction that this isn't true. Then Euler's Theorem wouldn't hold. \(\Box\)
Show that the image of a continuous function from the circle to some curve in the plane divides the plane in exactly two components.
Suppose for the sake of contradiction that we could suppose for the sake of contradiction that this isn't true. Then Euler's Theorem wouldn't hold. \(\Box\)
Proof by Axiomatization
When one fails to prove a statement immediately, a simple yet sound solution is to simply declare it as an
axiom.
Example:
Show that the order of a subgroup divides the order of the group.
By [your name here]'s Axiom, the above holds trivially. \(\Box\)
Show that the order of a subgroup divides the order of the group.
By [your name here]'s Axiom, the above holds trivially. \(\Box\)
Proof by Ex Falso
This strategy takes a bit of setup but makes your proof well-structured and clean.
Example:
Prove that given any \(k, n \in \mathbb{N}\), you can find an \(N \in \mathbb{N}\) such that if the complete \(k\)-hypergraph of \(N\) vertices is colored one of two colors, then there exists a mononchrome complete \(k\)-hypergraph on \(n\)-vertices.
First we'll show \begin{align}1 &= 1 + \sqrt{1}\\ &= 1 + \sqrt{(-1)(-1)}\\ &= 1 + \sqrt{-1}\sqrt{-1}\\ &= 1 + i^2\\ &= 1 - 1\\ &= 0. \end{align} This is a contradiction, so the above is true, ex falso. \(\Box\)
Prove that given any \(k, n \in \mathbb{N}\), you can find an \(N \in \mathbb{N}\) such that if the complete \(k\)-hypergraph of \(N\) vertices is colored one of two colors, then there exists a mononchrome complete \(k\)-hypergraph on \(n\)-vertices.
First we'll show \begin{align}1 &= 1 + \sqrt{1}\\ &= 1 + \sqrt{(-1)(-1)}\\ &= 1 + \sqrt{-1}\sqrt{-1}\\ &= 1 + i^2\\ &= 1 - 1\\ &= 0. \end{align} This is a contradiction, so the above is true, ex falso. \(\Box\)
I hope this tour of useful but rarely seen argument strategies helps in your next problem set. These logically sound tactics ensure a more creative approach to problem solving, and can help crack hard problems. Be careful, though, as with great power comes great responsibility.