MATH 302 Lecture 23

« previous | Monday, November 21, 2011 | next »

Relations

A relation from $A$ to $B$: a subset of the combination of an element in $A$ with an element in $B$ where there are no restrictions.

$S\subseteq A\times B$

Where $A\times B$ is the Cartesian Product.

Relations on A

Special relation where $R\subseteq A\times A$

Ways to describe self-relations

1. List ordered pair elements
2. Directed graph where each vertex represents an element in $A$ and each directed edge connects the first element to the second element in each pair
3. Zero-one matrices: first element represents row, second element represents column, write a 1 at each relation point.
4. Rules: $\{(x,y)\in A^2|\text{rules}\}$

Sample Relations

• greater than relation: $R=\{(x,y)\in A^2|x>y\}$
• Divisor relation: $R=\{(x,y)\in A^2|x\mathrm{d}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{s}y\}$
• Modulo $n$ relation: $R\{(x,y)\in A^2|x-y\mathrm{i}\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{o}\mathrm{f}n\}$

Properties

reflexive

for all $x\in A$, $(x,x)\in R_A$

wth a digraph, all vertices have a self-edge loop

with a zero-one matrix, the diagonal is all 1s

symmetric

$(x,y)\in R_A$ implies $(y,x)\in R_A$

with a digraph, all edges are undirected.

with a zero-one matrix, the matrix is diagonally symmetric

transitive

if $(x,y)\in R_A$ and $(y,z)\in R_A$, then $(x,z)\in R_A$

with a zero-one matrix, taking $R^n$ represents all of the positions you can reach with $n$ stops. In the transitive case, $n=2$

antisymmetric

if $(x,y)\in R_A$ and $(y,x)\in R_A$, then $x=y$

with a zero-one matrix, If there is a $M_{ij}=1$ on one diagonal half, then $M_{ji}=0$ on the opposite diagonal half

Equivalence Relations

An equivalence relation is a relation that satisfies the following properties:

• Reflexive
• Symmetric
• Transitive

Equality can be vague. With equivalence, we focus on certain characteristics

Partial Order Relations

A partial ordering is a relation that satisfies the following properties:

• Reflexive
• Transitive
• Antisymmetric

Partitions

A collection of subsets $A_0$, $A_1$, $A_i$ (equivalence classes) of a larger set $A$ such that

1. $A_i\cap A_j=\mathrm{\varnothing }$ (disjoint)
2. $\bigcup _{i\in I}{A}_i=A$

Equivalence Classes

For any $a\in A$, the equivalence class of $a$ is the set $\{x\in A|R(x,a)\}=[a]$.

We call $a$ a representative of an equivalence class.

Equivalence clasess often carry the properties of the superclass

Examples

Let $A$ be the bit strings of length 3 or more such that two bit strings $x$ and $y$ have the same first and third bits. Show that this is a recurrence relation.

Proof:

1. $R$ is reflexive since every bit string has the same first and third bits as itself
2. $R$ is symmetric since if $x$ has the same first and third bits as $y$, then $y$ has the same first and third bits as $x$
3. $R$ is transitive since if $R(x,y)$ and $R(y,z)$, then their first and third bits are the same. Therefore, $R(x,z)$