Some goals of a definition:
- A great definition should capture some phenomenon, like computation (Turing machines), efficient computation (P), efficient quantum computation (BQP). Cryptography has produced some of the best (and worst) definitions to capture security concerns.
- A great definition should be simple. Defining computability by a Turing machine--good. Definition computability by by the 1334 page ISO/IEC 14882:2011 C++ standard--not so good.
- A great definition should be robust. Small changes in the definition should have little, or better, no change in what fulfills the definition. That is what makes the P v NP problem so nice since both P and NP are robust to various different models of computing. Talking about the problems solvable by a 27-state Turing machine--not robust at all.
- A great definition should be logically consistent. Defining a set as any definable collection doesn't work.
- A great definition should be easy to apply. It should be easy to check that something fulfills the definition, ideally in a simply constructive way.
A great definition drives theorems not the other way around.
Sometimes you discover that a definition does not properly capture a phenomenon--then you should either change or discard your definition, or change your understanding of the phenomenon.
Let's go through an interesting example. In 1984, Goldwasser, Micali and Rackoff defined $k$-bits of knowledge interactive proof systems. Did they have good definitions?
- The definition of interactive proof systems hits all the right points above and created a new area of complexity that we still study today.
- Their notion of zero-(bits of) knowledge interactive proofs hits nearly the right points. Running one zero-knowledge protocol followed by another using the GMR definition might not keep zero-knowledge but there is an easy fix for that. Zero-knowledge proof systems would end up transforming cryptography.
- Their notion of k-bit knowledge didn't work at all. Not really robust and a protocol that output the factors of a number half the time leaked only 1-bit of knowledge by the GMR definition. They smartly dropped the k-bit definition in the journal version.
Two great definitions trump one bad one and GMR rightly received, along with Babai-Moran who gave an alternative equivalent definition of interactive proofs, the first Godel Prize.
This is a great exposition on good "external" definitions for theorems, but what about good "internal" definitions for lemmas? Sometimes what allows a proof to go forward is a correct definition, that "abstracts away" the parts that get in the way of a mathematical bashing. Good enough internal definitions sometimes even become external with time (and the lemma then becomes the theorem).
ReplyDeleteHere is a favorite and famous quote (by Spivak) about the mathematicians' approach to definitions. It departs, or at least adds nuance, to your claim that definitions should be simple.
ReplyDelete"There are good reasons why the theorems should all be easy and the definitions hard. As the evolution of Stokes' Theorem revealed, a single simple principle can masquerade as several difficult results; the proofs of many theorems involve merely stripping away the disguise. The definitions, on the other hand, serve a twofold purpose: they are rigorous replacements for vague notions, and machinery for elegant proofs."