이 글은 1983년 Sigact News라는 인공지능 관련저널 15권 1호에 실렸던 한 문서에 대한 이야기입니다. 다음 그림은 이 저널의 표지입니다.
목차를 보면 16쪽에 “How to Prove It”이라는 제목의 리포트가 있음을 확인할 수 있는데요, 이 글을 발표한 다나 앵글루인(Dana Angluin)은 2019년 현재 Yale University에서 인공지능을 연구하고 있는 분입니다. 아래 사진은 리포트의 원문을 캡처한 것입니다.
원문 링크: [Click!!]
이 글의 내용을 보면 실제 증명을 어떻게 하느냐를 말하는 것이 아니라 증명을 한답시고 학생/학자들이 대중 앞에서 저지르는 잘못된 행태를 적어놓은 것이라는 것을 알 수 있습니다. 세미나, 혹은 논문발표 전에 한 번씩 읽어보면 자세를 바로잡는 데 도움이 됩니다. 원문 및 번역은 아래에서 볼 수 있습니다. 제가 이해가 잘 안되는 문장은 번역을 하지 않았고, 그나마 번역된 문장에도 오류가 있을 수 있으니 번역은 참고만 하시기 바랍니다.
>>>>>>>>>> 원문
- Proof by example
- The author gives only the case n=2 and suggests that it contains most of the ideas of the general proof.
- Proof by intimidation
- "Trivial"
- Proof by vigorous handwaving
- Works well in a classroom or seminar setting.
- Proof by cumbersome notation
- Best done with access to at least four alphabets and special symbols.
- Proof by exhaustion
- An issue or two of a journal devoted to your proof is useful.
- Proof by omission
- "The reader may easily supply the details."
"The other 253 cases are analogous."
"..." - Proof by obfuscation
- A long plotless sequence of true and/or meaningless syntactically related statements.
- Proof by wishful citation
- The author cites the negation, converse, or generalization of a theorem from the literature to support his claim.
- Proof by funding
- How could three different government agencies be wrong?
- Proof by eminent authority
- "I saw Karp in the elevator and he said it was probably NP-complete."
- Proof by personal communication
- "Eight-dimensional coloured cycle stripping is NP-complete (Karp, personal communication)."
- Proof by reduction to the wrong problem
- "To see that infinite-dimensional coloured cycle stripping is decidable, we reduce it to the halting problem."
- Proof by reference to inaccessible literature
- The author cites a simple corollary of a theorem to be found in a privately circulated memoir of the Slovenian Philological Society, 1883.
- Proof by importance
- A large body of useful consequences all follow from the proposition in question.
- Proof by accumulation of evidence
- Long and diligent search has not revealed a counterexample.
- Proof by cosmology
- The negation of the proposition is unimaginable or meaningless. Popular for proofs of the existence of God.
- Proof by mutual reference
- In reference A, Theorem 5 is said to follow from Theorem 3 in reference B, which is shown to follow from Corollary 6.2 in reference C, which is an easy consequence of Theorem 5 in reference A.
- Proof by metaproof
- A method is given to construct the desired proof. The correctness of the method is proved by any of these techniques.
- Proof by picture
- A more convincing form of proof by example. Combines well with proof by omission.
- Proof by vehement assertion
- It is useful to have some kind of authority relation to the audience.
- Proof by ghost reference
- Nothing even remotely resembling the cited theorem appears in the reference given.
- Proof by forward reference
- Reference is usually to a forthcoming paper by the author.
- Proof by semantic shift
- Some of the standard but inconvenient definitions are changed for the statement of the result.
- Proof by appeal to intuition
- Cloud-shaped drawings frequently help here.
>>>>>>>>>> 번역
- 예제로 증명하기
- $n=2$인 경우만 증명하고 그 증명이 일반적인 경우의 증명에 필요한 대부분의 아이디어를 포함하고 있다고 말한다.
- 위협을 가해 증명하기
- “Trivial 합니다.” “자명하다.”
- 열정적으로 손을 휘저어(handwaving) 증명하기
- 수업시간이나 세미나 할 때 유용하게 써먹을 수 있다.
- 짜증나는 기호로 증명하기
- 최소 네 개의 알파벳과 특수기호를 섞으면 금상첨화다.
- 피곤하게 만들어 증명하기
- 당신의 증명에 중점을 둔, 저널에 개제된 한 두 가지의 논문을 써먹는다.
- 생략해서 증명하기
- “세부사항은 독자들이 쉽게 채워넣을 수 있다.”
“나머니 253가지도 이것과 비슷하다.”
“...”(점 세 개를 찍으면 증명된다.) - 못읽게 해서 증명하기
- 참이지만/또는 의미없는 문장을 논점 없이 길게 연결해버린다.
- 희망을 담은 인용을 통해 증명하기
- 자신의 주장을 뒷받침하기 위해 어떤 정리의 부정, 역, 또는 일반화를 담은 문헌을 인용한다.
- 펀딩을 통해 증명하기
- 어떻게 세 정부기관이 같이 틀릴 수 있겠어요?
- 권위자를 통한 증명
- “승강기에서 Karp를 봤는데, 그가 NP-complete라고 했어요.”
- 사적 대화를 이용한 증명
- “8차원 coloured cycle stripping은 NP-complete이다. (Karp, personal communication).”
- Proof by reduction to the wrong problem
- "To see that infinite-dimensional coloured cycle stripping is decidable, we reduce it to the halting problem."
- 접근 불가능한 문헌을 인용해서 증명하기
- Slovenian Philological Society에서 내부적으로 전해내려오는 회고록(1883)에서 발견할 수 있는 간단한 따름정리를 인용한다.
- 중요성에 의한 증명
- 문제의 proposition에서 수없이 많은 유용한 결과가 나옵니다.
- 증거 축적에 의한 증명
- 오랜 기간 열심히 찾아보았지만 반례를 찾지 못했다.
- 우주에 의한 증명
- 그 proposition의 부정은 상상불가하거나 의미가 없다. -- 신의 존재를 증명할 때 인기있는 방법이다.
- 상호참조에 의한 증명
- 참고문헌 A에서 정리 5가 참고문헌 B의 정리 3에 의해 성립한다고 한다. 참고문헌 B의 정리 3은 참고문헌 C의 따름정리 6.2에 의해 성립한다고 하는데, 이 따름정리는 참고문헌 A의 정리 5에서 나오는 쉬운 결론이라 참조한다.
- 초월증명에 의한 증명
- A method is given to construct the desired proof. The correctness of the method is proved by any of these techniques.
- 그림에 의한 증명
- 예제에 의한 증명법의 일종으로 좀더 설득력이 강한 형태. 생략에 의한 증명과 결합해서 사용하면 좋다.
- 강력한 주장에 의한 증명
- 청중에 대해 모종의 권위를 가진 경우 유용하게 활용할 수 있다.
- 유령참조에 의한 증명
- 참조된 문헌 안에 털끝만치도 비슷한 정리가 발견되지 않는다.
- 미리참조
- 발간되지도 않은 논문을 참조한다.
- 의미를 비틀어 증명하기
- 결론을 만들기 위해 표준 정의의 불편한 부분을 바꿔버린다.
- 직관에 호소하는 증명
- 구름 모양의 그림이 이 용도로는 딱이다.