Skip to main content
\(\newcommand{\versionNum}{$4.0$\ } \renewcommand{\tabcolsep}{2.4pt} \def\savedlnot{\lnot} \renewcommand{\arraystretch}{.63} \renewcommand{\arraystretch}{1} \renewcommand{\Naturals}{{\mathbb Z}^{\mbox{\tiny noneg}} } \renewcommand{\arraystretch}{.9} \renewcommand{\arraystretch}{.77} \newcommand{\hint}[1]{ } \newcommand{\inlinehint}[1]{ } \newcommand{\sageprompt}{ \texttt{sage$>$} } \newcommand{\tab}{} \newcommand{\blnk}{\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}} \newcommand{\suchthat}{\; \;} \newcommand{\divides}{\!\mid\!} \newcommand{\tdiv}{\; \mbox{div} \;} \newcommand{\restrict}[2]{#1 \,_{\,#2}} \newcommand{\lcm}[2]{\mbox{lcm} (#1, #2)} \renewcommand{\gcd}[2]{\mbox{gcd} (#1, #2)} \newcommand{\Naturals}{{\mathbb N}} \newcommand{\Integers}{{\mathbb Z}} \newcommand{\Znoneg}{{\mathbb Z}^{\mbox{\tiny noneg}}} \newcommand{\Zplus}{{\mathbb N}} \newcommand{\Enoneg}{{\mathbb E}^{\mbox{\tiny noneg}}} \newcommand{\Qnoneg}{{\mathbb Q}^{\mbox{\tiny noneg}}} \newcommand{\Rnoneg}{{\mathbb R}^{\mbox{\tiny noneg}}} \newcommand{\Rationals}{{\mathbb Q}} \newcommand{\Reals}{{\mathbb R}} \newcommand{\Complexes}{{\mathbb C}} \newcommand{\relQ}{\mbox{\textsf Q}} \newcommand{\relR}{\mbox{\textsf R}} \newcommand{\nrelR}{\mbox{$\not${\textsf R}}} \newcommand{\relS}{\mbox{\textsf S}} \newcommand{\relA}{\mbox{\textsf A}} \newcommand{\Dom}[1]{\mbox{Dom}(#1)} \newcommand{\Cod}[1]{\mbox{Cod}(#1)} \newcommand{\Rng}[1]{\mbox{Rng}(#1)} \DeclareMathOperator{\caret}{$\scriptstyle\wedge$} \renewcommand{\arraystretch}{.77} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section3.4Disproofs

The idea of a “disproof” is really just semantics — in order to disprove a statement we need to prove its negation.

So far we've been discussing proofs quite a bit, but have paid very little attention to a really huge issue. If the statements we are attempting to prove are false, no proof is ever going to be possible. Really, a prerequisite to developing a facility with proofs is developing a good “lie detector.” We need to be able to guess, or quickly ascertain, whether a statement is true or false. If we are given a universally quantified statement the first thing to do is try it out for some random elements of the universe we're working in. If we happen across a value that satisfies the statement's hypotheses but doesn't satisfy the conclusion, we've found what is known as a counterexample.

Consider the following statement about integers and divisibility:

This is phrased as a UCS, so the hypothesis is clear, we're looking for three integers so that the first divides the product of the other two. In the following table we have collected several values for \(a\), \(b\) and \(c\) such that \(a \divides bc\).

\(a\) \(b\) \(c\) \(a \divides b \, \lor \, a \divides c\) ?
2 7 6 yes
2 4 5 yes
3 12 11 yes
3 5 15 yes
5 4 15 yes
5 10 3 yes
7 2 14 yes
Exercise3.4.2

As noted in Section 1.2 the statement above is related to whether or not \(a\) is prime. Note that in the table, only prime values of \(a\) appear. This is a rather broad hint. Find a counterexample to Conjecture 3.4.1.

There can be times when the search for a counterexample starts to feel really futile. Would you think it likely that a statement about natural numbers could be true for (more than) the first 50 numbers a yet still be false?

Hidden within Euclid's proof of the infinitude of the primes is a sequence. Recall that in the proof we deduced a contradiction by considering the number \(N\) defined by \begin{equation*} N = 1 + \prod_{k=1}^n p_k. \end{equation*}

Define a sequence by \begin{equation*} N_n = 1 + \prod_{k=1}^n p_k, \end{equation*} where \(\{p_1, p_2, \ldots , p_n\}\) are the actual first \(n\) primes. The first several values of this sequence are:

\(n\) \(N_n\)
\(1\) \(1+(2) = 3\)
\(2\) \(1+(2\cdot 3) = 7\)
\(3\) \(1+(2\cdot 3\cdot 5) = 31\)
\(4\) \(1+(2\cdot 3\cdot 5\cdot 7) = 211\)
\(5\) \(1+(2\cdot 3\cdot 5\cdot 7\cdot 11) = 2311\)
\(\vdots\) \(\vdots\)

Now, in the proof, we deduced a contradiction by noting that \(N_n\) is much larger than \(p_n\), so if \(p_n\) is the largest prime it follows that \(N_n\) can't be prime — but what really appears to be the case (just look at that table!) is that \(N_n\) actually is prime for all \(n\).

Exercise3.4.5

Find a counterexample to the conjecture that \(1+\prod_{k=1}^n p_k\) is itself always a prime.

Subsection3.4.1Exercises

  1. Find a polynomial that assumes only prime values for a reasonably large range of inputs. \hint{It sort of depends on what is meant by “a reasonably large range of inputs.” For example the polynomial \(p(x) = 2x+1\) gives primes three times in a row (at \(x=1,2\) and \(3\)). See if you can do better than that. }

  2. Find a counterexample to the conjecture that \(\forall a,b,c \in \Integers, a \divides bc \; \implies \; a \divides b \, \lor \, a \divides c\) using only powers of 2. \hint{The intent of the problem is that you find three numbers, \(a\), \(b\) and \(c\), that are all powers of \(2\) and such that \(a\) divides the product \(bc\), but neither of the factors separately. For instance, if you pick \(a=16\), then you would need to choose \(b\) and \(c\) so that \(16\) doesn't divide evenly into them (they would need to be less than \(16\)…) but so that their product is divisible by \(16\). }

  3. The alternating sum of factorials provides an interesting example of a sequence of integers. \begin{equation*} 1! = 1 \end{equation*} \begin{equation*} 2! - 1! = 1 \end{equation*} \begin{equation*} 3! - 2! + 1! = 5 \end{equation*} \begin{equation*} 4! - 3! + 2! - 1! = 19 \end{equation*} et cetera Are they all prime? (After the first two 1's.) \hint{ Here's some Sage code that would test this conjecture: n=1 for i in [2..8]: n = factorial(i) - n show(factor(n)) Of course it turns out that going out to \(8\) isn't quite far enough… }

  4. It has been conjectured that whenever \(p\) is prime, \(2^p - 1\) is also prime. Find a minimal counterexample. \hint{I would definitely seek help at your friendly neighborhood CAS. In Sage you can loop over the first several prime numbers using the following syntax. for p in [2,3,5,7,11,13]: If you want to automate that somewhat, there is a Sage function that returns a list of all the primes in some range. So the following does the same thing. for p in primes(2,13): }

  5. True or false: The sum of any two irrational numbers is irrational. Prove your answer. \hint{This statement and the next are negations of one another. Your answers should reflect that.}

  6. True or false: There are two irrational numbers whose sum is rational. Prove your answer. \hint{If a number is irrational, isn't its negative also irrational? That's actually a pretty huge hint.}

  7. True or false: The product of any two irrational numbers is irrational. Prove your answer. \hint{This one and the next are negations too. Aren't they?}

  8. True or false: There are two irrational numbers whose product is rational. Prove your answer. \hint{The two numbers could be equal couldn't they?}

  9. True or false: Whenever an integer \(n\) is a divisor of the square of an integer, \(m^2\), it follows that \(n\) is a divisor of \(m\) as well. (In symbols, \(\forall n \in \Integers, \forall m \in \Integers, n \mid m^2 \; \implies \; n \mid m\).) Prove your answer. \hint{Hint: List all of the divisors of \(36 = (2\cdot 3)^2\). See if any of them are bigger than \(6\).}

  10. In an exercise in Section 3.2 we proved that the quadratic equation \(ax^2 + bx + c = 0\) has two solutions if \(ac \lt 0\). Find a counterexample which shows that this implication cannot be replaced with a biconditional. \hint{We'd want \(ac\) to be positive (so \(a\) and \(c\) have the same sign) but nevertheless have \(b^2-4ac > 0\). It seems that if we make \(b\) sufficiently large that could happen.}