Proving and Disproving Existential Statements
Proving Existential Statements Directly by Finding a Witness
Recall the following:
Thus, as was indicated in previous lessons, one way we can prove an existential statement (such as “\(\exists x\in D\) such that \(P(x)\)”) to be true is by finding a specific example \(x\in D\) (called a witness) such that \(P(x)\) holds/is true. It often helps to explain how \(P(x)\) is true based on your choice of \(x\in D\) to make your proof more robust.
Proof: Let \(n=5\). Then, notice that \(20=5\cdot 4\). Therefore \(20\) is a multiple of \(5\). Thus, we can conclude, by definition of “divides,” that \(n=5\vert 20\). QED.
Above, we proved the claim simply by finding an example \(n=5\) that made the predicate \(n\vert 20\) true, and explained how this was true by definition of “divides.” Often, this level of detail can be omitted. For right now, try reasoning from this level of detail, all the way down to fundamental definitions just to see how proofs flow from one statement to the next.
Proof: Let \(n=2\). Clearly \(n\) is even and prime. QED
You will see proofs like this if you continue your mathematical journey; i.e. proofs that claim something is “obvious” or “clear.” Most people would agree that it is obvious that \(2\) is an even prime number (it’s the only one, in fact), so a proof like this is fine in some cases. But of course, what is obvious to one person may not be obvious to another. Furthermore, since there is no support whatsoever for the claim, we can’t be certain that the claim is correct or that the author knows what they’re talking about! “The devil is in the details” as the saying goes.
A slightly more detailed proof: Let \(n=2\). \(n=2\) is even because \(2\) obviously divides itself, and numbers divisible by \(2\) are even. \(2\) is prime, because, clearly, \(1\) and \(2\) are the only positive integers that can divide \(2\) evenly. Therefore, we can conclude that \(2\) is both even and prime. Furthermore, we can conclude that there does indeed exist a natural number that is both even and prime. QED.
Notice that in the above, we still used terms like “obviously” and “clearly.” Again, this is fine, because we have spelled out a few more details that help the reader understand why \(n=2\) is indeed both prime and even.
Disproving an Existential Statement
Let \(P(x)\) be a predicate and let \(D\) be the domain of \(x\). We said an existential statement “\(\exists x\in D\) such that \(P(x)\)” is true provided there is at least one \(x\in D\) where the statement \(P(x)\) holds.
Therefore, to disprove an existential statement (i.e. to prove the statement to be false), one needs to prove its negation “\(\neg(\exists x\in D\) such that \(P(x))\)” which is logically equivalent to “\(\forall x\in D, \neg P(x)\).”
In other words, since the original existential statement claims the existence of at least one \(x\in D\) where \(P(x)\) holds, disproving this means showing that \(P(x)\) is FALSE FOR EVERY POSSIBLE \(x\in D\).
Disproving existential statements is usually harder than proving them. This matter is indirectly addressed in the next topic.
Prove the following existential statements.
Make sure that each statement you write in your proof helps to support the truth of the statement. Also, make sure that each sentence you write is either “obviously true” or is supported by a definition or another statement that is known to be true.
Let \(n=14\) and notice that \(14=7\cdot 2\). Therefore, by definition of “divides” we see that \(7\vert 14\). QED
(Note: your proof might read very differently. That’s okay, as long as it is supported properly.)
Let \(n=41\). Obviously, \(41\) is greater than or equal to \(35\) and less than or equal to \(45\). Note also that \(41\) is prime, since \(\sqrt{41}=6.4031\) and no prime number less than \(\sqrt{41}\) divides \(41\). Therefore, \(n=41\) is prime and \(35\leq 41 \leq 45\), (and so there exists a natural number \(n\) that is prime and \(35\leq n\leq 45\). QED
Nothing says that all statements have to be written with a slew of weird symbols!
Let \(n=15\) and \(m=2\). Note that since \(n\) and \(m\) are coprime (i.e. their GCD is 1, and they have no factor in common), their least common multiple is equal to their product. Therefore, there exist integers such that \(\text{lcm}(n,m)=30\). QED.
Some proofs require a little “background” or “scratch” work. In the case of this problem, you may have needed to write down a few different combinations of numbers before you came upon a pair that met the criteria. Scratch work you do for a proof rarely will be used in the proof itself, but it can certainly inform how to write the proof, or help you see why the given existential statement is correct.
When writing existential proofs, when you say “let \(n\) be ____” it will at times make you look like a genius, because the proof isn’t necessarily explaining how you got your \(n\), it is only showing that your \(n\) works!
Let \(n=30\) and \(m=14\). Note that \(\text{gcd}(30,14)=2\), which implies that \(n\) and \(m\) are not coprime. Note also that \(\text{lcm}(30,14)=210\) (since \(\text{lcm}(30,14)=\frac{(30\cdot 14)}{\text{gcd}(30,14)}=\frac{420}{2}=210)\). Therefore, the original statement in the problem holds. QED
Note that the reasoning for the LCM part of the proof above could probably be omitted because nearly anyone reading your proof (i.e. any mathematician who knows what GCD and LCM are) can tell you computed your LCM correctly.
When reading or writing proofs, it is helpful to go through each line of the argument and answer the question “why is this sentence true?” to yourself, especially when certain details are omitted.