12-15,17. Properties of relations

Properties of relations

Reflexive relations

Reflexive relation

A relation $R$ on a set $A$ is called a reflexive, if $(a, a) \in R$ for every element $a \in A$, in effect everything loops.

For example:

• Reflexive: $R_1=\{(1,1),(1,2),(3,1),(2,2),(3,3)\}$ on $\{1,2,3\}$ Each element refers to itself.

  digraph G {
  	1->1
    1->2
    3->1
    2->2
    3->3
  }

• Reflexive: $\le$, $\ge$, $=$ Each and every number is lesser than or equal to, greater than or equal or equal to itself.

• Reflexive: ‘divisibility’ on ${\mathbb{N}}^{+}$ Each and every number is divisible by itself.

• Not reflexive: $R_2=\{(1,1),(1,2),(3,1)\}$ on $\{1,2,3\}$ Not every element refers to itself.

  digraph G {
  	1->1
    1->2
    3->1
  }

Link to original

Irreflexive relations

Irreflexive relation

A relation $R$ on a set $A$ is called irreflexive if $(a,a) \notin R$ for every element $a \in A$, in effect there are no loops.

For example:

• Irreflexive: $<$, $>$, $\ne$ on $\mathbb{N}$ or on $\mathbb{Z}$ Elements do not refer to themselves.

• Irreflexive: $R_3=\{(1,2),(1,3),(2,1),(3,2)\}$ on $\{1,2,3\}$

  digraph G {
  	1->2
    1->3
    2->1
    3->2
  }

title: Not all "not reflexive" relations are irreflexive!
**Not irreflexive**: $R_2 = \{ (1,1), (1,2), (3,1) \}$ on $\{ 1,2,3 \}$
Some elements refer to themselves.
 
