Same binary operation * with two different outcome:Why?

• May 10th 2012, 04:12 PM
x3bnm
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?
• May 10th 2012, 05:09 PM
emakarov
Re: Same binary operation * with two different outcome:Why?
Quote:

Originally Posted by x3bnm
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).
• May 10th 2012, 06:34 PM
x3bnm
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$?
• May 10th 2012, 06:37 PM
emakarov
Re: Same binary operation * with two different outcome:Why?
Quote:

Originally Posted by x3bnm
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.
• May 10th 2012, 06:44 PM
x3bnm
Re: Same binary operation * with two different outcome:Why?
Here $c$ is the result of $a * b$ where $a,b,c \in \mathbb{Z}^+$
• May 10th 2012, 06:56 PM
emakarov
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 *.
• May 10th 2012, 07:28 PM
x3bnm
Re: Same binary operation * with two different outcome:Why?
Thanks a lot for clearing the conception.
• May 11th 2012, 10:15 AM
Deveno
Re: Same binary operation * with two different outcome:Why?

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).
• May 13th 2012, 03:34 AM
x3bnm
Re: Same binary operation * with two different outcome:Why?
Thank you Deveno for saving me again.

I've one last question. You said:

Quote:

> 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.
• May 13th 2012, 11:11 AM
Deveno
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).
• May 13th 2012, 01:35 PM
x3bnm
Re: Same binary operation * with two different outcome:Why?
Quote:

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.