We have been looking at properties of relations.

• Symmetric
• Reflexive
• Transitive

This collection of properties is irredundant. There are relations with any two but not the third.

• Anti-symmetry — lives off in its own world (let’s split $=$ into $\ge \wedge \le$ )

<aside> 🔖 Def.

A relation that is symmetric, reflexive and transitive is called an equivalence relation . $=$

</aside>

If we are talking about a specific equivalence relation, and there is only one relation in the discussion, we will often write $x\sim y$ instead of $(x,y)\in R$ or $xRy$.

Example we might write $\Delta ABC\sim \Delta DEF$ in geometry to mean the triangle with vertives $A,B$ and $C$ is similar to $\Delta DEF$ (or congruent, etc.)

<aside> 🔖 Def

If R is an equivalence relation, we define $[a]_R=\{b: aRb\}$.

The equivalence class of a with respect to $R$.

</aside>

<aside> 🔖 Theorem.

The following three statement are equivalent

• (1) $b\in [a]_R$
• (2) $a \in [b]_R$
• (3) $[a]_R \cap [b]_R \ne \empty$

Proof(Partial)

$(1)\rarr (2)$

If $b\in[a]_R$ then $aRb$

Since $R$ is symmetric, we see $bRa$

so $a\in [b]_R$

$(3)\rarr (1)$

If $[a]_R \cap [b]_R \ne \empty$

so $\exist c$ s.t. $c\in [a]_R$ and $c\in [b]_R$

thus $aRc$ and $bRc$

so by symmetry $cRb$ but then by transitivity $aRb$ and thus $b\in [a]_R$

</aside>

Exercise

Make sure you can prove the other $4$ implications.

The relation $(p(x),q(x))R(r(x),t(x))\larr\text{(Relation on ordered pairs of polynomials with the second half of each pair non-zero.)}$

when $p(x)t(x)=q(x)r(x) with q(x),t(x)\equiv 0$ polynomial is an equivalence relation and it lets us give meaning to the idea that

$\frac{x-1}{x-2},\frac{(x-1)(x-4)}{(x-2)(x-4)},$and $\frac{(x-1)(x-3)}{(x-2)(x-3)}$ want to be the same function.

<aside> 🔖 Def.

A collection of nonempty subsets of $S$ is called a partition of $S$ (set partition of $S$)

if

• the sets in the collection are pair wise disjoint
• the sets are each non-empty
• the union of the sets is $S$. </aside>

<aside> 🔖 Thrm.

If $R$ is an equivalence relation on set $S$, then the equivalence classed of $R$ are a set partition of $S$ conversely.

Any set partition is the equivalence classes of some relation.

Proof:

$(\rarr)R$ is an equivalence relation $S$, we want ti show the equivalence classes partition $S$.

If $x\in S$, then $x\in [x]R$ so $x\in \bigcup{y\in S}[y]R$, but also $\bigcup{y\in S}[y]_R\sube S$, so

$$ S=\bigcup_{y\in S}[y]_R $$

If $x,y\in S$ then $[x]_R=[y]_R$ or $[x]_R\cap[y]_R$ so the classes pairwise disjoint, etc.

$(conversely)$ Suppose we have a set partition $S$, for any $x,y\in S$

$$ \exist! P\in S\ s.t.\ x\in P\ and\ \exist! Q\in S\ s.t.\ y\in Q $$

define $R$ by $xRy$ iff $P=Q$.

</aside>

Ex.

Let $R$ be the relation for the partition $\{\{1,3\},\{2,4,6\},\{5\}\}$ or $\{1,2,3,4,5,6\}$,Then

$1R3$	$2R4$	$2R2$	$2R6$	$5R6$
$1R1$	$4R4$	$4R2$	$4R6$
$3R3$	$6R2$	$6R4$	$6R6$
$3R1$

Ex.

Say $f(x)Rg(x)$ iff $f(x)$ is $\varTheta(g(x))$.

Then $R$ is an equivalence relation and the equivalence classes are useful in algorithm analysis.

Chapter 10 (Graphs)

Last week, we saw directed graphs as a tool for representing relations.

We generalize to many different related ideas all called graphs.

<aside> 🔖 Def.

A graph $G$ is an ordered pair $(V,E)$ where $V$ is a non-empty set called the vertices and $E$ is called the edges. Each edge is associated with one or two vertices, called its endpoints.

The endpoints of an edge may or may not be ordered, depending on the application.

</aside>