proofs

What Proofs are in Mathematics and Why Bother?

This FAQ is about proofs. Proofs are central to mathematics, and writing proofs is for many people a skill that is hard to master. There are actually two separate skills that one must master: finding the proof and communicating the proof. We will try to focus on the former here, but we will try to say something about the latter anyway.

What is a proof?
A proof is a convincing statement about why something is true. Furthermore, a proof can use only definitions, axioms, and previously proven theorems or lemmas. By its very nature, a proof uses deductive reasoning and not empirical arguments. For example, let’s say you want to prove that [itex]n^2-n+41[/itex] is prime for all natural numbers n. One cannot prove such a thing by checking a few cases and noticing that it is true in these cases. Indeed, a proof must indicate why something is valid in all cases, with no exceptions.

In logic, we often work with “formal proofs”. These are proofs with a very rigid structure and contain only symbols and not words.  They are often quite difficult to read. In theory, all proofs should be “formal proofs”, but this would be unmanageable. Instead, mathematicians write informal proofs that are easy to read, but still convincing enough. Note, however, that every good informal proof can be written as a formal proof. It’s not practical to do so, though. The site http://us.metamath.org/ offers a wide variety of formal proofs.

Why bother with proofs?
Why not follow the method of other sciences? Just make a large number of experiments and form a conclusion based on those experiments. Surely, if a statement has been shown for a large number of cases, then the statement should be true?

This reasoning goes against the heart of mathematics. In mathematics, we don’t just want the statement to hold for “most cases”, we want to make the statement work for “all cases”. Mathematics tries to provide results that are 100% true or 100% false. A result that holds for “most cases” is uninteresting (unless one can rigorously define what “most cases” means).

In a previous paragraph, we were asked to prove that [itex]n^2-n+41[/itex] is always prime. One could argue that we can just test the statement for a number of cases, for example

If n=1, then [itex]n^2-n+41=41[/itex]
If n=2, then [itex]n^2-n+41=43[/itex]
If n=3, then [itex]n^2-n+41=47[/itex]
If n=4, then [itex]n^2-n+41=53[/itex]
If n=5, then [itex]n^2-n+41=61[/itex]
If n=6, then [itex]n^2-n+41=71[/itex]
If n=7, then [itex]n^2-n+41=83[/itex]
If n=8, then [itex]n^2-n+41=97[/itex]
If n=9, then [itex]n^2-n+41=113[/itex]
If n=10, then [itex]n^2-n+41=131[/itex]

We can go on to n=20 or n=30 and find only primes. So one could say that this proves that we only get primes. But this is false. For n=41, we get something that is not a prime:

[tex]41^2-41+41=41^2.[/tex]

So the statement is in fact false. There are other statements that seem to hold for billions and billions of cases but eventually fail.

What methods of proof are there?
There are several methods of proofs available. It takes practice and experience to know which method of proof one should actually use. Let’s try to give the most important methods:

Direct proof:
This is the most simple method available. You start from your assumptions and end up with the conclusion.

As an example, let’s prove that the square of an odd integer is always odd:

