Euclid’s proof that there are infinitely many primes is simple and ancient. This proof is given early in any course on number theory, and even then most students would have seen it before taking such a course.

There are also many other proofs of the infinitude of primes that use more sophisticated arguments. For example, here is such a proof by Paul Erdős. Another proof shows that there must be infinitely many primes because the sum of the reciprocals of the primes diverges. There’s even a proof that uses topology.

When I first saw one of these proofs, I wondered whether they were circular. When you use advanced math to prove something elementary, there’s a chance you could use a result that depends on the very thing you’re trying to prove. The proofs are not circular as far as I know, and this is curious: the fact that there are infinitely many primes is elementary but not foundational. It’s elementary in that it is presented early on and it builds on very little. But it is not foundational. You don’t continue to use it to prove more things, at least not right away. You can develop a great deal of number theory without using the fact that there are infinitely many primes.

The Fundamental Theorem of Algebra is an example in the other direction, something that is foundational but not elementary. It’s stated and used in high school algebra texts but the usual proof depends on Liouville’s theorem from complex analysis.

It’s helpful to distinguish which things are elementary and which are foundational when you’re learning something new so you can emphasize the most important things. But without some guidance, you can’t know what will be foundational until later.

The notion of what is foundational, however, is conventional. It has to do with the order in which things are presented and proved, and sometimes this changes. Sometimes in hindsight we realize that the development could be simplified by changing the order, considering something foundational that wasn’t before. One example is Cauchy’s theorem. It’s now foundational in complex analysis: textbooks prove it as soon as possible then use it to prove things for the rest of course. But historically, Cauchy’s theorem came after many of the results it is now used to prove.

**Related**: Advanced or just obscure?

Saying that what’s foundational is conventional is quite a bit stronger than saying that it changes. I would tend to think it’s up for grabs what is foundational, but that we don’t have complete freedom to choose what is conventional without going through incredible contortions.

Here’s a question in that vein: could someone write a straightforward work of number theory where the infinity of primes is treated as foundational? Would doing so constantly be awkward?

If you think of “possible ways these results could be taught” as partial orderings on the set of results, then doesn’t it become clear what is foundational and what is not? If result X has few (or no) predecessors in every partial ordering that works, then it’s foundational.

There are ways of teaching things that are logically possible though strange, maybe comprehensible to a small minority, so you have to qualify “possible.”

Graduate courses often teach material in a different order than undergraduate courses. But they cheat: they assume you’ve seen the material before, so they can do things in an order that is efficient but that lacks motivation.

This reminds me a bit of Rich Hickey’s talk about the difference between simple and easy. The talk was one of my favorites, if you have some time.

Thanks. That’s a great talk by Rich Hickey.