## What is a proof?

I recently described (here) a proof to be a convincing argument of why you think something is true. I’ll stick to that definition in spite of a few commenters who want there to be axioms or postulates, because I really don’t think that’s what happens in real life (which is a good thing! It would be an incredibly boring life!). Since I’m a utilitarian, I only care about and only want to discuss what actually happens.

The above definition immediately begs the question, convincing to whom? Can a proof to someone be a non-proof to someone else? Absolutely, proofs are entirely context-driven. If I’m trying to prove something to you and you remain unconvinced, then it is no proof, even if I’ve used the same argument before successfully.

This brings me to my first main point, which is that *it the responsibility of the person proving something to convince his or her audience that it’s true*. Likewise, it is the responsibility of the audience to remain skeptical (but attentive) and be open to being convinced or to finding a flaw in the argument.

Things get trickier when it’s not a live interaction, but when things are written down, like in published articles. On the one hand, written proofs give the audience more time to understand the reasoning and to come up with problems, but on the other hand there’s no opportunity to say “I just don’t get what you’re talking about,” which is the feeling one typically has at least 85% of the time.

In an ideal world, those who write proofs understand the goal to be that the reader should be able to understand the argument, and thus make the arguments coherent and understandable to their “typical reader.” Who is this typical reader? Someone who is probably relatively fluent in the basic objects of the field, say, but hasn’t recently thought about this problem.

Now that I’ve described the ideal situation, I’ll rant for a bit about how people game this system. There are two things that creep into the system that give rise to its gaming, and those two things are status and credit. People like to be high status (and like to signal high status even more), and of course people like to take credit.

First, status. It turns out that people often really want to explain their reasoning no to the typical audience, but to the expert audience. So they don’t give sufficient context, and they are lazy reasoners, because the experts can be expected to understand how to fill in the details.

It’s not only insecure young mathematicians that are guilty of this – there are plenty of experts who themselves fall prey to this habit (thus the signaling). I think it’s driven by a combination of feeling kind of smug and smart when people who are trying to follow your conversation leave because they’re exhausted and confused (and possibly ashamed), and the echo chamber that remains after people who don’t get it (or who admit to not getting it) leave. Whatever the reason, there are plenty of experts who get less and less understandable over time, in person and in print.

The other side of this status play is those experts get away with it. The papers written by these people are often accepted in spite of the fact that they are nearly unreadable to all but the 5 people in their field for whom they have been written, since after all, these guys are experts.

But does this approach constitute a proof? I claim it doesn’t, not if I have to be one of 5 people to read and understand it. The writer has choked, bigtime, on his or her responsibility to convince the reader.

Second, the credit thing. People want to get credit for proving things, because that’s how they get high status. But they don’t always want to prove everything they claim, because it’s hard work. So sometimes you see people proving something and then claiming an even more general thing is true, and giving a “sketch of a proof” for that more general thing (this is one example where “sketches” come up, but actually there are plenty of them).

Let’s examine that concept for a moment, the “sketch of a proof.” Usually this implies that the basic outline is there, but many details of how to rely on so-and-so’s theorem or what’s-his-name’s method are left out. It’s a proof lying in the shadows, and we’ve only seen it highlighted every few feet or so to wend our way through it.

Is a sketch a proof? No, it’s not. Best case scenario, it would take a typical reader a few minutes, maybe up to two hours, say, to turn that sketch into a proof.

But what if the typical reader can’t do it in two hours?

The problem with the concept of a sketch of a proof is that it’s too difficult to refute. If I am a reader and I say, “this is a false sketch” then I could just be opening myself up to people who tell me I didn’t spend my two hours wisely, or that I’m not good enough to complain about it. They may even expect me to prove that that method *cannot be used* to prove that result.

But that’s bullshit! As far as I’m concerned, if you claim to have sketched a proof, and if I’ve tried to prove it using your notes and I’ve failed, then that’s *your* fault, not mine. It’s your responsibility to prove it to me, and you haven’t.

Conclusion: let’s all remember when you claim a result, you are claiming credit, and it’s your responsibility to convince the audience it’s true – not just 5 experts. And second, if you aren’t willing to actually prove something, don’t claim it as a result. Instead, say something like, “this *may* generalize using so-and-so’s theorem or what’s-his-name’s method….”. Consider it a gift to the next person who reads your paper and wants to prove something new.

Read Euclid’s “Elements” for a fascinating look into what was considered a proof back in the old days, and the quality of the arguments from the Skeptics he had to overcome!

