Exploring the Conditions for Group Closure in Infinite Sets

[smurf_too]

Let G be a finite nonempty set with an operation * such that:
1. G is closed under *.
2. * is associative.
3. Given with a*b=a*c, then b=c
4. Given with b*a=c*a, then b=c


Give an example to show that under the conditions above, G is no longer a group if G is an infinite set?

 

[d_leet]

Do you have any ideas about what set you could choose that would satisfy these conditions, yet not be a group. First off what infinite groups do you know?

 

[matt grime]

And what is the only axiom of a group that might fail?

 

[smurf_too]

I understand for a Group there are 4 conditions that must be met.
1) Closure (if a,b are elements of G, then a*b must be elements of G)
2) Associativity (a*b)*c = a*(b*c)
3) Identify must exist e • a = a • e = a.
4) Inverse must exist a • b = b • a = e, where e is an identity element
Also, I understand the cardinality of a set is a measure of the "number of elements of the set". There are two approaches to cardinality – one which compares sets directly using bijections and injections, and another which uses cardinal numbers.
I also understand that when dealing with infinite sets that the view of Galileo - the whole cannot be the same as the part, was rejected, and Cantor introduced the cardniality number and showed that some infinite sets are greater than others. The smallest infinite cardinality is that of the natural numbers (X₀).
For cardinality I can use the 3 conditions below:
Case 1: |A| = |B|
Two sets A and B have the same cardinality if there exists a bijection, that is, an injective and surjective function, from A to B.
For example, the set E = {0, 2, 4, 6, ...} of non-negative even numbers has the same cardinality as the set N = {0, 1, 2, 3, ...} of natural numbers, since the function f(n) = 2n is a bijection from N to E.
Case 2: |A| ≥ |B|
A has cardinality greater than or equal to the cardinality of B if there exists an injective function from B into A.
Case 3: |A| > |B|
A has cardinality strictly greater than the cardinality of B if there is an injective function, but no bijective function, from B to A.
For example, the set R of all real numbers has cardinality strictly greater than the cardinality of the set N of all natural numbers, because the inclusion map i : N → R is injective, but it can be shown that there does not exist a bijective function from N to R.

So my question are:
Does Case 3 constitute a counter example. And if I understand injection and bijection correctly the
N set is (1,2,3,4…..) would map to R (-4, -3,-2, -1, 0, …..1, 2, 3, 4, 5, etc). And since the Negative and zero numbers would not be mapped to it is therefore not surjective and therefore not bijective. Also, does this mean it is no longer a group?
While under finite conditions I could define N to be (1,2,3,4,5) and R to be (1,2,3,4,5) and therefore bijective.
I am really struggling to grasp this whole concept, but understand a few of the pieces. Please help!

 

[matt grime]

There is no need to focus on cardinality questions at all. Forget Cantor, Galileo, and so on. There isn't in fact any need to mention infinite sets in the question, except for the fact that there are no finite sets with this property, so the question is just helping you in the right direction. I presume from the way the question is written, that you've just shown any finite set with those properties is a group.

Actually, I was too hasty above, there are 2 possible group axioms that might fail.

 

[HallsofIvy]

Let G be a finite nonempty set with an operation * such that:
1. G is closed under *.
2. * is associative.
3. Given with a*b=a*c, then b=c
4. Given with b*a=c*a, then b=c

I understand for a Group there are 4 conditions that must be met.
1) Closure (if a,b are elements of G, then a*b must be elements of G)
2) Associativity (a*b)*c = a*(b*c)
3) Identify must exist e • a = a • e = a.
4) Inverse must exist a • b = b • a = e, where e is an identity element

(1) and (2) are the same in both of these so it is only (3) and (4) that you must show.
Choose a to be any fixed element of the set and consider aⁿ for all integers n. Can you show that you must have aⁿ= a^m for two different values m and n? what follows from that?

 

[smurf_too]

I understand that aⁿ is the cardinality and that with an infinite set m=N_o (aleph-0), and a finite set has n=n and therefore they are not equal. Based on the above cardinality rules, the infinite set would fall under case 3 and is not bijective.

