Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

1: Binary Operations

( \newcommand{\kernel}{\mathrm{null}\,}\)

The most basic definition in this course is the following:

Definition 1.1: Binary Operation

A binary operation on a set S is a function from S×S to S. If (a,b)S×S then we write ab to indicate the image of the element (a,b) under the function .

The following lemma explains in more detail exactly what this definition means.

Lemma 1.1 A binary operation on a set S is a rule for combining two elements of S to produce a third element of S. This rule must satisfy the following conditions:

(a)

aS and bSabS.

[S is closed under .]

(b)

For all a,b,c,d in S
a=c and b=dab=cd.

[Substiution is permissible.]

(c)

For all a,b,c,d in S
a=bac=bc.

(d)

For all a,b,c,d in S
c=dac=ad.

Proof Recall that a function f from set A to set B is a rule which assigns to each element xA an element, usually denoted by f(x), in the set B. Moreover, this rule must satisfy the condition x=yf(x)=f(y) On the other hand, the Cartesian product S×S consists of the set of all ordered pairs (a,b) where a,bS. Equality of ordered pairs is defined by the rule a=c and b=d(a,b)=(c,d). Now in this case we assume that is a function from the set S×S to the set S and instead of writing (a,b) we write ab. Now, if a,bS then (a,b)S×S. So the rule assigns to (a,b) the element abS. This establishes (a). Now implication ([eqn1.1]) becomes (a,b)=(c,d)ab=cd. From ([eqn1.2]) and ([eqn1.3]) we obtain a=c and b=dab=cd. This establishes (b).

To prove (c) we assume that a=b. By reflexivity of equality, we have for all cS that c=c. Thus we have a=b and c=c and it follows from part (b) that ac=bc, as desired. The proof of (d) is similar.

Remark

In part (a) the order of a and b is important. We do not assume that ab is the same as ba. Although sometimes it may be true that ab=ba, it is not part of the definition of binary operation.

Statement (b) says that if a=c and b=d, we can substitute c for a and d for b in the expression ab and we obtain the expression cd which is equal to ab. One might not think that such a natural statement is necessary. To see the need for it, see Problem 1.7 below.

Part (c) of the above lemma says that we can multiply both sides of an equation on the right by the the same element. Part (d), says that we can multiply both sides of an equation on the left by the same element.

Binary operations are usually denoted by symbols such as +,,,×,,,,,,,,,,,,,, Just as one often uses f for a generic function, we use to indicate a generic binary operation. Moreover, if :S×SS is a given binary operation on a set S, we write ab instead of (a,b). This is called infix notation. In practice, we abbreviate even more; just as we use ab instead of ab or a×b in high school algebra, we will often use ab instead of ab for a generic binary operation.

Notation. We denote the natural numbers, the integers, the rational numbers, and the real numbers by the symbols N, Z, Q, and R, respectively.

Recall that N={1,2,3,}Z={,3,2,1,0,1,2,3,}Q={nm:n,mZ and m0} For now, we assume that students have a basic knowledge of all these number systems. Later in the course, we will give a list of axioms from which all properties of these number systems can be derived. See Appendix C for some basic properties of N and Z that we will need from time to time.

We now list some examples of binary operations. Some should be very familiar to you. Some may be new to you.

Example 1.1 Ordinary addition on N, Z, Q and R.

Example 1.2 Ordinary multiplication on N, Z, Q and R.

Example 1.3 Ordinary subtraction on Z, Q and R. Note that subtraction is not a binary operation on N since, for example, 12N.

Example 1.4 Ordinary division on Q{0} and R{0}. Note that division is not a binary operation on N and Z since, for example, 12N and 12Z. Also note that we must remove 0 from Q and R since division by 0 is not defined.

Example 1.5 For each integer n2 define the set Zn={0,1,2,,n1}. For all a,bZn let

a+b= remainder when the ordinary sum of a and b is divided by n, and

ab= remainder when the ordinary product of a and b is divided by n.

The binary operations defined in Example 1.5 are usually referred to as addition modulo n and multiplication modulo n. The integer n in Zn is called the modulus. The plural of modulus is moduli.

In Example 1.5, it would be more precise to use something like a+nb and anb for addition and multiplication in Zn, but in the interest of keeping the notation simple we omit the subscript n. Of course, this means that in any given situation, we must be very clear about the value of n. Note also that this is really an infinite class of examples: Z2={0,1}, Z3={0,1,2}, Z4={0,1,2,3}, etc. Just to be clear, we give a few examples of addition and multiplication:

In Z4:

2+3=1, 2+2=0, 0+3=3, 23=2, 22=0 and 13=3.

In Z5:

2+3=0, 2+2=4, 0+3=3, 23=1, 22=4 and 13=3\