I think there’s a lot of wiggle room in “typical reader.” When I was a graduate student I would certainly say I was “relatively fluent in the basic objects” of number theory, but it certainly took me much, much longer than 2 hours to understand and satisfy myself as to the correctness of, say, Barry’s paper on rational isogenies of prime degree. And I think it would be truly weird to say that paper contains only sketches of proofs, or to say that it should have been five times as long in order to include every detail that I worked out myself.

I recall back in HCSSIM ’71, Peter Miletta had lots of choice thoughts on this topic. Perhaps Kelly or Don might recall.

Cathy, I really agree with what you are saying. However, I worry that people who have not spent considerable time thinking about math (and preferrably doing math) are going to misinterpret this conversation. There is a difference between “proof” as in “idealized proof”, which can be made perfectly precise using rules of semantics, etc., and “proof” as in “pieces of text or speech used by mathematicians to convince other mathematicians”. I am concerned because there is a history of non-experts confusing the two notions and then claiming the ambiguity of the second notion also invalidates the first notion.

I would like to start this paper “Don’t End The Fed, Amend The Fed,” with the following comment by Cathy O’Neil (“mathbabe”), “this may generalize using so-and-so’s theorem or what’s-his-name’s method….”. Consider it a gift to the… person who reads … this paper and wants to prove something new.”

Please read and improve: “Don’t End The Fed, Amend The Fed”

This paper is easily found on “Google”

Excerpt …:

“Perhaps the answer lies in how you redistribute the wealth of a nation; as well as how you acquire it.”

***** “Believe nothing merely because you have been told it…But whatsoever, after due examination and analysis,you find to be kind, conducive to the good, the benefit,the welfare of all beings – that doctrine believe and cling to,and take it as your guide.”- Buddha[Gautama Siddharta] (563 – 483 BC), Hindu Prince, founder of Buddhism

Your discussion of “status” also clearly involves the related issue of “audience”. Different mathematical texts are written for different audiences. The author of a text (research article, book, etc.) has a responsibility to make clear who is the intended audience. However, it is unrealistic to expect every text to be accessible to the broadest possible audience. One reason is journal demands on page length (there are other, better reasons). If the audience for a research article includes a reasonable group of experts who are able and willing to referee, and if the article is sufficiently detailed so that audience can follow the proofs and attest to their correctness, then the article is valid even if non-audience members have trouble with the article.

Proving things to an unsophisticated audience (or maybe an unwilling one) is frustrating. I recall trying to convince someone that there were as many rationals as integers, and there were more irrationals than rationals. These proofs are well-known, and well-understood to all HCSSIM-ers, but try to convince a non-math major!

Great example!! And I’d agree it’s harder, but that’s real mathematics, and good for you for doing it!

Cathy

I do this regularly as I teach a general interest survey course in mathematics to non-majors which covers a broad swathe of undergraduate mathematics in a (fairly) non-technical manner.

One point is that there are two conflicting notions of “as many” related to two different notions of quantity. I describe them as the “matching” notion (which of course is the notion of 1-1 correspondence we know from Cantor) and the “Containment” notion (if thing A contains thing B, then thing A is “bigger than” thing B – think of the partial ordering of subset-inclusion).

It’s important to be clear as to what you mean by “bigger than” when presenting these results – and to acknowledge the difference and explain the limitations and purposes of each notion.

Well, unfortunately, my point was that I was unsuccessful. Somewhere, oddly enough, faith (faith in reason, perhaps) enters into it. Plus, it was an internet interaction, without diagrams.

I agree with you that many proofs need to be written better, even for the expert audience. However I don’t agree with you when you say:

“I think it’s driven by a combination of feeling kind of smug and smart when people who are trying to follow your conversation leave because they’re exhausted and confused (and possibly ashamed), and the echo chamber that remains after people who don’t get it (or who admit to not getting it) leave.”

At least, I have never seen anything like this. Rather, I think the motivation is impatience to prove the next theorem.

Absolutely agree. There are definitely people who write their papers with the singular goal of proving to the world how brilliant they are, but that is a small minority. It’s even in the minority of inscrutable papers. Most papers are written poorly simply because the writers just want to get the damn thing done and move on to proving more theorems.

The folk history of mathematics gives as the reason for the exceptional terseness of mathematical papers; so terse that filling in the gaps can be only marginally harder than proving it yourself; is Blame it on WWII. The story is that the paper shortage in WWII in the US meant that papers were stripped down down to the bare minimum and beyond. The fashion endured to the present day.

