0

I have a quiz with the following question:

Which of the following describes proof by contradiction?

D) To prove P, assume that ∼P is true and arrive at a false statement, thus proving ∼P would also be false, which would make P true.

D) isn't the correct answer, but I can't see why. Could someone explain what's wrong with this description?

Thank you in advance.

Edit: Full question

E), "None of the above" was correct.

enter image description here

Community
  • 1
Charles Clayton
  • 109
  • 2
    You should put the other options up. There may be a better answer – JasonM Jun 11 '16 at 21:48
  • @JasonM The correct answer was "None of the above". But I've added the full question. – Charles Clayton Jun 11 '16 at 21:50
  • I think this assure that ~$P$ can't happen, but this not show that $P$ must happen – ett Jun 11 '16 at 21:51
  • 1
    I have two guesses: 1) This quiz is being extremely nitpicky, and instead of arriving at a false statement, you have to arrive at a statement you know to be false 2) There are several slight variations of the method of proof by contradiction, and the quiz insists on following one of those to the letter. In one of the variations, you assume ~P, and arrive at both Q and ~Q (for some Q), in another one of the variations, you assume ~P, and arrive at P. – dankness Jun 11 '16 at 21:56
  • To prove $P \implies Q$ by contradiction, you would need to assume both $P$ and $\lnot Q$, then arrive at a contradiction (neither of the first two choices do that). I still don't see anything wrong with your choice. – pjs36 Jun 11 '16 at 22:05
  • The correct answer should be of the form "To prove $P \implies Q$, assume $ \sim P$ and $Q$, and arrive at a false statement, thus proving $\sim P$ does not imply $Q$, so $P \implies Q$ – JasonM Jun 11 '16 at 22:06
  • @JasonM: Why is that? Proof by contradiction isn't limited to proving statements of the form $P \implies Q$? – joriki Jun 11 '16 at 22:07
  • @joriki True, but most statements can be phrased as an implication – JasonM Jun 11 '16 at 22:10
  • 1
    In my view, D describes proof by contradiction perfectly. Whoever set this question doesn't know what they're talking about. – TonyK Jun 11 '16 at 22:15
  • @joriki I'm just throwing out ideas for why D) could be wrong. – JasonM Jun 11 '16 at 22:16
  • The only improvement to D that I can think of is replacing "false statement" with "statement incompatible with ~$P$". But I still think the question is stupid. – TonyK Jun 11 '16 at 22:18
  • Okay, thanks everyone. I just wanted to see if I was missing something. I'll ask my professor on tuesday and report back here what the logic was. – Charles Clayton Jun 11 '16 at 22:49
  • D. is certainly the best answer of A through D, and I don't see anything wrong with it as a characterization of proof by contradiction. If E is supposedly correct then it's a "trick" question, too nitpicky for its own good (or for yours). If $\bot$ is a falsehood, then $(\neg P \to \bot) \to P$ is a tautology. If you "assume that $\neg P$ is true and arrive at a false statement" [e.g. $\bot$], then you have proved $(\neg P \to \bot)$, so by modus ponens, $P$. – BrianO Jun 11 '16 at 22:50
  • I have changed my mind: E is correct. See my answer. – TonyK Jun 12 '16 at 14:07

1 Answers1

1

Having panned the question in the comments, I have come to realise that D is in fact wrong. Let's consider a classic proof by contradiction: the infinitude of the primes. Let $P$ be the statement "There are an infinite number of primes." So we start by assuming ~$P$: there are a finite number of primes.

Now we say, OK, then there are $n$ primes for some $n$. And we use this assumption to prove that there are at least $n+1$ primes. But this is not a false statement! It is not even a statement incompatible with ~$P$, as I suggested in my second comment. It's more subtle than that.

So I retract my comments: E is the right answer.

TonyK
  • 64,559
  • 1
    Eh...in the case of the Euclid-style proof of the infinitude of primes there are some tricky matters with quantifiers going on. You say "suppose there are finitely many primes; then there exists $n$ such that there are exactly $n$ primes; I now present a prime which is not one of these; thus there are in fact at least $n+1$ primes; this contradicts the instantiated statement that there are exactly $n$ primes". – Ian Jun 12 '16 at 14:26
  • 1
    Thus you assumed there was some finite number of primes and derived a contradiction from that (namely that there exists $n$ such that the set of primes has exactly $n$ elements and also more than $n$ elements). – Ian Jun 12 '16 at 14:27
  • @Ian: I don't see your point (and I don't know what you mean by an instantiated statement). What do you disagree with, exactly? – TonyK Jun 12 '16 at 15:07
  • The aim is to prove there are infinitely many primes. So we first assume that there is some finite number of primes. Then we use existential instantiation to choose a number $n$ to be the total number of primes. Then we use existential instantiation again to obtain the set of all $n$ primes. Then we use Euclid's trick to obtain a new prime. So we have a contradiction: we have both the statement "there are exactly $n$ primes" and the statement "there are more than $n$ primes". – Ian Jun 12 '16 at 15:12
  • Now we have to propagate that contradiction back to our original assumption: we know now that "there are exactly $n$ primes" is false, but that didn't depend on which $n$ we picked, so now we know we can't existentially instantiate "there are finitely many primes", so that's false too. So here the false statement is not "there exist more than $n$ primes" but "there exist exactly $n$ primes and more than $n$ primes". – Ian Jun 12 '16 at 15:12
  • I think these comments just go to emphasise that the original multiple-choice question is extremely ill-judged. – TonyK Jun 12 '16 at 16:13