SETSANDELEMENTS

Aset is a collection ofobjects called theelementsormembers oftheset. Theordering ofthe elements is not important and repetition of elements is ignored, for example{1, 3, 1, 2, 2, 1} ={1, 2, 3}.

Oneusuallyuses capital letters, A,B,X, Y, . . . , todenotesets, and lowercaseletters, a, b, x,y, . . ., to denoteelements ofsets.

Belowyou‘ll seejust asamplingofitems that could be considered as sets:

• Theitems in astore
• The English alphabet
• Even numbers

Aset could haveas manyentries asyou would like.

It could haveoneentry, 10 entries, 15 entries, infinitenumberof entries, orevenhave no entries at all!

For example, in the abovelist the English alphabet would have26 entries,whilethe set of even numbers would have an infinitenumberof entries.

Each entryinaset is known as an elementormember

Sets are written usingcurlybrackets“{“and“}“,with their elements listed in between.

For examplethe English alphabet could bewrittenas

{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}

and even numbers couldbe{0,2,4,6,8,10,…} (Note: thedots at the end indicatingthat theset goes on infinitely)

Principles:

∈    belongto

∉    not belongto

⊆    subset

⊂    propersubset,For example, {a, b} is apropersubset of{a, b, c}, but {a, b,c} is not apropersubset of{a, b, c}.

⊄    not subset

So we could replacethestatement “ais belongto the alphabet“with

a ∈{alphabet} and replacethestatement“3 is notbelongto theset of evennumbers” with3 ∉{Even numbers}

Nowif wenamed oursets we couldgo even further.

Givetheset consistingofthealphabetthename A, andgivetheset consistingof

even numbers thenameE.

We could now write a ∈A

and

3∉E.

Problem

Let A={2, 3, 4, 5} andC ={1, 2, 3, . . ., 8, 9},Showthat Ais apropersubset ofC.

Answer

Each element ofAbelongs toC so A⊆C. On theotherhand, 1∈C but 1∉A. HenceA≠C. ThereforeAis apropersubset ofC.

Therearethreeways to specifyaparticularset:

1. Bylist its members separated bycommas andcontained in braces{ }, (ifit is possible), for example,A={a,e,i,o,u}
2. Bystatethosepropertieswhich characterizethe elements in theset, for example,A={x:xis aletterin the English alphabet, xis avowel}
3. Venn diagram: (Agraphical representation ofsets).

Example (1)

A={x:xis aletterin the English alphabet, xis avowel} e ∈A(eisbelongto A)

f ∉A (fisnot belongtoA)

Example (2)

Xis theset {1,3,5,7,9} 3∈X  and      4∉X

Example (3)

Let E={x|x2−3x+2 =0}   → (x–2)(x–1)=0  → x=2 &x=1

E={2, 1}, and          2∈Ε

Universalset,emptyset:

Inanyapplication ofthetheoryofsets, themembers of all sets underinvestigation

usuallybelongto some fixed largeset called theuniversal set. For example, in human population studies theuniversal set consists of allthepeoplein the world.We will let thesymbol Udenotes theuniversal set.

Thesetwithnoelements is calledtheemptysetor nullsetandisdenotedby∅or{}

Subsets:

Everyelement in asetAis also an element ofaset B, then Ais called asubset ofB.

We also saythatBcontains A.This relationship is written: A⊂B       or         B⊃A

IfAis not asubset ofB,i.e. if at least oneelement ofAdosenot belongto B, we writeA⊄B.

Example4:

Considerthesets.

A={1,3,4,5,8,9}        B ={1,2,3,5,7}   and    C ={1,5}

ThenC⊂A and C⊂Bsince1 and 5, theelementofC, are also members ofA andB. ButB⊄Asincesomeofits elements, e.g. 2and7,do not belongto A.Furthermore,

sincethe elements ofA,Band C must also belongto theuniversal set U,wehavethat

Umust at least theset {1,2,3,4,5,7,8,9}.

∀:Forall               ﻞﻜﻟ

∃:Thereexists       ﻞﻗﻻﺍ ﻰﻠﻋ ﺪﺟﻮﻳ

Thenotion ofsubsets is graphicallyillustrated below:

Ais entirelywithin BsoA⊂B.