The main evidence is that the pre-WWII papers do seem to be much more verbose and hence easier to understand. By the way, I recommend the works of Stefan Banach. He wrote his papers in French, not his native language, and the result was exceptionally clear prose. I sometimes think it would be good thing to require that all papers be submitted in a non-native language.

So you’re blaming WWII for Fermat’s margin? :-)

Ah, another teaching post. The fact of the matter is that giving an acceptable proof to an interested layman or undergraduate involves a different set of skills than giving an acceptable proof to another mathematician – it’s much harder! For an example of a good style, try Dunham’s “Journey Through Genius”, wherein he starts with oldies like Pythagorus, works through Euler, and ends up at – iirc – Cantor.

It’s been my experience, btw, that relatively few people encompass the skill to write both for the layman and for their peers. Maybe you can put this down to laziness or indifference, but given the generality of the phenomenon, I think it’s more likely that it’s just plain hard to do both well.

In view of Goedel’s arguments about consistency and completeness, it’s hard to leave axioms and postulates out of the problem of proof, but I agree that formal proof (in the absolute sense) is not what happens in real life. It has been argued that the concept of proof itself exists only in mathematics and law, the latter highly questionable in its dubious world of finding the bright thin line between truth and falsehood. When modern “proofs” in mathematics require the use of thousands of lines of computer code, and DNA “proof” is relentlessly releasing hundreds of wrongly accused and fraudulently framed convicted innocents, it seems obvious the concept of proof is an evolving human creation, hardly an abstract, absolute, ethereal Plutonic Ideal.

The fragility of proof in physics is related to the developing concepts of truthiness in mathematics, at least in their application to fundamental physical assumptions. A Newton’s “Law” at 18,000 miles an hour may be goodenuf “true”, but at speeds closer to the speed of light becomes totally wrong, where currently Einstein’s “Theory” of Relativity gives the far better “truth”. This evolved not only from the failure of Newton’s conception of the absolute, immutable nature of space and time, but also from the failure of postulates of Euclidean geometry, after thousands of years of being held beyond question.

To be convincing to a sufficient consensus of experts or jurists or the populace, a working proof needs to have reasonably self-evident assumptions on which to base logical, plausible arguments — all understood to be within the context and limitations of the subject matter as interpreted at its moment in human knowledge.

Good points. A lot of the terseness of proofs is ingrained math culture. There is a very well-meaning side — stripping away tedious case checking and more desultory bits highlights key ideas and gives everything an elegant gloss. But the practice also dumps a large burden on the reader to fill in the missing bits, and it makes it a big challenge to decide when to accept that a sketchy argument can be completed and when it might have a hole that would be exposed by filling in the details.

It really starts early — nearly all instruction just walks through successful arguments, maybe with a mention of what challenge or obstacle was overcome. Homework and research papers focus only on the argument that works in the end, with everything extraneous and all the wrong paths taken first stripped out. No one wants to write or grade lots of tedium — they want to make sure the key ideas are grasped and good intuition develops.

It is nice to see more accessible and complete arguments. And I’d love more presentation of wrong directions and pathways that failed. But there is a strong current flowing the other direction.

Thurston’s famous essay “On Proof and Progress in Mathematics”

http://arxiv.org/abs/math.HO/9404236

actually advocates that more senior people provide sketches, but only if young people can obtain credit by filling them in.

He feels he killed off the field of foliations by providing too many full proofs.

Proof sketches are generally good things, so long as the result is not labeled “Theorem” in the paper. (And no decent referee would allow that.) However, if it is necessary but easy to fill in the details, that’s bad: Since there’s little motivation to write easy papers, the proof will probably never be written and the result will lie in limbo. In that case, the author would be better off giving the proof sketch to a grad student rather than including it in a paper. On the other hand, if the details are hard to fill in, then whoever does so will receive appropriate credit for doing it by those who understand the difficulties.

So is a proof by computer (algorithmically correct but difficult to grasp) really a proof by your criteria, or maight it fail on grounds of opacity?

In the world of “formal proof,” a proof is either correct or it isn’t. But a real-world proof not only has degrees of certainty over its correctness or completeness, but also carries other qualities. I would argue, going beyond what Cathy wrote, that the purpose of a proof is not only to convince someone *that* something is true but also to explain *why* it is true. The most extreme version of this hypothetical computer proof succeeds in only one of these goals and hence is a pretty shitty proof imho. Actually, I once wrote a little essay on this topic:

http://qcpages.qc.cuny.edu/~dlee2/prove.html

