20
$\begingroup$

I asked this question about a week ago on math.SE, without any answers. My motivation is pedagogical, but maybe the question comes closer to research-level than I thought.

The proof (at least the proof I know) that a principal ideal domain is a unique factorization domain uses the axiom of choice in multiple ways, and the usual way to show that a Euclidean domain is a UFD is to show that it's a PID (which is easy and constructive).

Is there a direct proof, not using the axiom of choice, that a Euclidean domain is a UFD?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ This doesn't exactly answer your question, but shows that a detour via PIDs is not going to work: mathoverflow.net/questions/31507/… $\endgroup$
    – Wojowu
    Commented Nov 21, 2016 at 14:57
  • $\begingroup$ @Wojowu: Thanks, I suspected that, but it's good to know for sure, and it makes me all the more interested in the answer to my question. $\endgroup$
    – Mark Meckes
    Commented Nov 21, 2016 at 14:59
  • 2
    $\begingroup$ Also, apparently, the book "Consequences of the Axiom of Choice" which was used to answer the previously linked question, doesn't have an answer to this one. There still might be hope :) $\endgroup$
    – Wojowu
    Commented Nov 21, 2016 at 15:02
  • $\begingroup$ A bit late to the party here, but what proof using choice were you thinking of? I am pretty sure that the proof KConrad describes in his answer is the one I learned in college ~15 years ago. I am actually quite curious how you WOULD get choice into the mix $\endgroup$
    – Vincent
    Commented Sep 16, 2018 at 21:18
  • 1
    $\begingroup$ @Vincent: The usual proof that a PID is a UFD uses Zorn's lemma, and as the question linked by Wojowu indicates, some form of choice is necessary (in the sense that ZF alone doesn't suffice). The point of KConrad's answer is that it's possible to prove that a Euclidean domain is a UFD without involving PIDs at all. $\endgroup$
    – Mark Meckes
    Commented Sep 16, 2018 at 21:38

2 Answers 2

Reset to default
17
$\begingroup$

There are two parts to showing a Euclidean domain or a PID are UFDs: (i) existence of an irreducible factorization for every nonzero nonunit and (ii) essential uniqueness of the irreducible factorization (any two use the same number of irreducible factors and the irreducibles that occur in both factorizations can be matched termwise up to multiplication by a unit).

To prove (ii), the key point is that every irreducible element is a prime element, and to prove that you need to be able to write $px + ay = 1$ for any irreducible $p$ and element $a$ where $p \nmid a$; the nondivisibility implies (since $p$ is irreducible) that the only common factors of $p$ and $a$ are units, so Euclid's algorithm in a Euclidean domain lets you algorithmically solve $px + ay = 1$ for some $x$ and $y$. In a PID you'd instead observe that the ideal $(p,a)$ has to be $(1)$.

To prove (i) is a major distinction between Euclidean domains and PIDs. You can do this for Euclidean domains in a much more concrete way than for PIDs. I compare approaches for each as Theorems 4.2 and 4.3 at http://www.math.uconn.edu/~kconrad/blurbs/ringtheory/euclideanrk.pdf. You need to read Sections 2 and 3 first to see why I mean about being able to assume the "$d$-inequality" holds: a Euclidean domain does not have to have its "norm" function $d$ be totally multiplicative or satisfy $d(a) \leq d(ab)$, but you can always adjust the "norm" function to fit that inequality all the time if it doesn't at the start. (Some books make this inequality part of the definition of a Euclidean domain and some do not.) Of course in $\mathbf Z$ and $F[x]$ that inequality is true, so you save some time when proving those rings are UFDs compared to a general Euclidean domain.

The bottom line is that you definitely do not need to introduce the machinery of PIDs in order to prove rings like $\mathbf Z$ or $F[x]$ have unique factorization. After all, unique factorization in those types of rings as well as in $\mathbf Z[i]$ was known (say, to Gauss) long before there was a concept of PID. I remember being surprised when I first saw how PIDs are proved to be UFDs, since I knew the case of Euclidean domains already and the proof of part (i) for PIDs was rather more abstract than I expected.