AandBaredisjointor(A∩B=∅)so wecouldwriteA⊄BandB⊄A.

Setofnumbers:

Several sets areused so often, theyaregiven special symbols.

N= theset ofnatural numbers orpositiveintegers

Z= theset ofall integers: . . . ,−2,−1, 0, 1, 2, . . .

Q = theset of rational numbers

Where Q={a/b:a,b∈Z,b≠0}

R= theset ofreal numbers

C= theset of complexnumbers

Where C={x+iy;x,y∈R;i=√–1} Observethat N ⊂Z⊂Q ⊂R⊂C.

Theorem1:

For anyset A, B, C:

• 1-∅⊂A⊂U.

   

• 2-A⊂A.

   

• 3-IfA⊂B andB ⊂C, thenA⊂C.

   

• 4-A=Bifand onlyifA ⊂BandB⊂A.

Setoperations:

1) UNION:

Theunionof twosetsAandB,denotedbyA∪B,isthesetof allelementswhich belongto Aorto B;

A∪B= {x:x∈A or x∈B} Example

A={1,2,3,4,5} B={5,7,9,11,13}

A∪B={1,2,3,4,5,7,9,11,13}

2)INTERSECTION

TheintersectionoftwosetsA andB,denotedbyA∩B,isthesetofelementswhichbelongtobothA

andB;

A ∩B= {x:x∈Aandx∈B}.

Example1

A={1,3,5,7,9}                        B={2,3,4,5,6}

The elements theyhavein common are3 and 5 A∩B={3,5}

Example2

A={The English alphabet}    B={vowels} SoA∩B={vowels}

Example3

A={1,2,3,4,5}                        B={6,7,8,9,10}

InthiscaseA andBhave nothingin common.A∩B=∅

1. THE DIFFERENCE:

   Thedifferenceoftwo sets ABor A–Bis those elements which belongtoAbut which do not belongtoB.

   AB={x:x∈A, x∉B}

    

    

    

2. COMPLEMENT OFSET:Complement ofset Acor A‘, is theset ofelements which belongto Ubut which do not belongto A.

Ac={x:x ∈U, x∉A}

Example: let    A={1,2,3}

B={3,4} U={1,2,3,4,5,6}

Find:

A∪B ={1,2,3,4} A∩B={3}

A-B ={1, 2}

Ac={4, 5, 6}

1. Symmetricdifferenceofsets

Thesymmetricdifferenceofsets A andB, denoted by      A B, consists ofthose elements which belongto AorBbut not to both. That is,

A B=(A∪B)(A∩B) or      A B=(AB)∪(BA)

Example: SupposeU=N={1, 2,3, .. .}istheuniversalset.

Let A={1, 2, 3, 4}, B={3, 4, 5, 6, 7},C={2, 3, 8, 9},E={2, 4, 6, 8,. . .}

Then:

Ac={5, 6, 7, . . .}, Bc={1, 2, 8, 9, 10, . . .}, Cc={1,4,5,6,7,10,…} Ec={1, 3, 5, 7, …}

AB={1, 2}, AC ={1,4}, BC={4, 5, 6, 7}, AE={1, 3},

BA={5, 6, 7}, CA={8, 9}, CB ={2, 8, 9}, EA={6, 8, 10, 12, . . .}.

Furthermore:

A B=(AB) ∪(BA)= {1,2,5,6, 7},       B C={2, 4, 5, 6, 7, 8, 9},

A C=(AC)∪(BC)={1,4,8,9},               A E={1, 3, 6, 8, 10, . . .}.

Theorem2 :

A ⊂B,A∩B=A,A∪B =B                are equivalent

Theorem3:(Algebra ofsets)

Sets underthe aboveoperations satisfyvarious laws oridentities which arelisted

below:

• 1-A∪A=AA∩A=A

   

• 2-(A∪B)∪C=A∪(B∪C)Associativelaws (A∩ B)∩C=A∩ (B∩C)

   

• 3-A∪B=B∪ACommutativity A∩ B=B∩A

   

• 4-A∪(Β∩C ) = (A∪Β)∩(Α∪C)Distributivelaws A∩(Β∪C )=(A ∩Β)∪(Α∩C)

   

