Actually, number theory is a nice vehicle for giving layfolk a taste of what math is about. Everybody knows about naturals and primes (and if they don't, and you're a mathematician who's been put on the spot, it's something you can explain in under a minute). So I tell people, look: there are obviously infinitely many naturals (for any number there's always a bigger one) and there are also infinitely many primes -- but this latter fact is less obvious and requires proof.

Here is where I've run into unexpected troubles. People have no problem accepting the infinitude of the naturals, but what they have trouble appreciating is that it's

*not obvious*that the primes are infinite. "C'mon -- there are infinitely many numbers, so

*of course*there are infinitely many primes!" I've heard this response from more than one person. "Now wait a minute" I protest. The primes are a subset of the naturals, so a priori, they have every right to be a smaller subset. "OK, gimme an example of a finite subset of the naturals". I'm happy to provide the example {1,2,3,4,5}. "Yeah, but you've

*constructed*it as a finite set, so it doesn't count" is the sort of reply I get.

What seems to be happening is that to an untrained intuition, any subset of the naturals defined by a property without explicit bounds appears to be obviously infinite. Has anyone else encountered this phenomenon? Alexandre? Can my mathematician readers try this out on some non-math friends (no need to obtain signed consent forms) and let me know what you find?

Finally, does anyone have a simple example of a "nontrivially finite" subset of the naturals? That is, a set defined by a (simple!) property P that makes no reference to explicit bounds, yet P is provably finite?

## 16 comments:

I suppose { x \in \mathbb{Z} : P(x) and not P(x) } doesn't count.

Hi Steve,

As stated it's probably too "exotic" to convey the point. But how's this: the set of all numbers divisible by 10 and *not* divisible by 5. It's not exactly what I wanted (I was hoping for a less trivial, non-empty example), but it's a start...

(1) Stanislas Dehane's

The Number Sense: How the Mind Creates Mathematicsis the best thing I've read on the psychology of naive mathematics (i.e., not what trained mathematicians do).(2) I can obfuscate your example so it doesn't look so obvious:

The set of all x such that the following equation holds:

(x-1)(x-2)(x-3)(x-4)(x-5) = 0

This would look even better if I wrote out the polynomial in a non-factored form. To go beyond number theory to a little geometry, but in the same spirit, "The set of points where two distinct, not-too-wiggly curves intersect" will generically be finite.

(3) It is not, however, at all clear to me that your friends' intuitions are wrong. That is, it would not surprise me if the following were true:

CONJECTURE: Almost all descriptions in Peano arithmetic have extensions whose cardinality is either 0 or alpha_null.

Of course one would need to sharpen "almost all" here to have a real conjecture.

By the way, I don't think many people would be surprised that it's easy to come up with descriptions whose extensions are

empty— square circles, odd numbers divisible by two, etc.Right -- hence my qualification "nontrivially finite"!

What about the set of Fermat primes? Of course, that one has the problem that there's no known proof that it is in fact finite.

Fermat's Last Theorem: The set of all n such that x^n+y^n=z^n has a non-zero integer solution.

-Dima from Weizmann

Nice, Dima! Just a bit bulky to state, but I'll try it out on some unsuspecting friends...

How about the set of Fibonacci numbers that are squares (1, 144, and 0 depending upon where you start counting)? -- the proof is difficult, but the statement isn't. Alternatively, Fibonacci perfect powers (1, 8, 144, if I'm not missing any...), which is a much more recent result. (These are used as examples in Hofstadter's new book /I am a Strange Loop/, although I'd heard about Fibonacci perfect powers before...) Or another alternative: Fibonacci numbers which are powers of 2 (1, 2, 8) -- the proof of this one is, "elementary", but not back-of-the-envelope elementary like the proof of the infinitude of primes.

There are lots of other random little diophantine equations you could use; i.e. {n | n^2 + 15 is a square} = {1, 7} (this one is back-of-the-envelope provable, because the gaps between the squares keep getting bigger), although I'm not sure how natural they are...

Thanks for the great examples, algebrumbertheorist! The n^2 + 15 is a particularly good one.

Actually, just today someone asked me what math people do (he assumed it was related to the actuarial field -- a common conflation). I used the infinite primes example and he had no trouble accepting that this actually requires proof. So my psychological conjecture really needs to be better tested...

In these discussions, I've always found it more natural to give examples of true statements that seem obviously false -- these clearly require proof.

How about that "there are the same number of integers as rational numbers"? This is clearly ridiculous, and yet has a nice back-of-the-napkin proof by picture.

I think part of the problem is that the primes are too familiar. Most people who care enough to be having such a conversation will remember factoring numbers into primes from school. This really makes it intuitively clear that there must be infinitely many primes, although it takes some sophistication to formulate it. (If there were only k primes, then there would be at most (1+log_2 n)^k possible factorizations for the integers from 1 to n, which is not enough. This is in some sense a justification of "there are infinitely many numbers, so

of coursethere are infinitely many primes".) I'm not saying these people have this idea in mind, just that the more comfortable you are with the primes, the clearer it is intuitively that there have to be a lot of them.I like the n^2+15 example a lot, partly because it is easy to explain even without algebra that the gaps between squares increase linearly.

My favorite set of this type is the set of pairs of natural numbers which are consecutive integer powers:

{ {x,y} | x^a − y^b = 1 }

Catalan conjectured that this set has cardinality one, namely {{8,9}}. This was open for long time, see

this wikipedia entry

That's a great example, Hermann!

What about the set of all consecutive primes, i.e. {2,3}? That's pretty obviously finite, but makes no reference to finiteness

The set of even primes makes for a nice connection with two 'obviously' infinite sets.

Post a Comment