Hi,
Could anyone help me with this question (from Bostock’s Intermediate
Logic)
"The theory of groups can be presented as having in its vocabulary
just identity and a single two-place function f(x,y) which we write as
‘x.y’. The usual laws for identity apply, and in addition these three
axioms:"
(A1) Axyz(x.(y.z) = (x.y).z)
(A2) AxyEz(x = z.y)
(A3) AxyEz(x = y.z)
Prove:
a = a.c |= c = c.c
(Hint: Use Ez(c = z.a))
Thanks for any help,
Mitch.
- Hide quoted text — Show quoted text -
Mitchell Hockley wrote:
> Hi,
> Could anyone help me with this question (from Bostock’s Intermediate
> Logic)
> "The theory of groups can be presented as having in its vocabulary
> just identity and a single two-place function f(x,y) which we write as
> ‘x.y’. The usual laws for identity apply, and in addition these three
> axioms:"
> (A1) Axyz(x.(y.z) = (x.y).z)
> (A2) AxyEz(x = z.y)
> (A3) AxyEz(x = y.z)
> Prove:
> a = a.c |= c = c.c
Hint: that means that every model of a = a.c is a model of c = c.c.
> (Hint: Use Ez(c = z.a))
Eh? What if a = 0 and c =/= 0?
–
I can’t go on, I’ll go on.
- Hide quoted text — Show quoted text -
On Wed, 2 Jun 2010, Mitchell Hockley wrote:
> "The theory of groups can be presented as having in its vocabulary
> just identity and a single two-place function f(x,y) which we write as
> ‘x.y’. The usual laws for identity apply, and in addition these three
> axioms:"
> (A1) Axyz(x.(y.z) = (x.y).z)
> (A2) AxyEz(x = z.y)
> (A3) AxyEz(x = y.z)
> Prove:
> a = a.c |= c = c.c
> (Hint: Use Ez(c = z.a))
Multiply both sides of a = ac, on the left by z.
- Hide quoted text — Show quoted text -
> Thanks for any help, Mitch.
Arturo Magidin wrote:
> Frederick Williams wrote:
> > Mitchell Hockley wrote:
> > > Hi,
> > > Could anyone help me with this question (from Bostock’s Intermediate
> > > Logic)
> > > "The theory of groups can be presented as having in its vocabulary
> > > just identity and a single two-place function f(x,y) which we write as
> > > ‘x.y’. The usual laws for identity apply, and in addition these three
> > > axioms:"
> > > (A1) Axyz(x.(y.z) = (x.y).z)
Right — the group operation is associative.
> > > (A2) AxyEz(x = z.y)
Right — my personal name for this axiom is "the reach axiom" — because
you can "reach" any x from any y in one step.
> > > (A3) AxyEz(x = y.z)
Can this be right? Taken together with A2, this says that for any x and y,
there is a z such that x = y.z = z.y. This would clearly be true in an
Abelian group, where Axy(x.y = y.x), but is it generally true for all
groups? I don’t think so.
Counterexample: at http://tinyurl.com/29c9erf at the group table for
the D4 symmetry group (which is *not* an abelian group) we have that
the element f_h = (r_3 . f_d) but *not* f_h = (f_d . r_3).
I think that what we want for a third axiom is
(A3′) Axyz [(x.y = x.z) -> (y = z)].
- Hide quoted text — Show quoted text -
> > > Prove:
> > > a = a.c |= c = c.c
> > Hint: that means that every model of a = a.c is a model of c = c.c.
> > > (Hint: Use Ez(c = z.a))
> > Eh? What if a = 0 and c =/= 0?
> I think you are confused; when we use "a=0" in a group, the operation
> is usually taken to be addition, not multiplication. In a group, if
> you have an element a such that Ay (ay=ya=a) (i.e., a "zero" element
> in the sense of semigroups), then you have that the group consists of
> only one element.
> The Hint refers to (A2) in which the x has been particularized to
> equal a.
> To the OP: suppose you have a structure satisfying (A1)-(A3), and in
> addition that Eac(a.c=a). You want to show that in that case, c.c=c.
> By A2, you have that Ez(c=z.a). So in c.c, you can replace the first c
> by z.a. Do that and see what happens.
–
hz
George Greene wrote:
> Arturo Magidin wrote:
> > To the OP: suppose you have a structure satisfying (A1)-(A3), and in
> > addition that Eac(a.c=a)
> This is sort of a misuse of the existential quantifier.
Sort of a slight abuse of notation — it might have been
more correct to just say "and in addition that a.c=a".
But that might have incorrectly suggested to the OP that
A.M. was trying to say that Axy(x.y=x) — see below.
> You are actually trying to prove that the implication holds
> for ALL a and ALL c.
> 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 ]
> 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.
I think that what’s going on is that the variables ‘x’,'y’,'z’
(from the end of the alphabet) are being instantiated to
constants ‘a’,'b’,'c’ (from the beginning of the alphabet).
Quantifying over constants is not quite kosher, I think.
–
hz
- Hide quoted text — Show quoted text -
Arturo Magidin wrote:
> herbzet wrote:
> > Arturo Magidin wrote:
> > > Frederick Williams wrote:
> > > > Mitchell Hockley wrote:
> > > > > Hi,
> > > > > Could anyone help me with this question (from Bostock’s Intermediate
> > > > > Logic)
> > > > > "The theory of groups can be presented as having in its vocabulary
> > > > > just identity and a single two-place function f(x,y) which we write as
> > > > > ‘x.y’. The usual laws for identity apply, and in addition these three
> > > > > axioms:"
> > > > > (A1) Axyz(x.(y.z) = (x.y).z)
> > Right — the group operation is associative.
> > > > > (A2) AxyEz(x = z.y)
> > Right — my personal name for this axiom is "the reach axiom" — because
> > you can "reach" any x from any y in one step.
> > > > > (A3) AxyEz(x = y.z)
> > Can this be right?
> Yes.
> >Taken together with A2, this says that for any x and y,
> > there is a z such that x = y.z = z.y.
> No, because the "z" that exists by A2 need not be the same "z’ that
> exists by A3. It says that for any x and for any y, there is a z and a
> w such that x = y.z = w.y.
Makes sense.
- Hide quoted text — Show quoted text -
> This is the well-known condition on groups that says that a semigroup
> (a nonempty set with a binary associative operation) is a group if and
> only if for every a and b, the equations
> a = bx and a = yb
> both have solutions.
> You *do* need both. To see an example where having A2 but not A3 does
> not suffice, consider the semigroup with underlying set S with at
> least two elements x and y, x=/=y, and operation a.b = a for all a
> and b. This operation is trivially associative, and for all a and b
> there exists c such that a = c.b, namely c=a. However, this is not a
> group because you have x.y = x.x, but x=/=y.
> > This would clearly be true in an
> > Abelian group, where Axy(x.y = y.x), but is it generally true for all
> > groups? I don’t think so.
> You are misinterpreting the two existentials. What you have is
> (*) AxyEz(x=z.y) /\ AxyEz(x=y.z)
> This is *different* from
> (**) Axy Ez (x=z.y /\ x=y.z).
> (**) is strictly stronger than (*). In (**), the first "Ez" only
> applies to the first formula; it is formally equivalent to
> (*’) AxyEz(x=z.y) /\ ArsEt(r=s.t).
> > I think that what we want for a third axiom is
> > (A3′) Axyz [(x.y = x.z) -> (y = z)].
> This may suffice (I haven’t checked), but the original A3 is perfectly
> fine too.
Thanks very much.
–
hz
herbzet wrote:
> Arturo Magidin wrote:
> > herbzet wrote:
> > > I think that what we want for a third axiom is
> > > (A3′) Axyz [(x.y = x.z) -> (y = z)].
> > This may suffice (I haven’t checked), but the original A3 is perfectly
> > fine too.
(A3′) reflects that I’m thinking of a group as a Latin square:
a Latin square is an n n table filled with n different symbols
in such a way that each symbol occurs exactly once in each row and
exactly once in each column (Wikipedia).
except I’m allowing the square to have an infinite number of rows
and columns.
So I’m conceptualizing a group as a (possibly infinite) Latin square
(the group operation matrix) that obeys the associative law.
I don’t know if that’s right, but it seems nice and neat.
–
hz
> Arturo Magidin wrote:
> > This is the well-known condition on groups that says that a semigroup
> > (a nonempty set with a binary associative operation) is a group if and
> > only if for every a and b, the equations
> > a = bx and a = yb
This is nice and neat also.
Can you smell the sawdust burning? I’m thinkin’.
–
hz
Arturo Magidin wrote:
> On Jun 2, 7:58 am, Frederick Williams <frederick.willia…@tesco.net>
> wrote:
> > Mitchell Hockley wrote:
> > > (Hint: Use Ez(c = z.a))
> > Eh? What if a = 0 and c =/= 0?
> I think you are confused; when we use "a=0" in a group, the operation
> is usually taken to be addition, not multiplication.
Yes, sorry. I’m an idiot.
–
I can’t go on, I’ll go on.
- Hide quoted text — Show quoted text -
Arturo Magidin wrote:
> Arturo Magidin 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.
Thanks for staying with it!
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.
I found a similar discussion at http://tinyurl.com/3yoet8l
started by me, which also shows how embarassingly slow I am
at learning things.
–
hz
On 06/08/10 16:17, Arturo Magidin wrote:
- Hide quoted text — Show quoted text -
> On Jun 2, 11:30 pm, Arturo Magidin <magi…@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
- Hide quoted text — Show quoted text -
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
On 06/09/10 12:21, Arturo Magidin wrote:
- Hide quoted text — Show quoted text -
> On Jun 8, 11:45 pm, "Robert E. Beaudoin" <rbeaud…@acm.org> wrote:
>> On 06/08/10 16:17, Arturo Magidin wrote:
>>> On Jun 2, 11:30 pm, Arturo Magidin <magi…@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
On 06/10/10 01:18, Robert E. Beaudoin wrote:
- Hide quoted text — Show quoted text -
> On 06/09/10 12:21, Arturo Magidin wrote:
>> On Jun 8, 11:45 pm, "Robert E. Beaudoin" <rbeaud…@acm.org> wrote:
>>> On 06/08/10 16:17, Arturo Magidin wrote:
>>>> On Jun 2, 11:30 pm, Arturo Magidin <magi…@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
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