binary relations

Work in Progress

Summary

Relations as both a set of tuples and an operator

Properties of binary relations

reflexive -> every element has a self-loop
symmetric -> every relation is two-way
transitive -> every relation that can be made in two steps can be made in one

Proving properties

note the number of variables needed(for proving/disproving)

Concept

Binary relation and its inverse

  • same predicate, flipped tuple
XYxyRR¡1

Composition

Inverse of composition (Theorem 2.4)

XYZxyzRSS±R(S±R)¡1=R¡1±S¡1

Transitivity and composition (Theorem 2.5)

A relation on a set can be represented by a undirected/directed graph

Application

Directed graph for subsets

  • binary operators can be binary relations
?fagfbgfa,bg

Some relations

the key lies in the predicate

Extra

Tikz template for arrow diagram between sets

latex
\usepackage{tikz}
\usetikzlibrary{arrows,fit,shapes}

\begin{document}
 \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt,minimum width=1.4cm,minimum height=1.8cm}]
  \node (X) at (0,5) {X};
  \node (Y) at (4,5) {Y};
  
  \node[ele,label=left:$a$] (a1) at (0,4) {};    
  \node[ele,label=left:$b$] (a2) at (0,3) {};    
  \node[ele,label=left:$c$] (a3) at (0,2) {};
  \node[ele,label=left:$d$] (a4) at (0,1) {};

  \node[ele,,label=right:$1$] (b1) at (4,4) {};
  \node[ele,,label=right:$2$] (b2) at (4,3) {};
  \node[ele,,label=right:$3$] (b3) at (4,2) {};
  \node[ele,,label=right:$4$] (b4) at (4,1) {};

  \node[draw,fit= (a1) (a2) (a3) (a4)] {} ;
  \node[draw,fit= (b1) (b2) (b3) (b4)] {} ;  
  \draw[->,shorten <=2pt,shorten >=2pt] (a1) -- (b4);
  \draw[->,shorten <=2pt,shorten >=2] (a2) -- (b2);
  \draw[->,shorten <=2pt,shorten >=2] (a3) -- (b1);
  \draw[->,shorten <=2pt,shorten >=2] (a4) -- (b3);
 \end{tikzpicture}
\end{document}