Sequences / Tuples
→
Sequence : list of things in a certain order .
To from sets brackets
→
distinguish sequences we use
instead of (
,
braces E) '
instead of 471 .
→ Order matters
→
repeated occurrences do matter .
→ also called Tuples when
they are finite
sequence of
K
→
length is a k -
tuple
→ 2-
tuple also called ordered
pairs .
Cartesian product of two sets
→ A ✗ B- -
{ Cny ) / n C- A and
y C-
B }
A ✗ B has ordered A and B
→
pairs from
e. g
A =
{ 1,2 } B =
{ a ,b, c
} G-
{ 0 ☐
, }
A ✗ BXC =
{ ( 1
,
a
,
☐
1,1 ,
a
,☐ ) , (2%0) ,
12,9 ☐)
,
(1) b) b) ( ,
1
,
b , ☐) ( 2 b , G) 12
, , ,
b,☐) ( 1,48,
, ,
(1) C ☐) , (2) C) D)
,
, (2) C , D) {
Binary Relations
sets A and B relation from A to
→ For
,
a
binary B
is subset R of cartesian product A ✗ B
any
( essentially a set consisting of some ordered pairs)
→ a Rb denotes ( a. b) ER and say that
related to b. else (a) b)
a is R -
4- R is written
as a ☒ b.
[ can also do R ( as b) and 7 Rca b)J ,
Relations on a set
→ a relation from set A b- A itself is called a relation on
A
→
essentially a relation on A is a subset of A ✗ A .
e-
9
< =
{ Coe, ) C-
y 2- ✗ z / n is smaller than y }
C- 1
,
0 ) C- <
(5) 2) ¢ <
Representing relations
→ e.
g
A = ( 1
,
2,3 , 4)
Relation of A =
9 ( 1,1 ) (127,1133%4) 131112,21
, ,
,
(2) 4), 13,3) }
can be represented as
f. •?
directedgraph.ly#.P
also relations using
→
can
represent 0-1 matrix
I 2 3 4
does not
%!%%a%?µ!!
" are
3
4
µ ,
00
00
I
000
↓ I
i
of matter but . row and column must
Properties of relations
→
Relation R on set A is a reflexive if (a) a) ER for
ever# a c- A ( one reflexive
non
in reflexive)
is
enough 6- make it
.
R
e. g -
{ ( 1,1 ) , (1) 2) , ( 1,3) (2) 2) (3)
, ,
(3) 3) }
Ori
{ 1, 2,3 }
→ lrrefkaive ( opposite of reflexive) Relation Ron : set A
must not have ( a a) ER for every element
,
a ER .
all elements a. b EA
→ A relation
R is
symmetric if for , D-
(a) b) C- R whenever (b) a) ER .
e-
g Re
{ ( 1,1 ) , (2
, 2) (3) 3) , { is
symetréc .
9
→
antisymmetric can also be antisymmetric
(opposite of symmetric symmetric is enough 6- make anti
lone non
←9
R -41,3 ) ( 2,3) , ( 1,27 }
-
,
symmetric )
Transitivity
→
if both la b) ,
ER and ( b c)
,
ER then
( a. c) ER
→ In a directed graph R is transitive if every
,
two step journey can be done in one step
e. g
k z → w
Not transitive
g
- -
x z → w Not transitive
y
- -
[Ézw
-✓
Transitive
2-
every
as
step journey is
covered .
Transitive closure
→
let R be a relation on set A
The transitive closure of R is the smallest transitive
relation on A containing R
it is denoted
→
by R* then R=R*)
( If R is already transitive
essentially copy of R but with the transitive
→
a
elements
→
defining R*
recursively
*
Basis R ≤ R
Recursive if fa , b) ER
*
and ( b , c) c- R* then
Ca , c) C- R*
e.g
*
R R
N# 2-
: → w :
- -
- -
-
- -
nE ? -7¥
→ what order will we add the transitive elements
Warshall 's
Algorithm
Algorithm A finite sequence of precise step by step
→
:
instructions
the matrix of transitive closure
→ Warshall's Algorithm computes
:
R* of R
→ Given Relation R on
a a set A with n elements
we
begin with an nxn matrix Mo
→
There are n rounds where in
every
round we
change the
matrix some rules
using
↳ M Me Mn
Mo ,
. _ .
.
→
Mn is the transitive closure relation
→
Rule No .
1 : Never change the Is
Rule No the 0s to Is if the values
change
→
. 2 :
adjacent to the 0 in the chosen column and now
are 1s .
i
; k
TE☆ unit I
'
-1
k I
Mk -1 Mk
relation
e.
g let R be a on set A
{ a. b. Sdl
R =/ ( a
,
d) , lb a) ( , ,
b
, c) / ↳ a)
, ,
Cec d) Cd c) /
, , ,
4 elements so ↳ rounds and 4×4 matrix
=\ : :|
•
I 0 I 0
Round I
④:- / :: :)
°
I 0 0 I
- mi 1 0 1 4
,
00 I O
O O I 0
→
skip to round 4
mil : : :
I
I 0
0 I
I
1
:|
1
Equivalence Relation
→ A relation R on a set A is an equivalence relation
if it is
1) Reflexive
2)
and
Symmetric
3) Transitive
→
e.g { & , g) C- 2- ✗ Z
/ x -
y is divisible
by 41
Partial Order
→ if relation R on set A is
D Reflexive
2) anti
symmetric
3) Transitive
order
e. g
≤ is a
partial
Hasse Diagram
→
Only for partial orders
→
since we know
they are reflexive ,
we can assume it and not
draw loops
since know
they transitive we can
ignore making
→
we are
,
arrows for shorter steps .
→ since we it is /all
antisymmetricheads arrows
go one way) ,
we can remove arrow and stack them
e.
g { 1 , 2,3 5,11 , 10,15 ,
,
25
}
ITALA
;i÷H¥É:& -
↑*••
÷¥%• 1
Linear Orders
→ Partial order where a.
b EA and either Ca b)
,
c- R or
(b) a) C- R
it called this the Hasse will
→ is as
diagram just
be a
straight line
Reflexive Not Reflexive
→ All points loop → Notallpoinbbop
lnrefkaive Not irrefbxive
→
Nopoinbbop →
sanepointsloop
Symmetric Not
Symmetric
→ allpointsiomein →
Notallpointscomeinpairs
pairs
Antisymmetric Not
Antisymmetric
→
Nopoinblome →
somepointscomeinpairs
in pairs
Transitive Not Transitive
There isasstep journey
→
every
2-
step path →
lhateannotbedanein
canbedoneintstep 1- step .
