More Relations
More Relations
Review of Relation composition and inverses:
If P is a relation on SxT and R is a relation on TxW, then RoP is the relation
obtained by following P from S to T and then following R to W
RoP = {<s,w> | ∃
t with <s,t>
∈
P and <t,w>
∈
R }
Inverse relation: if R is a relation on SxT, the the
inverse
of R is a relation on
TxS, written R
-1
= {<t,s> | <s,t> ∈
R}
IP = IsParentOf = {<p,c> | p is the (biological) parent of c}(from exercises 8.26-8.31)
What is IP
-1
?
What is IP o IP = IP
2
?
What is IP
-1
o IP?
What is IP o IP
-1
?
What is IP o IP o IP
-1
o IP
-1
?
What is IP o IP
-1
o IP o IP
-1
?
Properties of Relations
•
Reflexive
•
A relation R on a set S is reflexive if
∀
s
∈
S, <s,s>
∈
R.
•
That is, every element of S is related to itself
•
Example: Relation |, divides, on Z: every integer evenly divides itself
•
Example: <= on Z:
∀
n
∈
Z, n <= n
•
Example: For any relation R on S, when is R
-1
o R is reflexive?
•
Example: < on Z is not reflexive:
∀
n
∈
Z, not true that n < n
•
If R on a finite set is reflexive, then in the graphical representation every node
has a loop – an arrow to itself.
•
Irreflexive
•
A relation R on a set S is irreflexive if
∀
s
∈
S, not(<s,s>
∈
R)
•
No element of S is related to itself
•
Example: < on Z is irreflexive:
∀
n
∈
Z, not true that n < n
•
Example: IsParentOf is irreflexive: a person cannot be his/her own parent
•
Example: SquareOf on Z x Z = {<n,n2
> for any n
∈
Z} is neither reflexive nor irreflexive
•
<1,1>
∈
SquareOf, but <9,9> not
∈
SquareOf
•
If R on a finite set is irreflexive, then in the graphical representation there are no loops.
•
Symmetric
•
A relation R on S is symmetric if for any s, t
∈
S: <s,t>
∈
R
<t,s>
∈
R.
•
Example: IsSiblingOf on People is symmetric: If p is a sibling of q, then q is a sibling of p.
•
Example: The relation x = y mod 7 on Z
>=0
is symmetric. If x = y mod 7 , then y = x mod 7
•
This holds on any set of integers
•
Antisymmetric
•
A relation R on S is antisymmetric if for any s, t
∈
S: <s,t>,
<t,s>
∈
R
s = t
•
Example: I (divides) on Z
+
: if n|m and m|n, then n = m.
•
Example: <= on Z: if n <= m and m <= n, then n = m
•
Asymmetric
•
A relation R on S is asymmetric if for any s, t,
∈
S: <s,t>
∈
R
<t,s> not
∈
R.
•
Example: < on Z is asymmetric: If n < m then not(m < n).
•
Example: IsParentOf (IP): if p IP c, then not c IP p.
•
Example: SquareOf on Z x Z = {<n,n2
> for any n
∈
Z} is not symmetric
since <2,4>
∈
SquareOf, but <4,2> not
∈
SquareOf.
It is not asymmetric since <1,1>
∈
SquareOf.
It is
antisymmetric
since if x = x
2
, then x = x, namely 0 = 0
2
and 1 = 1
2
.
Graphic representations
1
2
3
Which of these are symmetric, asymmetric, antisymmetric?
•
A relation can be none of the three: not symmetric, not antisymmetric,
not asymmetric.
•
Consider {<a,a>, <a,b>, <b,a>, <b,c>}•
Not symmetric: <b,c> but no <c,b>
•
Not asymmetric: <a,b> and <b,a>
•
Not antisymmetric: <a,b> and <b,a>, but a != b
Theorem 8.1 (Symmetry in terms of inverses)
Let
R
⊆
A × A
be a relation and let R
−1
be its inverse. Then
:
R is symmetric if and only if
R ∩ R
−1
= R = R
−1
.
R is antisymmetric if and only if
R ∩ R
−1
⊆ {〈a, a
〉
: a
∈
A
}.
R is asymmetric if and only if
R ∩ R
−1
=
Ø.
•
Transitivity
•
A relation R on S is transitive if for any s, t, w
∈
S: <s,t> and <t,w>
∈
R
<s,w>
∈
R
•
Example: R = IsAncestorOf on S = people. If p1 R p2 and p2 R p3, then p1 R p3.
•
Example: >= on Z or > on Z
•
Example: | (divides) on Z
+
: if a|b and b|c, then a|c
•
Example: SquareOf on Z
+
x Z
+
= {<n,n2
> for any n
∈
Z} is not transitive
•
<2,4> and <4,16>
∈
SquareOf, but <2,16> not
∈
SquareOf.
Closures
•
A closure of a relation, R on a set A, for a property is the
smallest
relation, C, such that
R
⊆
C
and
the property holds for C
.
•
Reflexive closure of R, Ref(R), is the smallest relation such that
R
⊆
Ref(R) and Ref(R) is reflexive.
•
Symmetric closure of R, Sym(R), is the smallest relation such that
R
⊆
Sym(R) and Sym(R) is symmetric.
•
Transitive closure of R, T(R), is the smallest relation such that
R
⊆
T(R) and T(R) is transitive.
Graphic representation of closures
Example 8.27 (Closures of divides)
Recall the “divides” relation | = {〈n
,
m
〉 :
m
divides
n evenly
}.
Because
R
is both reflexive and transitive, the reflexive closure and transitive closure
of
R
are both just
R
itself.
The symmetric closure of
R
is the set of pairs 〈
n
,
m
〉 where one of
n
and
m
is a
divisor of the other (in either order): {〈n
,
m
〉 :
n
|
m
or
m
|
n
}.
Example 8.28 (Closures of >)
Recall the “greater than” relation {〈n
,
m
〉 :
n
>
m
}.
The reflexive closure of > is ≥ —that is, the set {〈n
,
m
〉 :
n
≥
m
}.
The symmetric closure of > is the relation ≠ —that is,
the set {〈n
,
m
〉 :
n
>
m
or
m
>
n
} = {〈n
,
m
〉 :
n
≠
m
}.
The relation > is already transitive, so the transitive closure of > is > itself.
Computing Closures
•
Reflexive closure of R on A
•
R
∪
{<s,s> for all s ∈
S}
•
Symmetric Closure
•
R
∪ R
-1
•
Transitive Closure
•
R
∪ R
2
∪ R
-3
∪ R
4
∪… ∪ R
n
, where n = |A|
•
Warshall’s algorithm
What are the closures of the successor relation on R = {<n,n+1> | n ∈
Z }
Reflexive closure?
Symmetric closure?
Transitive closure?
Reflexive-transitive closure?
Reflexive-symmetric-transitive closure>
Concepts of relation composition, inverses, reflexive, irreflexive, symmetric, and antisymmetric relations through examples and definitions. Discover how these properties apply in different scenarios and learn about the graphical representations of reflexive and irreflexive relations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Review of Relation composition and inverses: If P is a relation on SxT and R is a relation on TxW, then RoP is the relation obtained by following P from S to T and then following R to W RoP = {<s,w> | t with <s,t> P and <t,w> R } Inverse relation: if R is a relation on SxT, the the inverse of R is a relation on TxS, written R-1= {<t,s> | <s,t> R}
IP = IsParentOf = {<p,c> | p is the (biological) parent of c} (from exercises 8.26-8.31) What is IP-1? What is IP o IP = IP2? What is IP-1o IP? What is IP o IP-1? What is IP o IP o IP-1o IP-1? What is IP o IP-1o IP o IP-1?
Properties of Relations Reflexive A relation R on a set S is reflexive if s S, <s,s> R. That is, every element of S is related to itself Example: Relation |, divides, on Z: every integer evenly divides itself Example: <= on Z: n Z, n <= n Example: For any relation R on S, when is R-1o R is reflexive? Example: < on Z is not reflexive: n Z, not true that n < n If R on a finite set is reflexive, then in the graphical representation every node has a loop an arrow to itself.
Irreflexive A relation R on a set S is irreflexive if s S, not(<s,s> R) No element of S is related to itself Example: < on Z is irreflexive: n Z, not true that n < n Example: IsParentOf is irreflexive: a person cannot be his/her own parent Example: SquareOf on Z x Z = {<n,n2> for any n Z} is neither reflexive nor irreflexive <1,1> SquareOf, but <9,9> not SquareOf If R on a finite set is irreflexive, then in the graphical representation there are no loops.
Symmetric A relation R on S is symmetric if for any s, t S: <s,t> R <t,s> R. Example: IsSiblingOf on People is symmetric: If p is a sibling of q, then q is a sibling of p. Example: The relation x = y mod 7 on Z>=0 is symmetric. If x = y mod 7 , then y = x mod 7 This holds on any set of integers Antisymmetric A relation R on S is antisymmetric if for any s, t S: <s,t>, <t,s> R s = t Example: I (divides) on Z+: if n|m and m|n, then n = m. Example: <= on Z: if n <= m and m <= n, then n = m
Asymmetric A relation R on S is asymmetric if for any s, t, S: <s,t> R <t,s> not R. Example: < on Z is asymmetric: If n < m then not(m < n). Example: IsParentOf (IP): if p IP c, then not c IP p. Example: SquareOf on Z x Z = {<n,n2> for any n Z} is not symmetric since <2,4> SquareOf, but <4,2> not SquareOf. It is not asymmetric since <1,1> SquareOf. It is antisymmetric since if x = x2, then x = x, namely 0 = 02and 1 = 12.
Graphic representations 2 1 3 Which of these are symmetric, asymmetric, antisymmetric?
A relation can be none of the three: not symmetric, not antisymmetric, not asymmetric. Consider {<a,a>, <a,b>, <b,a>, <b,c>} Not symmetric: <b,c> but no <c,b> Not asymmetric: <a,b> and <b,a> Not antisymmetric: <a,b> and <b,a>, but a != b
Theorem 8.1 (Symmetry in terms of inverses) Let R A A be a relation and let R 1be its inverse. Then: R is symmetric if and only if R R 1= R = R 1. R is antisymmetric if and only if R R 1 { a, a : a A}. R is asymmetric if and only if R R 1= .
Transitivity A relation R on S is transitive if for any s, t, w S: <s,t> and <t,w> R <s,w> R Example: R = IsAncestorOf on S = people. If p1 R p2 and p2 R p3, then p1 R p3. Example: >= on Z or > on Z Example: | (divides) on Z+: if a|b and b|c, then a|c Example: SquareOf on Z+ x Z+ = {<n,n2> for any n Z} is not transitive <2,4> and <4,16> SquareOf, but <2,16> not SquareOf.
Closures A closure of a relation, R on a set A, for a property is the smallest relation, C, such that R C and the property holds for C. Reflexive closure of R, Ref(R), is the smallest relation such that R Ref(R) and Ref(R) is reflexive. Symmetric closure of R, Sym(R), is the smallest relation such that R Sym(R) and Sym(R) is symmetric. Transitive closure of R, T(R), is the smallest relation such that R T(R) and T(R) is transitive.
Graphic representation of closures Reflexive closure R Symmetric closure R R 1 2 1 2 1 2 5 3 5 3 5 3 4 4 4 Transitive closure R 1 2 5 3 4
Example 8.27 (Closures of divides) Recall the divides relation | = { n, m : m divides n evenly}. Because R is both reflexive and transitive, the reflexive closure and transitive closure of R are both just R itself. The symmetric closure of R is the set of pairs n, m where one of n and m is a divisor of the other (in either order): { n, m : n | m or m | n}. Example 8.28 (Closures of >) Recall the greater than relation { n, m : n > m}. The reflexive closure of > is that is, the set { n, m : n m}. The symmetric closure of > is the relation that is, the set { n, m : n > m or m > n} = { n, m : n m}. The relation > is already transitive, so the transitive closure of > is > itself.
Computing Closures Reflexive closure of R on A R {<s,s> for all s S} Symmetric Closure R R-1 Transitive Closure R R2 R-3 R4 Rn , where n = |A| Warshall s algorithm
What are the closures of the successor relation on R = {<n,n+1> | n Z } Reflexive closure? Symmetric closure? Transitive closure? Reflexive-transitive closure? Reflexive-symmetric-transitive closure>
