#constructive #math tip
Often in a proof using classical math, you might take a related proposition X and split into cases "X" and "not X". Some examples in number theory: <https://en.wikipedia.org/wiki/Riemann_hypothesis#Excluded_middle>.
We can't do this in constrictive math, but there is a trick that is equivalent (and more elegant)!
X is any kind of proposition, such as:
- a conjecture, like the Riemann hypothesis
- a statement with free variables, like "n > k" or "G is finite" or any instance of "x has property P"
- a statement independent of your axioms, like the continuum hypothesis or the axiom K
In many cases you might be able to prove excluded middle (EM) for your specific X, but here's an alternative that works for any X.
**The trick**
If you are trying to prove A⇒B, prove the following two lemmas first:
- A⇒(X or B)
- (A and X)⇒B
Classically this is equivalent to splitting on "X or not X" (the first lemma is the "not X" case since "A⇒(X or B)" is equivalent to "(A and not X)⇒B" if EM holds for X), but it's still a theorem constructively that those two lemmas imply A⇒B!
Proof
Assume A. By the first lemma we conclude X or B. There are two cases:
- X: By the second lemma conclude B.
- B: We conclude B.
Therefore B.
∎
If you are just trying to prove C, then use the above trick on "1=1⇒C". If you are trying to refute C, use the above trick on "C⇒0=1". For proof by induction, A can include the induction hypothesis.
Moreover, if you have n propositions of interest, you can split into 2^n lemmas. Adding more propositions never hurts since you can ignore any unneeded propositions when proving any of the lemmas! Many of the lemmas may be trivial or redundant if you already know some relationships between the propositions.