Results 1 to 11 of 11
Like Tree5Thanks
  • 1 Post By emakarov
  • 1 Post By emakarov
  • 1 Post By emakarov
  • 1 Post By Deveno
  • 1 Post By Deveno

Math Help - Same binary operation * with two different outcome:Why?

  1. #1
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Same binary operation * with two different outcome:Why?

    A binary operation * on set S has to fulfill two conditions given below:

    1) exactly one element is assigned to each possible ordered pair of element of S,
    2) for each ordered pair of elements of S, the element assigned to it is again in S.


    Now there is an example in Fraleigh's abstract algebra book(Example 2.25):

    Let S be a set consisting of 20 people, no two of whom are of the same height and let a * b = c, where c is the shortest person in S who
    is taller than both a and b. This * is not everywhere defined, since if either a or b is the tallest person in the set, a * b is not
    determined.

    Now in the exercise there is a problem(exercise 20):

    On \mathbb{Z}^+, define * by letting a * b = c, where c is the smallest integer greater than both a and b.

    The solution manual says this * is a valid binary operation. Why these two same problems with different wording have different outcomes?


    For exercise 20 my problem is:
    There can be a positive integer a or b that is greater than c. In that case shouldn't this binary operator be undefined according to example
    2.25?

    Then solution manual says that exercise 20 is a valid binary operation.

    Is it possible to tell me why in exercise 20 the binary operation is valid when example 2.25 says that the binary operation is invalid?
    Last edited by x3bnm; May 10th 2012 at 04:04 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Same binary operation * with two different outcome:Why?

    Quote Originally Posted by x3bnm View Post
    For exercise 20 my problem is:
    There can be a positive integer a or b that is greater than c. In that case shouldn't this binary operator be undefined according to example
    2.25?
    I am not sure what c is. Is this variable bound by a quantifier such as "for all c" or "there exists a c"? In every mathematical statement, objects have to be either defined previously or bound by quantifiers.

    The operation on \mathbb{Z}^+ is everywhere defined because unlike a finite set, \mathbb{Z}^+ does not have a maximal element (and also because the order on \mathbb{Z}^+ is well-founded, which allows choosing the smallest positive integer from every subset).
    Thanks from x3bnm
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Same binary operation * with two different outcome:Why?

    Thanks a lot for answering my problem and you're right.

    You mentioned about \forall and \exists statement.

    By the definition of binary operation in Fraleigh's book:

    A binary operation * on a set S is a function mapping S \times S into S. For each (a, b) \in S \times S, we will
    denote the element *((a, b)) of S by a * b.

    How is c used here? Is it used here as \forall or \exists?
    Last edited by x3bnm; May 10th 2012 at 05:38 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Same binary operation * with two different outcome:Why?

    Quote Originally Posted by x3bnm View Post
    A binary operation * on a set S is a function mapping S \times S into S. For each (a, b) \in S \times S, we will
    denote the element *((a, b)) of S by a * b.

    Does this mean c is used here as \forall or \exists?
    I don't see c in the quoted phrase.
    Thanks from x3bnm
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Same binary operation * with two different outcome:Why?

    Here c is the result of a * b where a,b,c \in \mathbb{Z}^+
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Same binary operation * with two different outcome:Why?

    I am getting a bit lost. In such situation, the best solution to recover understanding is to say things a bit more formally. Are you wondering if a certain mathematical statement is true or false? If so, what statement is this? Do you need to prove it?

    Initially I objected to the phrase "There can be a positive integer a or b that is greater than c," which probably means ∃a, b. a > c or b > c. Here a and b are introduced by quantifiers, but c is undefined. If by c you mean a * b where * was defined in exercise 20, then it cannot be less than a or b by the definition of *.
    Thanks from x3bnm
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Same binary operation * with two different outcome:Why?

    Thanks a lot for clearing the conception.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,310
    Thanks
    687

    Re: Same binary operation * with two different outcome:Why?

    to answer your question:

    a binary operation on S is by definition a function from SxS to S again. this means that "for all" a,b in S, "there exists" c in S with a*b = c. so this can fail in different ways:

    a*b exists, but is not in S. an example is S = Z+, and * = "divided by". for example 2/4 is the rational number 1/2, which is not a positive integer.

    a*b can fail to exist. this time, let S = Q+ U {0}, and let * = "divided by". then 3/0 does not exist (there is no number field in which this has an answer, it's not merely a matter of "S being too small").

    remember a function f on SxS has to have a defined value at every point (a,b) in SxS. for example, f(x,y) = x/y is NOT a function on RxR, it is undefined at (a,0), for example. at best, we can only say that f(x,y) = x/y is a function on R x (R - {0}).

    so just saying that something is a binary operation on a set S is already restricting the kinds of behavior we can have. not only is a*b in S, it also makes sense for EVERY pair (a,b).

    sometimes one will see things like "consider the function f:R-->R defined by f(x) = 1/x". this is very bad, because that is not a function defined on all of R. it's only defined for non-zero real numbers.

    in Fraleigh's first example, * is not defined on all of S (so it is NOT a binary operation on S, because it's not a function), because if a or b is the tallest person, a*b doesn't return a value (because there isn't anyone (in S) taller than the tallest person in S).

    when we switch to the positive integers, it's a different story, no matter how big an integer we pick (say n, for example), we can always find a bigger one: namely, n+1. this is the very essence of how infinite sets differ from finite sets...with an infinite set, no matter how big a finite subset we choose, we can always "add one more element that isn't in our finite set". because if S is a finite subset of an infinite set T, then S ≠ T, so there is some x in T - S. even when we add this to S, by taking S' = S U {x}, we still get another finite set. so S' ≠ T, so we can pick a y in T - S'. we can keep this up as long as we like...we'll never "exhaust" T, unless we do this an infinite number of times.

    hopefully this convinces you that for a finite set, there are only a finite number of possible binary operations on S (i believe it's |S|3). this greatly restricts the number of binary operation structures we can impose on S, and if we require that these operations satisfy other rules as well (such as associativity, or commutativity), the possibilities get fewer still. it also should help you see that just defining "what * does" is not enough, even if the definition of * "makes sense", we still have to check that "* stays within bounds".

    for example, if * = "complex multiplication", then if we have any complex number z with |z| > 1 in our set S, S has to have complex numbers of arbitrarily large magnitudes (it is an unbounded set). one way to keep this from happening is to choose S = {z in C: |z| = 1}, the unit circle, or S = {z in C : |z| < 1}, the open unit disk, in which case * is "well-behaved" (it "stays within the bounds imposed by the unit circle"). another way to impose the "kind of behavior we want" is to stipulate that Im(z) = 0 (that is z is of the form z = x + i0, so z is a real number). this limits us to complex numbers that lie on the real line ("bounded in one direction" (the y-axis)).

    long story short: finite things act fundamentally different than infinite things. in general, we can say lots more about "finite things" than "infinite things" (which often display bizarre behavior).
    Thanks from x3bnm
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Same binary operation * with two different outcome:Why?

    Thank you Deveno for saving me again.

    I've one last question. You said:

    > Deveno said:
    > hopefully this convinces you that for a finite set, there are only a finite number of possible binary operations on S (i believe it's |S|3).
    In Fraleigh's AA book he mentioned that if you lay out n elements of S in a binary operation table where n elements are on top column header and n elements in left row header you 'll have n^2 spaces and n^{n^2} possible binary operations.

    So if you have one element in S you'll have 1 possible binary operation. If you've 2 elements you'll have 2*2*2*2 = 2^4 = 16 and if 3 you'll have 3^{3^2} possible binary operations.

    I apologize for my ignorance but why did you said "i believe it's \left|S\right|^3 " possible binary operations? Why your number of possible binary operations is different than Fraleigh's? I didn't get that part. Again thanks for the nice explanation.
    Last edited by x3bnm; May 13th 2012 at 04:44 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,310
    Thanks
    687

    Re: Same binary operation * with two different outcome:Why?

    Fraleigh is correct. i was thinking it was n(n2), but it is indeed nn2.

    (for a finite set A, and a finite set B, there are |B||A| possible functions f:A→B. this is easiest to see when B = {0,1}, and we can identify a function f:A→{0,1} with a subset S of A, namely f(a) = 1 if a is in S, and f(a) = 0, if a is not in S. thus there are 2|A| possible subsets of A).
    Thanks from x3bnm
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Same binary operation * with two different outcome:Why?

    Deveno said:
    Fraleigh is correct. i was thinking it was n(n2), but it is indeed nn2

    (for a finite set A, and a finite set B, there are |B||A| possible functions f:A→B. this is easiest to see when B = {0,1}, and we can identify a function f:A→{0,1} with a subset S of A, namely f(a) = 1 if a is in S, and f(a) = 0, if a is not in S. thus there are 2|A| possible subsets of A).
    Thanks for the clarification.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. binary operation
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: March 14th 2010, 09:09 AM
  2. binary operation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 30th 2009, 07:10 PM
  3. New Binary operation
    Posted in the Algebra Forum
    Replies: 4
    Last Post: August 16th 2009, 12:31 AM
  4. I Need a Binary Operation
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 8th 2008, 09:14 AM
  5. binary operation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 4th 2008, 02:48 PM

Search Tags


/mathhelpforum @mathhelpforum