kj
Posts:
179
Registered:
8/17/09


Re: basic q on derived operations (general algebra)
Posted:
Feb 1, 2011 8:22 AM


In <5e63070aee1a46d7a59f1d1e4b2def80@o8g2000vbq.googlegroups.com> Arturo Magidin <magidin@member.ams.org> writes:
>On Jan 30, 9:56=A0pm, kj <no.em...@please.post> wrote: >> In <dd2421b451404086a6071c1e38801...@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. fiveway 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 mysteriouslooking, 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 afterthefact rationalization that would show that it is in fact M5. (In fact, I can't even come up for similarly lame 2020hindsight 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 9ary 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 nary 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 selfstudy, since I don't have the brains or the time required to basically rederive 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. Thinking about this stuff is like a drug.
~kj