• 5-A∪∅=AIdentitylaws

  A∩U=A

   

• 6-A∪U=UIdentitylaws

  A ∩∅ =∅

   

• 7-(Ac)c=ADouble complements

   

• 8-A∪Ac=UComplement intersections and unions

  A∩Ac =∅

   

• 9-Uc=∅

  ∅c      = U

   

• 10-(A∪B)c=Ac∩ BcDeMorgan‘s laws (A∩B)c=Ac∪ Bc

Wediscuss two methods ofproving equations involvingset operations. The first is to break downwhat it means for an object xto be anelement ofeach side, andthe second is to use Venn diagrams.

For example, considerthe first of DeMorgan‘s laws:

(A∪B)c         =Ac  ∩ Bc

Wemust prove:       1) (A∪B)c   ⊂ Ac  ∩ Bc

2) Ac  ∩ Bc ⊂ (A∪B)c

We first showthat      (A∪B)c   ⊂ Ac  ∩ Bc

Let‘s pickanelementat random x∈(A∪B)c  . We don‘tknowanything aboutx,it could beanumber,a function. All wedo know about x, isthat:

x∈(A∪B)c ,so x∉A∪B

becausethat‘swhat complement means. Therefore x∉Aand            x∉B,

bypulling apart theunion. Applyingcomplements again weget

x∈Ac and x∈Bc

Finally, ifsomethingis in 2 sets, it must bein theirintersection, so x∈Ac ∩Bc

So,anyelementwe pickatrandomfrom:(A∪B)c                   isdefinitelyin,Ac  ∩ Bc

, so bydefinition

(A ∪B)c   ⊂ Ac  ∩ Bc

Next weshowthat      ( Ac  ∩ Bc)⊂ (A∪B)c .

This follows averysimilar way.Firstly,wepickan element at random from the first set,x∈(Ac  ∩ Bc)

Usingwhat weknowabout intersections, that means x∈Ac   andx∈Bc

Now, usingwhat weknow about complements,

x∉A and        x∉B.

Ifsomethingis in neitherAnorB, it can‘t bein theirunion, so x∉A  ∪B,

And finally

∴     x∈(A ∪B)c

Wehaveprovethateveryelement of          (A∪B)c  belongsto Ac ∩Bcandthat everyelementof Ac ∩Bc                                                               belongsto A∪B)c .Together,these inclusionsprove that thesets havethesame elements, i.e. that                    (A∪B)c      =Ac  ∩ Bc

Powerset

Thepowerset ofsomeset S, denoted P(S), is theset of all subsets ofS (includingS itself and the emptyset)

Example1: Let A={ 1,23}

Powerset ofset A=P(A)=[{1},{2},{3},{1,2},{1,3},{2,3},{},A]

Example2: P({0,1})={{},{0},{1},{0,1}}

Classes ofsets:Collection ofsubset ofaset with someproperties Example: SupposeA={ 1,2 3} ,  let Xbethe class ofsubsets ofA which contain

exactlytwo elements ofA. Then

class  X=[{1,2},{1,3},{2,3}]

Cardinality

The cardinalityofaset S, denoted|S|, is simplythenumberofelements aset has. So

|{a,b,c,d}|= 4,and so on.The cardinalityofaset need not be finite: somesets have infinite cardinality.

Thecardinality ofthe powerset

Theorem:If|A|=n then|P(A)|=2n(Everyset with n elements has 2nsubsets)

Problemset

writethe answers to thefollowingquestions.

1.  |{1,2,3,4,5,6,7,8,9,0}|

2.  |P({1,2,3})|

3.    P({0,1,2})

4.    P({1})

Answers

1. 10

2.    23=8

3.    {{},{0},{1},{2},{0,1},{0,1,2},{0,2},{1,2}}

4.    {{},{1}}

TheCartesianproduct

TheCartesian Product oftwo sets is theset of all tuples made from elements oftwo sets. We writetheCartesian Product oftwo sets Aand BasA×B.It is defined as:

It maybe clearerto understand from examples;

Example:IfA={1, 2, 3} and B ={x,y} then

A. B={(1, x), (1,y), (2, x), (2,y), (3, x), (3,y)}