Yes, context is everything.

Generalizing to discussions, arguments and ‘sort-of proofs’ about the natural systems we live within and try to guide in our own best interests, I find that most of these reference a fantasy world that was constructed precisely to allow the preferred, proposed political, economic or social remedies to work.

The fantasy world of the Progressive Left overlap with those of the Progressive Right in that both assume the world is made up of mechanisms.

Thus, simple control system concepts can be assumed to work.

The fact that the reality is increasingly out of sync with the fantasy worlds, is only discussed by a few radicals like Glen Greenwald, Naom Chomsky, etc.

Mathbabe : Your unique insights can add a lot to this discussion, although some of your previous posts make me think you are a standard Progressive in your political views, thus have a lot to overcome.

In fact, we live within unique, open, evolving, complex systems and do not have the understanding necessary to produce control systems for these. There are reasons to believe that such control are impossible, e.g. computational chaos + computational complexity + emergent properties of systems.

For a topic closer to the edge of mathematics, you could discuss the mapping of reality onto a list of rules that are supposed to manage that reality. That doesn’t seem to me to be at all possible, is at the heart of the growth of regulations and the regulatory state.

What does Progressive Right mean?

Progressive == “use the power of the government to achieve a good for the people”

Left version of the good == “the common good”

Right version of the good == “the national interest”. Neocons are one prominent version of this, but I think almost all Congress critters believe this. Ron Paul is the major exception.

BTW: does anything in fractal math have to do with a mapping between reality and any rule set or mathematical equivalent?

I don’t believe, BTW, that either ‘the common good’ or ‘the national interest’ is definable. Practical difficulties in collecting the weightings of every entity with a possible interest under all possible futures. Theoretical difficulties finding an optimal set of weights combining all of those.

Certainly majority rules voting on candidates with a variety of views, some of which are true, some of which (true and false) cannot be over-ridden by is not such a function.

Your comment,

“The above definition immediately begs the question, convincing to whom? Can a proof to someone be a non-proof to someone else? Absolutely, proofs are entirely context-driven. If I’m trying to prove something to you and you remain unconvinced, then it is no proof, even if I’ve used the same argument before successfully.”

reminded me of a talk titled ‘Mathematics, morally’ given by Eugenia Cheng (http://cheng.staff.shef.ac.uk/) where she mentions the following

“It’s widely believed that the big aim of doing maths is to prove theorems ie move things

into the `proved’ area. But I think the aim is to get things into the `believed’ area – believed

by as many mathematicians as possible. It’s just that we need proof to move from my believed things to anyone else’s…

The key characteristic about proof is not its infallibility, not its ability to convince but

its transferrability. Proof is the best medium for communicating my argument to X in a way

which will not be in danger of ambiguity, misunderstanding, or defeat. Proof is the pivot for

getting from one person to another, but some translation is needed on both sides.”

To me “belief” is that interesting subject matter which cannot (yet?) be proven, either a working hypothesis if it is in the realm of the potentially provable, or an unfalsifiable proposition in the Popperian sense, which like revealed religion, is utter nonsense unworthy of much thought.

OK, something curious just showed up on Boing Boing:

http://boingboing.net/2012/08/07/what-do-christian-fundamentali.html

which posits that there are some Christian fundamentalists that have a problem with multiple infinities (which is news to me!).

This might explain my experience above, trying to “prove” that the set of reals is bigger than the set of integers to someone I only knew as a casual internet correspondent. His reticence to accept or even consider my reasoning struck me as more religious than rational.

Or maybe I just wasn’t explaining it well.

I believe you are confusing proof with sound argument. The criteria for proof are formation and transformation rules applied to axioms or postulates. The criteria for sound argument are valid logical argument form and true premises.

Proof is one type of sound argument, which is the premises are syntactically true. ON the other hand, argumentation in science and most significant arguments in daily life are based on assertions of empirical truth.

There are arguments in daily life that resemble proofs, in that at least one premise functions as a norm in the universe of discourse even though it may resemble a descriptive proposition in form. See Ludwig Wittgenstein, On Certainty for an exploration of the logic justification in ordinary language.

no, I’m not. I was very clear on that in the first paragraph.

This is not an original idea, I first recall running across it in a long-ago (paper) National Lampoon parody issue of the “USA Today” newspaper, as the caption to one of the characteristic surveys in pie chart form:

“Lead Now The Heaviest Element, Latest Survey Shows”

Are you familiar with DeMillo, Lipton and Perlis from CACM in 1979? It’s still a great read.