Please turn on javascript in your browser to play chess.
Science Forum

Science Forum

  1. Standard member adam warlock
    Baby Gauss
    01 Dec '14 06:42 / 1 edit
    Since we'be discussing a lot of mathematics on this forum recently I decided to post and old problem.

    Show that a set with a finite number of elements which is closed under the operation * (* is commutative) contains at least one identity element.
  2. Standard member DeepThought
    Losing the Thread
    01 Dec '14 17:16
    Can I assume the operation is associative (in which case I've got a partial proof)?
  3. Standard member adam warlock
    Baby Gauss
    01 Dec '14 20:20
    Originally posted by DeepThought
    Can I assume the operation is associative (in which case I've got a partial proof)?
    Yes, you can.
  4. Standard member DeepThought
    Losing the Thread
    02 Dec '14 17:04
    Originally posted by adam warlock
    Yes, you can.
    I'm a bit stuck on this, so I'll present the special case. Then I'll think some more about it. I need an extra axiom, so I'll list the axioms I've got, and add my extra one:

    A) Closure, for all a, b there exists c = a*b
    B) Associativity, for all a, b, c; a*(b*c) = (a*b)*c
    C) Commutativity, for all a, b; a*b = b*a
    D) There are a finite number of elements.
    E) Extra axiom, for all a, b, c, if a*b = a*c then b = c

    We can classify elements of S into three types. Type I elements are identity candidates a*a = a; Type II elements are ones where if we square them and then square the result and so one we end up back where we started. Type III are all others.

    So:
    Type I) a*a = a
    Type II) a*a = b; b*b = c; c*c = d; d*d = a (although the list could be much longer, and there need not be only one such subset of looping elements, the loops do have to be disjoint)
    Type III) all other elements, they form chains starting with an element a that is not the square of any element and a*a = b; b*b = c; c*c = element of type I or type II (Again the chain can be of arbitrary length assuming we don't run out of elements).

    I'm guaranteed that starting with a type III element and going along the chain of elements will get me to a type I or II element as the set is finite (Axiom D). Consider type II elements.

    Lemma: for all x, a there exists y such that x = a*y. Consider the product of a with each member of the set, by closure each such product must be in the set, and each such product must be different by axiom E, so the set of products span the set and y exists.

    Now, consider the product of all the elements of type II which form a closed loop (there may be more than one closed loop but they must be disjoint, I only want one of the disjoint ones). Suppose, without loss of generality (the magic words ) the loop is length 4 and the product of them is z = a*b*c*d; a*a = b; b*b = c; c*c = d; d*d = a

    a*z = a*(a*b*c*d) = (a*a)*b*c*d = b*b*c*d = c*c*d = d*d = a; where I've used the associativity axiom.
    b*z = b*a*b*c*d = a*(b*b)*c*d = a*c*c*d = a*d*d = a*a = b; where I've used both the associativity and commutativity axioms.

    similarly for c and d.

    By completeness z = a*b*c*d is in the set and it is an indentity w.r.t. a, b, c, and d. z cannot be one of the elements a, b, c, or d - say it is b, then b*z = b*b = c but b*z = b. So now I need to show that z*x = x, when x is any element.

    By my lemma (this is what I need the extra axiom for) there exists y such that x = a*y for any x in the set and a of Type II.
    Then x*z = (y * a) * z = y * (a * z) = y * a = x
    So z is an inverse w.r.t. all elements of the set []

    Now I need to work out how to do this for the cases where a*b = a*c does not imply that b = c. Which I'm a bit stuck on.
  5. Standard member DeepThought
    Losing the Thread
    02 Dec '14 17:35 / 1 edit
    A few additional comments. There must be at least one element of type I or a set of elements of type II. If there were not then my elements of type III would have nothing to terminate on and the set is finite. The proof works if there are no elements of type II since then there must be an element of type I - a type I element is like a type II element but the loop is of length 1, so the same argument works.

    z must be of type I because:
    z*z = (a*b*c*d)*(a*b*c*d) = a*a*b*b*c*c*d*d = b*c*d*a = a*b*c*d = z

    So my only problem is with elements of type III and sets with two or more disjoint groupings of elements of type II.
  6. Standard member adam warlock
    Baby Gauss
    02 Dec '14 21:09
    Originally posted by DeepThought
    I'm a bit stuck on this, so I'll present the special case. Then I'll think some more about it. I need an extra axiom, so I'll list the axioms I've got, and add my extra one:

    A) Closure, for all a, b there exists c = a*b
    B) Associativity, for all a, b, c; a*(b*c) = (a*b)*c
    C) Commutativity, for all a, b; a*b = b*a
    D) There are a finite number of e ...[text shortened]... w to do this for the cases where a*b = a*c does not imply that b = c. Which I'm a bit stuck on.
    I like your idea of divide and conquer but it seems that you're trying to kill flies with a cannon.

    Your extra axiom is equivalent to saying that there exists an inverse element to the * operation. And for an inverse element to exist you need to have the identity element. So in a way you're assuming what you want to prove.

    I'll give you a hint for an elegant proof of this result. List all elements of this set and use * on all of them. Take a look at the result and work from there.
  7. 02 Dec '14 21:18 / 1 edit
    Originally posted by adam warlock
    Since we'be discussing a lot of mathematics on this forum recently I decided to post and old problem.

    Show that a set with a finite number of elements which is closed under the operation * (* is commutative) contains at least one identity element.
    If you mean 'group' when you write 'set', then please write 'group'.
    I hope that you understand the distinction between a set and a group.

    http://en.wikipedia.org/wiki/Group_(mathematics)
  8. Standard member adam warlock
    Baby Gauss
    02 Dec '14 21:24
    Originally posted by Duchess64
    If you mean 'group' when you write 'set', then please write 'group'.
    I hope that you understand the distinction between a set and a group.

    http://en.wikipedia.org/wiki/Group_(mathematics)
    First sentence of your link: "In mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element...". Hence there was nothing wrong with my sentence: "a set with a finite number of elements which is closed under the operation *" because it implies that I'm describing a group (a set of elements together with an operation).

    Care to try and solve the problem?
  9. 02 Dec '14 21:54
    Originally posted by adam warlock
    First sentence of your link: "In mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element...". Hence there was nothing wrong with my sentence: "a set with a finite number of elements which is closed under the operation *" because it implies that I'm describing a group (a set of elements together with an operation).

    Care to try and solve the problem?
    "...because it implies that I'm describing a group."
    --Adam Warlock

    That's what I assumed, though it's helpful to have your (implicit) clarification.

    "Hence there was nothing wrong with my sentence..."
    --Adam Warlock

    From the perspective of clarity, there's something that should have been
    improved in your original post. If I had to devise a problem about a group
    for students, then I always would write *explicitly* that it was about a group.
    I would *not* write (misleadingly) that it's a problem about only a set
    (with conditions implying that it's a group) unless I intended to test students'
    comprehension of what constitutes a group. For example, I might write
    a problem and ask 'Is S a group?'

    If I wanted to pose a problem about a ring S, then I would *not* express
    in (needlessly misleading) terms of asking about the set S or the group S.
    I cannot imagine any mathematics professor devising a problem about a
    field S and expressing in terms of asking about the set S. (sarcasm)

    'Care to try and solve the problem?'

    No.
  10. Standard member DeepThought
    Losing the Thread
    02 Dec '14 23:01
    Originally posted by adam warlock
    First sentence of your link: "In mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element...". Hence there was nothing wrong with my sentence: "a set with a finite number of elements which is closed under the operation *" because it implies that I'm describing a group (a set of elements together with an operation).

    Care to try and solve the problem?
    If it's a group then the inverse axiom is present. Although since the presence of an identity is not explicitly in the axioms I've still proved that my extra axiom guarantees an identity element and inverse for each element.

    Part of the reason for posting my special case proof was to see if I was barking up the wrong tree or not.
  11. 02 Dec '14 23:09
    Originally posted by DeepThought to AdamWarlock
    If it's a group then the inverse axiom is present. Although since the presence of an identity is not explicitly in the axioms I've still proved that my extra axiom guarantees an identity element and inverse for each element.

    Part of the reason for posting my special case proof was to see if I was barking up the wrong tree or not.
    I commend you (DeepThought) for your mathematical interests, though not
    necessarily your style of exposition or your preferred methods of solution.

    Yet are you allowed to introduce an 'extra axiom' to make a hard problem
    easier or a confusingly expressed problem simpler for yourself?
    When I was in mathematical problem-solving competitions, I never considered
    introducing any 'extra axioms'. What opportunities I could have missed!

    By the way, I would suggest that recreational mathematical problems
    (if this is supposed to be one) tend to be more accessible about subjects
    besides abstract algebra. (Did Emmy Noether 'roll over in her grave'?)
  12. Standard member adam warlock
    Baby Gauss
    03 Dec '14 07:20 / 1 edit
    Originally posted by Duchess64
    "...because it implies that I'm describing a group."
    --Adam Warlock

    That's what I assumed, though it's helpful to have your (implicit) clarification.

    "Hence there was nothing wrong with my sentence..."
    --Adam Warlock

    From the perspective of clarity, there's something that should have been
    improved in your original post. If I had to devise a ...[text shortened]... ing in terms of asking about the set S. (sarcasm)

    'Care to try and solve the problem?'

    No.
    Sigh, I'll say it more clearly to see if it gets through your thick mathematical genius skull:

    If I state the problem with the word group instead of the word set then there is no need to prove that there exists an identity element since by definition a group needs to have an identity element (just check the link you provided in case you don't take my word for it . But read all the way through because maybe, just maybe you'll get the understand what is a group and what is the difference between a set, a group and a set with an * operation defined (not all of these sets need to be groups)).

    Your facade of having great mathematical knowledge is getting thinner as the days pass.
  13. Standard member adam warlock
    Baby Gauss
    03 Dec '14 07:26
    Originally posted by DeepThought
    If it's a group then the inverse axiom is present. Although since the presence of an identity is not explicitly in the axioms I've still proved that my extra axiom guarantees an identity element and inverse for each element.

    Part of the reason for posting my special case proof was to see if I was barking up the wrong tree or not.
    If it is a group then you need not to prove that there is an identity element since a group by definition has an identity element.

    The conditions are:

    It is a set
    It has finite elements
    It has an * operation which is commutative and associative.

    And only those conditions.

    If you insert the extra condition that there exists an inverse element than you are implicitly assuming the existence of an identity element.
  14. Standard member DeepThought
    Losing the Thread
    03 Dec '14 15:24
    Originally posted by adam warlock
    If it is a group then you need not to prove that there is an identity element since a group by definition has an identity element.

    The conditions are:

    It is a set
    It has finite elements
    It has an * operation which is commutative and associative.

    And only those conditions.

    If you insert the extra condition that there exists an inverse element than you are implicitly assuming the existence of an identity element.
    I'm left wondering if you expect the subset generated by taking product of an arbitrary element x with each element of the set to be the entire set. I added my extra axiom specifically to generate that condition. If not then I don't think it's trivial to show some sort of contradiction if it doesn't. Just checking?
  15. Standard member adam warlock
    Baby Gauss
    03 Dec '14 16:02 / 1 edit
    Originally posted by DeepThought
    I'm left wondering if you expect the subset generated by taking product of an arbitrary element x with each element of the set to be the entire set. I added my extra axiom specifically to generate that condition. If not then I don't think it's trivial to show some sort of contradiction if it doesn't. Just checking?
    Consider that the set has n elements: a_1, a_2,..., a_n

    Take the "product" a_1*a_2*...*a_n.

    From this, the result will follow.