Euclidean Domain is Principal Ideal Domain

From ProofWiki
Jump to navigation Jump to search


A Euclidean domain is a principal ideal domain.


Let $\struct {D, +, \times}$ be a Euclidean domain whose zero is $0$ and whose Euclidean valuation is $\nu$.

We need to show that every ideal of $\struct {D, +, \times}$ is a principal ideal.

Let $U$ be an ideal of $\struct {D, +, \times}$ such that $U \ne \set 0$.

Let $d \in U$ such that $d \ne 0$ and $\map \nu d$ is as small as possible for elements of $U$.

By definition, $\nu$ is defined as $\nu : D \setminus \set 0 \to \N$, so the codomain of $\nu$ is a subset of the natural numbers.

By the Well-Ordering Principle, such an element $d$ exists as an element of the preimage of the least member of the image of $U$.

Let $a \in U$.

Let us write $a = d q + r$ where either $r = 0$ or $\map \nu r < \map \nu d$.

Then $r = a - d q$ and so $r \in U$.

Suppose $r \ne 0$.

That would mean $\map \nu r < \map \nu d$ contradicting $d$ as the element of $U$ with the smallest $\nu$.

So $r = 0$, which means $a = q d$.

That is, every element of $U$ is a multiple of $d$.

So $U$ is the principal ideal generated by $d$.

This deduction holds for all ideals of $D$.

Hence the result.