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}
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
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:
- Bylist its members separated bycommas andcontained in braces{ }, (ifit is possible), for example,A={a,e,i,o,u}
- Bystatethosepropertieswhich characterizethe elements in theset, for example,A={x:xis aletterin the English alphabet, xis avowel}
- 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}.
A⊂B : {∀x∈A |
⇒ |
x∈B |
A⊄B : {∃x∈A |
but |
x∉B |
∀:Forall ﻞﻜﻟ
∃:Thereexists ﻞﻗﻻﺍ ﻰﻠﻋ ﺪﺟﻮﻳ
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
Where Q={a/b:a,b∈Z,b≠0}
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=∅
- THE DIFFERENCE:
Thedifferenceoftwo sets ABor A–Bis those elements which belongtoAbut which do not belongtoB.
AB={x:x∈A, x∉B}
- 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}
- 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
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
- 10
2. 23=8
3. {{},{0},{1},{2},{0,1},{0,1,2},{0,2},{1,2}}
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;
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
× |
A |
||
0 |
1 |
||
B |
2 |
(0,2) |
(1,2) |
3 |
(0,3) |
(1,3) |
Problemset
Answerthefollowingquestions:
1. {2,3,4}×{1,3,4}
2.{0,1}×{0,1}
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)}
- 3.3
- 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
- is not apartition ofS since7 in S does not belongto anyofthesubsets.
- is not apartition ofS since{1,3,5} and {5,7,9} arenot disjoint.
- 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:
- List Ahas 30 names and 20 areon list B; hence30 −20 =10 namesareonlyon list A.
- Similarly, 35 −20=15 areonlyon list B.
- 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:
- Allthreelanguages(F∩G∩R)
- 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
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.
- P(1)is true
- 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 :
- P(0):leftside =1
Right side =21–1=1
- 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:
- Bylanguage
- Byordered pairs
- Byarrow form
- Bymatrixform
- Bycoordinates
- By graphform
Example:
Let A={1,2,3}, therelation R on Asuch that: aRb ↔ a>b; a,b∈A
- Bylanguage:
R={(a,b): a,b∈A and aRb ↔ a>b}
- Byordered pairs
R ={(2,1),(3,1),(3,2)}
- Byarrowform
- Bymatrixform
- Bycoordinates
- By graphform
TYPESOF RELATIONS:
Properties ofrelations: Let R bea relation on theset A
- Reflexive:Risreflexiveif:∀a∈A→aRaor (a,a) ∈R;∀a,b ∈A..ThusR isnot reflexiveifthereexists a∈Asuch that (a,a)∉R.
- 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.
- 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.
- 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.
- Irreflexive:∀a∈A(a,a)∉R
- AntiSymmetric:ifaRbandbRa→a=b
therelations≥,≤and⊆areantisymmetric
Example5: Considertherelation ofC ofset inclusion on anycollection ofsets:
- A⊂Aforanyset,so ⊂is reflexive
- A⊂Bdosenot implyB ⊂A,so ⊂is notsymmetric
- IfA⊂BandB⊂C thenA⊂C, so ⊂is transitive
- ⊂is reflexive, notsymmetric&transitive, so⊂isnot equivalencerelations
- A⊂A,so ⊂is notIrreflexive
- 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 ?
- 2is in Abut (2,2)∉R,so R is not reflexive
- (2,3) ∈R but (3,2)∉R,so R isnot symmetric
- (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=?
- a=afor anyelement a∈A, so =is reflexive
- Ifa=b thenb = a, so=is symmetric
- Ifa=band b =cthen a= c, so =is transitive
4) =is (reflexive+symmetric+transitive), so =is equivalence
- a= a, so=is notIrreflexive
- 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 :
-
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)}
-
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
- Let L bealinein theplane. Then “betweenness”is aternaryrelation Ron the pointsofL; that is, (a, b, c)∈R, ifb lies betweena and con L.
- 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:
- 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:
- reflexive; (b)symmetric; (c)transitive; (d)antisymmetric.
- 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 :
- One–to–one: afunctionF:A→Bis saidto be one–to–oneifdifferentelements in
thedomain (A)havedistinct images. Or If F(a)=F(a’) ⇒ a=a’
- Onto : F:A→Bis said tobe anonto function if each element ofBistheimageof
some element of A.
∀b∈B ∃ a∈A:F(a)=b
- Invertible (One-to–onecorrespondence)
F:A→Bisinvertible if itsinverse relationf –1isa functionF:B→A
F:A→Bis invertible ifandonlyifFisboth one-to–one and onto
onetoonebutnotonto(3∈Bbutitisnottheimageunderf1)
bothonetoone&onto
(oronetoonecorrespondencebetweenAandB)
—–—–––—–––—–––—–––—–—–––—–––—–––—–––—–—–––—–––—–––—–––—–—
notonetoone&onto
notonetoone¬onto
—–—–––—–––—–––—–––—–—–––—–––—–––—–––—–—–––—–––—–––—–––—–—–––—
Graphofa function:
Byareal polynomial function, wemeana function f: R→ Rofthe form
wheretheaiarereal numbers. SinceRis an infiniteset, it would beimpossibleto plot each point ofthegraph.However, thegraph ofsuch a function can beapproximated by first plottingsomeofits points and then drawing asmooth curvethough thesepoints. The tablepoints areusuallyobtained from atable wherevarious values are assigned to xand the correspondingvalueof f(x) computed.
Example1 : let f:R→R and f(x)=x3, find f(x) f(3) =33=27
f(-2) =(-2)3= –8
Example2: let f: R→R and f (x)=x2 −2x– 3,, find f(x)
Geometrical CharacterizationofOne-to–OneandOnto Functions
Forthe functions oftheform f: R →R. thegraphs ofsuch functions maybeplotted in
theCartesian planeand functions maybeidentified with theirgraphs, so the concepts of beingone-to–oneand onto havesomegeometricalmeaning:
- f:R →R is said to beone-to–oneifthere areno 2 distinct pairs (a1,b)and (a2,b)in the
graph one-to–oneorifeach horizontal lineintersects thegraph offin at most onepoint. - f:R →R is an onto function if each horizontal lineintersects thegraphoffat oneor
- iffis both one-to–one and onto, i.e. invertible,then each horizontal line will intersect thegraph offatexactlyonepoint.
—–—–—–—–—–—–—–—–––—–—–—–—–—–—–—–—–––—–—–—–—–—–—–—–—–––—–—–—–—–—
f(x) NOT (ONE–TO–ONE)& NOT (ONTO)
Compositionoffunction:
Letf:A→B andg:B→C,tofind the composition functiongοf:A→C
(gοf)(a)=g(f(a))=g(y)=t
(gοf)(b)=g(f(b))=g(x)=s
(gοf)(c)=g(f(c))=g(y)=t
SEQUENCES OFSETS
Asequenceis a function from theset N={1, 2, 3,. . .} ofpositiveintegersinto aset A.
Thenotation anis used to denotetheimageoftheintegern. Thus asequenceis usually denoted by
a1, a2, a3, . . .
A finitesequenceoveraset Ais a function from {1, 2, . . . , m} into A,Such a finite sequenceiscalled alist.
EXAMPLE
- The followingaretwo familiarsequences:
Notethat the first sequencebegins with n =1 and thesecond sequencebegins with n =0.
- Thesequence1,−1, 1,−1, . . . maybedefined byan =(−1)n
, wherethesequencebegins with n =0.
Summation Symbol, Sums
Hereweintroduce thesummationsymbol∑(theGreeklettersigma).Considera
sequencea1,a2, a3, . . ..Then wedefinethe following:
n
∑aj = a1+ a2+・・・+an
J=1
EXAMPLE :
5
∑j2= 22+ 32+ 42+ 52= 4+9+ 16+ 25= 54
j=2
n
∑j= 1+ 2+・・+n =n(n+ 1)/2, forexample, 1 +2+・・+50= (50 x51)/2=1275
j=1
RECURSIVELY DEFINEDFUNCTIONS
A function is said to berecursivelydefined ifthefunction definition refers to itself.In
order forthedefinition not to be circular, the function definition must havethe following two properties:
- Theremust be certainarguments, called basevalues, for which thefunction does not referto itself.
- Each timethefunction does referto itself, theargument ofthe function must be closer to abasevalue.
A recursive function with thesetwo properties is said to bewell–defined.
FactorialFunction
Theproduct ofthepositiveintegers from 1 to n, inclusive, is called “n factorial” and is
usuallydenoted byn!. That is,
n!=n(n−1)(n−2)・・・3 ・2 ・1
where0!=1, so that thefunction is defined forall nonnegativeintegers. Thus: 0!=1, 1!=1,
2!=2.1 =2, 3!=3.2.1 =6,
4!=4.3.2.1 =24 5!=5.4.3.2.1=120
6!=6.5.4.3.2.1 =720
This is true for everypositiveintegern; that is,
n!=n・(n−1)!
Accordingly, thefactorial function mayalso bedefined as follows:
Definition ofFactorialFunction:
- Ifn =0, then n!=1.
- Ifn>0, then n!=n ・(n −1)!
Thedefinition ofn!is recursive, sinceit refers to itself when it uses(n −1)!. However:
- Thevalueofn!is explicitlygiven when n=0 (thus 0 is abasevalue).
- Thevalueofn!forarbitraryn is defined in terms ofasmallervalueofn which is closerto thebasevalue0.
Accordingly, thedefinition is not circular, or, in other words, the function is well–defined.
EXAMPLE :the4!Canbe calculated in 9 stepsusingtherecursivedefinition .
Fibonacci Sequence
TheFibonacci sequence(usuallydenoted byF0,F1, F2, . . .)is as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .
That is, F0 =0 andF1 =1 and each succeedingterm is thesum ofthetwo preceding terms. Forexample, thenext two terms ofthesequenceare
34 +55 =89 and 55 +89 =144
Fibonacci Sequence canbedefined:
- Ifn =0, orn=1, thenFn =n.
- Ifn>1, then Fn=Fn-2+Fn–1.
Where: Thebasevaluesare0 and 1,and thevalueofFn is defined in terms ofsmaller values ofn whicharecloserto thebasevalues.
Accordingly, this function is well–defined.
Logicandpropositional calculus
Aproposition (orstatement)is adeclarativestatement which is trueorfalse, but not both.
Example:the followingsixsentences:
- Ice floats in water.
- Chinais in Europe. (3)2 +2 =4
(4)2 +2 =5
- Whereareyougoing?
- Doyourhomework.
The first fourarepropositions, thelast two arenot. Also, (1) and (3) aretrue, but (2) and(4)are false.
CompoundPropositions
It is theproposition thatcomposed ofsubpropositions and various connectives.
Primitiveproposition istheproposition that cannot bebroken down into simplerpropositions. For example, the abovepropositions areprimitivepropositions, while:
“Roses arered and violets areblue.”and
“John is smart orhestudies everynight.”,Arecompound.
BASICLOGICAL OPERATIONS
1-Conjunction, p ^q
2-Disjunction, p vq
3-Negation, ¬p
EXAMPLE:Considerthefollowingfourstatements:
- Icefloats in waterand 2 +2 =4.
- Icefloats in waterand 2 +2 =5.
- Chinais in Europeand 2 +2 =4.
- Chinais in Europeand 2 +2 =5.
Onlythefirst statement is true. Each oftheothersis falsesince at least oneofits substatements is false.
EXAMPLE:Considerthefollowingfourstatements:
- Icefloats in wateror2 +2 =4.
- Icefloats in wateror2 +2 =5.
- Chinais in Europeor2 +2 =4.
- Chinais in Europeor2 +2 =5.
Onlythelast statement (iv)is false. Each oftheothers is truesinceat leastoneofits sub- statements is true.
EXAMPLE:Considerthefollowingsix statements:
(a1)Ice floats in water. (a2)It is falsethat ice floats in water. (a3)Icedoes not float in water. (b1)2 +2 =5 (b2)It is falsethat 2+2=5. (b3)2 +2≠5
Then (a2) and(a3)areeach thenegation of(a1); and (b2) and (b3) are eachthenegation of (b1). Since (a1)is true, (a2) and (a3) are false;and since (b1)is false,(b2)and (b3) aretrue.
PROPOSITIONS ANDTRUTH TABLES
Thetruth table forthe compoundproposition ¬(p∧¬q)is:
TAUTOLOGIES AND CONTRADICTIONS
Somepropositions P(p,q, . . .) contain onlyTin thelast column oftheirtruth tables or, in other
words, theyaretrueforanytruth values oftheirvariables. Such propositions arecalled tautologies. Analogously, aproposition P(p, q, . . .)is called acontradictionifit contains onlyF in thelast column ofits truth tableor, in other words, ifit is false for anytruth values ofits variables.For example, theproposition “p ornot p,”that is, p ∨¬p, is atautology, and the proposition “p and not p,”that is, p∧¬p, is a contradiction.
Notethat thenegation ofatautologyis acontradiction sinceit is always false, and thenegation ofa contradiction is atautologysinceit is always true.
LOGICAL EQUIVALENCE
Two propositions P(p, q, . . .) and Q(p, q, . . .) aresaid to belogicallyequivalent, or equal, denoted byP(p, q, . . .)≡Q(p, q, . . .)iftheyhaveidentical truth tables.
for example, thetruth tables of¬(p ∧q) and ¬p∨¬q, both truth tables arethesame, that is,
both propositions are falsein the first case and truein theotherthree cases.Accordingly, we can
write: ¬(p ∧q)≡¬p ∨¬q
ALGEBRAOF PROPOSITIONS
CONDITIONAL ANDBICONDITIONAL STATEMENTS
Manystatements, particularlyin mathematics, areofthe form “Ifp then q.”Such statements are called conditional statements and aredenoted by: p →q
The conditional p →q is frequentlyread “p implies q”or “p onlyifq.”
- Theconditional p →q is falseonlywhen thefirst part p is true and thesecond part q is false. Accordingly, when p is false, the conditional p →q is true regardless ofthetruth valueofq.
- Thebiconditionalp↔q istrue whenever pand qhavethe sametruthvaluesand false otherwise.
Notethat thetruth tableofp →q and ¬p ∨q and areidentical, that is, theyarebothfalseonly
in thesecond case. Accordingly, p →q is logicallyequivalent to ¬p ∨q; that is, p →q ≡¬p ∨q