Re: GCD(0,0)
- From: quasi <quasi@xxxxxxxx>
- Date: Mon, 02 Jan 2006 16:46:58 -0500
On 2 Jan 2006 19:05:34 GMT, Marc Olschok <invalid@xxxxxxxxxxx> wrote:
>quasi <quasi@xxxxxxxx> wrote:
>> On 31 Dec 2005 21:12:16 GMT, Marc Olschok <invalid@xxxxxxxxxxx> wrote:
>>
>> >quasi <quasi@xxxxxxxx> wrote:
>>[...]
>> >> I think the following is the standard:
>> >>
>> >> a|b iff a<>0 and b=a*x for some x.
>> >
>> >I always thought it was standard to leave out the part " a<>0 ".
>>
>> That's just the point. For some of these concepts there is a clear
>> standard, nearly universal, while for others there are competing
>> alternatives.
>>
>> For a|b, the choice as to whether or not to bar 0|0 is not so
>> universal, but it is barred in most of the texts I've looked at.
>>
>> So if you think it's standard to leave out the restriction a<>0, how
>> about some references? I'm sure there are references that allow 0|0 as
>> well as many that bar it. But here too, the power of a reference
>> depends to some extent on whether the author's text is itself viewed
>> as a standard.
>>
>> If it's clear that there is no real standard, then you can't insist
>> one is "right" -- it becomes author's choice. However, in such cases,
>> it's only fair for the author to warn the reader of competing
>> definitions or at least clearly declare the choice being made.
>
>You are right here. Certainly local clarity is valued higher
>than global consistency (after all this is mathematics, not engineering).
>For references see below.
>
>> However if there is an overwhelming standard, then in that case, using
>> a nonstandard definition is surely confusing. It's still author's
>> choice, but if an author does too much of that without some very good
>> reasons explained in advance, the resulting confusion will typically
>> cause the text to be rejected by the target audience, Who wants to
>> constantly be doing mental translations between nonstandard and
>> standard?
>>
>> >> The above definition works in any commutative ring, and while it
>> >> doesn't require x to be unique, it does bar 0|b.
>> >>
>> >> But even though I prefer 0 not to be regarded as a divisor of
>> >> anything, I can see how the case can be made for 0|0.
>> >
>> >By not imposing artificial conditions. While it is at least
>> >conceivable to bar 0 altogether from the natural numbers,
>>
>> In fact, for many books (not all) N = Z+, that is, {natural numbers} =
>> {positive integers}. However this definition is far from universal,
>> the alternative being N = Z+ union {0}, that is, {natural numbers} =
>> {nonnegative integers}.
>>
>> I think (but I'm not sure about this) that most number theory books
>> use N = Z+, while I know some computer science and discrete math texts
>> use N = Z+ union {0}.
>>
>> >once it is accepted there, it should not be barred from divisibility.
>>
>> Not necessarily. Many (and perhaps most?) abstract algebra and ring
>> theory texts define a|b in a ring theory context (where positive vs
>> nonnegative is not applicable), but still bar a=0 in the notation a|b.
>>
>> >> After all 0=x*0 would seem to suggest that 0 is both a multiple of 0
>> >> and a factor of 0.
>> >>
>> >> I have a feeling there's less agreement by texts as to whether 0|0
>> >> than as to whether gcd(0,0)=0.
>> >
>> >Some people like maximal elements.
>>
>> I think we all do, depending on what's being maximized.
>>
>> >> Certainly any text which bars 0|0 would also make gcd(0,0) undefined.
>> >>
>> >> But conceivably, there are some texts where 0|0 is accepted but for
>> >> which gcd(0,0) is still undefined (because of the g in gcd).
>> >
>> >A common misconception, see <41levcF1fatb8U1@xxxxxxxxxxxxxx>.
>>
>> I can't get that link -- it appears to be an email address, not a web
>> site.
>
>It is a Message-ID in this thread.
>You can throw it directly at your NNTP-host via ARTICLE <msgid>.
>
>The main passage was
>
>| If you unfold the definition if GCD you will see, that GCD(m,n)
>| is just the infimum of m and n with respect to the order |.
>| (also LCM(m,n) is the supremum of m an n).
>| Hence GCD(m,m)=m and in particular GCD(0,0)=0.
>|
>| If you consider all integers, the relation | is not antisymmetric
>| any more. But you still have the notion of "a greatest element",
>| and _a_ GCD(i,k) is _a_ greatest element of the set of common divisors
>| of i and k.
>|
>| That the _usual_ order on the naturals is not really important for
>| the concept of GCD becomes clear when more general Rings (i.e. k[X])
>| are considered.
>
>However, gcd is of course not the infimum with respect to the usual order
>on the naturals, even if 0 is excluded from consideration.
>
>So, using "|" instead of "<=" produces the notions of gcd and lcm as
>instances of simple and well known general concepts. This is IMO a plain
>"down to earth" _mathematical_ reason, why "|" should be used.
>
>A more didactical reason lies in the above observation that one cannot
>expect a counterpart of "<=" in other rings, but still has "|"; so one
>might as well start right away with the more sustainable choice.
>
>Note, that so far I do not insist on introducing gcd(m,n) for
>the case mn=0; the main point is the sensible choice of "greatest".
>It makes sense to chose some submonoid of (R,*) and the corresponding
>restriction of "|".
For the integers, the traditional definition of gcd use the word
"greatest" in the normal way. However, the only way to consistently
generalize gcd to rings is to base the definition of gcd on the
divisibility preorder. That doesn't mean you have to redefine it for
the integers since it's sufficient to observe that the evaluation of
gcd would stay the same.
Of course you could "redefine" gcd for the ordinary integers so as
have exactly the same definition as for general rings, and it's hard
to argue against that -- it really does makes sense,
So I'll concede that point -- that for consistency across rings in
general, the definition of gcd for the ordinary integers should be
based on the divisibility partial order on the positive integers. But
just because I think it should be defined in a certain way, doesn't
mean I can single-handedly change the standard.
However this post was mainly focused on gcd(0,0), with some posters
insisting that gcd(0,0)=0. For me, that went against the grain for
several reasons:
(1) Various posters were asserting the validity of gcd(0,0)=0 as if it
were a known fact. In fact, after reading those claims, I suddenly
wasn't sure if I had it right. But after doing some checks, it became
clear that the overwhelming majority of reputable texts define gcd in
such a way as to preclude gcd(0,0).
(2) In my understanding, 0 is not a divisor of anything, not even
itself. In other words, 0|b is barred for all b, including b=0. But if
I were to accept gcd(0,0)=0, that would mean I would also have to
accept 0|0. With so many posts asserting gcd(0,0)=0, I also began to
worry about whether barring 0|0 was standard or not. It appears that
most reputable texts do bar 0|0, but this is less universal than the
barring of gcd(0,0).
(3) There's really no need to allow 0|0 or gcd(0,0)=0. In practice, it
simply doesn't apply. Since the conflict with the traditional
definition has the potential to cause confusion, and since there's not
enough benefit, why bother?
>> >The definition of the gcd uses the divisibility preorder on
>> >a ring.
>>
>> Perhaps a course in abstract algebra or ring theory would make that
>> choice, but most number theory texts that I've seen, when defining
>> greatest common divisor, use the word greatest without any such
>> qualification, implying that the intended meaning is the standard
>> ordering. But as I've pointed out, even abstract algebra and ring
>> theory text tend not to allow gcd(0,0).
>>
>> To recap -- we appear to disagree on what's standard.
>>
>> I claim:
>>
>> (1) Most (but not all) reputable texts define the notation a|b as: a|b
>> iff a<>0 and b=a*x for some x.
>>
>> (2) The overwhelming majority of reputable texts define gcd in a way
>> that precludes giving a value to gcd(0,0).
>>
>> If you think otherwise, let's see some references.
>
>I claim:
>
>(a) they do not put such a any such funny condition as in (1)
>on the relation "|". Instead they restrict "|" to a suitable submonoid
>of the multiplicative Monoid of the Ring in question, for which they
>define the gcd.
Well, that sounds nice -- restrict it to a submonoid, but that's
simply not consistent with standard usage. The standard does allow a|0
if a<>0, but bars 0|b for any b. Thus, there's no submonoid since the
relation doesn't allow 0 on the left but does allow it on the right
(provided the left is nonzero).
Of course, I did point out that while most reputable texts bar 0|0,
some do allow it. Still, the standard is clear. Now if you want to
allow 0|0, fine, but it has to be specified since it's not the
default.
>(b) for a, b in this submonoid, the gcd(a,b) is defined as a greates
>common lower bound of a and b w.r.t. the restriction of "|".
As pointed out above, the submonoid idea doesn't work if we want
gcd(a,b) be defined when exactly one of a,b is zero.
>(c) that submonoid may or may not include 0. If it does not, then gcd(0,0)
>is obviously not defined. If it does, then gcd(0,0)=0, and this follows
>automatically from the definition in (b) via gcd(a,0) = a = gcd(0,a).
>There is there is absolutely no need to regard gcd(0,0)=0 as a special case.
>
>My first reputable choice is
>
>Saunders Mac Lane, Garret Birkhoff: Algebra (Chelsea, 1967, 3rd ed 1993)
>
>II-8 (The Division Algorithm), p111:
>: In any commutative ring K the following definitions apply:
>: b is divisible by a in K (in symbols a|b) when there exists
>: some c in K with ac=b.
>
>II-10 (Unique Factorization), p117:
>: An element d is called a greates common divisor or g.c.d of the elements
>: a,b of a domain D when, for all c in D,
>: d|a, d|b, c|a and c|b => c|d
>: Note that the adjective "greates" in this definition means not that d has
>: a greater magnitude than any other common divisor c, but that d is a
>: multiple of any such c.
That's a fine reference.
So for the MacLane / Birkhoff text, you have 0|0 and gcd(0,0)=0. As I
said, I know there are some texts which make this choice. Ok, so
that's one reputable text in favor of gcd(0,0)=0.
>
>My second reputable choice is
>
>Serge Lang: Algebra (3rd ed, Springer, 2004)
>
>[ unfortunately I do not have it with me right now, so it is from memory ]
>
>He considers only an entire ring, and defines the gcd as follows:
>suppose ab =/= 0 [ so both a and b are nonzero ]
>then d is a greatest common divisor if d divides a and b and every
>other common divisor of a and b divides d.
>
>It may surprise you, that I claim him as witness for me, although he
>obviously does define gcd only for nonzero arguments. But in fact, this
>is consistent with my claim: he _first_ chooses a suitable submonoid
>of (A,*), in this case A\{0}, then uses the restriction of "|" to this
>submonoid (without any artificial conditions) and then defines gcd(a,b)
>exactly as a greates common lower bound of a and b w.r.t. "|", like in
>the first example.
Well, I also cited Lang as a reference since he does bar gcd(0,0),
and that's the _main_ focus of this thread. So you're back to even.
One text in favor of gcd(0,0)=0 (MacLane & Birkhoff), one text that
bars it (Lang).
As far as your other point, whether you conceptualize it in terms of a
submonoid or not, the effect is still to allow or bar certain values
from being used. There's no real difference, provided the acceptable
inputs are the same. However, as I pointed out, for Lang's definition,
you can't really use the submonoid concept anyway (without making
exceptions to that) since Lang does allow gcd(a,0) if a<>0.
>My third reputable choice is
>
>Heinz Lüneburg: Vorlesungen über lineare Algebra (B.I. Mannheim, 1993)
>
>Kap. 3 (Ringe und Körper), s.73:
>
>| Sind a,b,c \in Z, so heißt c größter gemeinsamer Teiler von a und b,
>| falls c ein Teiler von a und b ist, und falls jeder gemeinsame Teiler
>| von a und b auch ein Teiler von c ist.
>
>At this stage, divisibility seems to be taken for granted for integers.
>Later there follows a definition of "|" and the gcd:
>
>Kap. 4 (Polynomringe), s.91/92:
>
>| Es sei R ein kommutativer Ring und a und b seinen Elemente von R.
>| Man nennt b Teiler von a, falls es ein c \in R gibt mit a=bc.
>|
>| Es sei R ein Integritätsbereich und a, b und c seien Elemente von R.
>| Genau dann heißt c größter gemeinsamer Teiler von a und b, wenn gilt
>|
>| 1) c ist Teiler von a und auch von b, dh., c ist gemeinsamer Teiler
>| von a und b.
>|
>| 2) Jeder gemeinsame Teiler von a und b teilt c.
>|
>| Da a und b in aller Regel viele größte gemeinsame Teiler haben, bezeichnen
>| wir die Menge ihrer größten gemeinsamen Teiler mit ggT(a,b). Im Ring Z der
>| ganzen Zahlen gilt ggT(4,-6) = ggT(2,-2) = {2,-2} und ggT(0,0) = {0}.
While I can't read German, I get the sense of the last line -- the
author is explicitly giving gcd(0,0)=0 as an example. So now you have
2 texts in favor of gcd(0,0)=0, 1 against.
I'm not knowledgeable about German authors, but I'll assume that Heinz
Lüneburg is a reputable author. However, I do know of one famous
German author -- Van Der Warden. I wonder how Van Der Warden would
choose on this issue.
>My fourth reputable choice is
>
>Hideyuki Matsumura: Commutative Ring Theory (CUP 1986)
>
>Section 20 (UFDs), p163/4:
>
>| Let A be an integral domain; for any two non-zero elements a,b \in A.
>| The notion of greatest common divisor (g.c.d) and
>| least common multiple (l.c.m) are defined as in the ring of integers.
>| That is, d is a g.c.d. of a and b if d divides both a and b, and any
>| element x dividing both a and b divides d;[...]
>
>which is the same as in Lang.
Not exactly the same.
Matsumura won't allow gcd(a,b) unless a,b are both nonzero, while Lang
allows gcd(a,b) unless a,b are both zero.
Take another look at the title of this thread. Matsumura bars
gcd(0,0). Thus, you're back to break even on this issue since 2 of
your 4 references bar gcd(0,0).
>For more I would need to raid the library,
No need, unless you really believe that you can tip the scale the
other way,
I'll admit though, the arguments against gcd(0,0)=0 are not that
strong. At this point, I could take either side. It's just a question
of what's standard.
quasi
.
- Follow-Ups:
- Re: GCD(0,0)
- From: Marc Olschok
- Re: GCD(0,0)
- From: JoeS
- Re: GCD(0,0)
- References:
- Re: GCD(0,0)
- From: quasi
- Re: GCD(0,0)
- From: Marc Olschok
- Re: GCD(0,0)
- Prev by Date: Re: Ideals in practice
- Next by Date: Re: Again I don't like this probability explantion
- Previous by thread: Re: GCD(0,0)
- Next by thread: Re: GCD(0,0)
- Index(es):
Relevant Pages
|
