Teaching Theory of Computation for the first time, I encountered a phenomenon which perhaps is familiar to others in different contexts. I realize most MESE participants are not conversant with Th.Comp., so I will just sketch the issue at a high level, without explaining the technical terms.

Two important theorems in Th.Comp. are (1) Every NFA is equivalent to a DFA, and (2) Every NFA is equivalent to a regular expression. In both cases, a well-chosen example illustrates the equivalence and is entirely convincing. Then launching into an inductive proof requires introducing formidable notation, and in my recent experience, rendered the theorem less clear than it was before the proof presentation. This even though the inductive proof was ultimately straightforward.

My questions are:

Q. Are there other important theorems that are more convincingly presented via a well-chosen example, than they are via a formal proof? If so, is the burden of formal abstract notation the barrier (as I sense it is in my examples)? Could one justifiably argue that the well-chosen example supplants the need for a formal proof?

  • 8
    $\begingroup$ This seems somewhat related to something many of us do: we discuss some examples of space-filling curves to explain the need for the Jordan Curve Theorem but never prove that theorem (because the proof would almost certainly take almost any course too far afield). Your question is distinct from this, but brings it to mind, nevertheless. $\endgroup$ – Jon Bannon Mar 13 '16 at 1:16
  • 7
    $\begingroup$ Might there not be cases where a well-chosen example is entirely convincing, but the result turns out to be false? $\endgroup$ – Gerald Edgar Mar 13 '16 at 13:37
  • 4
    $\begingroup$ @DanChristensen: Yes, but presenting a proof in the classroom may have different goals. For example, to convince the students that the theorem is true. $\endgroup$ – Joseph O'Rourke Mar 13 '16 at 18:54
  • 4
    $\begingroup$ To judge by common practice, Bolzano's theorem (intermediate values) and Weierstrass's theorem (extreme values) in first-year calculus are thought to have unIlluminating proofs. A picture is usually held to be clear enough. $\endgroup$ – user1527 Mar 13 '16 at 19:52
  • 6
    $\begingroup$ It's pretty obvious that the derivative of y=sin x is something like y = cos x. But proving it take me two class sessions (much of it review of trig). I remind students that we're reviewing trig, but I wonder whether I should do this differently... $\endgroup$ – Sue VanHattum Mar 13 '16 at 20:48

"A well-chosen example illustrates ... and is entirely convincing."

For me, all of what is usually called "generic proof" satisfy your criterion. Consider the Euclidean algorithm for finding the greatest common divisor of two numbers. A well-chosen example tells your students all they need including why the algorithm gives the greatest common divisor, how to use the algorithm, what is the structure of "proof", etc. The symbolic proof does not tell them anything more in terms of the content of the algorithm.

Let me give another example in the other direction where it is better to use symbols from start (of proof). Suppose you want to prove that the product of two sums of two squares is also a sum of two square. Of course, you can use numerical examples to show that is true. For example, $2=1^2+1^2$ and $5=1^2+2^2$, and for these, we have $2.5=10=1^2+3^2$. I bet if your students are like mine, that example would be "entirely convincing" for them! But, it is not what you want since, first of all, they shouldn't be convinced just by a couple of examples, and in this case, because the structure of the proof is in fact can be used to write the product as a sum of two squares. I believe, to illustrate the proof of this one, it is better not to use an example since concrete examples would hide the structure of the proof; using numbers make it hard for students to see how the product should be reorganized since they are naturally tempted to calculate all the intermediate steps rather that to keep the numbers as they are.

  • $\begingroup$ Nice examples! They seem to accurately distinguish between those proofs which can be accurately illustrated by examples, and those which cannot. $\endgroup$ – Joseph O'Rourke Mar 16 '16 at 1:51
  • 1
    $\begingroup$ I would not be able to resist introducing the Gaussian integers to talk about sums of two squares... $\endgroup$ – paul garrett Mar 16 '16 at 19:02
  • $\begingroup$ @paulgarrett In that case I really suggest that you read Euler's masterpiece on the subject. Here you can find my take and a link to Euler's papers: amirasghari.com/teaching-ideas/read-euler-read-euler $\endgroup$ – Amir Asghari Mar 16 '16 at 20:06

