Prev: Help with a question - throey of groups using functions
Next: Theory of groups with functions - Help on a question
From: Arturo Magidin on 8 Jun 2010 16:17
On Jun 2, 11:30 pm, Arturo Magidin <magi...(a)member.ams.org> wrote:

Not a full answer yet.

So, to recap: suppose you have a [nonempty] set S and a binary
operation (which we denote by concatenation) on S such that

(i) the operation is associative;
(ii) for every x and y in S, there exists z such that x = zy;
(iii) For every r,s,t in S, if rs = rt, then s=t.

Will S be a group?

I'm pretty sure the answer is "no" in general, but I asked a
colleague. He did point out that under some mild conditions, the
answer is "yes": S will be a group if any of the following hold:

(a) S contains an idempotent;
(b) every cyclic subsemigroup of S is finite;
(c) there is at least one cyclic subsemigroup of S that is finite;
(d) S is finite.

To see this, note that (d)->(c)->(b)->(a). Under condition (a), let e
be an idempotent. Then for all x in S, eex = ex, so by left
cancellation we have that ex=x for all x. Then from (ii) we get that
for every x there exists z such that zx=e, and we have both left
identity and left inverses, hence a group.

--
Arturo Magidin
From: Arturo Magidin on 9 Jun 2010 00:31
On Jun 8, 5:22 pm, herbzet <herb...(a)gmail.com> wrote:

>
> I'm still marvelling that, along with the associative property,
> it is sufficient that AxyEzw [x=zy /\ x=yw].  This "well-known
> property" was totally unknown to me.  This is equivalent to saying
> that in the (possibly infinite) matrix of the binary operation,
> every element occurs at least once in each row and each column.
>
> I thought you'd have to postulate also that each element
> occurs *at most* once in each row and each column.

This turns out to follow, so specifying it is in a sense superfluous.
Of course, the usual group axioms are somewhat superfluous as well,
since we need not specify that there is a two-sided neutral element
and that every element has a two-sided inverse, we just need to
require one-sided identity and one-sided inverses (provided we require
them on the same side).

To see that the proposition (together with associativity) suffices,
note that given a, there exists e_a (which may depend on a at this
stage) such that e_a*a = a. If b is any other element, then we
likewise have an element f_b (which may depend on b) such that b*f_b =
b. We also have an x such that a*x = f_b, and a y such that y*b = e_a.
Then we have:

e_a = y*b = y*(b*f_b) = (y*b)*f_b = e_a*f_b = e_a*(a*x) = (e_a*a)*x =
a*x = f_b,

This tells you that the e_a which may have dependend on a actually is
a two-sided identity for all elements. Then solving a*x = e for all a
gives you that every element has a right inverse, which now suffices
to give the group structure. From this, you get uniqueness of the
solutions, of course.

--
Arturo Magidin
From: Robert E. Beaudoin on 9 Jun 2010 00:45
On 06/08/10 16:17, Arturo Magidin wrote:
> On Jun 2, 11:30 pm, Arturo Magidin <magi...(a)member.ams.org> wrote:
>
> Not a full answer yet.
>
> So, to recap: suppose you have a [nonempty] set S and a binary
> operation (which we denote by concatenation) on S such that
>
> (i) the operation is associative;
> (ii) for every x and y in S, there exists z such that x = zy;
> (iii) For every r,s,t in S, if rs = rt, then s=t.
>
> Will S be a group?
>
> I'm pretty sure the answer is "no" in general, but I asked a
> colleague. He did point out that under some mild conditions, the
> answer is "yes": S will be a group if any of the following hold:
>
> (a) S contains an idempotent;
> (b) every cyclic subsemigroup of S is finite;
> (c) there is at least one cyclic subsemigroup of S that is finite;
> (d) S is finite.
>
> To see this, note that (d)->(c)->(b)->(a). Under condition (a), let e
> be an idempotent. Then for all x in S, eex = ex, so by left
> cancellation we have that ex=x for all x. Then from (ii) we get that
> for every x there exists z such that zx=e, and we have both left
> identity and left inverses, hence a group.
>
> --
> Arturo Magidin