B. A={(x, 1), (x, 2), (x,3), (y, 1), (y, 2), (y, 3)}

It is clearthat, thecardinalityoftheCartesian product oftwo sets A andB is:

ACartesian Product oftwo sets A andBcan beproduced bymakingtuples of each element ofA with each element ofB; this can bevisualized as agrid(which Cartesian implies)ortable: if, e.g., A={ 0, 1 } and B={ 2, 3 }, thegrid is

Problemset

Answerthefollowingquestions:

1. {2,3,4}×{1,3,4}

2.{0,1}×{0,1}

3.   |{1,2,3}×{0}|

4. |{1,1}×{2,3,4}|

Answers

1. {(2,1),(2,3),(2,4),(3,1),(3,3),(3,4),(4,1),(4,3),(4,4)}

2. {(0,0),(0,1),(1,0),(1,1)}

1. 3.3
2. 6

Partitionsofset:

Let S beanynonemptyset. A partition (∏)ofSis asubdivisionofS into nonoverlapping, nonemptysubsets.  Apartition ofS is a collection {Ai} ofnon-empty subsets ofS such that:

1)Ai≠∅,                wherei=1,2,3,……

2) Thesets of{Ai }aremutuallydisjoint

or Ai∩Aj=∅          wherei≠j.

3)UARiR     =S,       where  AR1R            ∪AR2R            ∪……………… ∪ARiR=S

Thepartition ofaset intofive cells, A1, A2,A3,A4,A5,can berepresented byVenn

diagram

Example1: let A={1,2,3,n}

A1 ={1},A2={3,n}, A3 ={2}

∏={A1, A2, A3} isapartition on Abecauseit satisfythethreeabove conditions.

Example2 :Considerthe following collectionsofsubsets ofS ={1,2,3,4,5,6,7,8,9} (i)         [{1,3,5},{2,6},{4,8,9}]

(ii)        [{1,3,5},{2,4,6,8},{5,7,9}]

(iii)       [{1,3,5},{2,4,6,8},{7,9}]

Then

1. is not apartition ofS since7 in S does not belongto anyofthesubsets.
2. is not apartition ofS since{1,3,5} and {5,7,9} arenot disjoint.
3. is apartition ofS.

FINITE SETS, COUNTING PRINCPLE:

Aset is said to be finiteifit contains exactlym distinct elements wheremdenotes

somenonnegativeinteger. Otherwise,aset is saidto beinfinite. For example, the emptyset∅andthesetoflettersofEnglishalphabetare finitesets,whereasthesetof even positiveintegers, {2,4,6,…..}, is infinite.

Ifaset Ais finite, welet n(A)or#(A)denotethenumberofelements ofA.

Example:IfA ={1,2,a,w} then

n(A)=#(A)=|A|=4

Lemma:IfAandBarefinitesetsanddisjointThenA∪Βisfinitesetand:

n(A∪B)=n(A)+n(B)

Theorem(Inclusion–Exclusion Principle):SupposeA andBare finitesets. Then

A ∪B andA∩Barefiniteand

|A∪B|=|A|+|B|-|A∩B|

That is, we find thenumberof elements in AorB (orboth)byfirst adding n(A) and n(B)(inclusion) and thensubtractingn(A∩B)(exclusion)sinceits elements were counted twice.

We can applythis result to obtain asimilar formula forthreesets:

Corollary:

IfA,B,C arefinitesets then

|A∪B∪C| =|A|+|B|+|C| -|A∩B|-|A ∩C| –|B ∩C| +|A ∩B ∩C|

Example (1):

A={1,2,3}

B={3,4}

C={5,6}

A∪B ∪C={1,2,3,4,5,6}

|A ∪B ∪C|=6

|A| =3      ,  |B| =2 ,  |C|=2

Α∩B ={3}               ,  |Α∩B|=1

Α∩C={}                   , |Α∩C|=0

B ∩C= {}                ,  |Β∩C|=0

Α∩B ∩C={}            ,  |Α∩B∩C|=0

|A∪B∪C|=|A|+|B|+|C| -|A∩B|-|A∩C| –|B∩C| +|A∩B∩C|

|A∪B∪C|=3+2+2–1–0–0+0=6

Example (2):

Supposealist A contains the30 students in amathematics class, andalist Bcontains

