A Curious Paradox

Is that truly possible?  Can every positive integer have an associated Prime Curio?  No.  If we list everything that any one person (perhaps yourself?) found interesting about primes, it would be a finite list, because we are finite (we can do a finite number of things at once and live for a finite period of time).  Yes, we can write an algorithm for assigning "curious" properties to integers, but using an algorithm would defeat the intent of our definition of curios.  Since the number of humans is finite, it follows then that the number of curios must also be finite -- but the set of integers is infinite!

Our proof that every integer has an associated Prime Curio is what is called a semantical paradox.  Perhaps the oldest of these is from Epimenides the Cretan who said that:

All Cretans were liars and all other statements made by Cretans were certainly lies.

Here is a simpler form of this paradox: suppose I say "I am lying."  If I am lying when I say this, then I am telling the truth; and if I am telling the truth when I say it, then I am lying.  Epimenides probably lived in the fifth or sixth century BC and is most likely the philosopher referred to by the Apostle Paul in Titus 1:12.  The stories of Epimenides' life are so fanciful (e.g., that he lived for hundreds of years and once slept for 57 years) that little is truly known about him.

Our proof is actually a version of a more recent semantical paradox sent by G. G. Berry of the Bodleian Library to Bertrand Russell in a letter dated 21 December 1904.  (This letter is reprinted in [Garciadiego92].)  You will often find Berry's paradox stated as "every integer is interesting."  If you reread our proof, you will be able to reconstruct the "proof" of Berry's paradox.

Berry is also credited with the invention of the greeting card paradox--he would introduce himself with a card that on one side said:

The statement on the other side of this card is false.

and on the other said:

The statement on the other side of this card is true.

If you think through these statements, then you will see we have another version of the Epimenides paradox: if either of the statements are true, then they must be false as well.

A slightly later version of these paradoxes is Richard's paradox (1906).  His paradox can be stated in the form:

Every positive integer can be uniquely defined using at most 100 keystrokes on a typewriter. 

To "prove" this statement you create the type of paradox above by considering the set S of all integers that cannot be so described.  By the well ordering principal this set has a least member, and is in fact:

The least positive integer that cannot be described in at most 100 keystrokes.

But of course we just described it uniquely using less that 100 keystrokes, so to avoid a contradiction the set S must be empty!  Yet, we can also easily disprove this statement because a typewriter has less that 200 keys (probably closer to 100), and it follows that 100 keystrokes can describe less than 200¹⁰⁰ integers, so Richard's paradox cannot be true.

Russell discussed each of these paradoxes (and several more) in his "Mathematical logic as based on the theory of types [Russell1908] (reprinted in [Heijenoort67]) and concludes that they do not affect the logical calculus which is incapable of expressing their character.

Again, these are semantical paradoxes unlike Russell's famous paradox of the set of all sets that do not contain themselves.  This paradox is often recast as a question about a barber:

If there is a town in which the barber shaves (exactly) those who do not shave themselves, then does the barber shave himself?

If he does shave himself, then he does not; and if he does not, then he does.

References

Garciadiego92

A. R. Garciadiego, "Bertrand Russell and the origins of the set-theoretic 'paradoxes'." Birhäuser-Verlag, Basel, 1992. xxx + 264 pp. ISBN 3-7643-2669-7

Heijenoort67

J. van Heijenoort, "From Frege to Gödel, a source book in mathematical logic, 1879--1931." Harvard University Press, Cambridge Mass. 1967. xi + 660 pp.

Russell1908

B. Russell, Mathematical logic as based on the theory of types. Amer. J. Math. 30, 1908, 222-262. Reprinted in B. Russell, "Logic and Knowledge," London: Allen & Unwin, 1956, 59-102, and in J. van Heijenoort, "From Frege to Gödel," Cambridge, Mass.: Harvard University Press, 1967, 152-182.