Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Something from nothing?

      Proofs by contradiction
      Marianne Freiberger
      4 July, 2018
      3 comments

      "You can take it or leave it" is a phrase we use purely for effect. It's obvious that the person we're talking to is either going to take it or leave it — what else can they do? — so in terms of information content, the phrase is useless. It's an example of a logical tautology: something that is always true, no matter the circumstance. That's probably why the phrase is so annoying.

      Rabbit in hat

      Proving things non-cnostructively is a bit like pulling a rabbit out of a hat.

      Curiously, mathematicians frequently draw meaning from such vacuous tautologies. The phrase above is of the form P OR NOT P, where P is some statement ("you can take it") and NOT P is its negation ("you can not take it"="you can leave it"). According to the classical rules of logic, such a statement is always true — put differently, if P is true then NOT P is false and vice versa.

      This so-called law of the excluded middle allows mathematicians to perform logical magic. Suppose you want to show that some statement P is true. If you can show that NOT P is definitely false, then P has no choice but being true and you're done. You have proved the statement P without necessarily getting your hands dirty with the details of P. The technique is called a proof by contradiction, or reductio ad absurdum to use the Latin description.

      If this sounds confusing, here is an example. A prime number is a natural number that is only divisible by itself and 1. The first few primes are 2, 3, 5, and 7. The primes are like building blocks for all the natural numbers, because every natural number that is not itself a prime can be written as a product of primes in a unique way. For example, 24 = 2x2x2x3.

      We are going to prove that there are infinitely many prime numbers using a proof by contradiction. Suppose there are only finitely many and label them p1, p2, p3, up to pn. Now consider the number p=p1p2...pn+1. Because it's different from all the p1 up to pn, and these are all the primes there are, it cannot itself be a prime. But then, as we have noted above, it must be a product of primes. This means that one of our p1 up to pn must divide it. But since the p1 up to pn divide p−1=p1p2...pn, they can't possibly divide p as well. This is a contradiction. Hence, the statement that there are only finitely many primes is false. Therefore, its negation, that there are infinitely many primes must be true. Here the statement P is "there are infinitely many primes" and NOT P is "there are finitely many primes".

      Depending on your preference, you might find this an elegant argument, or you might feel a little cheated. OK, so there are infinitely many primes, but what are they? How do you find them? Our proof is an example of a non-constructive proof, which shows that something exists without actually constructing it.

      Mathematics, as it is accepted by most people, relies heavily on non-constructive proofs and proofs by contradiction. As the famous mathematician David Hilbert remarked in 1928, "Taking the law of the excluded middle from the mathematician would be the same, say, as proscribing the telescope to the astronomer or to the boxer the use of his fists."

      Constructive mathematics

      Should all of mathematics be explicitly constructed?

      Some people believe, however, that logically such proofs live on thin ice. The proofs purport to show that something exists (or is true) by showing that it can't possibly not exist (or be false). Is that really as convincing as proving that it exists by actually constructing it? A school of thought called constructivism believes that it isn't, and that we should only deal with mathematical objects that we can get our heads around in a concrete way. There should be a recipe, an algorithm, for calculating all the properties of the object in question. To borrow a phrase from the US mathematician Errett Bishop, everything in mathematics should have "numerical meaning".

      Constructivists reject the law of the excluded middle. To them, a statement of the form P OR NOT P is only true when we know for certain that one of P or NOT P is true. Until we have proved, constructively, that there are infinitely many primes or that there are finitely many primes, the statement "either there are infinitely many primes or finitely many primes" means nothing, and we certainly can't base a proof on it.

      What does this constructivist stance mean for mathematics as whole? Our prime number proof from above can quite easily be saved: there's a version that isn't based on contradiction. Given any finite list of prime numbers label them p1, p2, p3, up to pn. Form the number p=p1p2...pn+1 and find all its prime factors (if p is itself a prime, then it's the only number in its prime factorisation). The primes p1, p2, p3, up to pn cannot appear in the prime factorisation of p because they divide p−1 and therefore don't divide p. Thus, the prime factorisation of p provides us with at least one prime not on the original list. You can now repeat the process including the new prime(s) in your list to find yet more new prime(s). And so on. In this way, you can generate infinitely many primes.

      Can all proofs in mathematics be rewritten in a constructive way so easily? We examine this question, as well as the ins and outs of constructivism, in this article.


      About this article

      Marianne Freiberger is Editor of Plus.

      FQXi logo

      This article is part of our Who's watching? The physics of observers project, run in collaboration with FQXi. Click here to see more articles about constructivism.

      • Log in or register to post comments

      Comments

      Paulo

      16 July 2018

      Permalink

      Sorry to point such a minor mistake, but 24 = 2x2x2x3...

      • Log in or register to post comments

      Marianne

      18 July 2018

      In reply to Small mistake by Paulo

      Permalink

      Oh dear, thanks for pointing that out! We have corrected it.

      • Log in or register to post comments

      Stephen

      1 August 2018

      Permalink

      Proving things non-cnostructively is a bit like pulling a rabbit out of a hat.

      • Log in or register to post comments

      Read more about...

      logic
      philosophy of mathematics
      non-constructive proof
      proof
      law of excluded middle
      The physics of observers
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms