Chapter 9 Relations¶

9.1 Relations and Their Properties & 9.2 n-ary Relations¶

binary relation from $A$ to $B$ is a subset of $A \times B$
$R \subseteq A \times B$
$R=\{(a,b)|a\in A,b\in B,aRb\}$

The relationship between function and relation

Function is a special relation
Relations are a generalization of graphs of function.

Counting problem

How many of relation on a set $A$ is a relation from $A$ to $A$?

Answer

$2^{|A|^2}$

Presenting relations¶

list its all ordered pairs
using a set build notation/specification by predicates
2D table
Connection matrix/zero-one matrix
Directed graph/Digraph

properties of relations¶

reflexive(自反): $\forall x(x\in A\to(x,x)\in R)$
irreflexive(反自反): $\forall x(x\in A\to(x,x)\notin R)$
symmetric(对称): $\forall x\forall y((x,y)\in R\to(y,x)\in R)$
antisymmetric(反对称): $\forall x\forall y((x,y)\in R\land(y,x)\in R\to x=y)$
asymmetric(非对称): $\forall x \forall y ((x, y) \in R \rightarrow (y, x) \notin R)$
transitive(传递): $\forall x\forall y\forall z((x,y)\in R\wedge(y,z)\in R\to(x,z)\in R)$

	Connection matrix	digraph
reflexive $2^{n^2 - n}$	All elements on the main diagonal must be 1s.	There is a loop at every vertex of the directed graph-> each vertex has a loop to itself
irreflexive $2^{n^2 - n}$	All elements on the main diagonal must be 0s.	No vertex has a loop to itself
symmetric $2^\frac{n(n+1)}{2}$	The symmetric positions are both 0 or 1	If there is an arc(x, y) there must be an arc(y, x) -> both bidirectional edge
antisymmetric $2^n \cdot 3^\frac{n^2-n}{2}$	Symmetric positions cannot both be 1 (they can both be 0)	If there is an arc(x, y) there must be no arc(y, x) -> no bidirectional edge
asymmetric $3^\frac{n^2-n}{2}$	antisymmetric + irreflexive	no bidirectional edge and loop to itself
transitive	$\overline{\left(m_{ij}\wedge m_{jk}\right)}\vee m_{ik}=1$	If there is an arc from x to y and one from y to z then there must be one from x to z

No general formula that counts the number of transitive relations on a finite set is known

inverse relation: $R^{-1}=\{ (b,a)\mid(a,b)\in R \}$
complementary relation: $\overline{R}=\{ (a,b)\mid(a,b)\notin R \}$

When check the property transitive, we can ignore arc(x, x) or loops to itself

reflexive and irreflexive are not opposites
- a relation can be neither reflexive and irreflexive
- empty relation is reflexive and irreflexive(Only such relation fits!)
symmetric and antisymmetric are not opposites
transitive doesn't require digraphs has a circle

Question

What property dose the relation x is a multiple of y on set of all integers/positive integers have? (NOTE: think carefully about all the properties of relation)

Answer

on set of all integers is reflexive, transitive
on set of positive integers is reflexive, antisymmetric, transitive

Combining Relations¶

the notation $\circ$: take effect from right to left!!!
$S\circ R=\{(a,c) \mid a\in A\land c\in C\land \exists b(aRb \land bSc)\}$
$S\circ R \neq R\circ S$
$S\circ R=M_R\cdot M_S$
Definition($R^n$): $R_1 = R, R^{n+1} = R^n \circ R$
By associative law, we have $R^{n+1} = R \circ R^n$
The relation $R$ on a set $A$ is transitive if and only if $R^n\subseteq R, n=1,2,3,...$

Try to proof it!

9.4 Closures of Relations 关系闭包¶

Definition: The closure of $R$ with respect to $P$ is the smallest relation $S$ on $A$ with property $P$ that contains $R$
smallest? is subset of all subset $A \times A$ containing $R$ with property $P$

Different Types of Closures¶

Reflexive ClosureSymmetric ClosureTransitive Closure

$r(R)=R\cup I_A,I_A=\{(x,x)\mid x\in A\}$
$R=R\cup I_A\Leftrightarrow R$ is reflexive

$s(R)=R\cup R^{-1}$
$R=R\cup R^{-1} \Leftrightarrow R$ is reflexive

