[PDF] Chapter 4: Binary Operations and Relations

View - Download Chapter 4: Binary Operations and Relations

Previous PDF

Next PDF

c

Dr Oksana Shatalov, Fall 20141

Chapter 4: Binary Operations and Relations

4.1: Binary Operations

DEFINITION1.Abinary operationon a nonempty setAis a function fromAAtoA. Addition, subtraction, multiplication are binary operations onZ.

Addition is a binary operation onQbecause

Division is NOT a binary operation onZbecause

Division is a binary operation on

Classication of binary operations by their properties

Associative and Commutative Laws

DEFINITION2.A binary operationonAisassociativeif

8a;b;c2A;(ab)c=a(bc):

A binary operationonAiscommutativeif

8a;b2A; ab=ba:

Identities

DEFINITION3.Ifis a binary operation onA, an elemente2Ais anidentity elementofAw.r.t if

8a2A; ae=ea=a:

EXAMPLE4.1is an identity element forZ,QandRw.r.t. multiplication.

0is an identity element forZ,QandRw.r.t. addition.

c

Dr Oksana Shatalov, Fall 20142

Inverses

DEFINITION5.Letbe a binary operation onAwith identitye, and leta2A. We say thatais invertiblew.r.t.if there existsb2Asuch that ab=ba=e: Iffexists, we say thatbis aninverseofaw.r.t.and writeb=a1:

Note, inverses may or may not exist.

EXAMPLE6.Everyx2Zhas inverse w.r.t. addition because

8x2Z; x+ (x) = (x) +x= 0:

However, very few elements inZhave multiplicative inverses. Namely,

EXAMPLE7.Letbe a binary operation onZdened by

8a;b2Z; ab=a+ 3b1:

(a)Prove that the operation is binary. (b)Determine whether the operation is associative and/or commutative. Prove your answers. (c)Determine whether the operation has identities. (d)Discuss inverses. c

Dr Oksana Shatalov, Fall 20143

EXAMPLE8.Letbe a binary operation on the power setP(A)dened by

8X;Y2P(A); XY=X\Y:

(a)Prove that the operation is binary. (b)Determine whether the operation is associative and/or commutative. Prove your answers. (c)Determine whether the operation has identities. (d)Discuss inverses.

EXAMPLE9.Letbe a binary operation onF(A)dened by

8f;g2F(A); fg=fg:

(a)Prove that the operation is binary. (b)Determine whether the operation is associative and/or commutative. Prove your answers. c

Dr Oksana Shatalov, Fall 20144

(c)Determine whether the operation has identities. (d)Discuss inverses. EXAMPLE10.1Letbe a binary operation on the setM2(R)of all22matrices dened by

8A1;A22M2(R); A1A2=A1+A2:

(a)Prove that the operation is binary. (b)Determine whether the operation is associative and/or commutative. Prove your answers.1 se Appendix at the end of the Chapter. c

Dr Oksana Shatalov, Fall 20145

(c)Determine whether the operation has identities. (d)Discuss inverses. EXAMPLE11.Letbe a binary operation on the setM2(R)of all22matrices dened by

8A1;A22M2(R); A1A2=A1A2:

(a)Prove that the operation is binary. (b)Determine whether the operation is associative and/or commutative. Prove your answers. c

Dr Oksana Shatalov, Fall 20146

(c)Show that the matrixI=1 0 0 1 is an identity element w.r.t..

