Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member genius
    Wayward Soul
    10 Oct '07 08:51 / 3 edits
    Prove that a set S={a[0], a[1], a[2], ... ,a[n]} that is closed under the operation * contains an element a[ i] such that a[ i]*a[p]=a[p]*a[ i]=a[p] (that is to say, an identity element).

    If this is not true, given a counter-example.
  2. 10 Oct '07 09:38
    Counterexample: Define a[p]*a[q]=a[p].
  3. Standard member adam warlock
    Baby Gauss
    10 Oct '07 10:32 / 1 edit
    Originally posted by genius
    Prove that a set S={a[0], a[1], a[2], ... ,a[n]} that is closed under the operation * contains an element a[ i] such that a[ i]*a[p]=a[p]*a[ i]=a[p] (that is to say, an identity element).

    If this is not true, given a counter-example.
    Is S is closed under the operation we have that a[p]*a[q] is still an element of S. So we can define define a[p]*a[q]=a[s] where a[s] is still an element of S.

    Then we notice that a[1]*a[2]*a[3]*...*a[n-1]*a[n]=a[k] is still an element of S by continuosly applying the previous argument. But since we exausted all the elements of S we can be sure that a[k]=a[p] for some p
  4. Standard member adam warlock
    Baby Gauss
    10 Oct '07 10:33 / 3 edits
    Is S is closed under the operation we have that a[p]*a[q] is still an element of S. So we can define define a[p]*a[q]=a[s] where a[s] is still an element of S.
  5. Standard member adam warlock
    Baby Gauss
    10 Oct '07 10:34 / 1 edit
    This keeps on cutting my full post. I'll send you the answer via PM.
  6. Standard member adam warlock
    Baby Gauss
    10 Oct '07 10:40 / 2 edits
    Meh, this is my last try...
    http://tinypic.com/view.php?pic=2gwhoav&s=2
  7. Standard member adam warlock
    Baby Gauss
    10 Oct '07 11:37 / 2 edits
    I think this will do the trick and since I can't edit one of my previous posts I'll have to spam this thread one more time. Sorry for that one. Anyway what was causing the problem was a less than sign.

    If S is closed under the operation * we have that a[p]*a[q] is still an element of S. So we
    can define a[p]*a[q]=a[s] where a[s] is still an element of S.

    Then we notice that a[1]*a[2]*a[3]*...*a[n-1]*a[n]=a[k] is still an element of S by
    continuously applying the previous argument. But since we exhausted all the elements
    of S we can be sure that a[k]=a[p] for some p in {1,2,...,n}. So without loss of generality let's take for instance k=2. Then we have a[1]*a[2]*a[3]*...*a[n-1]*a[n]=a[2] and in which case it'll be a[1]*a[3]*...*a[n-1]*a[n]=1.

    Note that the particular value of k that we took here doesn't really matter since with
    every other value we could make the following conclusion:
    a[1]*a[2]*a[3]*...*a[n-1]*a[n]=a[k] for some k in {1,2,...,n} then we would have
    a[1]*a[2]*...a[k-1]*a[k]*a[k+1]*...*a[n-1]*a[n]=a[k] which would imply
    a[1]*a[2]*...a[k-1]*a[k+1]*...*a[n-1]*a[n]=1
  8. Standard member Palynka
    Upward Spiral
    10 Oct '07 11:43 / 1 edit
    Originally posted by adam warlock
    I think this will do the trick and since I can't edit one of my previous posts I'll have to spam this thread one more time. Sorry for that one. Anyway what was causing the problem was a less than sign.

    If S is closed under the operation * we have that a[p]*a[q] is still an element of S. So we
    can define a[p]*a[q]=a[s] where a[s] is still an e a[k+1]*...*a[n-1]*a[n]=a[k] which would imply
    a[1]*a[2]*...a[k-1]*a[k+1]*...*a[n-1]*a[n]=1
    But how do you know that 1 (the RHS) is a part of the set? (that is, if we don't, how does that imply that an identity element exists?)
  9. Standard member adam warlock
    Baby Gauss
    10 Oct '07 11:56
    Originally posted by Palynka
    But how do you know that 1 (the RHS) is a part of the set? (that is, if we don't, how does that imply that an identity element exists?)
    Because the set is closed. That means that if you multiply elements of the set you will ALWAYS get elements of the set. a[1]*...*a[k-1]*a[k+1]*...a[n] belongs to the set with no doubt and by the equality a[1]*...*a[k-1]*a[k]*a[k+1]*...a[n]=a[k] it just equals 1. That is of course if the multiplication operation on the set S is commutative.
  10. Standard member adam warlock
    Baby Gauss
    10 Oct '07 12:22 / 2 edits
    Originally posted by David113
    Counterexample: Define a[p]*a[q]=a[p].
    I don't know if you're joking or not, but the counter-example would be a set S closed under the multilication operation that doesn't have the unit element in it.
    Just changing the letters in the indexes doesn't cut it cause they are dummy indexes.
  11. Standard member genius
    Wayward Soul
    10 Oct '07 12:57 / 2 edits
    Originally posted by adam warlock
    I think this will do the trick and since I can't edit one of my previous posts I'll have to spam this thread one more time. Sorry for that one. Anyway what was causing the problem was a less than sign.

    If S is closed under the operation * we have that a[p]*a[q] is still an element of S. So we
    can define a[p]*a[q]=a[s] where a[s] is still an e a[k+1]*...*a[n-1]*a[n]=a[k] which would imply
    a[1]*a[2]*...a[k-1]*a[k+1]*...*a[n-1]*a[n]=1
    As I said in the PM, i think you are implying that the set is commutative. I'll have a proper look at it tonight, but i don't think a[1]*a[2]*...a[k-1]*a[k]*a[k+1]*...*a[n-1]*a[n]=a[k] would imply a[1]*a[2]*...a[k-1]*a[k+1]*...*a[n-1]*a[n]=1 unless S was commutative.

    EDIT: but the identity is commutative with all S...hmm...

    EDIT2: spent so long contemplating your answer that i forgot to plunge my coffee. Its strong...
  12. Standard member adam warlock
    Baby Gauss
    10 Oct '07 13:11
    Originally posted by genius
    As I said in the PM, i think you are implying that the set is commutative. I'll have a proper look at it tonight, but i don't think a[1]*a[2]*...a[k-1]*a[k]*a[k+1]*...*a[n-1]*a[n]=a[k] would imply a[1]*a[2]*...a[k-1]*a[k+1]*...*a[n-1]*a[n]=1 unless S was commutative.

    EDIT: but the identity is commutative with all S...hmm...

    EDIT2: spent so long contemplating your answer that i forgot to plunge my coffee. Its strong...
    Yes, yes I'm assuming that the * defined in the set is commutative but I think it is a fair assumption.

    a[1]*a[2]*...a[k-1]*a[k]*a[k+1]*...*a[n-1]*a[n]=a[k] the things is if we can swap a[k] all the way through the end of the product, or front, to have a[1]*a[2]*...a[k-1]*a[k+1]*...*a[n-1]*a[n]*a[k]=a[k]. If so the result follows. So what really at stake here is not the fact of the identity being commutative but if the a[k] are commutative with eachother.

    By the way were did you get this problem from? And do you an answer that doesn't use the assumption of commutability of a[k]. If so just tell me and I'll think harder.
  13. Standard member adam warlock
    Baby Gauss
    10 Oct '07 13:19
    {0,0} is a counter example if the elements need not to be different.

    But if we assume that * is commutative then the previous result still holds.

    May I hijack your thread for a while? *hijacks thread anyway*

    Let's assume that * is indeed commutative and that the elements are different. Then how many elements have the set S. How many set S' can you find?

    If the elements need not to be different which is the form of the set S? And how many set S' exist now?
  14. Standard member Palynka
    Upward Spiral
    10 Oct '07 13:27 / 2 edits
    Originally posted by adam warlock
    Because the set is closed. That means that if you multiply elements of the set you will ALWAYS get elements of the set. a[1]*...*a[k-1]*a[k+1]*...a[n] belongs to the set with no doubt and by the equality a[1]*...*a[k-1]*a[k]*a[k+1]*...a[n]=a[k] it just equals 1. That is of course if the multiplication operation on the set S is commutative.
    But don't you have to multiply by 1/a[k] to get there, which is not guaranteed to be in the set?

    Edit - Ah, ok, I see it. You just call a[1]*...*a[k-1]*a[k]*a[k+1]*...a[n] as a[ i] and then a[ i]*a[k]=a[k]. Nice.
  15. Standard member genius
    Wayward Soul
    10 Oct '07 13:37 / 1 edit
    Originally posted by adam warlock
    Yes, yes I'm assuming that the * defined in the set is commutative but I think it is a fair assumption.

    a[1]*a[2]*...a[k-1]*a[k]*a[k+1]*...*a[n-1]*a[n]=a[k] the things is if we can swap a[k] all the way through the end of the product, or front, to have a[1]*a[2]*...a[k-1]*a[k+1]*...*a[n-1]*a[n]*a[k]=a[k]. If so the result follows. So what really at ...[text shortened]... oesn't use the assumption of commutability of a[k]. If so just tell me and I'll think harder.
    I have more of a sketch proof (I know, I know...but i'm not sure how correct it is). I came across a similar problem in one of my modules-Finite Maths-where we were asked to prove that in a finite field F there exists an integer n such that 1+1+...+1=0 (where there are n 1s). I couldn't think how to tackle it so i showed it (roughly) for a general finite set, although under a non-commutative (but closed!) operation (which, in retrospect, is silly as a field is commutative by definition).

    I really can't fault my logic, and it is actually quite a natural thing to assume in a finite set under a closed operation. However, I couldn't fault my logic when i made an elementary mistake the other day, so I could be completly wrong...