Hacker News Reader

Comment by quietbritishjim | Hacker News Reader

This statement can be proved without contradiction (except the little one in the middle mentioned in the current answer):

(1) Given a finite set of primes {p_1, ... p_n}, then there exists another prime not in that set.

However, turning that into the following statement does require proof by contradiction (or, equivalently, the law of the excluded middle):

(2) There are an infinite number of primes

Euclid himself made statement (1) and proved it without contradiction, so looking at the original source gives the impression that you don't need it. But (2) is so similar-looking that many people incorrectly make the deduction that it doesn't need proof by contradiction either.

View on HN

You could state (2) as a contrapositive where your re-phrasing of (2) is:

If A is the set of all primes, then A is an infinite set.

Contrapositive proof: Suppose A is a finite set containing only primes. By (1) we know there exists some p not in A and therefore A is not the set of all primes.

I don't believe contrapositive needs law of excluded middle but I'm honestly not sure. Logic is not my area

Oops, perhaps I meant proof by contradiction is equivalent to contrapositive (rather than equivalent to law of excluded middle). If you write out a classic high school proof by contradiction formally, then you find yourself basically writing out the contrapositive.

Let's say you know A and ~B=>~A, then you can deduce B. Proof by contradiction: assume otherwise, i.e. ~B, then by ~B=>~A you have ~A, but that contradicts A.

So if you have ~B=>~A then you have A=>B.

Okay yup, turns out this is correct and it's slightly upsetting to me honestly haha. Just for someone else if they're interested where contrapositive and contradiction both use law of excluded middle (the ==* step requires it):

Contrapositive:

A-> B == A or ~B == ~B or A ==* ~B or ~(~A) == ~B -> ~A

Contradiction:

~(~A and B) == ~~A or ~B ==* A or ~B == A -> B

You might be interested to know that in intuitionistic logic, you still have a one-sided contrapositive law, i.e. (A > B) > (~B > ~A):

  [1] A > B(assumption)
  [2] ~B (assumption)
  [3] A (assumption)
  [4] B (modus ponens on 1 and 3)
  [5] ~A (proof of negation on 3, 4 and 2)

It's only the converse that no longer holds. In general familiar equivalences from classical logic are still valid in intuitionistic logic but only in one direction.

Reply on news.ycombinator.com