nLab Euclidean ring

Contents

Context

Algebra

Constructivism, Realizability, Computability

Contents

Idea

In the same vein that commutative rings are to integral domains and GCD rings are to GCD domains, Euclidean rings are to Euclidean domains.

Definition

A Euclidean ring is a commutative ring RR for which there exists a function d:Can(R)d \colon \mathrm{Can}(R) \to \mathbb{N} from the multiplicative submonoid of cancellative elements in RR to the natural numbers, often called a degree function, such that for all fRf \in R and gCan(R)g \in \mathrm{Can}(R), there exist q,rRq, r \in R such that f=qg+rf = q \cdot g + r and either r=0r = 0 or d(r)<d(g)d(r) \lt d(g). There is no uniqueness requirement for q,rq, r.

One could posit, instead of the property that for all fRf \in R and gCan(R)g \in \mathrm{Can}(R), there exist q,rRq, r \in R such that f=qg+rf = q \cdot g + r and either r=0r = 0 or d(r)<d(g)d(r) \lt d(g); that the commutative ring has the structure of a function ()÷():R×Can(R)R(-)\div(-):R \times \mathrm{Can}(R) \to R called the division function, and a function ()%():R×Can(R)R(-)\ \%\ (-):R \times \mathrm{Can}(R) \to R called the remainder function, such that for all fRf \in R and gCan(R)g \in \mathrm{Can}(R), f=(f÷g)g+(f%g)f = (f \div g) \cdot g + (f\ \%\ g) and either f%g=0f\ \%\ g = 0 or d(f%g)<d(g)d(f\ \%\ g) \lt d(g). There might be multiple such division and remainder functions for the commutative ring RR.

One could also add the requirement that d(a)d(ab)d(a) \leq d(a b) for all nonzero a,ba, b. There is no loss of generality in assuming it; every Euclidean ring admits such a degree function dd', defining d(a)=min{d(ab):bCan(R)}d'(a) = \min \{d(a b): b \in \mathrm{Can}(R)\}.

In constructive mathematics

The definition of the Euclidean ring further bifurcates in constructive mathematics due to the disjunctive condition above. These statements, which are equivalent in the presence of excluded middle, include:

  • (r=0)(d(r)<d(g))(r = 0) \vee (d(r) \lt d(g))
  • ¬((r0)(d(r)d(g)))\not((r \neq 0) \wedge (d(r) \geq d(g)))
  • (d(r)d(g))(r=0)(d(r) \geq d(g)) \to (r = 0)

or equivalently,

  • (f%g=0)(d(f%g)<d(g))(f\ \%\ g = 0) \vee (d(f\ \%\ g) \lt d(g))
  • ¬((f%g0)(d(f%g)d(g))\not((f\ \%\ g \neq 0) \wedge (d(f\ \%\ g) \geq d(g))
  • (d(f%g)d(g))(f%g=0)(d(f\ \%\ g) \geq d(g)) \to (f\ \%\ g = 0)

Properties

Every Euclidean ring is a Bézout ring, and every prefield is an Euclidean ring.

Examples

  • The integers \mathbb{Z} are a Euclidean ring.

  • A classical Euclidean domain AA is a Euclidean ring where Can(A)\mathrm{Can}(A) is the multiplicative monoid of elements not equal to zero (where inequality is denial inequality)

Can(A){xA|x0}\mathrm{Can}(A) \cong \{x \in A \vert x \neq 0\}
  • A Heyting Euclidean domain AA is a Euclidean ring where Can(A)\mathrm{Can}(A) is the multiplicative monoid of elements apart from zero
Can(A){xA|x#0}\mathrm{Can}(A) \cong \{x \in A \vert x \# 0\}
  • An ordered Euclidean domain AA is a Euclidean ring where Can(A)\mathrm{Can}(A) is the multiplicative monoid of elements with a positive absolute value
Can(A){xA|0<|x|}\mathrm{Can}(A) \cong \{x \in A \vert 0 \lt \vert x \vert\}

See also

Last revised on December 10, 2022 at 14:53:18. See the history of this page for a list of all contributions to it.