Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Infinite Set

  1. Jul 10, 2008 #1
    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?
  2. jcsd
  3. Jul 10, 2008 #2
    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?
  4. Jul 11, 2008 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    And what is the only axiom of a group that might fail?
  5. Jul 11, 2008 #4
    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 (X0).
    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!!!!!
  6. Jul 11, 2008 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  7. Jul 11, 2008 #6


    User Avatar
    Science Advisor

    (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 an for all integers n. Can you show that you must have an= am for two different values m and n? what follows from that?
  8. Jul 11, 2008 #7
    I understand that an is the cardinality and that with an infinite set m=No (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 explaination above?
  9. Jul 11, 2008 #8
    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.
  10. Jul 12, 2008 #9
    Have you considered starting with an infinite group and trying to make it fail to be a group?
  11. Jul 12, 2008 #10


    User Avatar
    Science Advisor

    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 ....
  12. Jul 12, 2008 #11
    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.
  13. Jul 12, 2008 #12
    A subgroup would, but you were asked if you could find a subset with the required properties.
  14. Jul 12, 2008 #13
    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?
  15. Jul 12, 2008 #14


    User Avatar
    Science Advisor

    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?
  16. Jul 12, 2008 #15

    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...
  17. Jul 12, 2008 #16
    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....?
  18. Jul 12, 2008 #17
    Well, can you give an example of a finite set that meets those conditions but is not a group?
  19. Jul 12, 2008 #18
    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?
  20. Jul 12, 2008 #19
    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.
  21. Jul 13, 2008 #20
    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 dont 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!
  22. Jul 13, 2008 #21
    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.
  23. Jul 13, 2008 #22
    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.
  24. Jul 13, 2008 #23
    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.
  25. Jul 13, 2008 #24


    User Avatar
    Science Advisor

    Look at response number 6 again. That contains all you need.
  26. Jul 13, 2008 #25
    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
    [itex] f\circ h \equiv g \circ h [/itex]. 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
    [itex] h\circ f \equiv h \circ g [/itex].

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook