Corcoran, J. 2005. Counterexamples and proexamples. Bulletin of Symbolic Logic 11(2005) 460.
John Corcoran, Counterexamples and Proexamples.
Philosophy, University at Buffalo,
Buffalo, NY 14260-4150
E-mail: [email protected]
Every perfect number that is not even is a counterexample for the universal proposition that every perfect number is even. Conversely, every counterexample for the proposition “every perfect number is even” is a perfect number that is not even. Every perfect number that is odd is a proexample for the existential proposition that some perfect number is odd. Conversely, every proexample for the proposition “some perfect number is odd” is a perfect number that is odd.
As trivial these remarks may seem, they can not be taken for granted, even in mathematical and logical texts designed to introduce their respective subjects. One well-reviewed book on counterexamples in analysis says that in order to demonstrate that a universal proposition is false it is necessary and sufficient to construct a counterexample.
It is easy to see that it is not necessary to construct a counterexample to demonstrate that the proposition “every true proposition is known to be true” is false–necessity fails. Moreover the mere construction of an object that happens to be a counterexample does not by itself demonstrate that it is a counterexample–sufficiency fails. In order to demonstrate that a universal proposition is false it is neither necessary nor sufficient to construct a counterexample. Likewise, of course, in order to demonstrate that an existential proposition is true it is neither necessary nor sufficient to construct a proexample.
This article defines the above relational concepts of counterexample and of proexample, it discusses their surprising history and philosophy, it gives many examples of uses of these and related concepts in the literature and it discusses some of the many errors that have been made as a result of overlooking the challenging subtlety of the proper use of these two basic and indispensable concepts.