I've got a discrete math test coming up, and I've been studying religiously for the past week. Proof styles still frighten me though, I find it hard to wrap my head around them. Right now I am studying case analysis or 'proof by cases', I am looking at an example problem and solution posted by my professor and I need a little help.
Let the domain of x be the set of all integers. Give a case analysis
proof to prove (All x, x^2 != 5)
Sol:
Case 1: (x >= -2 and x =< 2): x^2 =< 4 < 5
Case 2: (x < -2 or x > 2): x^2 >= 9 > 5
I know case analysis is about splitting the domain into sections and solving each section, but I don't understand why the choice was made to split based on the absolute values of two. Is there any logic I am missing? Could someone talk to me more about the choice made here and case analysis in general?
Best Answer
The idea behind a proof by cases is to prove a statement $R$ seeing that, under the hypothesis, there are two possible cases (argument is similar for more cases); where the first case is the statement $P$, and $Q$ is the second. Thus, if we prove $P \implies R$ and $Q \implies R$, then we can conclude that $R$ is necessarily true. We can summarize with $$(P \implies R) \land (Q \implies R) \quad\implies\quad (P \lor Q) \implies R\,.$$ Since $T \lor \neg T$ is a tautology, it is common to use this to take tha possible cases.
I can show you some examples of proof by cases in set-theory and real-analysis, but I do not if this is what you are looking for.
Remember, the key to prove by cases $P \implies Q$ is to split $P$ in all possibles cases such that $$P_1 \lor P_2 \lor P_3 \lor \dotsm \lor P_n \iff P,$$ then prove $P_i \implies P$ where $i = 1, 2, 3, \dotso, n$.
In your problem, we need to use our "advanced knowledge" to pick the cases for $x^2 \ne 5$. Thus, since we know that for any numbers $a$ and $b$, only one of the three statements $a < b$, $a = b$ or $a > b$ is true. Since we have $x^2 \ne 5$, then must be either $x^2 < 5$ or $x^2 > 5$, but no both. For $x^2 < 5$, we have $S := \{x \in \Bbb Z: -2 \le x \le 2 \}$ satisfies the statement. For $x^2 > 5$, we have $T := \{x \in \Bbb Z: -3 \le x \text{ and } x \ge 3 \} = \{x \in \Bbb Z: -2 < x \text{ and } x > 2 \} $ satisfies $x^2 > 5$. Since $S \cup T = \Bbb Z$, we have our cases, i.e., we have $x \in S \implies x^2 < 5$ and $x \in T \implies x^2 > 5$, which is the same that $(x \in S \text{ or } x \in T) \implies (x^2 < 5 \text{ and } x^2 > 5)$, which is the same that $x \in \Bbb Z \implies x^2 \ne 5$.
Obviusly, this is not a rigorous proof. Also, you can to use the absolute value to ease the notation.