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.

Improve this question
$\endgroup$
8
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 11:41

3 Answers 3

Reset to default
6
$\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

Improve this answer
$\endgroup$
3
  • $\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, 2015 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, 2015 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, 2015 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"

Improve this answer
$\endgroup$
3
  • 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$
    – Sidharth Ghoshal
    Jul 23, 2015 at 15:50
  • $\begingroup$ Given your idea: How can one say which proof of two is more understandable... $\endgroup$
    – Stephan Kulla
    Jul 29, 2015 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$
    – Sidharth Ghoshal
    Jul 29, 2015 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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