the35 students in an English class, and supposethereare20 names on both lists. Find thenumberofstudents:

(a)onlyon list A

(b)onlyon list B

(c)onlistA∪B

Solution:

1. List Ahas 30 names and 20 areon list B; hence30 −20 =10 namesareonlyon list A.
2. Similarly, 35 −20=15 areonlyon list B.
3. Weseekn(A∪B).By inclusion–exclusion,

n(A∪B)=n(A) + n(B)− n(A∩ B)= 30 + 35− 20= 45.

Example (3):

Supposethat 100 of120 computersciencestudents at a collegetake at least oneof

languages: French,German, and Russian and: 65 studyFrench(F).

45 studyGerman (G). 42 studyRussian (R).

20studyFrench&GermanF∩G. 25studyFrench& RussianF∩R. 15studyGerman& RussianG∩R.

Find thenumberofstudents who study:

1. Allthreelanguages(F∩G∩R)
2. Thenumberofstudents in each ofthe eight regions ofthe Venn diagram

Solution:

|F ∪G ∪R|=|F|+|G|+|R| –|F∩G| –|F∩R|-|G∩R| +|F∩G∩R| 100          =65 +45 +42 – 20        –           25                       –  15                        +|F∩G∩R|

100                 =92      +|F∩ G∩R|

∴|F∩ G∩ R|=8studentsstudythe3languages

20 – 8 =12      (F∩G)-R

25 – 8 =17     (F∩R)-G

15 – 8 =7       (G∩R)-F

65 – 12 – 8 – 17 =28   students studyFrench only

45 – 12 – 8 7 =18       students studyGerman only

42 – 17 – 8 7 =10       students studyRussian only

120 – 100 =20         students do not studyanylanguage

Mathematicinduction:

It is usefulforprovingpropositions that must betrue for all integers or forarangeof

integer.

Proposition: is anystatement P(n) which can beeithertrueorfalse foreach n in N. SupposeP has the followingtwo properties.

1. P(1)is true
2. P(k+1)is true wheneverP(k)is true ThenPistrueforeverypositiveinteger∀n≥k.

Example1: Let P betheproposition that thesumofthe first n odd numbers is n2; that is,

P(n):      1 +3 +5 +…+ (2n – 1)=n2

ProveP (forn ≥ 1)

Solution:

(Thenth odd numberis 2n – 1, and thenext odd numberis 2n +1.) Observethat P(n)

is true forn =1,

(i)     n=1;      P(1):     2*n–1 =12

(ii)    n=k;      AssumingP(k)is true,

We add (2k–1)+2  =2K+1 to bothsides ofP(k), obtaining:

1 +3 +5 +… + (2k – 1)+(2k +1)=k2+(2k +1)

=(k +1)2

Which is P(k +1).  That is, P(k +1)is true wheneverP(k)is true.  Bytheprincipleof mathematicalinduction,Pistrueforalln≥.k.

Example2:.

P(n):      1 +2 +3 +4+..… +n=1/2 n(n+1)

Rn

or          ∑i =1/2 n (n +1)

i=1

ProveP (forn ≥ 1)

solution :

n =1        (i) P(1):         left side =1

Right side =1/2 * 1 * (2) =1

(ii)let P(k)is true; n=k

1 +2 +3 +4+..… +k =1/2 *  k *  (k+1 )

to provethat P(k+1)is true

1 +2 +3 +4+..… +k +(k+1)=1/2 *k * (k+1)+ (k+1)

k (k+1 )+2(k+1 )

= —–—–—–—–—–—–—–— 2

(k+1 )(k+2)

= —–—–—–—–— 2

SoPistrueforalln≥k

=1/2 (k +1)(k +2)

Example3:

Provethe followingproposition (forn ≥ 0):

P(n): 1 +2 +22+23+… +2n=2 n+1−1

solution :

1. P(0):leftside =1

   Right side =21–1=1

2. AssumingP(k)is true; n=k

P(k): 1 +2 +22+23+… +2k=2 k+1−1

We add 2k+1 to both sides ofP(k), obtaining

1 +2 +22+23+… +2k+2 k+1=2 k+1−1+2 k+1

=2(2 k+1)−1 =2 k+2−1

which is P(k +1). That is,P(k +1)is true wheneverP(k)is true. Bytheprincipleof induction, P(n)is true forall n.

Homework:

Provebyinduction:

1) 2 +4 +6 +…….+2n =n (n +1)

2) 1 +4 +7 +…….+ (3n –2)=1/2 n (3n-1)

Relations Binary relation:

Therearemanyrelationsin mathematics :“less than”,“is parallel to“,“is asubset of“,

etc. Theserelations considerthe existenceornonexistenceofacertain connection between pairs ofobjects taken in adefiniteorder.Wedefinearelation simplyin terms ofordered pairs ofobjects.

Productsets:

Considertwo arbitrarysets A and B. Theset of allordered pairs (a,b) wherea∈Aand b∈Bis called theproduct, or cartesianproduct, ofA and B.

A×B ={(a,b):a∈Aand b∈B}

Example:Let A={1,2}and B ={a,b ,c} then

A×B ={(1,a), (1,b),(1,c),(2,a),(2,b),(2,c)}

Also, A×A={(1, 1), (1, 2),(2, 1), (2, 2)}

– Theorderin which thesets are considered is important,so A×B ≠B ×A.

LetAandBbesets. Abinaryrelation, R, from Ato Bis asubset ofA×B.If(x,y)∈R, wesaythat xis R–relatedtoyand denotethis by                                                             xRy

if(x,y)∉R, wewrite      x y    and saythat xis not R–related toy.

ifR is a relation  from Ato A,i.e. R is asubset ofA× A, then wesaythatR is a

relation on A.

Thedomain ofa relationR is theset of all first elements oftheordered pairs which belongto R, and therangeofR is theset ofsecond elements.

Example1:

LetA={1, 2, 3, 4}. Definea relation R on Abywriting(x,y)∈R ifx<y.Then R ={(1, 2), (1, 3),(1, 4), (2, 3),(2, 4), (3, 4)}.

Example2:

let A={1,2,3} and R ={(1,2),(1,3),(3,2)}. Then Ris a relation on Asinceit is a

subset of A×A with respect to this relation: 1R2, 1R3, 3R2            but                            (1,1)∉R&(2,1)∉R

Thedomain ofR is {1,3} and

The rangeofR is {2,3}

Example3:

LetA={1,2,3}.DefinearelationRonAbywriting(x, y)∈R,suchthat a≥b,list the element ofR

aRb↔a≥b,a,b∈A

∴ R={(1,1),(2,1),(2,2),(3,1),(3,2),(3,3)}.

Example4:

A relation on thesetZofintegers is “m divides n.”A common notation forthis relation is to writem|nwhen m divides n. Thus 6|30                                                          but        7 25.

Representation ofrelations:

1. Bylanguage
2. Byordered pairs
3. Byarrow form
4. Bymatrixform

1. Bycoordinates
2. By graphform

Example:

Let A={1,2,3}, therelation R on Asuch that: aRb ↔ a>b;          a,b∈A

1. Bylanguage:

   R={(a,b): a,b∈A and aRb ↔ a>b}

    

2. Byordered pairs

   R ={(2,1),(3,1),(3,2)}

    

3. Byarrowform

    

    

4. Bymatrixform

    

    

    

    

    

5. Bycoordinates

    

6. By graphform

TYPESOF RELATIONS:

Properties ofrelations: Let R bea relation on theset A

1. Reflexive:Risreflexiveif:∀a∈A→aRaor (a,a) ∈R;∀a,b ∈A..ThusR isnot reflexiveifthereexists a∈Asuch that (a,a)∉R.

    

2. Symmetric: aRb →bRa∀a,b∈A. ifwhenever (a, b)∈ Rthen(b, a)∈R. ThusRis not symmetricifthere exists a, b ∈ Asuch that(a, b)∈ Rbut(b, a)∉R.

    

3. Transitive: aRb∧bRc→aRc.thatis,ifwhenever (a, b),(b,c)∈R

   then (a,c)∈ R. Thus Ris not transitiveifthereexist a, b, c∈ Rsuch that (a, b),(b,

   c)∈ Rbut(a, c)∉R.

    

4. Equivalence relation :it is Reflexive&Symmetric&Transitive. That is,Ris an equivalence relation on Sifit has the followingthreeproperties:

   a-For everya∈S, aRa. b-IfaRb, thenbRa.

   c–IfaRband bRc, then aRc.

    

5. Irreflexive:∀a∈A(a,a)∉R
6. AntiSymmetric:ifaRbandbRa→a=b

   therelations≥,≤and⊆areantisymmetric

    

   Example5: Considertherelation ofC ofset inclusion on anycollection ofsets:

   1. A⊂Aforanyset,so ⊂is reflexive
   2. A⊂Bdosenot implyB ⊂A,so ⊂is notsymmetric
   3. IfA⊂BandB⊂C thenA⊂C, so ⊂is transitive
   4. ⊂is reflexive, notsymmetric&transitive, so⊂isnot equivalencerelations
   5. A⊂A,so ⊂is notIrreflexive
   6. If A⊂BandB⊂AthenA=B,so⊂is anti–symmetric

       

      Example6:IfA={1,2,3} and   R={(1,1),(1,2),(2,1),(2,3)}

      Is R equivalence relation ?

1. 2is in Abut (2,2)∉R,so R is not reflexive
2. (2,3) ∈R but (3,2)∉R,so R isnot symmetric
3. (1,2)∈R and (2,3)∈R but (1,3)∉R, soR is nottransitive So R is not Equivalence relation

Example7 :What is theproperties oftherelation=?

1. a=afor anyelement a∈A, so =is reflexive
2. Ifa=b thenb = a, so=is symmetric
3. Ifa=band b =cthen a= c, so =is transitive

4) =is  (reflexive+symmetric+transitive), so =is equivalence

1. a= a, so=is notIrreflexive
2. Ifa=band b =athen a=b, so =is anti–symmetric

Remark:Thepropertiesofbeingsymmetric and being antisymmetricarenot negatives ofeach other.For example, therelation R= {(1, 3), (3, 1),(2, 3)} is neither symmetricnorantisymmetric. On theotherhand,the relation R= {(1, 1), (2, 2)} is both symmetric andantisymmetric.

–ReflexiveClosures

Let Rbearelation on aset A. Then:

R∪{(a,a)|a∈A} isthe reflexive closure ofR.Inother words,reflexive(R) is obtained bysimplyaddingto Rthose elements(a,a)in thediagonal whichdo not

alreadybelongto R.

-SymmetricClosures

R ∪R−1isthe symmetric closure ofR.inother words,symmetric(R) isobtainedby addingto Rall pairs(b, a)whenever(a, b)belongs to R.

EXAMPLE :Considerthe relation R={(1, 1),(1, 3),(2, 4),(3, 1),(3, 3),(4, 3)} on

theset A={1, 2, 3, 4}.Then

reflexive(R)=R∪{(2,2),(4,4)}and

symmetric(R)=R∪{(4,2),(3,4)}

-TransitiveClosure

R*is thetransitive closureofR, where:

R*=R∪R2∪R3∪….∪Rn andR2=R◦R  and  Rn=Rn−1◦R

Theorm: SupposeAis afiniteset with n elements andLet Rbearelationon aset A

with n elements. Then :      transitive(R) =R∪R2∪R3∪….∪Rn

EXAMPLE:Considertherelation R={(1,2),(2,3),(3, 3)}on A={1,2,3}. Then:

R2 =R◦R={(1, 3),(2, 3), (3, 3)} and

R3 =R2◦R={(1, 3),(2,3),(3, 3)} then

transitive(R)={(1, 2),(2, 3),(3, 3),(1, 3)}

Inverse relations:

R–1={(b,a): (a,b)∈R}

Example1 :

Let R bethe followingrelation on A ={1,2,3} R ={(1,2),(1,3),(2,3)}

∴R–1={(2,1),(3,1),(3,2)}

ThematrixforR :

and

MR–1is thetransposeofmatrixR

Composition ofrelations: Let A,B, C besets and let :

R :A →B                             (R⊂A×B)

S : B→C                               (S⊂B×C)

Thereis arelation fromAto C denoted by R°S(compositionofRandS):A→C

R°S={(a,c):∃b∈B forwhich(a,b) ∈R and (b,c) ∈S}

