A universal theorem over a finite universe can sometimes be proved by checking every case. This method is called proof by exhaustion. It is useful only when the universe is explicitly finite and small enough for all cases to be verified. In this lesson, proof by exhaustion and theorem terminology are introduced through finite numerical examples and the language of theorems and corollaries. :::definition[Proof by Exhaustion] A proof by exhaustion is a proof method used for a finite universe. Given a finite universe, to prove that a statement is true for every element of the universe, one verifies the statement separately for each element. If $$\begin{equation*} U=\{a_1,a_2,\ldots,a_n\}, \end{equation*}$$ then to prove $\forall x\in U,\ p(x)$, it is enough to show $$\begin{equation*} p(a_1),p(a_2),\ldots,p(a_n). \end{equation*}$$ ::: :::example[Sum of at Most Three Perfect Squares] Let the universe be $$\begin{equation*} U=\{2,4,6,8,\ldots,24,26\}. \end{equation*}$$ For every $n\in U$, we want to prove that $n$ can be written as the sum of at most three perfect squares. Since the universe is finite, proof by exhaustion is appropriate. ::: :::definition[Exhaustive List of Representations] For the universe $U=\{2,4,6,8,\ldots,24,26\}$, the following list gives each element as a sum of at most three perfect squares: $$\begin{equation*} \begin{array}{lll} 2=1+1, & 10=9+1, & 20=16+4,\\ 4=4, & 12=4+4+4, & 22=9+9+4,\\ 6=4+1+1, & 14=9+4+1, & 24=16+4+4,\\ 8=4+4, & 16=16, & 26=25+1,\\ & 18=16+1+1. & \end{array} \end{equation*}$$ Here $1,4,9,16,25$ are perfect squares. ::: A proof by exhaustion succeeds only when the chosen finite universe is completely checked. This calculator searches for representations of even numbers as a sum of at most three perfect squares. Enter an even start and end value, then run the check. The output lists one representation for every number in the selected universe or reports the first value that is not covered. This helps students see why the proof is the completed list of cases, not a pattern guessed from a few examples. :::calculator[Exhaustion Representation Checker] ::: :::solved-problem Prove that every element of $U=\{2,4,6,8,\ldots,24,26\}$ can be written as the sum of at most three perfect squares. ::: :::solution Given that $$\begin{equation*} U=\{2,4,6,8,\ldots,24,26\}. \end{equation*}$$ To prove that every $n\in U$ is the sum of at most three perfect squares. We verify each element of $U$: $$\begin{equation*} \begin{array}{lll} 2=1+1, & 4=4, & 6=4+1+1,\\ 8=4+4, & 10=9+1, & 12=4+4+4,\\ 14=9+4+1, & 16=16, & 18=16+1+1,\\ 20=16+4, & 22=9+9+4, & 24=16+4+4,\\ 26=25+1. && \end{array} \end{equation*}$$ Each element of the universe has been checked. Therefore every element of $U$ can be written as the sum of at most three perfect squares. Hence the statement is proved by exhaustion. ::: :::definition[Theorem] A theorem is a mathematical statement that has been proved to be true. A theorem usually states a general result and is justified by a proof. ::: :::definition[Corollary] A corollary is a result that follows directly or almost directly from a theorem. If a theorem has already been proved, then a corollary often needs only a short proof or a direct explanation. ::: :::remark[Finite Universe Requirement] Proof by exhaustion is reasonable only when the universe is finite and small enough to check every case. If the universe is large or infinite, a different proof method is usually needed. ::: :::solved-problem Why does the verification for $U=\{2,4,6,8,\ldots,24,26\}$ stop at $26$ and not at $28$? ::: :::solution Given that the universe is $U=\{2,4,6,8,\ldots,24,26\}$. To prove a statement over $U$, only elements of $U$ must be checked. The number $28$ is not an element of this universe. Therefore the verification stops at $26$. Hence $28$ is not included because it is outside the given universe. ::: :::solved-problem Why are the odd integers between $2$ and $26$ not included in the verification? ::: :::solution Given that the universe is $U=\{2,4,6,8,\ldots,24,26\}$. This universe contains only even integers from $2$ through $26$. Odd integers between $2$ and $26$ are not members of $U$. Therefore they are not checked in the proof. Hence the statement is only about the specified even integers. ::: :::solved-problem Use the method of exhaustion to show that every even integer between $30$ and $58$, including $30$ and $58$, can be written as a sum of at most three perfect squares. ::: :::solution Given that $U=\{30,32,34,36,38,40,42,44,46,48,50,52,54,56,58\}$. To prove that every element of $U$ is the sum of at most three perfect squares, verify: $$\begin{equation*} \begin{array}{lll} 30=25+4+1, & 32=16+16, & 34=25+9,\\ 36=36, & 38=25+9+4, & 40=36+4,\\ 42=36+4+1, & 44=36+4+4, & 46=36+9+1,\\ 48=16+16+16, & 50=25+25, & 52=36+16,\\ 54=49+4+1, & 56=36+16+4, & 58=49+9. \end{array} \end{equation*}$$ Each element of the universe has been checked. Hence the statement is proved by exhaustion. ::: :::solved-problem Use the method of exhaustion to show that every even integer in $U=\{4,6,8,\ldots,36,38\}$ can be written as the sum of two primes. ::: :::solution Given that $U=\{4,6,8,\ldots,36,38\}$. We verify each case: $$\begin{equation*} \begin{array}{lll} 4=2+2, & 6=3+3, & 8=3+5,\\ 10=5+5, & 12=5+7, & 14=7+7,\\ 16=5+11, & 18=7+11, & 20=7+13,\\ 22=11+11, & 24=11+13, & 26=13+13,\\ 28=11+17, & 30=13+17, & 32=13+19,\\ 34=17+17, & 36=17+19, & 38=19+19. \end{array} \end{equation*}$$ Each element of $U$ has been written as the sum of two primes. Hence the result is proved by exhaustion. ::: :::exercise Answer the following. (1) State when proof by exhaustion is appropriate. (2) Explain why checking $0$ and $1$ does not prove $\forall n\in\mathbb{Z}[n^2=n]$. (3) Use exhaustion to verify that each element of $\{4,6,8,10\}$ is a sum of two primes. (4) Explain the difference between a theorem and a corollary. ::: :::answer (1) It is appropriate when the universe is finite and every case can be checked. (2) The universe of integers is infinite, and $n=2$ gives $2^2\neq 2$. (3) $4=2+2$, $6=3+3$, $8=3+5$, and $10=5+5$. (4) A theorem is a proved statement; a corollary follows directly from a theorem. ::: :::faq[Frequently Asked Questions] Q: Does proof by exhaustion work for infinite universes? A: No. It requires checking every element, so it is suitable only for finite universes. Q: Why must the universe be stated? A: The universe tells us exactly which cases must be checked. Q: Is a long list always a proof? A: It is a proof only when the list covers every element of the finite universe. ::: :::call-to-action[Check Every Case] subtitle: Use proof by exhaustion only when the finite universe is completely specified, then move to quantified argument rules. button: Next Lesson | /discrete-mathematics/mathematical-logic/quantifiers-definitions-and-proofs-of-theorems/universal-specification-in-quantified-arguments button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/quantifiers-definitions-and-proofs-of-theorems/biconditional-definitions-with-quantifiers :::