I am not sure how this relates to Group definitions #3 and #4? Could you explain the relationship?

Would mapping the natural set to a real set be an acceptable counter example?

The problem asks that I provide an example of an infinite set which would be false under the original group conditions, would I need to define a function (f(g) = 2g) in addition to the explanation above?

 

[d_leet]

No... Stop thinking about cardinalities, stop thinking about functions, neither are required or really have anything to do with this question other than that you are looking for an infinite set.

 

[n_bourbaki]

Have you considered starting with an infinite group and trying to make it fail to be a group?

 

[HallsofIvy]

For example, the set of all integers, with the usual addition, form a group. Can you find a subset of that that still satisfies
1) is closed under addition
2) is associative (which is a property of the operation, not the set and so is automatically true)

but is NOT a group because it does not have ...

 

[smurf_too]

Ok, now I'm really confused...

The set of all integers with an addition operation is a group that is closed, associative and
the inverse equal to -a and identity of 0.

Wouldn't any subgroup have the same properties?

Please help clarify.

 

[n_bourbaki]

A subgroup would, but you were asked if you could find a subset with the required properties.

 

[smurf_too]

I'm not picking up on what your trying to say...

Are your referring to mapping the natural integers to real numbers, in which case, its not onto, and therefore is not bijective?

 

[HallsofIvy]

NO, no one is talking about mappings or cardinalities or anything like that. We are talking about arithmetic! Remember you are looking for a subset that is NOT a group.

To put it right in your face, does the set of all positive integers, with the operation of addition, satisfy the conditions you give in your first post? Is that set a group?

 

[uman]

No.

Find a subset (NOT SUBGROUP) of the integers that either doesn't have inverses or doesn't have an identity.

Edit: HallsOfIvy beat me to it...

 

[smurf_too]

Ok, please bare with me. I'm really struggling with all this.

I understand that an infinite positive set fails because the inverse is negative (using addition) and is not in the set/group. But even a finite set would fail for the same reason. So I don't understand how this answers the question. I'm assuming the original question is asking for a set that fails when infinite but meets the group definition when its finite. Am I misunderstanding the question...?

 

[uman]

Well, can you give an example of a finite set that meets those conditions but is not a group?

 

[smurf_too]

Ok, the integers under multiplication (Z,x) is not a group because it fails the inverse. Therefore a finite set of this would also fail.

However, the problem asks for a finite set that is a group, but when extended to infinity fails the group definition. Is this not what the question is asking?

 

[d_leet]

Ok, the integers under multiplication (Z,x) is not a group because it fails the inverse. Therefore a finite set of this would also fail.

However, the problem asks for a finite set that is a group, but when extended to infinity fails the group definition. Is this not what the question is asking?

This does not satisfy the condition that if ac=bc then a=b, take a=3, b=7, and c=0.

Also I don't think you understand the question, it is asking you to find an infinite set which satisfies those properties, but is not a group.

 

[smurf_too]

Thank you.

Is the question getting at ranking of algebraic structures in the order of increasing complexity (i.e. magma, semigroup, monoid, group,...).

The original finite set with closure, associative, and a*b=a*c, and b*a=c*a is a group because the right and left cancellation properties hold, and imply the identity and inverse exist. (I am just starting to learn about right/left cancellation)

The infinite example we are going after is really a semigroup, where we only need closure, and associative properties to hold. Thus, the example (N, +) would work because we don't care that it fails the inverse and identity criteria of a group. Similarly we could use (Z, x) as an example of a monoid since it fails the inverse but has an identity of 1, but (Z, +) would be a group since it has both an identity of 0 and an inverse of -a.

So the question is really comparing algebraic structure complexity and not "finite vs infinite" sets?
Also, could you explain how the right/left cancellation implies identity and inverse for finite but fails for infinite sets? Thanks again for your patience in helping me understand all this!

 

[smurf_too]