An odd integer has the form 2n+1. When we square this, we get [itex](2n+1)^2=4n^2+4n+1=2(2n^2+2n)+1[/itex]. This has the form 2m+1 (with [itex]m=2n^2+2n[/itex] and thus is odd.

We did leave out some details, such as why anything of the form 2m+1 is odd. But overall, this proof should be convincing enough.
As another example, let’s take a polynomial [itex]aX+b[/itex] and let’s show that [itex]\frac{-b}{a}[/itex] is always a root of this polynomial (provided that [itex]a\neq 0[/itex]).

We must prove that
[tex]a\left(\frac{-b}{a}\right) + b=0[/tex]
Let’s simplify the left-hand side
[tex]\begin{eqnarray*}
LHS
& = & a\left(\frac{-b}{a}\right) + b\\
& = & \frac{-ba}{a} + b\\
& = & -b+b\\
& = & 0\\
\end{eqnarray*}
[/tex]

As you can see, we just stated what we need to prove, made some calculations, and ended up with the result. This is essentially what a direct proof is.

Proof by contradiction
The idea behind the proof of contradiction is that there are two possibilities: the things we are required to prove is correct or it is incorrect. Instead of directly proving that it is correct, we actually show that it cannot be incorrect. To show that it cannot be incorrect, assume that it is incorrect and derive a contradiction (an absurd statement).

Let us use a proof by contradiction to actually show the converse of what we proved in the last section. That is: if n is an integer such that [itex]n^2[/itex] is odd, then n must be odd.
So assume that n is an integer such that [itex]n^2[/itex] is odd. There are 2 possible cases: n can be odd or n can be even. If we show that n cannot be even, then it must be odd.

So, assume that n is even, then it has the form n=2k. But then [itex]n^2=(2k)^2=4k^2=2(2k^2)[/itex]. This has the form 2m (with [itex]m=2k^2[/itex]), thus [itex]n^2[/itex] is even. But we made the assumption that [itex]n^2[/itex]was odd, so we have reached a contradiction. So, n cannot be even (otherwise [itex]n^2[/itex] must be even), hence n must be odd.

A proof by contradiction seems something farfetched, but it actually isn’t. We do such things every day, we just don’t think about it. For example, let’s say that we want to solve the following (very easy) sudoku:

[tex]\begin{array}{|c|c|} 1 & \\ \hline \\ & \\ \end{array}[/tex]

So, we have to write 1 and 2 in the above square, but we cannot have two identical numbers in the same row or in the same column. Reasoning we often apply is the following:

We can write a 0 or a 1 next to the 1 in the first row. But if we would write a 1, then we would have identical numbers in the first row. This is forbidden (i.e. this is a contradiction), thus we have to place a 0 next to the 1.
We can write a 0 or a 1 under the 1 in the first row. But if we were to write a 1, then we would have identical numbers in the first column. This is a contradiction, thus we have to place a 0 under the 1.

As you can see, we have actually used a proof by contradiction to solve the puzzle. So a proof by contradiction might not be as unnatural as you might think.

Proof by induction
A proof by induction is often used when we have to proof something for all natural numbers. The idea behind the proof by contradiction is that of falling dominoes. If we set up a sequence of dominoes next to each other, and if we push the first domino, then all dominoes will fall. Indeed: the first domino falls because we push it, the second domino falls because it is pushed by the first domino, the third domino will fall because it is pushed by the second domino,…

The same idea is used by the proof of induction. In such a proof, we prove two things:

  • The statement holds for a certain specific value a.
  • If the statement holds for n, then it holds for n+1.

The result is that the statement must hold for all numbers larger than a. Indeed, the statement holds for a by the first point. But the second point says that if it holds for a, then it must hold for a+1. But since it holds for a+1, it must hold for a+2. And thus it must hold for a+3, a+4, a+5, etc. by applying the second point over and over again. In the end, it will hold for all numbers greater than a.

Let’s give an example. Let’s prove that [itex]1+2+3+…+n=\frac{n(n+1)}{2}[/itex]. This is a typical statement that uses a proof by induction.

  • The statement certainly holds for n=1, since [itex]1=\frac{1(1+1)}{2}[/itex].
  • Assume now that the statement holds for n, that is: we know that [itex]1+2+3+…+n=\frac{n(n+1)}{2}[/itex] (this is called the induction hypothesis). We must show that the statement holds for n+1. That is, we must show that [tex]1+2+3+…+n+(n+1)=\frac{(n+1)(n+2)}{2}[/tex]

But this is easy, since we know the result for n:

[tex]\begin{eqnarray*}
1+2+3+…+n+(n+1)
& = & \frac{n(n+1)}{2}+(n+1)\\
& = & \frac{n^2+n}{2}+\frac{2n+2}{2}\\
& = & \frac{n^2+3n+2}{2}\\
& = & \frac{(n+1)(n+2)}{2}\\
\end{eqnarray*}[/tex]

Let’s do another example. Let’s prove the inequality of Bernouilly. This states that [itex](1+x)^n\geq 1+nx[/itex] for positive integers n and x a real number greater than -1. So, let’s do induction on n:

  • The statement holds for n=0, since [itex]1=(1+x)^0=1+0x=1[/itex].
  • Assume that the statement holds for n, that is: we know that [itex](1+x)^n\geq 1+nx[/itex]. We must show that it also holds for n+1. Thus we must show that[tex](1+x)^{n+1}\geq 1+(n+1)x[/tex]

Indeed, we know that [itex](1+x)^n\geq 1+nx[/itex]. Because [itex]x+1\geq 0[/itex], we can multiplicate both sides by x+1. This yields

[tex](1+x)^n(1+x)\geq (1+nx)(1+x)[/tex]

or

[tex](1+x)^{n+1}\geq 1+(n+1)x+x^2\geq 1+(n+1)x[/tex]

since [itex]x^2[/itex] is always positive.

How to write down good proofs
Writing down and communicating proofs is a skill to master. First of all, you must keep in mind the level of the audience. Presenting a proof for a high-schooler is very different from presenting a proof for an audience of math professors. In the former case, you must go quite slow and explain everything. In the latter case, you can safely skip the boring or easy parts.

Contrary to what many beginning students think, it is not ok to write many symbols in proofs. A proof should mostly consist of texts and explanations of what you are doing. Calculations must still be made, but be sure to accompany them with some texts and explanations.

For example, a bad proof for the statement “if n is odd, then [itex]n^2[/itex] is odd” is

[tex]n=2k+1 ~\Rightarrow~ n^2=(2k+1)^2=4k^2+4k+1 ~\Rightarrow~ \exists m:~n^2=2m+1[/tex]

Sure, this is correct, but it is quite intensive for the reader to see what you are doing. Better would be not to write symbols like [itex]\Rightarrow[/itex] or [itex]\exists[/itex]. And best would be to replace them with a guiding text.

Further reading
Be sure to check out wiki’s page on mathematical proofs: http://en.wikipedia.org/wiki/Mathematical_proof
For a lot of tips on how to write proofs and mathematical texts, see tex.loria.fr/typographie/mathwriting.pdf

Contributors
bcrowell
mathwonk
micromass

Click For Forum Comments

28 replies
  1. Mark44 says:

    [QUOTE=”glaucousNoise, post: 5245299, member: 570615″]perhaps you should stop debating the philosophy of mathematical proofs then[/QUOTE]
    You’re the one who keeps wanted to steer the thread in this direction. Much of this thread has been a discussion of the Insights article in the first post. Later, the discussion went off on somewhat of a tangent about computers being used to prove mathematical statements.

  2. glaucousNoise says:

    [QUOTE=”lavinia, post: 5244721, member: 243745″]These Forums are not for Philosophy (which is why I always object to the term “real world”) and this should be taken off line.[/QUOTE]
    perhaps you should stop debating the philosophy of mathematical proofs then

  3. lavinia says:

    [QUOTE=”glaucousNoise, post: 5244681, member: 570615″]definitely seems as though aikismos, lavinia, and myself would enjoy from a new insights post on the philosophy of mathematical proof if we can find some qualified people![/QUOTE]

    These Forums are not for Philosophy (which is why I always object to the term “real world”) and this should be taken off line.

  4. glaucousNoise says:

    definitely seems as though aikismos, lavinia, and myself would enjoy from a new insights post on the philosophy of mathematical proof if we can find some qualified people!

  5. aikismos says:

    Hmmm. Certainly a good rebuttal about the nature of mathematical proof. Obviously, the FAQ in question is severely simplified, so maybe an intermediate FAQ could be created? My experience has been that even mathematical undergraduates often have questions about the nature of proof in math as it’s generally an aside in class and an appendix in the textbook, and that the same sort of scholastic rigor isn’t applied to examining the topic like it is in science.

    Okay, you raise some good points, so let me clarify.

    1) Yes, mathematical physics has embraced computation and modeling, but it does so as an abductive appendage to what is primarily an inductive pursuit, and strictly speaking mathematical models of the universe aren’t empirical science per se which traditionally moves from intersubjective observation of phenomena to predictive logical statements (obviously inseparable from set-theoretic and arithmetic relations) which are often infused with qualitative overtones for future predictions. Sure, they’re both math in one sense, but where they come from and where they arrive at are very distinct. In this way, I would say that mathematical theories and scientific theories are entirely different beasts. Scientific theories use mathematical theories as building blocks in their proof. That’s why in the popular media when famous physicists like Seth Lloyd say “the universe is a computer” or Marvin Minsky says “we may be living in a simulations”, there’s a lot of linguistic merit to what they say (because these are only analogies), but the statements are metaphysical, and NOT scientific. (Anyone who literally believes the universe is a computer, and we are software would have to prove the existence of hardware because information always exists in a medium, and if the medium is information, then another layer of regress!). Mathematical physics is like a calculator to the notebook of science and measurement of the world around us, and the nature of their proofs are still distinct. Simulation isn’t proof of causality.

    2) In regards to mathematical theories, let me say that I understand your use of the term now, and I apologize for presuming you were making the simple error I referred to. Obviously you’re knowledgeable in mathematical proof. But in the sense that it tends to be used, number theory, for example, it’s just a synonym for discipline. Obviously among the mathematically literate it’s still used as you used it, and that’s to describe an overarching collection of proofs moving in a general direction or by a theme. I do accept the point that mathematical proof is completely a function of a philosophy of math and the selection of assumptions be they axioms, postulates, or first-order predicates, etc. however, the nature of what constitutes mathematical phenomena is largely been accepted in the scientific community to be a function of human cognitive states, and therefore is embodied in the mind and explored not soley through phenomenological techniques, though they still play a role, but through correlates among neurofunction as observed by fMRI, objective measures of mathematical performance, and simple introspection. (See [URL]https://en.wikipedia.org/wiki/Where_Mathematics_Comes_From[/URL]) Note also, that I make no such claim about mathematicians who seem to violate a symmetry of using science to practice math as scientists actually practice math. (Plato has cursed the philosophy of math, in the same way Aristotle cursed science, IMO.) So, yes, they are theories, but in a way, unlike a scientific theory which is true because evidence supports it, mathematical theory is true by assumption. For example, Euclidian theory is equally as relevant as non-Euclidian theories of mathematics.

    3) “What you are saying is that you can deduce elliptical orbits from Newton’s Laws and certain initial conditions – as one would do with any differential equation.” No, I think that’s a mischaracterization, although I’m sympathetic to your simplification. Let me reiterate. Yes, one can deduce the model even with initial conditions, but in deduction by definition of the process itself, the initial conditions are irrelevant to the conclusion and therefore the deductive proof the model of the orbit can be proven, but that proof is mathematical and not scientific, where as using the deductive proof as a model to make a scientific prediction which can be verified against intersubjective measure is the scientific proof and is therefore much greater in scope. In this way, scientific theory (primarily the math deduction of a model) only plays a role in scientific practice of theory building.

    Please let me know if this is clear, because the nature of mathematical and scientific proof are relevant to my pursuit of establishing a metaphysics of STEM which is rigorous. I’d certainly love rebuttals and rejoinders on where you draw the lines around mathematical proof.

  6. lavinia says:

    [QUOTE=”aikismos, post: 5244572, member: 564756″]1) Math isn’t really considered a science anymore, and that is an old fashioned language popular during the time of Gauss. The scientific methods have diverged substantially from the mathematical methods although really both are quite severely intertwined in practice. Proof is used by science and logic and even law and argumentation, but this article is just about math proof, so no need to get all technical on the divergence of the term ‘proof’ itself.[/QUOTE]

    In fact, mathematics and theoretical physics have converged in the last century.

    [QUOTE]
    2) Theories aren’t arrived at from deduction of axioms. I think you meant theorems. The former is scientific nomenclature for assertions, while the latter is mathematical.
    [/QUOTE]

    True but there are mathematical theories just as there are empirical theories. In fact, these theories are what mathematicians study – and invent. In some sense one can consider mathematics to be empirical since its theories are derived from examining mathematical phenomena – not to mention so called “real world” phenomena. As an example of a theory that is being actively researched today, take look at the theory of differential extensions of homology theories. For a classical example, look at Riemann’s theory of algebraic functions.

    [QUOTE]
    3) While Pythagorean’s Theorem can be proven from algebraic or geometric theorems, actual elliptical orbits are never deduced strictly from Newton’s laws. Strictly speaking, specific ellipses can be even in mathematical models, but elliptical orbits are physical phenomena which require initial states obtained through astronomical measurements and are actually subject to complicated gravitational fields (the two-body problem is an ideal and simple model). Then after modeling, generally physical orbits have to be checked against more measurements.[/QUOTE]

    What you are saying is that you can deduce elliptical orbits from Newton’s Laws and certain initial conditions – i.e. you are solving a differential equation.

  7. aikismos says:

    [QUOTE=”Mark44, post: 5244641, member: 147785″]My complaint about this is that the proofs were done beforehand — for example, that ##pi = 4sum_{n = 0}^{infty} frac{(-1)^n}{2n + 1}## (Gregory-Liebniz series), to name just one formulation. There are many more here – [URL=’https://en.wikipedia.org/wiki/Approximations_of_%CF%80′]https://en.wikipedia.org/wiki/Approximations_of_π[/URL]. The role of the computer was to to the arithmetic, not the actual proof.[/QUOTE]

    Ahhh, that clarifies what you meant when you said “being used for a proof” in the OP. You’re talking more about symbolic computation. [URL]https://en.wikipedia.org/wiki/Automated_theorem_proving[/URL] Thanks for clarifying your statement. According to ([URL]https://en.wikipedia.org/wiki/Automated_theorem_proving[/URL]), it looks like one of the first use of automation of proofs occurred in the early 1950’s. To wit:

    ‘In 1954, [URL=’https://en.wikipedia.org/wiki/Martin_Davis’]Martin Davis[/URL] programmed Presburger’s algorithm for a [URL=’https://en.wikipedia.org/wiki/JOHNNIAC’]JOHNNIAC[/URL] vacuum tube computer at the [URL=’https://en.wikipedia.org/wiki/Princeton_Institute_for_Advanced_Study’]Princeton Institute for Advanced Study[/URL]. According to Davis, ‘Its great triumph was to prove that the sum of two even numbers is even”‘”.

    Hey, maybe the FAQ could contain a brief mention in the opening that computers are now doing the work of mathematicians?

  8. Mark44 says:

    [QUOTE=”aikismos, post: 5244623, member: 564756″]:) Not a stretch at all, and in fact, for two-thousand years, arguments over the nature of proof of fractions to approximate constants have raged between some math minds greater than you or I. As proof that rational approximations of irrational constants requires proof, cite me any irrational approximation, and I will show you that the value was derived from a mathematical technique PROVEN to be true.[/QUOTE]
    My complaint about this is that the proofs were done beforehand — for example, that ##pi = 4sum_{n = 0}^{infty} frac{(-1)^n}{2n + 1}## (Gregory-Liebniz series), to name just one formulation. There are many more here – [URL]https://en.wikipedia.org/wiki/Approximations_of_%CF%80[/URL]. The role of the computer was to to the arithmetic, not the actual proof.

  9. aikismos says:

    [QUOTE=”Mark44, post: 5244606, member: 147785″]That’s really a stretch, IMO. There is a huge difference between a Univac-era computer cranking out the decimal digits of ##pi##, as compared to a computer tabulating all possible ways that a map could be colored using four colors.[/QUOTE]

    :) Not a stretch at all, and in fact, for two-thousand years, arguments over the nature of proof of fractions to approximate constants have raged between some math minds greater than you or I. As proof that rational approximations of irrational constants requires proof, cite me any irrational approximation, and I will show you that the value was derived from a mathematical technique PROVEN to be true. Now granted we don’t teach them in school (and hence our lack of familiarity with the thousands of proofs used to find values for pi), but our ignorance doesn’t imply that those proofs don’t exist (they clearly do and are argued like any other) or that they are irrelevant (science relies heavily on math constants for their calculations). When anyone says that pi is about 3.1415, it’s not an assumption, but a proven approximation. Both Karl Gauss and Leonard Euler devised proofs for approximations of pi. Of course, if you’re suggesting your views on proof bear more weight, than I can respect your self-confidence. ;) Perhaps you’re just biased towards proofs in discrete mathematics over real analysis?

    Oh, and to show you that the approximation of pi relies on a mathematical proof, here’s an interesting case where a crank almost got a wrong value of pi passed as state law in the US. (To be fair the legislators were in Indiana). You may have never thought about it, and it may not give you the warm fuzzies, but fractions to approximate irrational values aren’t picked out of a hat. They’re proven with algebraic axioms to be true. :D [URL]https://en.wikipedia.org/wiki/Indiana_Pi_Bill[/URL]

  10. Mark44 says:

    [QUOTE=”aikismos, post: 5244598, member: 564756″]Technically speaking, the approximation of irrational values to rational ones (such as those historically used as constants in calculations involving Pi) ARE theorems.[/QUOTE]
    That’s really a stretch, IMO. There is a huge difference between a Univac-era computer cranking out the decimal digits of ##pi##, as compared to a computer tabulating all possible ways that a map could be colored using four colors.

  11. aikismos says:

    [QUOTE=”Mark44, post: 5244588, member: 147785″]I was talking about using computers in proofs of theorems, not for calculating numbers, such as the digits of ##pi##.[/QUOTE]
    Technically speaking, the approximation of irrational values to rational ones (such as those historically used as constants in calculations involving Pi) ARE theorems.

  12. Mark44 says:

    [QUOTE=”Mark44, post: 5241400, member: 147785″]The first time that I recall computers being used for a proof was back in the mid-70s, in the Four Color Problem.[/QUOTE]
    [quote=aikismos]I’m pretty sure that computerized proofs go back to mechanical computers computing Pi. [/quote]I was talking about using computers in proofs of theorems, not for calculating numbers, such as the digits of ##pi##.

  13. aikismos says:

    [QUOTE=”Mark44, post: 5241400, member: 147785″]Go ahead and start one, if you like. The first time that I recall computers being used for a proof was back in the mid-70s, in the Four Color Problem.[/QUOTE]
    I’m pretty sure that computerized proofs go back to mechanical computers computing Pi. If you’d like… I have a simple but informative source and could find this if you’d like.

  14. aikismos says:

    [QUOTE=”lavinia, post: 5242198, member: 243745″]A concise and clear description of what a proof is.

    1) One might add that proof is used in all scientific theories. The difference in mathematics is that proof gives certainty while in other sciences it does not. All theories deduce conclusions from axioms. Just as the Pythagorean theorem may be deduced from the axioms of Euclidean geometry so can elliptical orbits of a two body system be deduced from Newton’s Laws. Proof is not unique to mathematics.

    2) I think this sentence is badly stated.

    “This reasoning goes against the heart of mathematics. In mathematics, we don’t just want the statement to hold for “most cases”, we want to make the statement work for “all cases”. Mathematics tries to provide results that are 100% true or 100% false. A result that holds for “most cases” is uninteresting (unless one can rigorously define what “most cases” means).”

    Any theory wants to define conditions in which certain principles hold always.[/QUOTE]

    1) Math isn’t really considered a science anymore, and that is an old fashioned language popular during the time of Gauss. The scientific methods have diverged substantially from the mathematical methods although really both are quite severely intertwined in practice. Proof is used by science and logic and even law and argumentation, but this article is just about math proof, so no need to get all technical on the divergence of the term ‘proof’ itself.

    2) Theories aren’t arrived at from deduction of axioms. I think you meant theorems. The former is scientific nomenclature for assertions, while the latter is mathematical.

    3) While Pythagorean’s Theorem can be proven from algebraic or geometric theorems, actual elliptical orbits are never deduced strictly from Newton’s laws. Strictly speaking, specific ellipses can be even in mathematical models, but elliptical orbits are physical phenomena which require initial states obtained through astronomical measurements and are actually subject to complicated gravitational fields (the two-body problem is an ideal and simple model). Then after modeling, generally physical orbits have to be checked against more measurements.

    4) “This reasoning goes against the heart of mathematics. In mathematics, we don’t just want the statement to hold for “most cases”, we want to make the statement work for “all cases”. Mathematics tries to provide results that are 100% true or 100% false. A result that holds for “most cases” is uninteresting (unless one can rigorously define what “most cases” means).” – I think that given the target audience, this sentence is fair with the caveat that we obviously redefine our domains to make our statement (entirely) true or false. Once you start saying 100%, then we’re moving into fuzzy sets!

  15. lavinia says:

    A concise and clear description of what a proof is.

    1) One might add that proof is used in all scientific theories. The difference in mathematics is that proof gives certainty while in other sciences it does not. All theories deduce conclusions from axioms. Just as the Pythagorean theorem may be deduced from the axioms of Euclidean geometry so can elliptical orbits of a two body system be deduced from Newton’s Laws. Proof is not unique to mathematics.

    2) I think this sentence is badly stated.

    “This reasoning goes against the heart of mathematics. In mathematics, we don’t just want the statement to hold for “most cases”, we want to make the statement work for “all cases”. Mathematics tries to provide results that are 100% true or 100% false. A result that holds for “most cases” is uninteresting (unless one can rigorously define what “most cases” means).”

    Any theory wants to define conditions in which certain principles hold always.

  16. Mark44 says:

    [QUOTE=”glaucousNoise, post: 5241362, member: 570615″]Mark44 got mad at me (reasonably, I think) for making the thread somewhat off topic. If somebody wants to create a new thread which discusses the merits of proof in the 21st century world of big data and supercomputers, I would love to have that discussion.[/QUOTE]
    Go ahead and start one, if you like. The first time that I recall computers being used for a proof was back in the mid-70s, in the Four Color Problem.

  17. glaucousNoise says:

    Mark44 got mad at me (reasonably, I think) for making the thread somewhat off topic. If somebody wants to create a new thread which discusses the merits of proof in the 21st century world of big data and supercomputers, I would love to have that discussion.

  18. Mark44 says:

    [QUOTE=”Krylov, post: 5239817, member: 571630″]I believe it is “Bernoulli” instead of “Bernouilly”.[/QUOTE]
    I agree. [USER=205308]@micromass[/USER], [USER=211768]@bcrowell[/USER], or [USER=13785]@mathwonk[/USER], one of you might want to take care of this.

  19. andrewkirk says:

    [QUOTE=”glaucousNoise, post: 5238197, member: 570615″]doesn’t searching for problems where it is possible to obtain a binary true or false answer severely limit the problems you can look at?[/quote]Every question that has a non-binary answer, such as ‘What is the value of ##e^{ipi}##?’, when given an answer, has a supplementary question: ‘[I]How do you know[/I]?’, to which the answer is a proof.

    Indeed, in a sense a proof is an answer to the question ‘[I]How do you know that P[/I]?’ where [I]P[/I] is some proposition. That is a non-binary question. Yes or No doesn’t cut it as a proof.
    [quote]it seems as though the vast majority of problems will be “unprovable.”[/QUOTE]I personally feel that is right, because of some vague, unformed connection to Godel’s First Incompleteness Theorem. But it’s just a feeling and, since the set of possible propositions is infinite, and the subsets that are provable and unprovable given any given logical language and set of non-logical axioms, both have cardinality ##aleph_0##, it’s not clear what we could mean by ‘the vast majority’.

  20. Mark44 says:

    [QUOTE=”glaucousNoise, post: 5238197, member: 570615″]doesn’t searching for problems where it is possible to obtain a binary true or false answer severely limit the problems you can look at?
    [/quote]So what? You’re missing the point of this article, which is a short description of some types of proofs in mathematics. Each proof justifies a given statement in mathematics, which is either true or false. A proof gives us confidence that the statement is true.

  21. glaucousNoise says:

    [QUOTE=”jbriggs444, post: 5238266, member: 422467″]Any problem that has a real-valued numeric answer can, in principle, be answered by posing an infinite sequence of yes or no questions. This is one of the ways that the computability of a real number is phrased within the mathematics of computing.

    Since the number of finitely expressible problems is countably infinite, the notion of a “majority” is not clear cut. But yes, not all problems can be solved.[/QUOTE]
    I don’t care about “in principle”, I want in practice, and any definition of the space of possible problems which is not finite is meaningless since we’re only interested in a) the space of problems at a fixed point in time and b) problems which exceed a certain cutoff in interest.

  22. jbriggs444 says:

    [QUOTE=”glaucousNoise, post: 5238197, member: 570615″]doesn’t searching for problems where it is possible to obtain a binary true or false answer severely limit the problems you can look at?
    [/QUOTE]
    Any problem that has a real-valued numeric answer can, in principle, be answered by posing an infinite sequence of yes or no questions. This is one of the ways that the computability of a real number is phrased within the mathematics of computing.

    [QUOTE]it seems as though the vast majority of problems will be “unprovable.”[/QUOTE]
    Since the number of finitely expressible problems is countably infinite, the notion of a “majority” is not clear cut. But yes, not all problems can be solved.

  23. jbriggs444 says:

    There appears to be a typo in…

    [QUOTE]
    Proof by induction
    A proof by induction is often used when we have to proof something for all natural numbers. The idea behind the proof by [B][I]contradiction[/I][/B] is that of falling dominoes.
    [/QUOTE]

  24. andrewkirk says:

    Nice article. I like the list of tips in the linked text by Knuth et al too. I’ll read more of it at my leisure to try to improve my writing. I’ve a couple of comments:

    For me the worst flaw in proof writing is when the writer does not explain their steps. For example the justification for getting from one line to the next may be a result that was observed briefly in passing 20 pages ago and has not been mentioned since, but the author doesn’t reference it so the reader is left feeling stupid because they don’t remember the result and can’t understand how the step is justified. A number of widely-used physics texts do this frequently and I think it’s very poor. This is one area where reading symbolic logic proofs can actually be easier than reading some more wordy mathematical ones, because it is a requirement of a symbolic logic proof that the justification of every line be formally stated.

    The reason that many authors omit such justification is that it’s a lot of work to insert all the correct references. But for every two minutes that an author saves herself by not locating and inserting the justification ref, she has cost her readers collectively dozens, maybe hundreds of hours (depending on how many readers there are!) racking their brains and leafing through the book trying to work out the justification.

    Numbering all non-trivial equations is one way to make it much easier to include such refs.

    Knuth et al suggest varying one’s words in order to avoid monotony. For instance one might alternate ‘so’, ‘hence’, ‘therefore’, ‘it follows that’. My practice in the past has been to do that but now I am questioning it. One doesn’t read maths proofs for the beauty of their prose (that’s what poetry and fiction are for) but to gain understanding, and unnecessarily varying the terms used seems to me to be more likely to detract from understanding than to support it. A problem that sometimes arises is that, in the search for synonyms, the writer ends up using a word that has alternative possible meanings, and hence introduces ambiguity into the text. This is a matter for judgement and I imagine that there’s a sweet spot somewhere between the extremes of always using the same word and avoiding using the same key word twice in a paragraph. Currently I find I’m steering away from variety towards greater consistency and clarity in word choice, relative to where I was.

  25. Stephen Tashi says:

    [QUOTE]In logic, we often work with “formal proofs”. These are proofs with a very rigid structure and contain only symbols and not words.  They are often quite difficult to read. In theory all proofs should be “formal proofs”, but this would be unmanageable. Instead, mathematicians write informal proofs that are easy to read, but still convincing enough.[/QUOTE]That passage might make sense to a person who understands that "logic" refers to a specialized discipline.   However, in mathematics, I disagree with using terminology "formal proof" to mean a proof that only uses symbols.  The FAQ is useful to someone wanting to know "What is a proof?"  It doesn't provide practical guidance to people who want to know "How do I do a proof?".

  26. aikismos says:

    1) You say "There are actually two separate skills that one must master: finding the proof and communicating the proof." and that you focus on the former, but really, you're focusing on the later. Devising mathematical proofs (which usually involves abduction and often empirical calculation these days) isn't really covered in the article at all.2) You might also want to revise "A proof is a convincing statement" to say collection of statements to which logic is applied to arrive at a true conclusion. I've never seen a proof that is a single statement.3)  "By its very nature, a proof uses deductive reasoning and not empirical arguments." Proof is not strictly deductive in nature (see your article where you cite example and description of proof by induction). In fact, I think you might want to revise the article to contain Proof by Exhaustion as it is often used in education to show simple cases or is a part of larger proofs. It would be prudent to include the word counter-example in your example of the equation 412−41+41=412. Euclid didn't even do most of his research deductively. It's more of a communicational and didactic tool to use deduction than actual research math (which is way more creative and less constrictive than deduction).4) You might want to compare examples of a paragraph proof, two-column proof, and flow proof if you're trying to help math newbies understand the nature of proof. Most newbies are sloshed around different classes which may ask them to do each.Overall, a good start on a useful FAQ!

  27. glaucousNoise says:

    doesn't searching for problems where it is possible to obtain a binary true or false answer severely limit the problems you can look at?it seems as though the vast majority of problems will be "unprovable."

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply