basic q on derived operations (general algebra)
kj
Let M3 be the ternary operation on {0, 1} defined by M3(x, y, z)
= 1 whenever the number of its arguments that is 1 is greater than
1, and 0 otherwise (i.e. "majority rule on 3 yes-no votes").
What n-ary operations can be derived from M3? I'm totally lost
with this one.
As far as I can tell, no 0-ary operation can be derived from M3
(since, without any arguments at all, I can see no way to invoke
M3), but I'm not sure if this reasoning constitutes a valid proof,
and if not, I can't figure out how a valid proof would go.
For n > 0, and again, reasoning very informally, I'd say that any
n-ary operation O derived from M3 would have to be "odd" since M3
is odd. (I'm calling "odd" any operation O such that O(~x) = ~O(x),
where ~0 = 1 and ~1 = 0.) Once more, I wouldn't even know where
to begin to prove this formally.
The only unary operation I can come up with is the identity I: I(x)
= M(x, x, x). I can't come up with ~ (i.e. "negation", as defined
above), even though it is odd, but, again, I can't prove it can't
be done.
As for binary operations, the only ones I can derive are the ones
that correspond to "first coordinate" (p0(x, y) = M(x, x, x)) and
"second coordinate" (p1(x, y) = M(y, y, y)). (In fact, this
generalizes to the "j-th coordinate n-ary" operation, for any n >
0, and any 1 <= j <= n.) I can't come up with xor nor !xor (i.e.,
not xor), both of which are odd, nor can I can up with a proof that
this is impossible.
And so on...
I imagine that all the missing proofs above can be done with
basically the same argument. Any help would be appreciated.
TIA!
~kj
quasi
wrote:
>
>Let M3 be the ternary operation on {0, 1} defined by M3(x, y, z)
>= 1 whenever the number of its arguments that is 1 is greater than
>1, and 0 otherwise (i.e. "majority rule on 3 yes-no votes").
>
>What n-ary operations can be derived from M3? I'm totally lost
>with this one.
>
>As far as I can tell, no 0-ary operation can be derived from M3
>(since, without any arguments at all, I can see no way to invoke
>M3), but I'm not sure if this reasoning constitutes a valid proof,
>and if not, I can't figure out how a valid proof would go.
No, that's not right.
The 0-ary operations are the constants 0 and 1.
But 1 = M3(1,1,1) and 0 = M3(0,0,0), which defines both 0-ary
operations in terms of M3. There are other choices, but we only need
to show one way to do it.
Next try 1-ary operations.
A 1-ary operation on {0,1} is just a function from
{0,1} -> {0,1}
thus there are 4 such functions, namely the functions
a(x) = 0
b(x) = 1
c(x) = x
d(x) = 1-x
The functions a,b,c can be defined as follows:
a(x) = M3(0,0,0)
b(x) = M3(1,1,1)
c(x) = M3(x,1,0)
The function d is problematic.
You can define it as
d(x) = M3(1-x,1,0)
provided the expression M3(1-x,1,0) is allowed.
I haven't looked at 2-ary operations (there are 8 of them), but some
of them are easy.
For example, consider the max function. We can define it as.
max(x,y) = M3(x,y,1)
If the inputs to M3 are allowed to use expressions like 1-x, then I'll
guess that all n-ary operations can be defined in terms of M3, and
that the proof can be done by induction.
If the inputs to M3 are only allowed to be constants 0,1 and/or the
arguments to the desired function, then I think it's clear that some
functions can't be defined -- those that really need negation.
So you need to clarify what is meant by defining a function in terms
of M3. What are the restrictions on the inputs? What expressions
involving M3 are allowable?
quasi
Arturo Magidin
> Let M3 be the ternary operation on {0, 1} defined by M3(x, y, z)
> = 1 whenever the number of its arguments that is 1 is greater than
> 1, and 0 otherwise (i.e. "majority rule on 3 yes-no votes").
>
> What n-ary operations can be derived from M3?
This is a problem in George Bergman's "An Invitation to General
Algebra and Universal Constructions." It is usually solved, over the
course of the entire semester, by one or two students in the course.
It's not a trivial exercise.
So I'm afraid I'm not going to just give away the solution over which
I labored for an entire semester...
> I'm totally lost
> with this one.
>
> As far as I can tell, no 0-ary operation can be derived from M3
> (since, without any arguments at all, I can see no way to invoke
> M3), but I'm not sure if this reasoning constitutes a valid proof,
> and if not, I can't figure out how a valid proof would go.
The derived operators are generated by the operators you have plus the
arbitrary n-ary projection operators. Prove that at no point in the
constructions of derived operators will you get a zero-ary operator,
by induction.
> For n > 0, and again, reasoning very informally, I'd say that any
> n-ary operation O derived from M3 would have to be "odd" since M3
> is odd.
> (I'm calling "odd" any operation O such that O(~x) = ~O(x)
> where ~0 = 1 and ~1 = 0.) Once more, I wouldn't even know where
> to begin to prove this formally.
Induction again.
>
> The only unary operation I can come up with is the identity I: I(x)
> = M(x, x, x). I can't come up with ~ (i.e. "negation", as defined
> above), even though it is odd, but, again, I can't prove it can't
> be done.
>
> As for binary operations, the only ones I can derive are the ones
> that correspond to "first coordinate" (p0(x, y) = M(x, x, x)) and
> "second coordinate" (p1(x, y) = M(y, y, y)). (In fact, this
> generalizes to the "j-th coordinate n-ary" operation, for any n >
> 0, and any 1 <= j <= n.)
You always have the projection operators that take (x_1,\ldots,x_n) to
x_i, 1<= i <=n.
> I can't come up with xor nor !xor (i.e.,
> not xor), both of which are odd, nor can I can up with a proof that
> this is impossible.
>
> And so on...
>
> I imagine that all the missing proofs above can be done with
> basically the same argument. Any help would be appreciated.
Suggestions for exploration:
(1) Can you obtain *any* "majority vote" operation? Try to get a 5-
person majority-vote operator using M3. How about a 4-person majority
vote operator, where one particular voter can break ties? How about
more general ones?
(2) Can you obtain "weighted" majority vote operators? An n-ary
operator on {0,1} is a "weighted majority vote" if there exist
nonnegative integers a_1,...,a_n such that W(x_1,...,,x_n) is the
majority of x_1,..,x_n, with x_1's vote counting a_1 times, x_2's vote
counting a_2 times, and so on. You can set tie-breaker votes.
An obvious conjecture, if the answers to the two questions above are
"yes", is:
(3) Can you determine whether *every* derived operator is a weighted
majority vote operator? If so, you're done. If not, can you exhibit
one that is not a weighted majority vote operator?
I'll let you to it now.
--
Arturo Magidin
kj
In <ip9bk6tpdnv0s32vs...@4ax.com> quasi <qu...@null.set> writes:
>On Sun, 30 Jan 2011 17:30:23 +0000 (UTC), kj <no.e...@please.post>
>wrote:
>>
>>Let M3 be the ternary operation on {0, 1} defined by M3(x, y, z)
>>= 1 whenever the number of its arguments that is 1 is greater than
>>1, and 0 otherwise (i.e. "majority rule on 3 yes-no votes").
>>
>>What n-ary operations can be derived from M3? I'm totally lost
>>with this one.
To clarify: to define operations "in terms of M3" means operations
like, e.g. q(w, x, y, z) = M3(M3(w, x, y), z, M3(x, y, z)).
>>As far as I can tell, no 0-ary operation can be derived from M3
>>(since, without any arguments at all, I can see no way to invoke
>>M3), but I'm not sure if this reasoning constitutes a valid proof,
>>and if not, I can't figure out how a valid proof would go.
>No, that's not right.
>The 0-ary operations are the constants 0 and 1.
>But 1 = M3(1,1,1) and 0 = M3(0,0,0), which defines both 0-ary
>operations in terms of M3. There are other choices, but we only need
>to show one way to do it.
The notes I'm following explicitly rule out what you're proposing.
According to these notes, to be able to write a term like M3(0, x,
y) (let alone M3(0, 0, 0)), one already needs to have the 0-ary
operation that yields 0. To quote the original:
"...since our system ({0, 1}, M3) does not include the *zeroary
operation* 0 (nor 1), 'M3(0, x, y)' is not a term."
("An invitation to general algebra", by G. Bergman. Exercise 1.7:1
(p. 18, ch 1) Available online as a set of PostScript files.)
Thanks for your reply. Clearly I can't explain the problem adequately
without replicating a lot of formal machinery that I barely
understand. (It is very likely that I don't understand the problem
to begin with.)
~kj
Arturo Magidin
>
> The notes I'm following explicitly rule out what you're proposing.
> According to these notes, to be able to write a term like M3(0, x,
> y) (let alone M3(0, 0, 0)), one already needs to have the 0-ary
> operation that yields 0. To quote the original:
>
> "...since our system ({0, 1}, M3) does not include the *zeroary
> operation* 0 (nor 1), 'M3(0, x, y)' is not a term."
>
> ("An invitation to general algebra", by G. Bergman. Exercise 1.7:1
> (p. 18, ch 1) Available online as a set of PostScript files.)
>
> Thanks for your reply. Clearly I can't explain the problem adequately
> without replicating a lot of formal machinery that I barely
> understand. (It is very likely that I don't understand the problem
> to begin with.)
No, you are correct that you don't have the zeroary operators; but you
do have the projections.
--
Arturo Magidin
Arturo Magidin
> On Sun, 30 Jan 2011 17:30:23 +0000 (UTC), kj <no.em...@please.post>
> wrote:
>
>
>
> >Let M3 be the ternary operation on {0, 1} defined by M3(x, y, z)
> >= 1 whenever the number of its arguments that is 1 is greater than
> >1, and 0 otherwise (i.e. "majority rule on 3 yes-no votes").
>
> >What n-ary operations can be derived from M3? I'm totally lost
> >with this one.
>
> >As far as I can tell, no 0-ary operation can be derived from M3
> >(since, without any arguments at all, I can see no way to invoke
> >M3), but I'm not sure if this reasoning constitutes a valid proof,
> >and if not, I can't figure out how a valid proof would go.
>
> No, that's not right.
>
> The 0-ary operations are the constants 0 and 1.
The *possible* zeroary operations are the constants 0 and 1, but they
are not zeroary operators in the clone of M3.
(Consider the case of semigroups, which begin with a single binary
operator; there are no zero-ary derived operators for semigroups at
all).
When you construct derived operators, you get the operators you are
given, and you may also assume you have all the projection operators
p_{n,i} : X^n --> X given by p_{n,1}(x_1,...,x_n) = x_i. But that's
it. You don't get zero-ary operators for free.
You are not looking for *all* operators, just the derived ones.
> But 1 = M3(1,1,1) and 0 = M3(0,0,0), which defines both 0-ary
> operations in terms of M3. There are other choices, but we only need
> to show one way to do it.
>
> Next try 1-ary operations.
>
> A 1-ary operation on {0,1} is just a function from
>
> {0,1} -> {0,1}
>
> thus there are 4 such functions, namely the functions
>
> a(x) = 0
> b(x) = 1
> c(x) = x
> d(x) = 1-x
The only 1-ary *derived* operator here is the identity map, which is
the "1-ary" projection.
> The functions a,b,c can be defined as follows:
>
> a(x) = M3(0,0,0)
> b(x) = M3(1,1,1)
> c(x) = M3(x,1,0)
Nope.
> The function d is problematic.
The function d is not a derived function (I know because I know
exactly what all the derived functions are, having solved this problem
16 years ago, but it may not be obvious right now).
> You can define it as
>
> d(x) = M3(1-x,1,0)
>
> provided the expression M3(1-x,1,0) is allowed.
Since x|-> 1-x, 1, and 0 are not derived operators, while it is true
you can *define* it this way, it is not a derived operator in this
algebra.
Quasi, I think you'll find this exercise *very* interesting and fun;
but you should check out the original notes to see what is and what is
not allowed. They are available at George Bergman's website,
http://math.berkeley.edu/~gbergman/245/
Look in the index to find the problem.
--
Arturo Magidin
Ilmari Karonen
> On Sun, 30 Jan 2011 17:30:23 +0000 (UTC), kj <no.e...@please.post>
> wrote:
>>
>>Let M3 be the ternary operation on {0, 1} defined by M3(x, y, z)
>>= 1 whenever the number of its arguments that is 1 is greater than
>>1, and 0 otherwise (i.e. "majority rule on 3 yes-no votes").
>>
>>What n-ary operations can be derived from M3? I'm totally lost
>>with this one.
>>
>>As far as I can tell, no 0-ary operation can be derived from M3
>>(since, without any arguments at all, I can see no way to invoke
>>M3), but I'm not sure if this reasoning constitutes a valid proof,
>>and if not, I can't figure out how a valid proof would go.
>
> No, that's not right.
>
> The 0-ary operations are the constants 0 and 1.
>
> But 1 = M3(1,1,1) and 0 = M3(0,0,0), which defines both 0-ary
> operations in terms of M3. There are other choices, but we only need
> to show one way to do it.
From kj's post, I'd assume he didn't mean to allow the constants 0 or
1 to be used.
> So you need to clarify what is meant by defining a function in terms
> of M3. What are the restrictions on the inputs? What expressions
> involving M3 are allowable?
That is indeed a good question. Pending kj's answer, I'll offer my
guess: specifically, that an "n-ary operation derived from M3" means
a function f: {0,1}^n -> {0,1} of the form
f(a_1, a_2, ..., a_n} = M3(x, y, z),
where x, y and z are either arguments to f (i.e. a_1, ..., a_n), or
expressions of the form M3(x', y', z'), with x', y' and z' being
either arguments to f or expressions of the same form. For the
derived operation to be well defined, we should also require that
there be no infinitely nested chains of subexpressions.
From this definition, we can see that any operation derived from M3
must retain two properties of M3 itself:
symmetry: 1-f(a_1, ..., a_n) = f(1-a_1, ..., 1-a_n), and
monotonicity: f(a_1, ..., a_n) >= f(b_1, ..., b_n) whenever a_i >=
b_i for all i in {1, ..., n}.
As kj argues above, clearly this definition rules out any 0-ary
operation derived from M3. If we wanted to try deriving such, we
could also allow the definitions to contain arbitrary variables,
subject to the constraint that the value of f not depend on the value
of those variables for any choice of arguments. But it's not hard to
see that the symmetry property still prevents us from deriving any
0-ary operation from M3: if the value of the operation were 0 for some
choice x=a, y=b, z=c, ... of the internal variables, then it would
have to be 1 for x=1-a, y=1-b, z=1-c, ....
It's also easy to see that there is only one symmetric and monotone
unary operation (f(a) = a), and only two such binary operations
(f(a,b) = a and f(a,b) = b). Of ternary operations with these
properties, I believe there are four: M3 itself and three trivial ones
similar to the unary and binary cases.
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? We can obviously derive them
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.
Another interesting question is how many arguments are needed to get
an operation derived from M3 which is _not_ expressible as a simple
weighted majority vote. Obviously 9 is enough (since you can have
M3(M3(a,b,c), M3(d,e,f), M3(g,h,i)) while 4 isn't, but that still
leaves a considerable gap.
I'm sure this has all been thoroughly studied, so perhaps others more
familiar with the topic may settle the issue. In the mean time, it
should be possible to enumerate all the operations derivable from M3
recursively for reasonable argument counts; I may try that tomorrow if
no-one beats me to it.
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
Arturo Magidin
>
> 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? We can obviously derive them
> 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:
Look at F(a,b,c,d,e)= M3(M3(a,b,c), M3(a,d,e), M3(b,c,d)).
This is a 5-way majority function whenever b and c vote differently.
If b=/=c, then if a=d=1, the first and second entries are 1; if a=e=1
then the first and second entries are 1; and if d=e=1 then the second
and third entries are 1.
If a=d=0, then the first and second entries are 0; if a=e=0 then the
second and third entries are 0; and if d=e=0 then the second and third
entries are 0.
However, this function will be 1 if b=c=1, and 0 if b=c=0, so it's not
*quite* a 5-way majority function.
Symmetrically, G(a,b,c,d,e)= M3(M3(b,a,d), M3(b,c,e), M3(a,d,c)) is a
5-way majority function provided that a and d vote differently, but
will give 1 if a=d=1, and 0 if a=d=0.
And H(a,b,c,d,e) = M3(M3(a,b,e), M3(a,c,d), M3(c,d,e)) is a 5-way
majority function if b=/=e, but will give 1 if b=e=1, and 0 if b=e=0.
Now take the 3-way majority of all of them,
K(a,b,c,d,e)=M3(F(a,b,c,d,e),G(a,b,c,d,e),H(a,b,c,d,e)). If at least
two of them are 5-way majority functions, then their 3-way majority is
itself a 5-way majority, since two of them agree with the 5-way
majority.
If none of them are 5-way majorities, that is if b=c=e and a=d, then
we get 1 if b=c=e=1 and 0 if b=c=e=0, which is in fact the 5-way
majority.
If F is a 5-way majority (b=/=c) but G and H are not (so a=d and b=e),
then:
* If a=d=1, then F=1 and G=1, then K is 1, the right answer.
* If a=d=0, then F=0 and G=0, so K is 0, again the right answer.
If G is a 5 way majority (a=/=d) but F and H are not (so b=c=e), then:
* If b=c=e=1, then F=H=1, so K=1, the right answer.
* If b=c=e=0, then F=H=0, so K=0, the right answer.
If H is a 5-way majority (b=/=e) but F and G are not (b=c and a=d),
then:
* if a=d=1, then G=H=1, so K=1, the right answer.
* if a=d=0, then G=H=0, so K=0l the right answer.
Thus, K is a 5-way majority function.
> Another interesting question is how many arguments are needed to get
> an operation derived from M3 which is _not_ expressible as a simple
> weighted majority vote. Obviously 9 is enough (since you can have
> M3(M3(a,b,c), M3(d,e,f), M3(g,h,i)) while 4 isn't, but that still
> leaves a considerable gap.
If I recall correctly, 5 is the smallest.
> I'm sure this has all been thoroughly studied, so perhaps others more
> familiar with the topic may settle the issue.
Indeed; as noted, this is an exercise in Bergman's book. A nice, fun,
exercise. Usually students present partial solutions throughout the
semester, presenting conjectures, examples, counterexamples, etc,
until the full answer is established sometime towards the end of the
semester.
--
Arturo Magidin
kj
>On Jan 30, 4:07=A0pm, 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? =A0We can obviously derive them
>> 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:
>Look at F(a,b,c,d,e)=3D M3(M3(a,b,c), M3(a,d,e), M3(b,c,d)).
>This is a 5-way majority function whenever b and c vote differently.
>If b=3D/=3Dc, then if a=3Dd=3D1, the first and second entries are 1; if a=
>=3De=3D1
>then the first and second entries are 1; and if d=3De=3D1 then the second
>and third entries are 1.
>If a=3Dd=3D0, then the first and second entries are 0; if a=3De=3D0 then th=
>e
>second and third entries are 0; and if d=3De=3D0 then the second and third
>entries are 0.
>However, this function will be 1 if b=3Dc=3D1, and 0 if b=3Dc=3D0, so it's =
>not
>*quite* a 5-way majority function.
>Symmetrically, G(a,b,c,d,e)=3D M3(M3(b,a,d), M3(b,c,e), M3(a,d,c)) is a
>5-way majority function provided that a and d vote differently, but
>will give 1 if a=3Dd=3D1, and 0 if a=3Dd=3D0.
>And H(a,b,c,d,e) =3D M3(M3(a,b,e), M3(a,c,d), M3(c,d,e)) is a 5-way
>majority function if b=3D/=3De, but will give 1 if b=3De=3D1, and 0 if b=3D=
>e=3D0.
>Now take the 3-way majority of all of them,
>K(a,b,c,d,e)=3DM3(F(a,b,c,d,e),G(a,b,c,d,e),H(a,b,c,d,e)). If at least
>two of them are 5-way majority functions, then their 3-way majority is
>itself a 5-way majority, since two of them agree with the 5-way
>majority.
>If none of them are 5-way majorities, that is if b=3Dc=3De and a=3Dd, then
>we get 1 if b=3Dc=3De=3D1 and 0 if b=3Dc=3De=3D0, which is in fact the 5-wa=
>y
>majority.
>If F is a 5-way majority (b=3D/=3Dc) but G and H are not (so a=3Dd and b=3D=
>e),
>then:
> * If a=3Dd=3D1, then F=3D1 and G=3D1, then K is 1, the right answer.
> * If a=3Dd=3D0, then F=3D0 and G=3D0, so K is 0, again the right answer.
>If G is a 5 way majority (a=3D/=3Dd) but F and H are not (so b=3Dc=3De), th=
>en:
> * If b=3Dc=3De=3D1, then F=3DH=3D1, so K=3D1, the right answer.
> * If b=3Dc=3De=3D0, then F=3DH=3D0, so K=3D0, the right answer.
>If H is a 5-way majority (b=3D/=3De) but F and G are not (b=3Dc and a=3Dd),
>then:
> * if a=3Dd=3D1, then G=3DH=3D1, so K=3D1, the right answer.
> * if a=3Dd=3D0, then G=3DH=3D0, so K=3D0l the right answer.
>Thus, K is a 5-way majority function.
Thanks! Here's another one:
M3(a, M3(b, c, d), M3(b, e, M3(c, d, e)))
My program found a ton more, of roughly the same complexity.
>Indeed; as noted, this is an exercise in Bergman's book. A nice, fun,
>exercise. Usually students present partial solutions throughout the
>semester, presenting conjectures, examples, counterexamples, etc,
>until the full answer is established sometime towards the end of the
>semester.
Hmmm, so far, I'm not sure what I learned from this exercise...
The solution (at least mine) gives me no insight. I had
hoped/imagined/assumed that the answer would hinge on some algebraic
constraint (e.g. whether the arity was divisible by 3, or some
such).
Then again, I'm done yet...
I like these notes so far, but I wish Bergman pointed out the
difficulty level of these exercises. If I'd known that this one
was going to be so much work, I would have skipped it. I'm doing
this just to learn the basic ideas, not to become a general algebra
ninja... :)
~kj
Arturo Magidin
> In <dd2421b4-5140-4086-a607-1c1e38801...@e2g2000yqi.googlegroups.com> Arturo Magidin <magi...@member.ams.org> writes:
>
>
>
> >On Jan 30, 4:07=A0pm, 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? =A0We can obviously derive them
> >> 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! Here'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.
> My program found a ton more, of roughly the same complexity.
>
> >Indeed; as noted, this is an exercise in Bergman's book. A nice, fun,
> >exercise. Usually students present partial solutions throughout the
> >semester, presenting conjectures, examples, counterexamples, etc,
> >until the full answer is established sometime towards the end of the
> >semester.
>
> Hmmm, so far, I'm not sure what I learned from this exercise...
> The solution (at least mine) gives me no insight.
I did not mean "Write the 5-way majority function as a derived
operator", I mean the *full* exercise: give a nice description of the
set of all derived operations.
> I had
> hoped/imagined/assumed that the answer would hinge on some algebraic
> constraint (e.g. whether the arity was divisible by 3, or some
> such).
They *will*, in the end. Just perhaps not the one you are expecting
right now.
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) =
1?
(ii) Is it true that if q is a derived operation, then q(0,0,...,0) =
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) ?
> Then again, I'm done yet...
>
> I like these notes so far, but I wish Bergman pointed out the
> difficulty level of these exercises. If I'd known that this one
> was going to be so much work, I would have skipped it. I'm doing
> this just to learn the basic ideas, not to become a general algebra
> ninja... :)
This was one commplaint that the reviewer in MathReviews had in an
otherwise generally glowing review.
--
Arturo Magidin
>
> ~kj
quasi
Ah, I see the issue.
Thanks for the clarification.
quasi
quasi
<mag...@member.ams.org> wrote:
>On Jan 30, 12:42 pm, quasi <qu...@null.set> wrote:
>> On Sun, 30 Jan 2011 17:30:23 +0000 (UTC), kj <no.em...@please.post>
>> wrote:
>>
>> >Let M3 be the ternary operation on {0, 1} defined by M3(x, y, z)
>> >= 1 whenever the number of its arguments that is 1 is greater than
>> >1, and 0 otherwise (i.e. "majority rule on 3 yes-no votes").
>> >
>> >What n-ary operations can be derived from M3? I'm totally lost
>> >with this one.
>> >
>> >As far as I can tell, no 0-ary operation can be derived from M3
>> >(since, without any arguments at all, I can see no way to invoke
>> >M3), but I'm not sure if this reasoning constitutes a valid proof,
>> >and if not, I can't figure out how a valid proof would go.
>>
>> No, that's not right.
>>
>> The 0-ary operations are the constants 0 and 1.
>
>The *possible* zeroary operations are the constants 0 and 1, but they
>are not zeroary operators in the clone of M3.
Ok, I see.
>(Consider the case of semigroups, which begin with a single binary
>operator; there are no zero-ary derived operators for semigroups at
>all).
Yes, I follow.
Yes, it seems like it would be a nice problem to play with.
Thanks for the clarification on the allowable constructions.
quasi
Arturo Magidin
Seems I misrememberd the exact wording.
Here's the review:
MR1650275 (99h:18001)
Bergman, George M.(1-CA)
An invitation to general algebra and universal constructions. Henry
Helson, Berkeley, CA, 1998. ii+398 pp. ISBN: 0-9655211-4-1
18-01 (00A05 08-01 16-01 20-01)
My first reaction to this book was that I would love to teach a course
based on it. My second reaction was that I would love to have students
I could teach such a course to. The book is intended as a textbook for
a somewhat idiosyncratic course in what I have always called universal
algebra, here called general algebra, the older term being somewhat
overblown. In fact, it is much more a course in category theory,
although a slightly idiosyncratic version of that too, in ways I will
explain.
The content of the book consists mostly of definitions, informal
discussions, statements of theorems, a few proofs and problems,
problems, problems, over 600 of them. Most of the actual mathematics
resides in them. Some of them include suggestions; most do not. A
relative few are routine; most are not and some are unsolved. Just to
mention one instance, the very non-routine problem of classifying the
epimorphisms in the category of groups is just dropped in among some
relatively easier questions. Note that the student is not even asked
to prove they are surjections (which is plenty hard), but just to
classify them. The student is not expected to do all the problems, but
a selection of them, of his own choosing. He is expected to spend at
least five minutes contemplating every one of them that is not
immediately solvable and is usually given little guidance as to which
ones are tractable.
The exposition in the book is extraordinarily good. There is always
a tension in any mathematical exposition between readability and
logical correctness. Most authors attempt a compromise and wind up
with something that is neither particularly readable nor completely
rigorous. Through some sort of magic, the discussion in this book is
completely rigorous, making notational distinctions, such as between
an algebra and its underlying set, that I have long ago abandoned. At
the same time, it manages to avoid seeming overly pedantic, remaining
very clear and readable! This sort of exposition is not dashed off in
a minute.
Here is a list of the chapters, accompanied by brief descriptions.
The number of pages is listed in order to give an idea where the main
emphasis lies. Chapter 0, "About the course, and these notes'' (6
pages), basically consists of instructions to the student. Chapter 1,
"Making some things precise'' (9 pages), is essentially an informal
description of signatures, algebras, terms, and equations, using the
theory of groups as the paradigm. Chapter 2, "Free groups'' (14
pages), gives three distinct constructions of free groups. The first
is as equivalence classes of terms (beginning with the base), the
second is as a subobject of a product as given by the general adjoint-
functor theorem and the third is as terms in normal form. It is
perhaps not made as clear as it might be that the first two
constructions are perfectly general, while the third requires that
there be a normal form. Chapter 3, "A Cook's tour of other universal
constructions'' (51 pages), consists of example after example of
limits, colimits, and adjoints, without mentioning those words. These
are as diverse as abelianization of a group, Grothendieck group of a
monoid, tensor products, Stone-Čech compactification, and much more.
This chapter is pure category theory without the words. Chapter 4,
"Ordered sets, induction, and the axiom of choice'' (35 pages), could
have been titled, "Everything you wanted to know about sets and
ordinals but were afraid to ask''. Chapter 5, "Lattices, closure
properties, and Galois connections'' (16 pages), is described by its
title, save for some mysticism about threes that most readers will
ignore. Chapter 6, "Categories and functors'' (56 pages), also
includes natural transformations and is a fine introduction to
categories. It includes a discussion of universes, a subject I have
always tried to avoid since you always wind up proving that the choice
of universe has no effect on anything. Chapter 7, "Universal
constructions in category-theoretic terms'' (61 pages), puts back the
words omitted in Chapter 3. It does more, of course, giving a fine
motivation for directed limits using the $p$p-adic numbers and then
general limits and colimits including the usual existence theorems.
There is one terminological oddity in that Bergman calls equalizers
and coequalizers difference kernels and difference cokernels,
respectively. The older names go back to the days when all categories
of interest were abelian and were never very evocative in more general
categories. In any case, they have not been in general use in 30
years. Included is Freyd's general adjoint-functor theorem, but not
the much more informative special adjoint-functor theorem. Chapter 8,
"Varieties of algebras'' (50 pages), finally gets to the general
algebra of the book's title. Even so there is little of the usual
preoccupations of universal algebra such as lattices of varieties or
lattices of subalgebras and congruences. Not that I am complaining,
but I am a bit surprised. The chapter also contains the one
mathematical error that I found. The suggestion for the solution to
Exercise 8.10:6, part (ii), that the category Clone of Lawvere
theories is not itself varietal cannot be right, since it would also
imply that the full subcategory Clone$_0$0 of Lawvere theories without
constants was not varietal, which it is. (This is mentioned in the
errata, see below.) One surprising omission from this chapter is the
theorem that characterizes when a functor $U\colon \bold V \to {\rm
Set}$U:V→Set that has a left adjoint is varietal: First, V has to have
the property that every equivalence relation on every object is a
kernel pair, and second that $Uf$Uf is surjective if and only if $f$f
is a regular epimorphism, and, finally, that $Uf$Uf is injective if
and only if $f$f is a monomorphism. This elegant result certainly
deserves a place here. An even more surprising omission is any mention
of, or even a pointer to, triples (or monads), which I would have
thought, after Lawvere theories, to be the main point of contact
between category theory and universal algebra. (The author tells me
that this is to be included in a projected Chapter 10.) Chapter 9,
"Algebra and coalgebra objects in categories and functors having
adjoints'' (52 pages), is mainly concerned with "representable''
functors between varietal categories. Such a functor $F\colon\bold V\to
\bold W$F:V→W is given by an object of V that is a coalgebra for the
theory of W. It also studies contravariant adjoints between varieties.
These are given by sets with operations that are models of each theory
in such a way that the operations for each are homomorphisms for the
other (such sets of operations are said to commute).
As can be seen from the page count, there is much more here that is
category theory than is universal algebra. This is a beautiful book,
but I do not know many students that could make much headway with the
exercises, and they are the heart of it.
This book is available on the web at http://math.berkeley.edu/$\break
^\sim$∼gbergman/245 with errata at http://math.berkeley.edu/$\break ^
\sim$∼gbergman/updates/245.html.
Reviewed by M. Barr
Marshall
> On Jan 30, 10:32 pm, Arturo Magidin <magi...@member.ams.org> wrote:
>
> > On Jan 30, 9:56 pm, kj <no.em...@please.post> wrote:
> > > I like these notes so far, but I wish Bergman pointed out the
> > > difficulty level of these exercises. If I'd known that this one
> > > was going to be so much work, I would have skipped it. I'm doing
> > > this just to learn the basic ideas, not to become a general algebra
> > > ninja... :)
>
> > This was one commplaint that the reviewer in MathReviews had in an
> > otherwise generally glowing review.
>
> Seems I misrememberd the exact wording.
>
> Here's the review:
>
> MR1650275 (99h:18001)
> Bergman, George M.(1-CA)
> An invitation to general algebra and universal constructions. Henry
> Helson, Berkeley, CA, 1998. ii+398 pp. ISBN: 0-9655211-4-1
> 18-01 (00A05 08-01 16-01 20-01)
I don't suppose anyone knows where I could pick up a hardcopy?
It's out of print; amazon doesn't say much about it.
I could download the PDF but reading this sort of dense material
doesn't work so well for me on computer screens.
Marshall
Arturo Magidin
> On Jan 31, 6:40 am, Arturo Magidin <magi...@member.ams.org> wrote:
>
>
>
> > On Jan 30, 10:32 pm, Arturo Magidin <magi...@member.ams.org> wrote:
>
> > > On Jan 30, 9:56 pm, kj <no.em...@please.post> wrote:
> > > > I like these notes so far, but I wish Bergman pointed out the
> > > > difficulty level of these exercises. If I'd known that this one
> > > > was going to be so much work, I would have skipped it. I'm doing
> > > > this just to learn the basic ideas, not to become a general algebra
> > > > ninja... :)
>
> > > This was one commplaint that the reviewer in MathReviews had in an
> > > otherwise generally glowing review.
>
> > Seems I misrememberd the exact wording.
>
> > Here's the review:
>
> > MR1650275 (99h:18001)
> > Bergman, George M.(1-CA)
> > An invitation to general algebra and universal constructions. Henry
> > Helson, Berkeley, CA, 1998. ii+398 pp. ISBN: 0-9655211-4-1
> > 18-01 (00A05 08-01 16-01 20-01)
>
> I don't suppose anyone knows where I could pick up a hardcopy?
> It's out of print; amazon doesn't say much about it.
The book was published by Henry Helson, 15 The Crescent, Berkeley, CA,
94708; it was, I believe, print-on-demand.
> I could download the PDF but reading this sort of dense material
> doesn't work so well for me on computer screens.
The website has PostScript versions of the files (not PDF). You could
always print it, of course...
--
Arturo Magidin
Arturo Magidin
> On Jan 31, 9:54 am, Marshall <marshall.spi...@gmail.com> wrote:
>
>
>
> > On Jan 31, 6:40 am, Arturo Magidin <magi...@member.ams.org> wrote:
>
> > > On Jan 30, 10:32 pm, Arturo Magidin <magi...@member.ams.org> wrote:
>
> > > > On Jan 30, 9:56 pm, kj <no.em...@please.post> wrote:
> > > > > I like these notes so far, but I wish Bergman pointed out the
> > > > > difficulty level of these exercises. If I'd known that this one
> > > > > was going to be so much work, I would have skipped it. I'm doing
> > > > > this just to learn the basic ideas, not to become a general algebra
> > > > > ninja... :)
>
> > > > This was one commplaint that the reviewer in MathReviews had in an
> > > > otherwise generally glowing review.
>
> > > Seems I misrememberd the exact wording.
>
> > > Here's the review:
>
> > > MR1650275 (99h:18001)
> > > Bergman, George M.(1-CA)
> > > An invitation to general algebra and universal constructions. Henry
> > > Helson, Berkeley, CA, 1998. ii+398 pp. ISBN: 0-9655211-4-1
> > > 18-01 (00A05 08-01 16-01 20-01)
>
> > I don't suppose anyone knows where I could pick up a hardcopy?
> > It's out of print; amazon doesn't say much about it.
>
> The book was published by Henry Helson, 15 The Crescent, Berkeley, CA,
> 94708; it was, I believe, print-on-demand.
However, it would appear Mr Helson died in 2010. I don't know what
the status is now.
But even if you bought it from the publisher, it would pretty much
look exactly the same as if you download the PS files and print them
yourself. It was printed right off those files. with softcover binding
around it.
--
Arturo Magidin
Marshall
I know the academic world is much used to postscript, but
I generally find PDF easier to work with. There is a PDF
available at:
http://fldit-www.cs.uni-dortmund.de/~peter/GenAlg.pdf
According to which, there are "two copies available in Evans Hall"
so maybe I should whip over there, ha ha. (In the early 1980s
I spent many a late night in Evans Hall, staring at my C code
on an adm3a.)
Marshall
Arturo Magidin
Actually, this is not due to the "academic world", but that George
Bergman took a long time before he started using LaTeX (the book was
prepared using trff, if I remember correctly). You can change PS to
PDF using the freely available ps2pdf utility (it comes with my LaTeX
installation, for example).
> but
> I generally find PDF easier to work with. There is a PDF
> available at:
>
> http://fldit-www.cs.uni-dortmund.de/~peter/GenAlg.pdf
>
> According to which, there are "two copies available in Evans Hall"
> so maybe I should whip over there, ha ha. (In the early 1980s
> I spent many a late night in Evans Hall, staring at my C code
> on an adm3a.)
You could also try sending a polite query to the author.
--
Arturo Magidin
Frederick Williams
>
> According to which, there are "two copies available in Evans Hall"
> so maybe I should whip over there, ha ha.
Also: "Copies may be purchased at $5 discount from my office." So
perhaps the author can sell you one.
--
When a true genius appears in the world, you may know him by
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting
Marshall
OMG, what an excellent, and in retrospect obvious, suggestion.
Thanks.
Marshall
PS. And thanks to Frederick for a similar post.
kj
>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.
Thinking about this stuff is like a drug.
~kj
Marshall
> >
> >Thus, K is a 5-way majority function.
>
> Thanks! Here's another one:
>
> M3(a, M3(b, c, d), M3(b, e, M3(c, d, e)))
>
> My program found a ton more, of roughly the same complexity.
This may not be surprising.
Consider that:
M3(a, b, c) = M3(a, c, b) = M3(b, a, c) = M3(b, c, a) = M3(c, a, b) =
M3(c, b, a)
If this were a binary function I'd call it "commutativity" but I
don't have a name for it here. ("Generalized 3-way commutativity"?)
If the subterms are all variables, then each of these six terms
are alpha equivalent, but in the case of your five-way tie term,
there will be an equivalence class of terms, all of size 13,
and all of which are semantically equivalent by the above
six-way equation.
I think that makes for 18 different orientations of your term,
if we restrict ourselves to considering only terms in which
variables are introduced in canonical order. With five variables,
there are 120 ways that variables can be introduced, for a
total of 18*120 = 2160 terms in the overall equivalence class
of your term. (I did this before breakfast so I haven't check
it at all closely; I may have done some figuring wrong.)
Marshall
Arturo Magidin
M3(b, e, M3(c, d, e))
is a 4-way majority function where e has tie-breaking vote.
The way I used to think of these was in terms of "committees". c, d,
and e are a committee that is reporting to the conference. The only
way e cannot have his way is if everyone votes against him: if either
b agrees with e, or one of c and d agree with e, then at least two of
the votes in the entire conference will go e's way.
So now take the poll of the other 3, of b, c, and d. If they all
agree, then the 4-way majority agreed with them anyway. If two of them
agree, then the 4-way majority went the way that e went; if e agreed
with the majority of b, c, and d, then M3(b,c,d) and M3(b,e,M3(c,d,e))
agree, so that's the way the 5-way vote goes. If e disagreed with
them, then we have an even split between b, c, d, and e, and an even
split between M3(b,c,d) and M3(b,e,M3(c,d,e)). So the deciding vote
goes to a, hence you take M3(a, M3(b,c,d), M3(b, e, M3(c,d,e)) ).
The class was not a lecture; as students would present partial
(sometimes correct, sometimes not) solutions, the discussions would
ensue.
> 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 reviewer is refering to Section 5.4 (page 139 and following). It
is completely irrelevant to the development, more "musing out loud"
than anything else, including quoting Alan Dundes (folklorist at
Berkeley). As Bergman notes at the end of the section,
"I do not attach great importance to the observations of this
section. But I have noticed them for years, and thought it would be a
good place to mention them."
Excise the section, nothing whatosever is lost from the book. This is
what the reviewer refered to.
--
Arturo Magidin