Conference rusure::math

Prove the following theorems, and solve the problems.  In all cases the
operation is closed on F and associative.

Theorem 1. The Cartesian product of two L-froops is an L-froop; and
  similarly for R-froops, C-froops, froops, and Abelian froops.
Theorem 2. If u is an L-, R-, or C-inverse, uu = u.
Theorem 3. If u is an L-inverse, it is a left identity (ua = a for all a).
  Similarly an R-inverse is a right identity.
Theorem 4. In an L-froop or R-froop, every element is idempotent
  (aa = a for all a).
Theorem 5. In a C-froop, aaa = aa for all a.
Theorem 6. If u is an L-inverse and v an R-inverse, u=v.  Therefore every
  froop has a unique inverse.
Theorem 7. Every L-inverse or R-inverse is also a C-inverse.
  Therefore every L-froop or R-froop is a C-froop.
Problem 8. Find an L-froop of minimal order that isn't an R-froop,
  thus showing that the converse of Theorem 6 doesn't hold.
Problem 9. Find a C-froop of minimal order which is neither an L-froop
  nor an R-froop.
Theorem 10. Prove that F is an L-froop with inverse u iff (1) u is a left
  identity, and (2) every element of F is idempotent.  (Similarly for
  R-froops; and froops require u be both a left and right identity.)
Theorem 11. If F is a finite Abelian semigroup with every element
  idempotent, then F is a froop.  Show this doesn't necessarily follow
  if F is infinite.
Problem 12. Does there exist a C-froop with a non-idempotent element?

Well, I need to see if I can even construct a simple froop.  Let's try 3
elements:

	*	A	B	C

A		_	_	_

B		_	_	_

C		_	_	_

Your definition said:


> Recall that a group has a unique identity, and each of its elements has an
> inverse.  The idea behind froops is that a froop has a unique inverse, and
> each element has an identity.
> 
> Let us use the following definitions.  As usual, we identify a froop F with
> its set of elements.  The operation is assumed to be closed on F and
> associative; it is denoted in the manner of group multiplication.



o.k.  If A,B,C are part of a froop, then there is a unique inverse.  So let's
have element "A" be our inverse.

What does this mean ?  Well, for A to be "the" inverse, it means when A is
multiplied by any element, the product (which is in F too by closure) is
an "identity".

But what's an "identity" ?  It's like the number 1.  It's an element which
when multiplied by any element, you just get the original element.

o.k.  So A is our inverse.  Let's assume it's a "left" inverse.  So, let's
try multiplying it by B.  What can we say about

	A*B

Well, the product is an identity.  Hence anything multiplied by A*B doesn't
change the value.  I don't know if identities have to be commutative.
Let's assume our identity is a left-side one.  Hence we know

	(A*B)*A = A
	(A*B)*B = B
	(A*B)*C = C

Where can we go from these ?  Well, for one thing, it's associative, so we
can move the parens and get:

 	A*(B*A) = A
	A*(B*B) = B
	A*(B*C) = C


What else can we do ?  Well, we arbitrarily multiplied A by B originally.
Let's multiply it by C instead.  Since A is "the" inverse, then multiplying
it by C on the left produces an identity, which in turn can then be multiplied
on the left by everything without changing the value.  So we have:

	(A*C)*A = A
	(A*C)*B = B
	(A*C)*C = C

and associating those 3, we get

	A*(C*A) = A
	A*(C*B) = B
	A*(C*C) = C

Since A is an inverse, we can also multiply it by itself and necessarily
get an identity too, right ?  So we have a third set:

	(A*A)*A = A
	(A*A)*B = B
	(A*A)*C = C

and associating these we have:

	A*(A*A) = A
	A*(A*B) = B
	A*(A*C) = C

Now, can we use the above information to fill in the original table ?  Filling
in the original table means calculating either A, B or C for each of the
9 expressions A*A, A*B, A*C, B*A, B*B, B*C, C*A, C*B, C*C.

Here's the expressions we have so far (merely repeated and condensed):


	(A*B)*A = A
	(A*B)*B = B
	(A*B)*C = C
 	A*(B*A) = A
	A*(B*B) = B
	A*(B*C) = C
	(A*C)*A = A
	(A*C)*B = B
	(A*C)*C = C
	A*(C*A) = A
	A*(C*B) = B
	A*(C*C) = C
	(A*A)*A = A
	(A*A)*B = B
	(A*A)*C = C
	A*(A*A) = A
	A*(A*B) = B
	A*(A*C) = C

