[FOM] Transfinite Euclidean Algorithm

hendrik@topoi.pooq.com hendrik at topoi.pooq.com
Thu Nov 15 10:21:16 EST 2007


On Wed, Nov 14, 2007 at 09:47:02AM -0500, joeshipman at aol.com wrote:
> >-----Original Message-----
> >from: hendrik at topoi.pooq.com
> >> Commutative rings exist in which there is no Euclidean algorthm, but
> >> there is a "division algorithm" in which the appropriate "norm" with
> >> respect to which the remainder decreases takes values in a more 
> complex
> >> well-ordered set than the integers. Can anyone give a simple example 
> of
> > such a ring?
> 
> >polynomials over the integers with ordinal exponents but only a
> >finite number of terms in each polynomial?
> 
> How does that work? What happens when you divide x^omega + x + 1 by x^3?
> 
> If you say the quotient is x^(omega-3) and the remainder is (x+1), then 
> you have more than just ordinal exponents.

I got a quotient of x^omega, since x^3 * x^omega = x^(3+omega) = 
x^omega, and a remainder of x + 1.  The norm of the quotient is the dame 
as the norm of the dividend, but the norm of the remainder is small.

Noncommutativity of addition in the exponents is getting in the way. 
The ring appears not to be commutative as a result.

  x^omega * x^3 = x^(omega + 3)
  but
  x^3 + x^omega = x^(3 + omega) = x^omega.

So this isn't the example you were looking for.

-- hendrik


More information about the FOM mailing list