```graphviz
digraph G {
  1->1
  1->2
  3->1
}

Link to original

Symmetric relations

Symmetric relation

A relation $R$ on a set $A$ is called symmetric, if for all elements $a, b \in A$, $(b,a) \in R$ whenever $(a, b) \in R$. In effect, all relations must be mirrored.

For example:

• Symmetric: $R_1=\{(1,1),(1,2),(2,1),(2,3),(3,2),(3,3)\}$ on $\{1,2,3\}$ All pairs of elements have the same properties in both directions.

  digraph G {
  	1->1
    1->2
    2->1
    2->3
    3->2
    3->3
  }

• Symmetric: $R_2=\{(1,1),(2,2),(3,3)\}$ on $\{1,2,3\}$ All pairs of elements have the same properties in both directions.

  digraph G {
  	1->1
    2->2
    3->3
  }

• Symmetric: $\{(x,y)\in \mathbb{N}\times \mathbb{N}|x-y\text{ is divisible by }3\}$ on $\mathbb{N}$

• Not symmetric: $R_3=\{(1,1),(1,2),(2,1),(3,1),(3,3)\}$ on $\{1,2,3\}$ Not all pairs of elements have the same properties in both directions.

  digraph G {
  	1->1
    1->2
    2->1
    3->1
    3->3
  }

Link to original

Antisymmetric relations

Antisymmetric relation

A relation $R$ on a set $A$ is called antisymmetric, if $(a, b)$ and $(b, a)$ cannot both be in $R$ unless $a = b$.

(it also does not mean $(a,a)$ should be in $R$)

This is also not opposite to symmetric, instead it means that you can go one way but you cannot come back unless if you’re going from an element to itself.

For example:

• Antisymmetric: $<$, $>$, $leq$, $geq$ on $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$ or $\mathbb{R}$.

• Antisymmetric: $R_1=\{(1,1),(1,3),(2,3),(3,3)\}$ on $\{1,2,3\}$ You can go one way but not the other.

  digraph G {
  	1->1
    1->3
    2->3
    3->3
  }

• Antisymmetric (also symmetric): $R_2=\{(1,1),(2,2),(3,3)\}$ on $\{1,2,3\}$ You can go one way but not the other.

  digraph G {
  	1->1
    2->2
    3->3
  }

• Not antisymmetric: $R_3=\{(1,1),(1,2),(2,1)\}$ on $\{1,2\}$ There are bi-directional paths here.

  digraph G {
    1->1
  	1->2
    2->1
  }

Link to original

Transitive relations

Transitive relation

A relation $R$ on a set $A$ is called transitive, if the following hold, for all elements $a,b,c\in A$: $$ \text{If both } (a, b) \in R \text{ and } (b, c) \in R \text{ then } (a, c) \in R $$

In the directed graph representing $R$, $R$ is transitive, if every two-step journey along arrows can be done in one step. For example:

• The following graphs are not transitive:

  digraph A {
  	x->y
    y->z
    z->w
    x->z
  }
   
  digraph B {
  	x->y
    y->z
    z->w
    x->z
    x->w
  }

• The following graph is transitive:

  digraph B {
  	x->y
    y->z
    z->w
    x->z
    x->w
    y->w
  }

• Transitive: $<$, $>$, $\le$, $\ge$ on $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, or $\mathbb{R}$ For example, if $a<b$ then $b<c$ and so on…

• Transitive: $R_1=\{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\}$ on $\{1,2,3,4\}$

  digraph B {
  	1->1
    1->2
    1->3
    2->2
    2->3
    3->3
  }

• Transitive: $R_2=\{(3,4)\}$ on $\{3,4\}$ We cannot show it’s not transitive, since we only have one one-step journey.

  digraph B {
    3->4
  }

• Not transitive: $R_3=\{(1,1),(1,2),(2,1)\}$ on $\{1,2\}$

  digraph B {
    1->1
    1->2
    2->1
  }

Link to original

Transitive closure

Transitive closure

Given that $R$ is a relation on a set $A$. The transitive closure of $R$ is the smallest transitive relation on $A$ containing $R$. We denote the transitive closure of $R$ by $\boxed {R^*}$.

If $R$ is already transitive, then $R^{\ast }=R$.

For example, given the following definition of $R$, we find $R^{\ast }$:

digraph A {
	label="R"
	x->y
	y->z
	z->w
	x->z
}
digraph B {
	label="R*"
	x->y
	y->z
	z->w
	x->z
	x->w
	y->w
}

Given $R$, we can define the transitive closure, $R^{\ast }$, recursively: ?

• Basis step: $R\subseteq R^{\ast }$ The pairs in $R$ are all in $R^{\ast }$.
• Recursive step: If $(a,b)\in R^{\ast }$ and $(b,c)\in R^{\ast }$ then $(a,c)\in R^{\ast }$. We add the missing pairs step by step.

Warshall’s algorithm

Warshall's algorithm

Algorithm

An algorithm is a finite sequence of precise step-by-step instructions.

Link to original

Warshall’s algorithm computes the matrix of the transitive closure $R^{\ast }$ of $R$. ?

• Given a relation $R$ on a set $A$ with $n$ elements, we begin with its $n\times n$ matrix. $\boxed{M_0}$
• There are $n$ rounds. For each, we mutate the matrix. $$M_0\stackrel{\text{round 1}}{⇝}{M}_1\stackrel{\text{round 2}}{⇝}{M}_2\stackrel{\text{round 3}}{⇝}...\stackrel{\text{round n}}{⇝}{M}_n$$ $\boxed{M_n}$ is the matrix of the transitive closure $R^{\ast }$ of $R$.
  • 1st rule: never change $1$ to $0$
  • 2nd rule: for the $k$ round, we select the $k$th row and the $k$th column, we look at all of the $0$ values not in this row or column. From the position of the $0$ value we are looking at, we check to see if the corresponding cells in the $k$th row and column are $1$, if they are, we change $0$ to $1$ otherwise we don’t do anything. $$\begin{array}{cc}& jk\text{th column}\\ \begin{array}{c}i\\ \\ k\text{th row}\end{array}& \left[\begin{array}{ccc}0& \to & 1\\ \downarrow & & \\ 1& & \end{array}\right]\end{array}\stackrel{\text{round }k}{⇝}\begin{array}{cc}& \begin{array}{ccc}j& & k\end{array}\\ \begin{array}{c}i\\ \\ k\end{array}& \left[\begin{array}{ccc}\text{1}& & 1\\ & & \\ 1& & \end{array}\right]\end{array}$$

Link to original

Example

Let $R$ be a relation on $\{a,b,d,d\}$. $R=\{(a,d),(b,a),(b,c),(c,a),(c,d),(d,c)\}$

We first construct our starting matrix.

$$M_0=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}0& 0& 0& 1\\ 1& 0& 1& 0\\ 1& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right]\end{array}$$

Round 1.

$$M_1=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}0& 0& 0& 1\\ 1& 0& 1& \boxed{1}\\ 1& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right]\end{array}$$

Round 2.

$$M_2=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}0& 0& 0& 1\\ 1& 0& 1& 1\\ 1& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right]\end{array}$$

Round 3.

$$M_3=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}0& 0& 0& 1\\ 1& 0& 1& 1\\ 1& 0& 0& 1\\ \boxed{1}& 0& 1& \boxed{1}\end{array}\right]\end{array}$$

Round 4.

$$M_4=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}\boxed{1}& 0& \boxed{1}& 1\\ 1& 0& 1& 1\\ 1& 0& \boxed{1}& 1\\ 1& 0& 1& 1\end{array}\right]\end{array}$$

Hence this is our final relation.

$$R^{\ast }=\{(a,a),(a,c),(a,d),(b,a),(b,c),(b,d),(c,a),(c,c),(c,d),(d,a),(d,c),(d,d)\}$$

digraph A {
	label = "R"
	a->d
	b->a
	b->c
	c->a
	c->d
	d->c
}
 
digraph B {
	label = "R*"
	a->a
	a->c
	a->d
	b->a
	b->c
	b->d
	c->a
	c->c
	c->d
	d->a
	d->c
	d->d
}

Link to original

Equivalence relation

Equivalence relation

A relation $R$ on a set $A$ is called an equivalence relation if it is: ?

• reflexive: everything loops
• symmetric: all arrows come in pairs
• transitive: every 2-step journey must be also done in 1-step

For example:

• $=$ on any set
• $\{(x,y)\in \mathbb{Z}\times \mathbb{Z}|x-y\text{ is divisble by }4\}$ on $\mathbb{Z}$

Link to original

Partial Order

Partial order

A relation $R$ on a set $A$ is called an partial order if it is: ?

• reflexive: everything loops
• antisymmetric: we can only travel one way
• transitive: every 2-step journey must be also done in 1-step

For example:

• $\le$, $\ge$, and ‘divisibility’ on ${\mathbb{N}}^{+}$
• Prove that $\subseteq$ is a partial order on the power set $P(S)$ of a set $S$.
  • $\subseteq$ is reflexive because $A\subseteq A$ for every set $A$.
  • $\subseteq$ is antisymmetric because if $A\subseteq B$ and $B\subseteq A$, then $A=B$ holds.
  • $\subseteq$ is transitive because if $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$ holds.

Link to original

Linear Order

Linear order

A relation on a set $A$ is called a linear order if: ?

• It is also a partial order.
• For all $a,b\in A$, either $(a,b)\in R$ or $(b,a)\in R$.

For example:

$\le$ on $\mathbb{N}$	$\ge$ on $\mathbb{Z}$
Graph of less than or equal to on natural numbers graph G { 2--1 1--0 } Link to original	Graph of greater than or equal to on integer numbers graph G { { m [label="-1"] } m--0 0--1 } Link to original

Example

Let $S$ be a set with more than one element. Show that $\subseteq$ is not a linear order on $P(S)$.

If $S$ has more than one element, then there are at least two different elements, say $x$ and $y$:

• $x\in S$ so $\{x\}\subseteq S$ and so $\{x\}\in P(S)$
• $y\in S$ so $\{y\}\subseteq S$ and so $\{y\}\in P(S)$
• Neither $\{x\}\subseteq \{y\}$ or $\{y\}\subseteq \{x\}$ hold as $x\ne y$.

So $\{x\}$ and $\{y\}$ are two elements in $P(S)$ such that either $\{x\}\subseteq \{y\}$ or $\{y\}\subseteq \{x\}$, so so $\subseteq$ is not a linear order. (It does not form a line.)

graph G {
	{
		a [label="P(s)"]
		x [label="{x}"]
		y [label="{y}"]
	}
	
	x,y--a
}

Link to original