I'm stuck.  Where do we go from here ?  How do we melt down 3-variable values
into 2-variable ones ?


/Eric

Well, not knowing any better, let's arbitrarily see if A*B could be A.

So, I'll replace A*B by A in all the expressions we have so far:


	A*A = A
	A*B = B
	A*C = C
 	A*(B*A) = A
	A*(B*B) = B
	A*(B*C) = C
	(A*C)*A = A
	(A*C)*B = B
	(A*C)*C = C
	A*(C*A) = A
	A*(C*B) = B
	A*(C*C) = C
	(A*A)*A = A
	(A*A)*B = B
	(A*A)*C = C
	A*(A*A) = A
	A*A = B
	A*(A*C) = C

We see there's a contradiction, so we've made headway !  (We now know A*B
can't B A).  The contradiction is that the first line says that A*A is A
and the next to last line says A*A is B.  It can't be both !

So let's see if A*B can be B.  Again, do the replacements:


	B*A = A
	B*B = B
	B*C = C
 	A*(B*A) = A
	A*(B*B) = B
	A*(B*C) = C
	(A*C)*A = A
	(A*C)*B = B
	(A*C)*C = C
	A*(C*A) = A
	A*(C*B) = B
	A*(C*C) = C
	(A*A)*A = A
	(A*A)*B = B
	(A*A)*C = C
	A*(A*A) = A
	A*B = B
	A*(A*C) = C

So far so good.

We have a candidate for A*B.  So far we have:


	B*A = A
	B*B = B
	B*C = C
 	A*(B*A) = A
	A*(B*B) = B
	A*(B*C) = C
	(A*C)*A = A
	(A*C)*B = B
	(A*C)*C = C
	A*(C*A) = A
	A*(C*B) = B
	A*(C*C) = C
	(A*A)*A = A
	(A*A)*B = B
	(A*A)*C = C
	A*(A*A) = A
	A*B = B
	A*(A*C) = C


What about A*C ?  Can it be A ?  No, because we'd see both A*A=A and A*A=C.
So try A*C=B.  That looks o.k. I think.  But let's fill in entire table:


	B*A = A
	B*B = B
	B*C = C
 	A*(B*A) = A
	A*(B*B) = B
	A*(B*C) = C
	B*A = A
	B*B = B
	B*C = C
	A*(C*A) = A
	A*(C*B) = B
	A*(C*C) = C
	(A*A)*A = A
	(A*A)*B = B
	(A*A)*C = C
	A*(A*A) = A
	A*B = B
	A*B = C

Duplicate lines start to appear so let's remove them:

 	A*(B*A) = A
	A*(B*B) = B
	A*(B*C) = C
	B*A = A
	B*B = B
	B*C = C
	A*(C*A) = A
	A*(C*B) = B
	A*(C*C) = C
	(A*A)*A = A
	(A*A)*B = B
	(A*A)*C = C
	A*(A*A) = A
	A*B = B
	A*B = C

Assuming some sort of lexical order, for instance A*A, A*B, A*C, B*A, B*B etc.,
the first item we don't see yet is A*A.

Here's our list so far:


	B*A = A
	B*B = B
	B*C = C
 	A*(B*A) = A
	A*(B*B) = B
	A*(B*C) = C
	(A*C)*A = A
	(A*C)*B = B
	(A*C)*C = C
	A*(C*A) = A
	A*(C*B) = B
	A*(C*C) = C
	(A*A)*A = A
	(A*A)*B = B
	(A*A)*C = C
	A*(A*A) = A
	A*B = B
	A*(A*C) = C


Could A*A be A ?  I think so.  Replacements gives:


	B*A = A
	B*B = B
	B*C = C
 	A*(B*A) = A
	A*(B*B) = B
	A*(B*C) = C
	(A*C)*A = A
	(A*C)*B = B
	(A*C)*C = C
	A*(C*A) = A
	A*(C*B) = B
	A*(C*C) = C
	A*A = A
	A*B = B
	A*C = C
	A*A = A
	A*B = B
	A*(A*C) = C

Again, removing duplicates:


	B*A = A
	B*B = B
	B*C = C
 	A*(B*A) = A
	A*(B*B) = B
	A*(B*C) = C
	(A*C)*A = A
	(A*C)*B = B
	(A*C)*C = C
	A*(C*A) = A
	A*(C*B) = B
	A*(C*C) = C
	A*A = A
	A*B = B
	A*C = C
	A*(A*C) = C

It's only the C's we don't know yet, namely C*A, C*B, C*C.  Can C*A be A ?
It looks o.k:


	B*A = A
	B*B = B
	B*C = C
 	A*(B*A) = A
	A*(B*B) = B
	A*(B*C) = C
	(A*C)*A = A
	(A*C)*B = B
	(A*C)*C = C
	A*(C*B) = B
	A*(C*C) = C
	A*A = A
	A*B = B
	A*C = C
	A*(A*C) = C
	C*A = A

Oh, I just noticed that the first three lines allow the second three to be
removed, since substituting the first three into the second three yield
ones near the bottom:


	B*A = A
	B*B = B
	B*C = C
	(A*C)*A = A
	(A*C)*B = B
	(A*C)*C = C
	A*(C*B) = B
	A*(C*C) = C
	A*A = A
	A*B = B
	A*C = C
	A*(A*C) = C
	C*A = A

How about C*B.  Can it be A ?  No, we'd get a contradiction.  Can C*B be
B ?  Looks o.k.


	B*A = A
	B*B = B
	B*C = C
	(A*C)*C = C
	A*(C*C) = C
	A*A = A
	A*B = B
	A*C = C
	A*(A*C) = C
	C*A = A
	C*B = B

Substitution and removal of duplicates yields the rest of the story:


	A*A = A
	A*B = B
	A*C = C
	B*A = A
	B*B = B
	B*C = C
	C*A = A
	C*B = B
	C*C = C

Now we can fill in the table (assume it's left * top):


	*	A	B	C

A		A	B	C

B		A	B	C

C		A	B	C


Well, that's a rather uninteresting looking arrangement.  But if I haven't
made any errors, it *is* a froop.  Hmmm, let's review the requirements and
see if it works.

> Recall that a group has a unique identity, and each of its elements has an
> inverse.  The idea behind froops is that a froop has a unique inverse, and
> each element has an identity.

We postulated that A would be our unique inverse.  First of all, is A an
inverse ?  In other words, does every element when multiplied by A on the
left produce an identity ?

That is to say, is every product with A on the left a value which when in
turn used on the left doesn't change the value ?

Well, from chart, A on the left times anything produces the thing itself.
Does that thing itself then act as identity ?  It seems to.

So A is an inverse.  But is anything else ?  Is B an inverse ?  In other
words, when B is put on left of anything, does their product when put on the
left of anything not change the value ?  Well, B on the left of A produces
A, which indeed doesn't change the value when put in front of anything.  So
B seems to be an inverse.  So A is not a UNIQUE inverse.  Hence we've FAILED
so far to produce a froop.

Do I feel like going back and adjusting some values to make it into a froop?
Not really.

Anyone else have some ideas ?

This seems slow so far.  Tedium just to produce an *example* of a froop, let
alone trying to prove theorems on general froops...

/Eric

Maybe proofs are easier than finding an example of a froop ?  That is:

	IF a froop exists, then the following theorems would hold...

o.k. let's try it.  Theorem 1 says

	Theorem 1. The Cartesian product of two L-froops is an L-froop; and
  similarly for R-froops, C-froops, froops, and Abelian froops.


When I think of two froops, I think of two tables.  Each table might
have A,B,C along side and top (but might have some other values???)  Each
table has the 9 cross-values filled in differently.

So what does it mean to take the cartesian product ?  I think of cartesian
product as meaning every combination of something, but what ?  Headache...

Let's try the next:

Theorem 2. If u is an L-, R-, or C-inverse, uu = u.



u is the left inverse.  So, if we multiply u by any element A, we get
an identity.  So

	uA

is an identity.  This means uA times anything produces that thing.  So
for any element B, we have

	(uA)B = B

Since we're trying to reach uu=u, let's try using u instead of B:

	(uA)u = u

We might as well use u instead of A also:

	(uu)u = u

That looks close to what we want.  What can we do from here ?  Well, there's
associativity, so we can say

	u(uu) = u

Hmmm, are we allowed to plug one into the other ?  Using the left side of
the last equation as an alternate expression for u, and plugging into the
lone u on the left side of the second to last equation, gives:

	(uu)(u(uu)) = u

Associating this, we get:

	((uu)u)(uu) = u

This is turning into a mess...

    I see a possible source of confusion.  In the prolog, when I said that
    each element has an identity, it was a loose way of speaking: what was
    meant was an identity particular to that element.  For any froop
    element,
    one identity (there may be others) for that element is produced by
    multiplying it by the universal inverse u.  Now if the operation isn't
    commutative, you  must specify whether the inverse is to be multiplied
    on the left or right, and whether the resulting "identity" for the
    element a is a left identity (ea = a) or a right identity (ae = a).
    (Here I've used e as the name of the "identity".)
    
    The various theorems prove that, in any froop, the universal inverse u
    is also both a left and right (general) identity, au = ua = a for all
    a,
    and every element is idempotent (aa = a).  This means that you know at
    least one row, one column, and the diagonal.  Therefore, if the froop
    is of order 1 or 2, it's completely specified (the order-1 froop is
    called the "trivial froop" by analogy with groups).
    
    Exercise.  Prove there are just 2 (up to isomorphism) froops with 3
    elements, one Abelian and one not.  If you call the elements u, a, b,
    then the only products you must determine are ab and ba.

The reference in problem 8 should be to Theorem 7.

One of the "Theorems" is bogus.  Which one?

The following Ada program shows that there is an order 5 C-froop with an element
that isn't idempotent, solving #12.  Translation to Pascal should be easy.

To use on a VMS system, assuming you don't already have an Ada library:
$ acs create library [.adalib]
$ acs set library [.adalib]
Then compile, link, and run:
$ ada froop.ada
$ acs link froop
$ run froop

with Text_IO;
procedure froop is
  procedure Comment(S: in String) renames Text_IO.Put_Line;

  type F is (u,  a, aa, ua, au);
  times: constant array (F, F) of F := (
    u   => ( u, ua, aa, ua,  u),
    a   => (au, aa, aa,  a, aa),
    aa  => (aa, aa, aa, aa, aa),
    ua  => ( u, aa, aa, ua, aa),
    au  => (au,  a, aa,  a, au)
  );

  function "*"(l, r : F) return F is
  begin
    return times(l, r);
  end "*";
begin
  for x in F loop
    if x*u*x /= x then
      Comment("Axiom fails: x = " & F'Image(x));
    end if;
  end loop;
  for x in F loop
    for y in F loop
      for z in F loop
	if (x*y)*z /= x*(y*z) then
	  Comment("Associativity fails: x = " & F'Image(x) & " y = "
		& F'Image(y) & " z = " & F'Image(z));
	end if;
      end loop;
    end loop;
  end loop;
end froop;

    Hats off to Wesley Lane and MFY. A good few hours of entertainment.
    
    I note that the power set of any set S has two natural froop structures
    given by the intersection (^) and union (v) operators:
    
    For all A in P(S), (S^A)^A = A = A^(A^S)
    
    For all A in P(S), (�vA)vA = A = Av(Av�)	[� is the empty set]
    
    Obviously any Boolean latice is a froop in a similar way. Can anyone
    find any other familiar mathematical objects which are froops,
    especially one-sided froops?
    
    If as set has two froop operations on it, one distributive over the
    other, does this make it a gield?
    
    Andy.

Well, I found it surprising anyway... it's not one I remember from the old
canon...  :-)

Let F have an associative operation.  If *every* element of F is an L-inverse,
then every element is also a left identity, and ab = b for all a and b. 
Similarly, if every element is an R-inverse, ab = a.  For a set S, let L(S)
and R(S) be the "strong" L-froop and R-froop on S defined this way.

The question I considered was, what can you tell if every element is a
C-inverse?  Here's my challenge: prove the following, confirming my claimed
proof, or find a counterexample.  It should be doable by hardened algebraists.

Theorem.  Every element of F is a C-inverse iff F is isomorphic to a Cartesian
product L(S) x R(T) for some suitably chosen S and T.

Note it isn't assumed that F is finite.

This proof is more mechanical than interesting, so I'm clearing it off of
people's plates, as it were.  Possible hint: if you get Theorem 2, you'll
probably then get the others.

>Theorem 1. The Cartesian product of two L-froops is an L-froop; and
  similarly for R-froops, C-froops, froops, and Abelian froops.

Cartesian products preserve associativity and commutativity.  So it is easy to
see that the theorem for Abelian froops follows from that for froops; and that
for froops, from that for L-froops and R-froops.

If u is an L-inverse for F1 and v for F2, then for any (x,y) in F1xF2,
  (u,v)(x,y)(x,y) = (uxx,vyy) = (x,y)
so (u,v) is an L-inverse for F1xF2, and F1xF2 is an L-froop.  A similar proof
works for C-froops and R-froops.