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}~|~{\mbox{rules}}\}$

Sample Relations

• greater than relation: $R=\{(x,y)\in A^{2}~|~x>y\}$
• Divisor relation: $R=\{(x,y)\in A^{2}~|~x\ \mathrm {divides} \ y\}$
• Modulo $n$ relation: $R\{(x,y)\in A^{2}~|~x-y\ \mathrm {is\ a\ multiple\ of} \ 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}=\emptyset$ (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)$