Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Google search yields the paper by RH Cowen called Generalizing König's infinity lemma. Due to my insufficient technical background, I am afraid, I cannot fully appreciate the paper.

Tout court, Cowen proves three theorems and concludes they are equivalent to prime ideal theorem of Boolean algebra.

Here is the first theorem which is generalization of KL:

Theorem 1 Let T be a collection of locally finite trees such that for any finite set of levels of T there is a consistent set of vertices piercing those levels. Then there is a consistent set of vertices piercing the entire set of levels of T.

Then he states:

Theorems 1-3 are equivalent to each other and to P.I., the prime ideal theorem for Boolean algebras; this is easy to establish using our results in [l] where some strong forms of Rado's selection lemma were shown to be equivalent to P.I

My questions are two-fold:

  • Does this paper show the connection between König's Lemma (KL) and primes through Prime Ideal Theorem (PIT)?

  • Has there been research done to prove primes' infinitude via KL?

Or am I completely off?

share|cite|improve this question
The prime ideal theorem is not really that closely related to prime numbers. The paper in your p.s. refers to a different result named after Konig. – Qiaochu Yuan Dec 28 '11 at 1:53
@QiaochuYuan I realized it and edited it out. – Sniper Clown Dec 28 '11 at 1:54
@QiaochuYuan Regarding your first statement, would you then say it is a possible research avenue to attempt to prove between relation primes and KL? – Sniper Clown Dec 28 '11 at 1:57
Also (very minor quibble), you're mixing two baseball metaphors in your last sentence ("off base" and "out in left field"). – Qiaochu Yuan Dec 28 '11 at 2:11
Konig's Lemma (if it's the thing I'm thinking of) proves there's an infinite path in some kind of tree, but part of the hypothesis is that the tree is infinite in the first place. So it seems unlikely to me that you'd get a proof of the infinity of primes out of Konig. I could be wrong. – Gerry Myerson Dec 28 '11 at 2:30

To answer your question on infinitude of primes properly, one would need to set up a very restrictive and strict version of the area of mathematical logic known as reverse mathematics. (This is partly because the question asks for arithmetical consequences of a second order statement.) This strict setting has not been developed/studied yet.

Traditional research in reverse mathematics builds on the basis of a theory called $RCA_0$; adding to it a weak version of König's Lemma (stating that every infinite subtree of the full binary tree has a branch) results in a system denoted $WKL_0$, which is strictly stronger and has been extensively studied. $RCA_0$ is a very weak system, but proves the infinitude of primes and much more.

The study of weak systems of first order arithmetic is also a very extensively studied area, but the mixture of the two is at its infancy, as far as I know.

As for the question regarding the prime ideal theorem, we can do better, at least in terms of the classical version of König's Lemma: $WKL_0$ suffices to prove that every countable commutative ring has a prime ideal. This is as far as we can expect, as we are limited by the language of second order arithmetic, so the rings we can study are countable.

Let me add a slightly technical remark on why answering the question looks difficult. For formal investigations involving the natural numbers, there is a bare minimum we need to adopt to be able to talk of arithmetic, namely the theory $Q$ of Robinson arithmetic. Strengthening this fragment is usually achieved by assuming induction for certain classes of formulas. For example, $I\Delta_0$ assumes induction for bounded formulas. The study of theories in the neighborhood of $I\Delta_0$ is the topic of bounded arithmetic, see for example the work of Sam Buss. It is still open whether $I\Delta_0$ suffices to prove the infinitude of primes, but just a bit more suffices (for example, $I\Delta_0$ plus a version of the pigeonhole principle).

To properly address your problem, we would need to work over a theory consisting of a suitable formalization of König's Lemma (a second order principle), and a first order fragment around the level of $I\Delta_0$, if not weaker. This leaves us almost without any coding devices. The adoption of König's Lemma should help to make up for this weakness, but on the other hand, there seem to be very few trees we could build in such a setting to which the Lemma would apply.

The problem looks interesting, and the appropriate setting for this work should be an extension of what is now called bounded reverse mathematics.

(You may also be interested in this MO question on formalizing proofs of the infinitude of primes.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.