Improve this answer
$\endgroup$
9
  • 2
    $\begingroup$ Your last paragraph pretty well expresses why I asked in the first place. The usual line is that the norm function lets you do all kinds of things in a more concrete, computational way than in more general rings, so I found it quite strange to go through the more abstract proof that PIDs are UFDs in order to get unique factorization in Euclidean domains. $\endgroup$
    – Mark Meckes
    Commented Nov 21, 2016 at 19:56
  • $\begingroup$ And thanks for the link to your note more generally --- it addresses a lot of other nice pedagogical points. $\endgroup$
    – Mark Meckes
    Commented Nov 21, 2016 at 19:56
  • 1
    $\begingroup$ @MarkMeckes To prove $F[x]$ is a UFD you don't need the machinery of PIDs, but you do not need the machinery of Euclidean domains either. You just need the notion of degree, which shows more generally that a polynomial ring over a UFD is a UFD. Also, again while it is true you don't need the PID machinery to prove rings like $\mathbb{Z}$ or $\mathbb{Z}[i]$ are UFDs, you also don't need the Euclidean domain machinery. In fact, for rings like $\mathbb{Z}[\sqrt{14}]$ it is extremely difficult to show they are Euclidean, but fairly easy to prove they are PIDs and UFDs. $\endgroup$
    – Pace Nielsen
    Commented Nov 21, 2016 at 20:37
  • $\begingroup$ @PaceNielsen: Well, yeah, for $F[x]$ and $\mathbb{Z}[i]$ all sorts of stuff is easy. My point was that Euclidean domains are sometimes advertised with a slogan like "In these rings you can do the same kind of computations as in $\mathbb{Z}$ (or $\mathbb{Z}[i]$ or $F[x]$)", making it strange to introduce PIDs in order to prove something as fundamental as unique factorization. I'm very interested by your comment about $\mathbb{Z}[\sqrt{14}]$, though. $\endgroup$
    – Mark Meckes
    Commented Nov 21, 2016 at 20:48
  • 3
    $\begingroup$ @MarkMeckes $\mathbb{Z}[\sqrt{14}]$ was long known to not be Euclidean with respect to the field norm. But in 2004, as proven by Malcolm Harper, was it shown that there exists some Euclidean norm. See: cms.math.ca/10.4153/CJM-2004-003-9 As for "doing the same kind of computations" I understand your surprise that they'd divert through PIDs. One historical reason for this is that checking PIDness for rings of integers is a finite computation, but there is no known algorithm (unless you use RH in conjunction with PID) to tell whether it is Euclidean. $\endgroup$
    – Pace Nielsen
    Commented Nov 21, 2016 at 21:28
5
$\begingroup$

Given a non-unit $r \in R$, let $p$ be a non-unit divisor of $r$ that has minimal norm. Then $p$ must be irreducible. By induction on the norm, we know that $r/p$ is a product of primes (or a unit), so $r = p \cdot (r/p)$ is a product of primes. I don't think the usual proof of the uniqueness of the decomposition uses the axiom of choice (the key is just to prove that if $p \mid ab$, then either $p \mid a$ or $p \mid b$), so it seems to me that we are done.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't see why you can do it like this. The Euclidean function needn't be multiplicative, so 1. you can't deduce $p$ is irreducible and 2. you don't necessarily know what $r/p$ has smaller norm. $\endgroup$
    – Wojowu
    Commented Nov 21, 2016 at 19:30
  • $\begingroup$ @Wojowu: It looks to me like the proof sketched here is basically the same one in Theorem 4.2 of the note KConrad linked to. Your objections are explicitly answered in section 3 of that note. $\endgroup$
    – Mark Meckes
    Commented Nov 21, 2016 at 19:42
  • $\begingroup$ @MarkMeckes That's indeed the case, but IMO they should be addressed, or at the very least mentioned, in the answer. For example, for the more general definition of Euclidean function, $p$ is a nonunit divisor of minimal norm doesn't mean $p$ is irreducible, so some clarification would be desirable. $\endgroup$
    – Wojowu
    Commented Nov 21, 2016 at 19:45
  • $\begingroup$ BTW, to explain the downvote (which is mine), it is not there because I think the answer is wrong, but rather because I think the answer is not complete. $\endgroup$
    – Wojowu
    Commented Nov 21, 2016 at 19:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .