\documentclass{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts, amssymb}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{amsfonts}
\setcounter{MaxMatrixCols}{10}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.50.0.2953}
%TCIDATA{}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Created=Thursday, July 21, 2005 14:31:30}
%TCIDATA{LastRevised=Wednesday, May 09, 2012 17:58:51}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=Math.cst}
%TCIDATA{PageSetup=72,72,72,72,0}
%TCIDATA{AllPages=
%F=36,\PARA{038
\hfill \thepage}
%}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\DeclareMathOperator{\lcm}{lcm}
\input{tcilatex}
\begin{document}
\section{Problems and Comments on Relations}
\section{Chapter 9}
\subsection{\protect\vspace{1pt}Section 9.1, Problems: 1, 26, 32, 49, 55}
\subsection{Section 9.4, Problems: 1, 2, 3, 22, 23}
\subsection{Section 9.5, Problems: 3, 16, 41, 55, 57}
\subsection{ Section 9.6, Problems: 5, 12, 15, 33, 62, 66}
\vspace{1pt}
\vspace{1pt}
The idea of a relation between elements of a set $A$ and a set $B$ can be
formalized by specifying a subset $R$ of the Cartesian product $A\times B.$
Instead of saying that $a$ and $b$ are in the relation $R,$ or $aRb,$ we say
that $(a,b)\in R\subseteq A\times B.$ On any set $A$ we have the equality
relation, $x=y,$ and this turns into the diagonal $\Delta =\{(a,a)|~a\in
A\}. $If $A=%
%TCIMACRO{\U{211d} }%
%BeginExpansion
\mathbb{R}
%EndExpansion
,$ then $\Delta $ is the graph of the function $y=x.$ The order relation $%
x,$
because $aa.$ You should pay special attention to functions. The
inverse relation for a function is a function only if the function is
invertible.
Of great importance is the composition of relations. As it is the case for
functions, relations in order to be composable have to be connected. If $%
R\subseteq A\times B,S\subseteq B\times C$ then the composition of $S$ and $%
R $~is defined by:$~S\circ R=\{(a,c)|\exists b\,(a,b)\in R,(b,c)\in S\}.$ In
particular, we can form all powers $R^{n~}$of $R~$where $R^{0}$ is defined
as $\Delta ,R^{1}=R,R^{2}=R\circ R,$and $R^{n+1}=R^{n}\circ R.$ Notice that
the composition of composable relations is associative. Composition with a
diagonal does not change a relation.
Notice that $(a,b)\in R^{n}$ iff there are
\begin{equation*}
c_{1},c_{2,},\ldots ,c_{n-1} \text{ such that } aRc_{1},c_{1}Rc_{2},\ldots
,c_{n-1}Rb
\end{equation*}
\begin{equation*}
R^{\ast }=\bigcup \{R^{n}|~n\geq 1\}
\end{equation*}
is called the \textit{connectivity relation} for $R.$ We have $(a,b)\in
R^{\ast }~$iff there is a path in $R$~from $a$ to $b.$
If the relation is transitive, then one has $R^{2}\subseteq R:(a,b)\in R$
and $(b,c)\in R,$that is $(a,c)\in R^{2}$ yields $(a,c)\in R.$ On the other
hand, the meaning of $R^{2}\subseteq R$ is that whenever one has some $b$
such that $(a,b)\in R,(b,c)\in R$ one has that $(a,c)\in R.$ But this is
transitivity. \textit{Hence, }$R^{2}\subseteq R$\textit{\ iff }$R$\textit{\
is transitive. }
If $R^{2}\subseteq R$\textit{\ , }then $R\circ R^{2}=R^{3}\subseteq R\circ
R=R^{2}\subseteq R,$that is $R^{3}\subseteq R$. That is, $R$\textit{\ is
transitive if and only if }$R^{n}\subseteq R,n\geq 1.$ Thus $R$ is
transitive iff $R^{\ast }=R.$ (Notice that $R\subseteq R^{\ast }$)
That the relation $R$ is reflexive means $\Delta =R^{0}\subseteq R.$
The relation $R$ on $A$ is symmetric if $R^{-1}=R.$
If $R$ is any relation on $A,$ $R\subseteq A\times A,$~then adding the
diagonal makes it reflexive. $R\cup \Delta $ is called the \textit{reflexive
closure} of $A.$
To make $R$ symmetric, one needs to add $R^{-1}$ to $R,$ $R\cup R^{-1}$ is
called the \textit{symmetric closure} of $A.$
To make $R$ transitive, on has to add all powers $R^{n}~$of $R$ to $R$. The
connectivity relation $R^{\ast }$ is also called the \ \textit{transitive
closure} of $R.$
It is easy to see that the intersection of reflexive relations is reflexive.
For any given relation $R$ on $A$, there is is a relation which contains $R~$%
and which is reflexive, namely $R\times R.$ From this observation alone, one
can conclude that there is a smallest relation that contains $R$, and which
is reflexive. This relation then might be called the reflexive closure. We
already know what this closure looks like.
Similarly, the intersection of symmetric relations is symmetric and $R\times
R$ is symmetric. Hence, for any relation $R$ there is a smallest symmetric
relation that contains $R$. This relation is the symmetric closure of $R.$
The intersection of transitive relations is transitive and $R\times R~$is
transitive. Hence for any relation $R~$on $A$ there must be a smallest
transitive relation that contains $R,$ the transitive closure. It is $%
R^{\ast }.$
Pay attention to Lemma1, p. 501, in the book. If $A$ is finite with $n~$%
elements, then one needs only the calculation of the first $n~$powers of $R$
in order to calculate $R^{\ast }.$
\begin{exercise}
Show that the intersection of transitive relations is transitive and that
\begin{equation*}
\bigcap \{S|~R\subseteq S,S\text{ transitive~}\}=R^{\ast }
\end{equation*}
\end{exercise}
Equality is reflexive, we certainly have $a=a$, equality is symmetric, that
is $a=b\Longrightarrow b=a$ and equality is transitive, $a=b,b=c%
\Longrightarrow a=c.$ Equivalence relations are relations which share with
equality these three properties. Congruence and similarity of triangles are
equivalence relations between triangles. Triangles are congruent if the
lengths of their sides are the same. Triangles are similar if the have the
same angles. The idea of an equivalence between objects $A$ and $B$ (e.g.,
triangles $A$ and $B$) is that $A$ and $B$have certain characteristics
(e.g., length of sides, angles) in common. If we define a function $f$ on
the set of triangles that assigns to a triangle $A$ the lengths of its three
sides, like $f(A)=(a=3,b=5,c=5)$ then $A\equiv B$ iff $f(A)=f(B).$ The idea
that objects are equivalent if a function defined for them agree can be
vastly generalized:
Let $f:A\rightarrow B$ be any function. Define $\ker
(f)=\{(a_{1},a_{2})|~~f(a_{1})=f(a_{2})\}.$ Then $\ker (f)$ is an
equivalence and called the \textit{kernel} of the function $f.$.
Every equivalence relation $E$ leads to a partition $\pi _{E}.~$(a partition
is a collection of non-empty subsets of $A,$called classes, which are
pairwise disjoint and whose union is $A$). Two elements are in the same
class of $\pi _{E}$ iff they are equivalent. \ And every partition $\pi $
leads to an equivalence $E_{\pi }$ where elements are equivalent if they
belong to the same class. The relationship between equivalence relations and
partitions $~$is nearly tautological but requires a formal proof (Theorem 1,
Theorem 2 on p. 510, 512).
For linear maps $T:U\rightarrow V$ \ between vector spaces, one identifies
the class of the zero vector, $N=[0]=\{u|~T(u)=0\},$ with the kernel. One
can do that because $N,$ also called the null space (for $T$),~determines
any other class: $[u]=u+N.$
If $T$ is a temperature distribution function, then the equivalence classes
for $T$ are called isotherms.
If $N:$ $C\rightarrow \{A,B,C,D,F\}$ is the function which assigns to a
student in the class $C$ his standing with respect to his grade, then $C$
partitions into the classes of $A$-students, $B$-students etc.
Transitivity is a fundamental property of any concept of ordering.
Anti-symmetry is equally important, one cannot have $a\leq b$ and $b\leq a$
unless $a=b.$ A relation $\leq ~$which is reflexive, transitive and
anti-symmetric is called a\textit{\ partial ordering}. If any two elements $%
a $ and $b~$are comparable, that is either $a\leq b$ or $b\leq a,$ then the
partial order is called a\textit{\ total order.}
For any subset $S$ of a partially ordered set one can define that $u$ is an
\textit{upper bound} for $S:u\geq s$ for all $s\in S.$ An upperbound for $S~$%
which belongs to $S$ is the \textit{maximum} of $S$. If a set has a maximum
then it is unique (Proof?). \textit{Lower bounds} and \textit{minima }are
similarly defined.
\vspace{1pt}If for a subset $S,$ the set of upper bounds is non-empty and
has a minimum, then this least upper bound is called the \textit{supremum}
of $S.$ \textit{Infimum} is similarly defined as the largest lower bound of
a set $S.$ The open interval $(0,1)$of real numbers has infimum $0$ and
supremum $1.$
It is an axiom for real numbers that any subset $S$ of real numbers which
has an upper bound, has a supremum. This is the \textit{Least Upper \ Bound
Axiom}.
A partially ordered set $(P,\leq )$ is called \textit{bounded }if it has a
minimum as well as a maximum. A bounded partially ordered set is called a
\textit{complete lattice} in case that every non-empty subset $S$ has a
supremum and an infimum. For any set $S$ the powerset $\mathbf{P}(S)~$with
inclusion as partial ordering is an example of a complete lattice. The
infimum of a set of subsets is its intersection, the supremum is its union.
A partially ordered set $(L,\leq )$ is called a \textit{lattice} if every
finite subset has a supremum and an infimum. The natural numbers ($\mathbb{N}%
,|)$, where $|$ is the partial order given by divisibility, is a lattice.
Here the infimum of $\{a,b\}$ is the $\gcd \{a,b\},$ the greatest common
divisor. Recall that the greatest common divisor of $a,b$ is the number $d$
such that $d|a$ and $d|b.$ That is, $d$ is a lower bound with respect to
divisibility of $a$ and $b,$ and if $e~$is any other lower bound for $a$ and
$b,$ that is $e|a$ and $e|b,$ then $e|d.$ That is, $d$ is the greatest lower
bound for $\{a,b\}.$ The lowest common multiple of $\{a,b\}$ is the supremum
of $\{a,b\}$. The existence of $\lcm$ and $\gcd $ is shown in any modern
algebra course. It is not trivial and relies on the unique prime
factorization theorem. The uniqueness part of this theorem is not trivial.
\vspace{1pt}Any partial order on a finite set can be extended to a total
order. This is called topological sorting and the book provides an algorithm
for doing that. The following exercise will do the same and can be applied
to infinite partial orderings.
\begin{exercise}
Let $(A,R)$ be a partial ordering and assume that neither $aRb$ nor $bRa$
holds, i.e., $(a,b)\notin R,(b,a)\notin R$. Then the transitive closure of $%
R\cup \{(a,b)\}$is antisymmetric
\end{exercise}
\end{document}