Example: let A ={1,2,3,4}

B={a, b, c, d}

C ={x,y, z}

R ={(1,a),(2,d),(3,a),(3,d),(3,b)}

S ={(b,x),(b,z),(c,y),(d,z)}

FindR°S? Solution :

1. The first waybyarrow form

Thereis anarrow(path)from 2 to d which is followed byan arrowfrom d to z 2Rd      and      dSz  ⇒ 2(R°S)z

and3(R◦S)xand 3(R◦S)z

so R°S= {(3,x),(3,z),(2,z)}

1. Thesecond waybymatrix:

R °S=  MR.MS=

R°S= {(2,z),(3,x),(3,z)}

Theorem 2.1:Let A,B,C and Dbesets. SupposeR is a relation from AtoB, S is a relation fromBto C, and

Tis a relation from C toD. Then (R ◦S)◦T=R◦(S ◦T)

n-ARY RELATIONS

All the relations discussed above werebinaryrelations. Byan n–aryrelation, we mean aset ofordered n–tuples. For anyset S, asubset oftheproduct set Snis called an n-aryrelation on S.In particular, asubset ofS3is called aternaryrelation on S. EXAMPLE

1. Let L bealinein theplane. Then “betweenness”is aternaryrelation Ron the pointsofL; that is, (a, b, c)∈R, ifb lies betweena and con L.

    

2. The equation x2 +y2+z2 =1 determines aternaryrelation T on theset Rof real numbers. That is, atriple(x, y, z)belongs to T if(x, y, z)satisfies theequation, which means(x,y, z)is the coordinates ofapoint in R3 on thesphereS with radius 1 and centerat theorigin O=(0, 0, 0).

Homework:

1. Considerthe followingrelations on theset A={1, 2, 3}:

R={(1, 1),(1, 2),(1, 3),(3, 3)},

S ={(1, 1)(1, 2),(2,1)(2, 2),(3, 3)},

T ={(1, 1),(1, 2),(2, 2),(2, 3)}

∅=emptyrelation

A×A=universal relation

Determine whetherornot each oftheaboverelations on Ais:

1. reflexive; (b)symmetric; (c)transitive; (d)antisymmetric.

    

1. fortherelation R={(a, a),(a, b),(b,c),(c, c)}on theset A={a, b, c}.

Find: (a)reflexive(R);(b)symmetric(R);(c)transitive(R).

Function:

Function is an importantclass of relation.

Definition:

Let A,Bbe two nonemptysets,afunction F: A→Bis a rule whichassociates with each

element ofAauniqueelement in B.

Theset Ais called thedomain ofthefunction, and theset Bis called therangeofthe function.

Example1:

Considerthefunctionf(x)=x3,i.e.,fassignstoeachrealnumberitscube.Thentheimage of2is8,andso

we maywritef (2)=8.

Example2 :

considerthe followingrelation on thesetA={1,2,3} F={(1,3),(2,3),(3,1)}

Fis a function

—–—–—–—–—–—–—–—–––—–—–—–—–—–—–—–—–––—–—–— G={1,2},(3,1)}

Gis not a function fromAto A

—–—–—–—–—–—–—–—–––—–—–—–—–—–—–—–— H={(1,3),(2,1),(1,2),(3,1)}

His not a function

—–—–—–—–—–—–—–—–––—–—–—–—–—–—–—–—–––—–—–—–—–—–—–—–—–––—–—–—–—–—

One-to–one ,onto andinvertiblefunctions :

1. One–to–one: afunctionF:A→Bis saidto be one–to–oneifdifferentelements in

   thedomain (A)havedistinct images. Or If  F(a)=F(a’)           ⇒                           a=a’

2. Onto : F:A→Bis said tobe anonto function if each element ofBistheimageof

   some element of A.

   ∀b∈B       ∃      a∈A:F(a)=b

3. Invertible (One-to–onecorrespondence)

F:A→Bisinvertible if itsinverse relationf –1isa functionF:B→A

F:A→Bis invertible ifandonlyifFisboth one-to–one and onto

F–1:{(b,a)∀(a,b)∈F}

onetoonebutnotonto(3∈Bbutitisnottheimageunderf1)

bothonetoone&onto