up vote 12 down vote favorite
4

I was reading this article on the axiom of choice (AC) and it mentions that a growing number of people are moving into school of thought that considers AC unacceptable due to its lack of constructive proofs. A discussion with Mariano Suárez-Alvarez clarified that this rejection of AC only occurs when it makes sense.

This got me thinking. What are some examples of theorems in number theory that require the axiom of choice or its equivalents (ie Zorn's lemma) for its proof?

Note: Someone mentioned to me that Fermat's Last Theorem requires AC. Can someone verify this?

share|cite|improve this question
5  
Regarding FLT there was a thorough discussion of whether the proof used inaccessible cardinals on MO: mathoverflow.net/questions/35746/… . The existence of such a thing is independent of ZFC. Perhaps that is what your friend was thinking of. – Qiaochu Yuan May 31 '12 at 5:19
    
@QiaochuYuan Thanks for the link! – Eugene May 31 '12 at 5:24
1  
Consider the following basic result of abstract algebra: every non-trivial ring has a maximal ideal. This is Krull's theorem, and a theorem of Hodges is that this is equivalent to the axiom of choice in the general case. But maybe you can get away without AC when the powerset of your ring is well-ordered... – Zhen Lin May 31 '12 at 6:59
2  
@Zhen: the only proof I can think of where one actually appeals to this result in anything like full generality is one proof (IIRC) of the existence of algebraic closures, and it's known that in that case you can replace AC with the ultrafilter lemma (mathoverflow.net/questions/46566/…). – Qiaochu Yuan May 31 '12 at 7:09
2  
As an aside, the irony of rejecting AC on the grounds that it's not constructive is that the AC can become a theorem in suitable constructive settings: roughly speaking, if you can construct a set, then you can refine the construction to produce a well-ordering of that set too. – Hurkyl May 31 '12 at 7:34
up vote 17 down vote accepted

If we take a narrow enough view of number theory, AC can in principle be dispensed with. Take a sentence $\varphi$ of (first-order) Peano Arithmetic, and let $\varphi'$ be the usual translation of $\varphi$ into the language of set theory. If $\varphi'$ is provable in ZFC, then $\varphi'$ is provable in ZF.

There is a substantial extension of this result called the Shoenfield Absoluteness Theorem.

Remark: The result could be viewed as an argument for the acceptability of AC. For even if AC is as a matter of fact false, it cannot lead to false elementary assertions about the integers, unless ZF already does. Thus even if one has philosophical doubts about it, one can freely use it to prove number-theoretic assertions.

share|cite|improve this answer
    
I personally have no qualms about using AC as well. I was curious to see if AC is fundamental to number theory. It seems like it is not. – Eugene May 31 '12 at 22:01
1  
@Eugene: This again amounts to what do you mean by AC and what do you mean by fundamental. If by AC you mean "full blown all-giving AC" then the big portion of mathematics wouldn't even need half of that. If you mean any choice principle (i.e. provable from ZFC, not from ZF) then most modern mathematics would require some choice to hold as usual. – Asaf Karagila Jun 1 '12 at 6:30
    
@AsafKaragila I see. Thanks for the insight. – Eugene Jun 2 '12 at 1:15
    
@Andre Nicolas : +1 for the last paragraph. It is my impression that Wiles's proof used all kinds of fancy set theory, including accepting various more advanced axioms less familiar and difficult to explain than AC. If this impression is correct, it is not apparent to me why one should accept these axioms rather than their negations as being "true". Is there some theorem similar to the one you cite that proves that I don't need to worry about that? I could make this a Question, but I am afraid of drawing a lot of condescending answers and comments, unless you have a good answer prepared. – Stefan Smith Dec 26 '13 at 0:30
    
The only additional issue for the proof of FLT is the (formal) presence of large cardinal axioms. One cannot get rid of them mechanically by appealing to absoluteness. I believe there is consensus that they are not needed, and there are theorems that go at least part way to making this consensus a theorem. My brain functioning is diminished by Dec. 24 alcohol, and I do not recall the name of the author. – André Nicolas Dec 26 '13 at 0:50
up vote 10 down vote

This really depends on "what is number theory" for you. If you only think of statements about natural numbers then I cannot, for the life of me, come up with a good example of the axiom of choice hiding inside.

Things like Wilson's theorem, or Euclid's proof of the infinitude of prime numbers require no choice at all. Recall that ZF proves the consistency of PA, so things which are provable directly from PA do not require the axiom of choice.

On the other hand, modern number theory is a lot more than that. It is a tangled web of algebra and analysis which goes on to use heavy machinery from modern mathematics. We talk about ideals, about algebraic closures, we talk about $p$-adic fields and we talk about representation theory.

Many of those require the axiom of choice, perhaps we can then limit the choice we use if we are interested in things which "live" inside or around $\mathbb C$, but we would still have to use some portion like dependent choice and ultrafilter lemma.

share|cite|improve this answer
    
When I said number theory I meant "modern number theory". – Eugene May 31 '12 at 22:01
2  
@Eugene: Well, from what I [very] vaguely know about modern number theory it is likely that Dependent Choice+Ultrafilter Lemma (even limited to sets of size continuum or so) would be more than enough. I would be surprised if all the common results are provable from ZF alone, even if they are in some sense... finitary (as Matt E remarked). – Asaf Karagila May 31 '12 at 22:05
up vote 7 down vote

My experience, which is among the group of people who are working on automorphic forms, Galois representations, and their interrelations, is that no-one cares about whether or not AC is invoked. I think for some, this is simply because they genuinely don't care. For others (such as myself), it is because AC is a convenient tool for setting up certain frameworks, but they don't believe that it is truly necessary when applied to number theory. (For reasons somewhat related to Asaf Karagila's answer, I guess: there is a sense that all the rings/schemes/etc. that appear are of an essentially finitistic and constructive nature, and so one doesn't need choice to work with them --- although no-one can be bothered to actually build everything up constructively, so, as I said, AC is a convenient formal tool.)

On a somewhat related note: My sense is that most number theorists, at least in the areas I am familiar with, argue with second order logic on the integers, rather than just first order logic, i.e. they are happy to quanitfy over subsets of the naturals and so on. And they are really working with the actual natural numbers, not just an arbitrary system satisfying PA. So it's not immediately clear as to whether results (such as FLT) which are proved for the natural numbers are actually true for any model of PA. But, as with the use (or not) of AC, it can be hard to tell, because people aren't typically concerned with this issue, and so don't phrase their arguments (even to themselves) in such as way as to make it easily discernible what axiomatic framework they are working in. (I think many have the view that "God made integers ...".) One example of this is the question of determining exactly what axiom strength is really needed to prove FLT. As far as I know, this is not yet definitively resolved.

share|cite|improve this answer
    
Andre, in his answer, referred to Shoenfield's absoluteness theorem. This theorem holds for "simple" second-order sentences as well. So even second-order, if simple enough, can get away without a problem. – Asaf Karagila May 31 '12 at 12:25
    
@Asaf: However, it still makes sense to wonder (as Matt does) whether FLT is a theorem of PA or only one of ZF(C). – Henning Makholm May 31 '12 at 20:18
    
@Henning: Of course. Interestingly enough, I had several discussions with this recently. Most of the (real and experienced) set theorists all agreed that probably no one knows the answer yet, and it is likely that no one will invest too much effort into that for now. More interesting things await! – Asaf Karagila May 31 '12 at 21:07
    
I personally have no qualms about using AC as well. I was curious to see if AC is fundamental to number theory. It seems like it is not. – Eugene May 31 '12 at 22:00
up vote 0 down vote

I can't really add anything substantial to the answers above, but maybe it is helpful to see an explicit example. Modern number theory has a lot to do with algebraic geometry, and therefore with commutative algebra. One very basic theorem which is equivalent to the axiom of choice is Krull's theorem. It states that any commutative unital ring has a maximal ideal. This is definitely very crucial for many reasons and it is probably not easy to work without this property.

share|cite|improve this answer
    
It is important to remark, though, most rings dealt with in number theory are bounded in their cardinality. This means that only requiring these would have maximal ideals is not even close to AC in full. – Asaf Karagila May 31 '12 at 11:06
    
@AsafKaragila Fair enough. I just know that the existance of closed points in affine schemes is important. Whether we can get this without AC if we restrict ourselves to a certain family of rings is beyond my knowledge. But apperently you can (that's what you are saying, right?). – Simon Markett May 31 '12 at 11:15
1  
Simon, we can require that the axiom of choice holds in full (i.e. as if the axiom of choice was truly present) for everything whose cardinality is less than that of $\mathcal{P(P(P(P(P(P(P(P(P(P(P(P(P(P(P(P(}\mathbb N))\ldots)$. This means that if your ring is "reasonable" (say of size continuum) then you can apply all the usual choice-Zorn-whatever arguments to it. Then we can ensure that the axiom of choice breaks badly for sets above that size, so it does not really hold in the universe. If you require "every ring ..." then you impose no limitations on cardinality, and you get full choice. – Asaf Karagila May 31 '12 at 11:19
    
Asaf, nice to know thank you! I assume the dots mean sth like $\mathcal P^\infty(\mathbb N)$, if that makes sense. – Simon Markett May 31 '12 at 11:27
2  
No, I was just too lazy to count all the $\mathcal P$'s I used. It is a bit ambiguous to use $\infty$ in this context, since it often denotes "for every ordinal", but if we reiterate the power set $\mathbf{Ord}$-many times we generate the whole universe... on the other hand, you can take $\mathcal P^\omega(\mathbb N)$ (the union of every finite iteration), this is not a large set (I mean, it is quite large but "most sets are larger") and that is fine too. – Asaf Karagila May 31 '12 at 11:41

Your Answer

 
discard

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.