Prev: Help with a question - throey of groups using functions
Next: Theory of groups with functions - Help on a question
From: Robert E. Beaudoin on 10 Jun 2010 01:18
On 06/09/10 12:21, Arturo Magidin wrote:
> 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


Oops, sorry, I misread your condition (ii), and the argument I gave just
shows (with a few minor changes) that (i), (iii), and

(ii') for all x and y there is z so that x = yz

are enough to imply S is a group. Probably you knew that already. Give
me a moment to wipe some egg off my face.

My apologies for the erroneous and misleading post.

Robert E. Beaudoin

From: Robert E. Beaudoin on 10 Jun 2010 10:09
On 06/10/10 01:18, Robert E. Beaudoin wrote:
> On 06/09/10 12:21, Arturo Magidin wrote:
>> 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
>
>
> Oops, sorry, I misread your condition (ii), and the argument I gave just
> shows (with a few minor changes) that (i), (iii), and
>
> (ii') for all x and y there is z so that x = yz
>
> are enough to imply S is a group. Probably you knew that already. Give
> me a moment to wipe some egg off my face.
>
> My apologies for the erroneous and misleading post.
>
> Robert E. Beaudoin
>


Well, I've got to stop posting at 1 AM. Sorry (again) for replying to
myself, but now I see that I'm mistaken in the above post as well: (i),
(ii'), and (iii) are not enough to imply S is a group. For a
counterexample take S = {a, b} (with a and b distinct) with
multiplication given by xy = y for all x and y in S. Your original
question (with (i), (ii), and (iii)) I still can't settle one way or the
other.

R. Beaudoin

From: herbzet on 10 Jun 2010 13:19


herbzet wrote:
> George Greene wrote:

> > The original problem is arguably mis-phrased (in the book).
> > What you ACTUALLY want to prove is NOT
> > > a = a.c |= c = c.c
> > BUT RATHER
> > Aac[ a=a.c --> c=c.c ]

Taken this way (and it seems reasonable to take it this way)
then I don't think the group axioms are needed at all (and
neither is the author's "Hint") -- it's just a FOL validity:
just let a be c. The group axioms are just a distraction.

This was actually my first thought after Frederick Williams
reminded us of what '|=' means (one of the meanings, anyway).
Every structure in which Aac[a=a.c] holds is a structure in
which Ac[c=c.c].

I'm *agreeing* with you that the book phrasing seems unclear,
given only what was in the post.

After a week, it was still bothering me, so now it's off my chest.

> > The fact that the original is stated withOUT quantifiers really
> > is problematic unless the book has a convention regarding
> > how they ought to be put back in.

--
hz
From: Arturo Magidin on 10 Jun 2010 14:50
On Jun 8, 5:22 pm, herbzet <herb...(a)gmail.com> wrote:

> > 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.

[...]

Indeed, the answer is "no". I was close to the following
counterexample, but I kept trying to throw in all the bijections which
was messing me up.

The counterexample is called the Baer-Levi semigroup; they are dealt
with in detail in Clifford and Preston's "The Algebraic Theory of
Semigroups", volume II, pages 82-86.

Let X be a denumerable (countably infinite) set. Let S be the
semigroup, under composition, of all one-to-one maps f:X-->X such that
X-f(X) is infinite. It is straightforward that this is not a group. It
is also straightforward that this semigroup satisfies left
cancellation, since in general one-to-one set-maps can be cancelled on
the left.

So it only remains to show that for all a and b in S, there exists f
such that a=fb. Let a and b in S be given, and let y in X.

If y is in b(X), say y = b(x), then let f(y) = f(b(x)) = a(x).

Now, to define y in X - b(X), let h be any one-to-one map from X-b(X)
to X-a(X) with the property that (X-a(X)) - h(X-b(X)) is infinite.

If y is in X-b(X), then define f(y) = h(y).

Then f is one-to-one, X-f(X) is infinite, and a = fb.

Thus, S is a semigroup, not a group, that satisfies the desired
condition.

--
Arturo Magidin
From: herbzet on 10 Jun 2010 16:51


Arturo Magidin wrote:
> herbzet wrote:
>
> > > 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.
>
> [...]
>
> Indeed, the answer is "no". I was close to the following
> counterexample, but I kept trying to throw in all the bijections which
> was messing me up.
>
> The counterexample is called the Baer-Levi semigroup; they are dealt
> with in detail in Clifford and Preston's "The Algebraic Theory of
> Semigroups", volume II, pages 82-86.
>
> Let X be a denumerable (countably infinite) set. Let S be the
> semigroup, under composition, of all one-to-one maps f:X-->X such that
> X-f(X) is infinite. It is straightforward that this is not a group. It
> is also straightforward that this semigroup satisfies left
> cancellation, since in general one-to-one set-maps can be cancelled on
> the left.
>
> So it only remains to show that for all a and b in S, there exists f
> such that a=fb. Let a and b in S be given, and let y in X.
>
> If y is in b(X), say y = b(x), then let f(y) = f(b(x)) = a(x).
>
> Now, to define y in X - b(X), let h be any one-to-one map from X-b(X)
> to X-a(X) with the property that (X-a(X)) - h(X-b(X)) is infinite.
>
> If y is in X-b(X), then define f(y) = h(y).
>
> Then f is one-to-one, X-f(X) is infinite, and a = fb.
>
> Thus, S is a semigroup, not a group, that satisfies the desired
> condition.

My goodness!

Thanx very much for following up on my rather off-the-cuff remark!

--
hz
First  |  Prev  | 
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