I understand that (N, +) meets conditions 3 and 4 yet has no inverse function and therefore is an answer to the problem. Could you explain how the right/left cancellation implies identity and inverse for finite sets but fails for infinite sets?

Thanks again.

 

[eastside00_99]

Is the question getting at ranking of algebraic structures in the order of increasing complexity (i.e. magma, semigroup, monoid, group,...).

Not really. We already have complete definitions for what we mean by those algebraic structures. But, possibly you could look at it that way: What you know, or could easily prove, is that the law cancelation (both right and left cancelation) hold in any group. So, given a semigroup G, the law of cancelation (on the right and left) is a necessary condition if G is also going to be a group. What you are asked to prove is that it is not a sufficient condition. So, really these laws given in your first post cannot be taken as an alternate definition of a group. At one time, in the history of group theory, they were actually taken as the definition of a group --- well what really happened was in the late 19th century people really started being uninterested in the concrete properties of 'groups' and more with the abstract properties of groups. In 1882, Heinrich M. Weber gave one of the first abstract definitions of a group which was given by the properties listed in your first post. But, in that same year Walther von Dyck gave the definition which we use today. It is more abstract as you are in the process of showing a infinite semigroup which obeys both the left and right cancellation law is not necessarily a group.

 

[n_bourbaki]

Could you explain how the right/left cancellation implies identity and inverse for finite sets but fails for infinite sets?

It would be much better if you tried to prove it yourself. This time it actually does have something to do with the properties of sets, and is not very hard.

 

[HallsofIvy]

I understand that (N, +) meets conditions 3 and 4 yet has no inverse function and therefore is an answer to the problem. Could you explain how the right/left cancellation implies identity and inverse for finite sets but fails for infinite sets?

Thanks again.

Look at response number 6 again. That contains all you need.

 

[eastside00_99]

Another helpful way of looking at, if not the best way, is that we are thinking about cancellation vs. inversion. For instance let f,g,h: S --> S be a function on a set. Assume
$f\circ h \equiv g \circ h$. For, h being onto (which will mean h is bijective), will be enough to show f and g are functionally equivalent. But, instead look at the following
$h\circ f \equiv h \circ g$.

Here all we need is h to be one to one. Now, in the case where S is a finite set, this will imply h is bijective, but in the case where S is infinite, it will not. So, here we will have an example: all injective functions from a set S into S where S is infinite. It is easy to show that such a collection of functions is an infinite set.

The other good thing about thinking this way is that when we require S to be finite, our collection actually becomes the set of all permutations a finite set. I.e., it becomes the symmetric group S_n. People used to be mainly interested in finite symmetric groups, and this is why a good leap in the right direction for defining a group was the cancellation laws.

 

[matt grime]

I would not accept that people were originally mainly interested in finite symmetric groups (without evidence). I would accept they were interested in finite concrete groups exclusively.

 

[eastside00_99]

Well, maybe "mainly" is not the right word. But, instead, that the concept of a group was heavily influenced in the investigations of finite symmetric groups: Lagrange, Vandermonde, Ruffini, Galois, and Chauchy...For example, look at the biography of Ruffini:

http://www-history.mcs.st-andrews.ac.uk/Biographies/Ruffini.html

 

[matt grime]

I see lots of references to permutation groups i.e. concrete groups acting as bijections on a finite set - that isn't the same as being a symmetric group.

 

[eastside00_99]

in my language, permutation group = finite symmetric groups. Whether or not I call his work concrete or not would mean me reading his work. I'm not doing that.

 

[matt grime]

Then you should re-evaluate your language - a permutation group is just a subgroup of the set of all permutations of a set. That is the common definition.

It is certainly not true that the groups of symmetries of the roots of a polynomial (the work of Ruffini and Galois that you cite) is always a symmetric group.

You don't need to read his work to decide if it's 'concrete', since that is not the meaning of a concrete group. A concrete group is one that acts as a subgroup of permutations of a set. I've said nothing that wouldn't be covered by a decent elementary book on group theory, which would also show that a concrete group and is an abstract group and vice versa (Cayley's theorem I believe).