Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: basic q on derived operations (general algebra)
Replies: 22   Last Post: Feb 1, 2011 11:12 AM

 Messages: [ Previous | Next ]
 kj Posts: 197 Registered: 8/17/09
Re: basic q on derived operations (general algebra)
Posted: Feb 1, 2011 8:22 AM

In <5e63070a-ee1a-46d7-a59f-1d1e4b2def80@o8g2000vbq.googlegroups.com> Arturo Magidin <magidin@member.ams.org> writes:

>On Jan 30, 9:56=A0pm, kj <no.em...@please.post> wrote:
>> In <dd2421b4-5140-4086-a607-1c1e38801...@e2g2000yqi.googlegroups.com> Art=
>uro Magidin <magi...@member.ams.org> writes:
>>
>>
>>

>> >On Jan 30, 4:07=3DA0pm, Ilmari Karonen <usen...@vyznev.invalid> wrote:
>>
>> >> Things get slightly more interesting with four arguments: besides the
>> >> four trivial operations which return one of their arguments, and the
>> >> four which ignore one of their arguments and return M3 of the rest,
>> >> there are also four operations corresponding to a majority vote where
>> >> one of the arguments gets a double vote.

>>
>> >> Can we actually derive these from M3? =3DA0We can obviously derive the=
>m
>> >> from M5 (i.e. five-way majority vote), so it would suffice to derive
>> >> M5 from M3, but I'm not really sure if that's possible or not.

>> >Yes, M5 is a derived operation here. I can't remember if this is the
>> >simplest expression, but here's one:

> [...]

>> Thanks! =A0Here's another one:
>>
>> M3(a, M3(b, c, d), M3(b, e, M3(c, d, e)))

>Simpler than the one above I gave, for sure.

Yes, but pretty mysterious-looking, don't you think? Not in a
million years would I have been able to guess that this is M5. I
can't even come up with a lame after-the-fact rationalization that
would show that it is in fact M5. (In fact, I can't even come up
for similarly lame 20-20-hindsight rationalization "showing" that
it's invariant to reordering of its arguments!)

>Here are a few more things you can try to check for the derived
>operations:

>(i) Is it true that if q is a derived operation, then q(1,1,...,1) =3D
>1?
>(ii) Is it true that if q is a derived operation, then q(0,0,...,0) =3D
>0?
>(iii) If q is a derived operator, can you say anything about how
>q(0,x_2,...,x_n) compares with q(1,x_2,...,x_n) (fix x_2,...,x_n) ?

Thanks, those are interesting questions. Ilmari's observations go
a long way in answering them. And, as you said, one is lead to
ideas that have a very algebraic flavor (to my ignorant taste,
anyway). So I've been staring at the Hasse diagram of P({5})...
(Also, thanks to Ilmari for pointing out that the case of the 9-ary
operation M3(M3(a,b,c),M3(d,e,f),M3(g,h,i)) is a case to be reckoned
with.)

So now I have a slightly sharper necessary condition for derivability
of an n-ary operation in terms of M3, but it is too unwieldy to be
much better than simply saying that such operation must be increasing
and "odd". I have no reason at all to think that it's sufficient.
What's worse, I don't think I could prove any of what I have so
far formally. (In another post you suggested induction for a few
items, and that's what I would try with some of the conjectures I
have, but I don't trust that I'd get the induction right. I wish
Bergman had included a fully worked out example. He even points
out serious errors that students often make when thinking about
this stuff, so he must know that this is sufficiently alien territory
to the unitiated that a fully worked out example is in order.
Maybe he did it in class...)

My difficulties with these questions always boil down to not having
any good way to think about the infinite set of possible formal
terms. (Granted, in this system, for any given arity, the number
of possible operations is finite, but the number of formal terms
is infinite.)

Anyway, I wanted to thank you for all your posts in this thread.
The review of Bergman's book was a very interesting read. (For
one thing, it told me that maybe I should pick a different book
for self-study, since I don't have the brains or the time required
to basically re-derive the better part of the theory of general/universal
algebra by myself, which, from the reviewer's comments, seems to
be the task of anyone using this book outside of a class.) I'm
particularly intrigued by the reviewer's comment about "some
mysticism about threes". Kabbalah?

The problem presented in this exercise is indeed a beautiful one.

~kj

Date Subject Author
1/30/11 kj
1/30/11 quasi
1/30/11 kj
1/30/11 magidin@math.berkeley.edu
1/31/11 quasi
1/30/11 magidin@math.berkeley.edu
1/31/11 quasi
1/30/11 Ilmari Karonen
1/30/11 magidin@math.berkeley.edu
1/30/11 kj
1/30/11 magidin@math.berkeley.edu
1/31/11 Arturo Magidin
1/31/11 Marshall
1/31/11 magidin@math.berkeley.edu
1/31/11 magidin@math.berkeley.edu
1/31/11 Marshall
1/31/11 magidin@math.berkeley.edu
1/31/11 Marshall
1/31/11 Frederick Williams
2/1/11 kj
2/1/11 magidin@math.berkeley.edu
2/1/11 Marshall
1/30/11 magidin@math.berkeley.edu