(d)Discuss inverses (Use the following FACT: \A matrix is invertible if and only if its derminant does

not equal to zero"). PROPOSITION12.Letbe a binary operation on a nonempty setA. Ifeis an identity element on

Atheneis unique.

Proof.

PROPOSITION13.Letbe an associative binary operation on a nonempty setAwith the identitye, and ifa2Ahas an inverse element w.r.t., then this inverse element is unique.

Proof.See Exercise 12.

c

Dr Oksana Shatalov, Fall 20147

Closure

DEFINITION14.Letbe a binary operation on a nonempty setA, and suppose thatXA. Ifis also a binary operation onXthen we say thatXis closed inAunder. EXAMPLE15.Determine whether the following subsets ofZare closed inZunder addition and mul- tiplication. (a) Z (b) E (c) O EXAMPLE16.Determine whether the following subsets ofM2(R)is closed inM2(R)under matrix addition and multiplication: S=a b c d

2M2(R)ja=d:

c

Dr Oksana Shatalov, Fall 20148

4.2: Equivalence Relations

DEFINITION17.ArelationRon a setAis a subset ofAA. If(a;b)2R, we writeaRb. EXAMPLE18.On the setRone can deneaRbbya < b. Then, for example, EXAMPLE19.On the power setP(Z)one can deneRbyARBifjAj=jBj.

Properties of Relations

DEFINITION20.LetRbe a relation on a setA. We say:

1.Risre

exiveifaRa,8a2A:

2.Rissymmetricif8a;b2A, ifaRbthenbRa.

3.Ristransitiveif8a;b;c2A, ifaRbandbRc, thenaRc.

4.Risantisymmetricif8a;b2A, ifaRbandbRa, tena=b.

DEFINITION21.A relationRon a setAis called anequivalence relationif it is re exive, sym- metric, and transitive. EXAMPLE22.LetRbe the relation onZdened byaRbifab. Determine whether it is re exive, symmetric, transitive, or antisymmetric. c

Dr Oksana Shatalov, Fall 20149

EXAMPLE23.LetRbe the relation onRdened byaRbifjabj 1(that isais related tobif the distance betweenaandbis at most 1.) Determine whether it is re exive, symmetric, transitive, or antisymmetric. EXAMPLE24.LetRbe the relation onZdened byaRbifa+3b2E. Show thatRis an equivalence relation. REMARK25.WhenRis an equivalence relation, it is common to writeabinstead ofaRb, read \a is equivalent tob." c

Dr Oksana Shatalov, Fall 201410

EXAMPLE26.Letn2Z+. DeneaRbonZbynjab. (In particular, ifn= 2theaRbmeansab is). Show thatRis an equivalence relation. REMARK27.The above relation is calledcongruencemodn, and usually written ab(modn) c

Dr Oksana Shatalov, Fall 201411

Equivalence Classes

DEFINITION28.IfRis an equivalence relation on a setA, anda2A, then the set [a] =fx2Ajxag is called theequivalence classofa. Elements of the same class are said to beequivalent. EXAMPLE29.DeneaRbonZby2jab:(In other words,Ris the relation of congruence mod2onZ.) (a)What integers are in the equivalence class of6? (b)What integers are in the equivalence class of25? (c)How many distinct equivalence classes there? What are they? EXAMPLE30.DeneaRbonZbynjab:(In other words,Ris the relation of congruence modnon Z.) (a)How many distinct equivalence classes there? What are they? c

Dr Oksana Shatalov, Fall 201412

(b)Show that the set of these equivalence classes forms a partition ofZ: THEOREM31.IfRis an equivalence relation on a nonempty setA, then the set of equivalence classes onRforms a partition onA.

Proof.

So, any equivalence relation on a setAleads to a partition ofA. In addition, any partition ofAgives rise to an equivalence relation onA. c

Dr Oksana Shatalov, Fall 201413

THEOREM32.LetRbe a partition of a nonempty setA. Dene a relationR1onAbyaR1bifaand bare in the same element of the partitionR. ThenR1is an equivalence relation onA.

Proof.

Conclusion:Theorems 31 and 32 imply that there is a bijection between the set of all equivalence relations ofAand the set of all partitions onA. EXAMPLE33.LetRbe the relation onZdened byaRbifa+3b2E. By one of the above examples, Ris an equivalence relation. Determine all equivalence classes forR. cquotesdbs_dbs2.pdfusesText_2

[PDF] élément absorbant

[PDF] exercice nombre complexe

[PDF] statistiques maths 1ere sti2d

[PDF] cours nombres complexes terminale s pdf

[PDF] exercice nombre complexe terminale sti2d

[PDF] cours sur les nombres complexes terminale sti2d

[PDF] exercice nombre complexe sti2d

[PDF] fonction du théatre dissertation

[PDF] module et argument sti2d

[PDF] cours maths nombres complexes terminale sti2d

[PDF] nombres complexes bac pro

[PDF] le théâtre et ses fonctions

[PDF] produit scalaire 1ere sti2d

[PDF] comment resoudre un systeme dans c

[PDF] système nombre complexe