$t(R) = R^* = R\cup R^2\cup...UR^k$
$t(R) = R^*$ is transitive
How to obtain t(R)?
- brute solving
- Warshall’s Algorithm(like Flyid Algorithm)

Path¶

Let $R$ be a relation on a set $A$. There is a path the of length n, where n is a positive integer, from a to b if and only if $(a, b) \in R^n$
Connectivity relation($R^*$), consists of pairs (a, b) such that there is a path (in $R$) from a to b $R^*=\bigcup_{n=1}^\infty R^n$

The suggested order to computing closure

s(R) -> t(R) -> r(R)

9.5 Equivalence Relations¶

equivalence relation ~: relation with property reflexive, symmetric, and transitive
equivalence class $[a]_R$:

9.6 Partial Orderings¶

partial order: relation with property reflexive, antisymmetric, and transitive
partially ordered set/poset $(S, R)$: set of partial order $R$ on set $S$

$a \preceq b$: $(a, b) \in R$
$a \prec b$: $a \preceq b \wedge a \ne b$
common partial order: $\le, |, \subseteq$

Comparable: $a \preceq b$, or $b \preceq a$
Incomparable: not comparable

total/linear order: every two elements of $S$ are comparable
well-ordered set: every nonempty subset of $S has a least element

Lexicographic Order¶

$(a_1, a_2) \prec (b_1, b_2)$: $a_1 \prec_1 b_1$ or $a_1 = b_1 \wedge a_2 \prec_2 b_2$

Hasse Diagram¶

Hasse diagram is obtained from the digraph for this relation. Below is the procedure:
Construct a digraph representation of the poset (S, R)
remove all loops(that is, eliminate property reflexive)
remove all redundant(多余的) edges(that is, eliminate property transitive)
remove all arrows to obtain an undirected graph

Maximal and Minimal Elements¶

maximal/minimal: $\neg \exists b \in S(a \prec b/b \prec a)$
greatest/least: $\forall b \in S(b \preceq a/a \preceq b)$

upper/lower bound (of a set (1))
greatest lower bound(g.l.b)/least upper bound(l.u.b)

maybe a subset of given poset

Question

The greatest/least element are unique when they exist.
The unique maximal/minimal element is greatest/least element

answer

√
×

Lattices¶

lattice: every pair of elements has a l.u.b and a g.l.b

Example

ex1ex2ex3

$(Z, \le)$

l.u.b: the larger of the two elements
g.l.b: the smallest of the two elements

Every totally ordered set is a lattice.

$(Z^+, |)$

l.u.b: the least common multiple
g.l.b: the greatest common divisor

$(P(S), \subseteq)$

l.u.b: $S_1 \cup S_2$
g.l.b: $S_1 \cap S_2$

Determine the g.l.b and l.u.b of the below subsets

$(P(S), \subseteq)$, where $P(S)$ is the power set of a set S
$(P(S), \supseteq)$, where $P(S)$ is the power set of a set S

answer

g.l.b: $A \cap B$ & l.u.b: $A \cup B$
g.l.b: $A \cup B$ & l.u.b: $A \cap B$

Topological Sorting¶

Extra

	Connection matrix	digraph
reflexive \(2^{n^2 - n}\)	All elements on the main diagonal must be 1s.	There is a loop at every vertex of the directed graph-> each vertex has a loop to itself
irreflexive \(2^{n^2 - n}\)	All elements on the main diagonal must be 0s.	No vertex has a loop to itself
symmetric \(2^\frac{n(n+1)}{2}\)	The symmetric positions are both 0 or 1	If there is an arc(x, y) there must be an arc(y, x) -> both bidirectional edge
antisymmetric \(2^n \cdot 3^\frac{n^2-n}{2}\)	Symmetric positions cannot both be 1 (they can both be 0)	If there is an arc(x, y) there must be no arc(y, x) -> no bidirectional edge
asymmetric \(3^\frac{n^2-n}{2}\)	antisymmetric + irreflexive	no bidirectional edge and loop to itself
transitive	\(\overline{\left(m_{ij}\wedge m_{jk}\right)}\vee m_{ik}=1\)	If there is an arc from x to y and one from y to z then there must be one from x to z