There are many situations in which we have a clear collective understanding of intention, or goals, and examples which persuade us that these goals are plausible, as well as illustrating apparent causal mechanisms identifiable as "reasons" for things being the way they are.

For many reasons, the contemporary style of proof-writing, especially in intensely didactic situations, is wildly different from any attempt at "persuasion", or invocation of "intuition". Indeed, on one hand, one certainly wants whatever "physical" intuition is available, but, on the other, one eventually wants a proof that independent of literal physical phenomena or analogies.

The fundamental theorem of calculus, the intermediate value theorem, and many other of the basics of calculus, were visibly more-or-less true long before they were formalizable at all... and their utility gave some interest to eventual formal proofs, even while those formalized arguments, needing also formalized contexts, do not (to my perception) clarify or enhance the physical intuitions.

At least one particular pattern of events produces unhelpful, unpersuasive proofs: situations in which some interesting, important examples are fairly immediate, but it is less clear what "the general case" might be, and how to describe it. For example, the topic of "topological vector spaces" is arguably very practical, insofar as many natural spaces of functions should appear here, but there has been sufficient abstraction and eponymous-adjectification so that statements of theorems, and their proofs, can be couched in terms that do not obviously refer to any example of interest... and it often requires some scholarly chops to figure out the relevance of the iconic theorems to any particular tangible example.

In a different vein, the Cayley-Hamilton theorem? Historically/originally, just proven for the two-by-two case and three-by-three, and in the two-by-two the most naive possible computation succeeds. The three-by-three case can also succeed by most-naive means, but it is ghastly. The general case needs at least one of several more-abstract devices.

Not really undergrad, but certainly discussion of Sobolev spaces and regularity properties on Riemannian manifolds is best introduced by $\mathbb R^n$ and $n$-fold products of circles.

Generalities about automorphic forms and $L$-functions, and "Whittaker models" are arguably best introduced via discussion of the holomorphic case, with explicit exponentials for "Whittaker functions", etc.

Riemann surfaces are probably best introduced via the square root function, logarithm, and so on, prior to "covering by an atlas of charts..."

And from the other side, it is invariably wise to check an idea by considering examples... and if one cannot find any tangible example, or cannot determine the truth or falsity of the immediate question, that in itself is telling.


I think that whether or not a proof makes a theorem more convincing depends on who exactly you are trying to convince. While teaching an introductory math course to non-mathematicians (like say, calculus I in the U.S.), the emphasis is often on using the results. I think it is rare that a proof helps a student use a result, so proofs might not help a student go, "Oh, I see that result is true!"

I think the example of the product of sums of squares in the answer of Amir Ashgari is not quite fair. Imagine if instead you told students that the theorem was $$(b^2+c^2)(e^2+f^2) = (cf+be)^2+(ce-bf)^2.$$ Then there is no need to find anything useful in the proof. Moreover, with this statement, examples do illustrate the proof well.

In calculus, we don't (or I don't) say to students that the derivative of the product of two functions can be expressed using the derivatives of the the two individual functions and the functions themselves, and then leave the actual formula to be discovered in the proof. Instead, I give them a formula and illustrate it with examples that can be checked "by hand".

Of course, if the main result of a theorem is not a formula, then this discussion doesn't apply as readily. I am fine with the statement that every metric space is Hausdorff. I think the proof of this statement does a better job than any specific example. (Because any specific example would likely generalize to the proof in general. But there are lots of metric spaces, so maybe the student would not be convinced by the specific example.) Now to criticize my own example, I could have stated this result as: Any two distinct points in a metric space are separated by open balls of small enough radius. This way, the proof is basically in the statement, just like the theorems whose punchline is a formula.

So I guess my (very weak) answer to all of the questions in the post is that it just depends on the audience. The audience determines how one should state theorems as well as how one should illustrate the truth of any given statement.

  • $\begingroup$ Isn't it more persuasive to discover "formulas", whether by examples or whatever, than to be given a formula as though from an oracle? Doesn't this teach bad methodology, and suggest some "unknowability" of mathematics? Things should be discoverable, I think. $\endgroup$ – paul garrett Mar 16 '16 at 19:03
  • $\begingroup$ @paulgarrett I agree wholeheartedly with you, but some things are more discoverable than others. $\endgroup$ – Mark Fantini Mar 18 '16 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.