[FOM] Transfinite Euclidean Algorithm

Vaughan Pratt pratt at cs.stanford.edu
Wed Nov 14 11:24:08 EST 2007


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?

A more basic question would be, how can such polynomials form a 
commutative ring to begin with when ordinal addition is not commutative? 
  How is x * x^w equal to x^w * x, for example?

Vaughan Pratt


More information about the FOM mailing list