Seems like these three conditions alone are enough to ensure S is a
group: Define f : S --> S^S by f(x)(y) = xy. By (iii), for every x in
S f(x) is one-to-one. By (ii), for every x in S f(x) maps S onto S.
By (i) for every x and y in S we have f(xy) = f(x) o f(y). So f is a
semi-group homomorphism from S into Sym(S), the group of permutations of
S. But picking an element c from the nonempty set S and applying (ii)
with x = y = c yields an e in S so that ec = c. Applying f we get f(e)
o f(c) = f(c), and as f(c) has an inverse in Sym(S) we must have f(e)
equal to the identity permutation. But f(e)(x) = x for all x in S
implies ex = x for all x. In other words, e is a left identity element
for S. Arguing as you did above then shows S is a group, and in fact f
is a group monomorphism from S into Sym(S).

Robert E. Beaudoin


From: herbzet on 9 Jun 2010 01:48


Arturo Magidin wrote:
> herbzet wrote:
>
> >
> > I'm still marvelling that, along with the associative property,
> > it is sufficient that AxyEzw [x=zy /\ x=yw]. This "well-known
> > property" was totally unknown to me. This is equivalent to saying
> > that in the (possibly infinite) matrix of the binary operation,
> > every element occurs at least once in each row and each column.
> >
> > I thought you'd have to postulate also that each element
> > occurs *at most* once in each row and each column.
>
> This turns out to follow, so specifying it is in a sense superfluous.
> Of course, the usual group axioms are somewhat superfluous as well,
> since we need not specify that there is a two-sided neutral element
> and that every element has a two-sided inverse, we just need to
> require one-sided identity and one-sided inverses (provided we require
> them on the same side).
>
> To see that the proposition (together with associativity) suffices,
> note that given a, there exists e_a (which may depend on a at this
> stage) such that e_a*a = a. If b is any other element, then we
> likewise have an element f_b (which may depend on b) such that b*f_b =
> b. We also have an x such that a*x = f_b, and a y such that y*b = e_a.
> Then we have:
>
> e_a = y*b = y*(b*f_b) = (y*b)*f_b = e_a*f_b = e_a*(a*x) = (e_a*a)*x =
> a*x = f_b,
>
> This tells you that the e_a which may have dependend on a actually is
> a two-sided identity for all elements. Then solving a*x = e for all a
> gives you that every element has a right inverse, which now suffices
> to give the group structure. From this, you get uniqueness of the
> solutions, of course.

Thank you.

--
hz
From: Arturo Magidin on 9 Jun 2010 12:21
On Jun 8, 11:45 pm, "Robert E. Beaudoin" <rbeaud...(a)acm.org> wrote:
> On 06/08/10 16:17, Arturo Magidin wrote:
>
>
>
> > On Jun 2, 11:30 pm, Arturo Magidin <magi...(a)member.ams.org> wrote:
>
> > Not a full answer yet.
>
> > So, to recap: suppose you have a [nonempty] set S and a binary
> > operation (which we denote by concatenation) on S such that
>
> > (i) the operation is associative;
> > (ii) for every x and y in S, there exists z such that x = zy;
> > (iii) For every r,s,t in S, if rs = rt, then s=t.
>
> > Will S be a group?
>
> > I'm pretty sure the answer is "no" in general, but I asked a
> > colleague. He did point out that under some mild conditions, the
> > answer is "yes": S will be a group if any of the following hold:
>
> > (a) S contains an idempotent;
> > (b) every cyclic subsemigroup of S is finite;
> > (c) there is at least one cyclic subsemigroup of S that is finite;
> > (d) S is finite.
>
> > To see this, note that (d)->(c)->(b)->(a). Under condition (a), let e
> > be an idempotent. Then for all x in S, eex = ex, so by left
> > cancellation we have that ex=x for all x. Then from (ii) we get that
> > for every x there exists z such that zx=e, and we have both left
> > identity and left inverses, hence a group.
>
> > --
> > Arturo Magidin
>
> Seems like these three conditions alone are enough to ensure S is a
> group:  Define f : S --> S^S by f(x)(y) = xy.  By (iii), for every x in
> S  f(x) is one-to-one.  By (ii), for every x in S  f(x) maps S onto S.

I'm sorry, but how do you get that?

Saying that f(x) maps S onto S is saying that for all z there exists y
such that z=xy. But what we have is the *other* condition: for all z,
there exists y such that z = yx: (ii) specifies that you can always
solve equations *on the left*, not on the right.

Am I missing something?

If you know that f(x) is onto for every x, then you know that for all
a and b, there exists c such that a = bc. This gives that you can
solve all equations of the form a = bx; and (ii) gives that you can
solve all equations of the form a=yb; and these two together give that
you have a group, yes. But how do you know that f(x) is onto for every
x?

--
Arturo Magidin
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Help with a question - throey of groups using functions
Next: Theory of groups with functions - Help on a question