Example 1.6 For each integer n1 we let [n]={1,2,,n}.
A permutation on [n] is a function from [n] to [n] which is both one-to-one and onto. We define Sn to be the set of all permutations on [n]. If σ and τ are elements of Sn we define their product στ to be the composition of σ and τ, that is, στ(i)=σ(τ(i))for all  n. See Appendix B if any of the terms used in this example are unfamiliar.

Again, we have an infinite number of examples: S1, S2, S3, S4, etc. We discuss this example as well as the other examples in more detail later. First, we give a few more examples:

Example 1.7 Let K denote any one of the following: Z,Q,R,Zn. Let M2(K) be the set of all 2×2 matrices [abcd] where a,b,c,d are any elements of K. Matrix addition and multiplication are defined by the following rules:

[abcd]+[abcd]=[a+ab+bc+cd+d]

[abcd][abcd]=[aa+bcab+bdca+dccb+dd]

for all a,b,c,d,a,b,c,dK.

Example 1.8 The usual addition of vectors in Rn, nN. More precisely

Rn={(x1,x2,,xn) | xiR for all i}.

Addition is defined by the rule: (x1,x2,,xn)+(y1,y2,,yn)=(x1+y1,x2+y2,,xn+yn). where xi+yi denotes the usual addition of the real numbers xi and yi.

Example 1.9 Addition modulo 2 for binary sequences of length n, nN. (This example is important for computer science.) In this case the set is Zn2={(x1,x2,,xn) | xiZ2 for all i}. Recall that Z2={0,1}. Addition is defined by the rule: (x1,x2,,xn)+(y1,y2,,yn)=(x1+y1,x2+y2,,xn+yn). where xi+yi denotes addition modulo 2 (also called exclusive or) of xi and yi. More precisely 0+0=0, 0+1=1, 1+0=1 and 1+1=0.

Example 1.10 The cross product u×v of vectors u and v in R3. Recall that if u=(u1,u2,u3)v=(v1,v2,v3) then u×v is defined by the formula u×v=(|u2u3v2v3|,|u1u3v1v3|,|u1u2v1v2|), where |abcd|=adbc.

Example 1.11 The set operations and are binary operations on the set P(X) of all subsets of X. Recall that the set P(X) is called the power set of X; and, if A and B are sets, then AB is called the union of A and B and AB is called the intersection of A and B.

Definition 1.2:

Assume that is a binary operation on the set S.

  1. We say that is associative if

    x(yz)=(xy)zfor all x,y,z  S.

  2. We say that an element e in S is an identity with respect to if

    xe=x and ex=xfor all x in S.

  3. Let eS be an identity with respect to . Given xS we say that an element yS is an inverse of x if both xy=e and yx=e.
  4. We say that is commutative if xy=yx for all x,yS.
  5. We say that an element a of S is idempotent with respect to if aa=a.
  6. We say that an element z of S is a zero with respect to if zx=z and xz=zfor all xS.

Problem 1.1 Assume that is a binary operation on the set S. Prove the following statements.

(i) If e and e are identities with respect to on S then e=e. [Hint: What is ee?]

(ii) If z and z are zeros with respect to on S then z=z. [Hint: What is zz?]

Problem 1.2 Go through all of the above examples of binary operations and determine which are not associative. Show non-associativity by giving three specific elements a,b,c such that a(bc)(ab)c.

Problem 1.3 Go through all of the above examples of binary operations and determine which are not commutative. Show non-commutativity by giving two specific elements a,b such that abba.

Remark

A set may have several binary operations on it. For example, consider the set R of real numbers. We write (R,), (R,+), and (R,) to indicate the set R with the binary operations multiplication, addition and subtraction, respectively. Similarly, we use this notation for other sets such as the set M2(R), of 2×2 matrices over the real numbers R. We use (M2(R),) and (M2(R),+) to denote matrix multiplication and matrix addition, respectively, on M2(R).

Problem 1.4 Determine which of the examples (R,), (R,+), (M2(R),), and (P(X),) have identities. If there is an identity, determine the elements which do not have inverses.

Problem 1.5 Determine which of the examples (R,), (R,+), (M2(R),), and (P(X),) have zeros. If there is a zero, determine whether or not there are non-zero elements whose product is zero.

Problem 1.6 Determine which of the examples (R,), (R,+), (M2(R),), and (P(X),) have idempotents. Try to find all idempotents in each case.

Problem 1.7 Here we give an example of a rule that appears to define a binary operation, but does not, since substitution is not permissible. Let a,b,c,d be integers with b0 and d0. Then abQ  and  cdQ. Define on Q by: abcd=a+cb2+d2. Show that abcdQ, so Q is closed under . Show by specific example that this rule does not permit substitution.


This page titled 1: Binary Operations is shared under a not declared license and was authored, remixed, and/or curated by W. Edwin Clark via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?