SpecialElementsInARelationAlgebra 2008-02-15 17:39:16 2008-02-16 10:22:12 Definition relation algebra function element injective element surjective element reflexive element symmetric element transitive element equivalence element domain element range element ideal element rectangle square antisymmetric element subidentity \usepackage{amssymb,amscd} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{mathrsfs} \usepackage{tabls} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions \usepackage{amsthm} % making logically defined graphics \usepackage{xypic} \usepackage{pst-plot} % define commands here \newcommand*{\abs}[1]{\left\lvert #1\right\rvert} \newtheorem{prop}{Proposition} \newtheorem{thm}{Theorem} \newtheorem{ex}{Example} \newcommand{\real}{\mathbb{R}} \newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}} Let $A$ be a relation algebra with operators $(\vee,\wedge,\ ;,',^-,0,1,i)$ of type $(2,2,2,1,1,0,0,0)$. Then $a\in A$ is called a \begin{itemize} \item \emph{function element} if $e^-\ ; e\le i$, \item \emph{injective element} if it is a function element such that $e\ ; e^-\le i$, \item \emph{surjective element} if $e^-\ ;e=i$, \item \emph{reflexive element} if $i\le a$, \item \emph{symmetric element} if $a^-\le a$, \item \emph{transitive element} if $a\ ; a\le a$, \item \emph{subidentity} if $a\le i$, \item \emph{antisymmetric element} if $a\wedge a^-$ is a subidentity, \item \emph{equivalence element} if it is symmetric and transitive (not necessarily reflexive!), \item \emph{domain element} if $a\ ; 1 = a$, \item \emph{range element} if $1\ ; a=a$, \item \emph{ideal element} if $1\ ; a\ ; 1=a$, \item \emph{rectangle} if $a=b\ ; 1\ ; c$ for some $b,c\in A$, and \item \emph{square} if it is a rectangle where $b=c$ (using the notations above). \end{itemize} These special elements are so named because they are the names of the corresponding binary relations on a set. The following table shows the correspondence. \begin{center} \begin{tabular}{|c|c|} \hline element in relation algebra $A$ & binary relation on set $S$ \\ \hline\hline function element & function (on $S$) \\ \hline injective element & injection \\ \hline surjective element & surjection \\ \hline reflexive element & reflexive relation \\ \hline symmetric element & symmetric relation \\ \hline transitive element & transitive relation \\ \hline subidentity & $I_T:=\lbrace (x,x)\mid x\in T\rbrace$ where $T\subseteq S$ \\ \hline antisymmetric element & antisymmetric relation \\ \hline equivalence element & symmetric reflexive relation (not an equivalence relation!) \\ \hline domain element & $\operatorname{dom}(R)\times S$ where $R\subseteq S^2$ \\ \hline range element & $S\times \operatorname{ran}(R)$ where $R\subseteq S^2$ \\ \hline ideal element & \\ \hline rectangle & $U\times V\subseteq S^2$ \\ \hline square & $U^2$, where $U\subseteq S$ \\ \hline \end{tabular} \end{center} \begin{thebibliography}{8} \bibitem{sg} S. R. Givant, \emph{The Structure of Relation Algebras Generated by Relativizations}, American Mathematical Society (1994). \end{thebibliography}