14
$\begingroup$

Is there a way to measure the understandability of a proof? From a search in the internet I have only found methods for measuring the understandability of software or tests for measuring the readability of a text.

Are there similar tests or methods to measure the understandability or the complexity of a proof? My final goal is to compare to different proofs of the same theorem by their understandability.

$\endgroup$
  • 1
    $\begingroup$ This is a really nice question. I suspect the answer is no, but it would be difficult to prove a negative. $\endgroup$ – mweiss Jul 21 '15 at 13:27
  • 1
    $\begingroup$ Probably not a quantitative, but I find a good proof is readable from a literary standpoint and provides some deeper intuition into the problem. $\endgroup$ – Chris C Jul 21 '15 at 13:58
  • 1
    $\begingroup$ Have you looked into proof theory? (For examples of MathOverflow questions with the proof-theory tag, see here.) $\endgroup$ – Benjamin Dickman Jul 22 '15 at 2:20
  • 2
    $\begingroup$ @BenjaminDickman No, but as far as I know proof theory does not investigate the understandability of proofs... $\endgroup$ – Stephan Kulla Jul 22 '15 at 11:15
  • 2
    $\begingroup$ could a proof be highly understandable and wrong? if so how is understandability different than readability? $\endgroup$ – emory Jul 23 '15 at 11:41
5
$\begingroup$

I will note here a litmus test for an understandable proof.

A proof is understandable only when :

a) you can explain it to another person, and

b) that person can explain it to a third person, and

c) the third person can explain it to you in a fashion that is:

  • 1) different from how you explained it, and
  • 2) convincing to you, and
  • 3) understandable by you

There are more exacting criteria, but for me, the above is the one that matters.

Gerhard "Science Is Meant For Sharing" Paseman, 2015.07.21

$\endgroup$
  • $\begingroup$ That's a good starting point. It does not provide a measure yet but your test may lead in such a measure. Thx... $\endgroup$ – Stephan Kulla Jul 22 '15 at 12:01
  • $\begingroup$ I don't disagree with anything in this answer, but I don't think it really answers the question. $\endgroup$ – mweiss Jul 22 '15 at 14:15
  • 1
    $\begingroup$ If I thought I could make the same point as effectively in a comment, I would. However, it gives a 0-1 valued measure of a proof. I think the original poster could use this in whatever procedure for measuring they develop. I further contend that any measure that is developed and worth their salt should have the above or moral equivalent as a component. Gerhard "But I Said That Already" Paseman, 2015.07.22 $\endgroup$ – Gerhard Paseman Jul 22 '15 at 19:36
2
$\begingroup$

Lets say you give the proof as a sequence of sentences

$$S_1$$ $$S_2$$ ... $$S_n$$

I consider a proof understandable, if at any point, I ask "why do this?" for that sentence, it should be obvious what the motivation is and where it is going to lead (IE by the time you get to sentence X, it should be obvious what sentence X+1 should be).

If that isn't the case, then usually the proof needs to be re-written, sentences rearranged, and motivation made clearer, until the entire thing jut gives off the air of "this obviously the clearest way to go about it"

$\endgroup$
  • 3
    $\begingroup$ In other words, a proof is perfect, if the reader of the proof, never having seen the proof of that problem before exclaims "ah! why I didn't I think of that, this makes so much sense". Usually thats a sign of a well written idea $\endgroup$ – frogeyedpeas Jul 23 '15 at 15:50
  • $\begingroup$ Given your idea: How can one say which proof of two is more understandable... $\endgroup$ – Stephan Kulla Jul 29 '15 at 13:35
  • $\begingroup$ Assuming they have the same number of sentences, whichever proof takes fewer steps to reduce to perfectly intuitive. I suppose you can't count steps as the #of text edits + rearrangements including additions and deletions. It's still subjective but it's at least a little more mechanical to go through $\endgroup$ – frogeyedpeas Jul 29 '15 at 14:04
0
$\begingroup$

One useful metric is: Does the proof yield a construction?

Given a constructive proof and a non-constructive proof of the same length, the constructive proof is usually easier to understand.

This metric can be refined further, in terms of the complexity of the construction, or how obvious the construction is from the proof.

A good test case is the Fundamental Theorem of Algebra, since multiple books have multiple proofs of the theorem.

$\endgroup$

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.