Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The Green-Tao primes theorem "The primes contain arbitrarily long arithmetic progressions" Ann Math 2008, is certainly a tour de force and extremely technical.

The authors point out that they have taken precautions to not use Axiom of Choice. Choice is mentioned several times in the paper, eg p.485:

In particular we shall always remain in the finitary setting of ZN , in contrast to the standard ergodic theory framework in which one takes weak limits (invoking the axiom of choice) to pass to an infinite measure-preserving system.


In the original ergodic theory arguments of Furstenberg this algorithm was not guaranteed to terminate, and indeed one required the axiom of choice (in the guise of Zorn’s lemma) in order to conclude the structure theorem. However, in our setting we can terminate in a bounded number of steps...

In terms of constructive vs classical mathematics however AC is only one of the forbidden axioms. Another is excluded middle. But I can't follow the paper to understand whether results that invoke excluded middle are used.

Kolmogorov, in "On the tertium non datur principle" writes "a proposition is pseudo-true if its double negation is true".

Is the Green-Tao theorem true or pseudo-true?

share|improve this question

closed as not a real question by Will Jagy, JDH, Zhen Lin, Asaf Karagila, J. M. Aug 14 '12 at 5:00

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

It is probably "pseudo-true". Many fundamental results in real analysis – such as the intermediate value theorem – are only "pseudo-true". But even if the Green–Tao proof isn't intuitionistically valid as-is, to answer the question properly one would have to either produce an intuitionistic counterexample to Green–Tao, or reprove the theorem using intuitionistic methods. –  Zhen Lin Aug 10 '12 at 4:38
Excluded middle is omnipresent in mathematics. –  André Nicolas Aug 10 '12 at 5:36
I see there is a vote to delete this question. This question should not be deleted, because of the useful answer and some of its comments. –  Jonas Meyer May 31 '13 at 5:44
I have to say that I find the title of the question very annoying. Objectively speaking: okay, you want to ask whether a certain proof satisfies a certain logical property: to me this is one of the less interesting questions one could possibly ask about Green-Tao, but it may be interesting to others. However...just because Kolmogorov wrote something somewhere does not make it a good idea to redefine the terminology of mathematical truth! It is culturally impossible for me not to read the title as loaded bordering on insulting. –  Pete L. Clark Feb 21 at 23:49
@PeteL.Clark, As far as I know the only axiom in common to all branches of math, whether constructive or not, is the rule of deduction or Modus Ponens. Maybe you have an insider's view as to what the terminology of mathematical truth is- but I think any conclusion (B) is conditional on the truth of the assumption A (as well as the truth of the implication A-->B). Is there an alternative interpretation? –  alancalvitti Feb 27 at 21:54

1 Answer 1

Concerning just classical logic and the use of AC, I am surprised to hear that precautions were taken to avoid AC, since the theorem is expressible in first-order number theory, and such statements are absolute from the set-theoretic universe $V$ to the constructible universe $L$, where the axiom of choice holds. It follows from this that the axiom of choice has no bearing on the argument, and any use of the axiom of choice could be omitted simply by pointing out this absoluteness. So actually, no precautions were necessary.

The basic situation is that the arithmetic consequences of ZFC are precisely the same as the arithmetic consequences of ZF, and so one may assume AC for such purposes without loss of generality.

A similar situation arises for example with Fermat's last theorem, meaning that it wouldn't have mattered whether or not Wiles had used AC in his proof. Even if he had, we could have constructed a new proof that does not use AC by arguing that we may first assume V=L and hence AC without loss of generality, since the truth of FLT is not affected by moving to L, and then carrying out the previous proof.

share|improve this answer
But actually, reading the passages now, I would say that the concern was apparantly not the axiom of choice so much as the axiom of infinity, since they were concerned to remain in a finitary setting. This is a very different concern, and of course ZF is not conservative over very weak finitary systems, even PA. So it does make sense to be concerned about one's assumption if one wants to prove the system in a weak finitary system. –  JDH Aug 10 '12 at 4:35
@alancalvitti: "finitary" methods are those that do not make essential use of infinite sets or processes. These methods were first singled out by Hilbert in his consistency program. However, like "constructive", the term "finitary" is not formal, and different authors use it with different meanings. –  Carl Mummert Aug 10 '12 at 11:11
Oh, since you put things that way, I beg your pardon, and I'm very sorry to have engaged with you. –  JDH Aug 11 '12 at 2:05
@alancalvitti Such confrontational responses are not perceived well here. I can only imagine that you are ostracizing those who might wish to help, like JDH. –  mixedmath Aug 11 '12 at 14:58
@alancalvitti, you have tagged your question with logic. Both JDH and Carl are well-known experts in the topic, they know what they are talking about, and they have tried to help you with your question. Posting polemical quotes from other mathematicians who are not experts in the topic is not a nice behavior and doesn't imply anything. –  Kaveh Aug 13 '12 at 20:08

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