\documentclass{amsart}


\usepackage{amsthm}

\usepackage{stmaryrd}%\fatsemi

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\defiff}{\stackrel{def}{\Longleftrightarrow}}
\theoremstyle{definition}\newtheorem{df}{\bf Definition}
\newtheorem{ex}{\bf Example}
\newtheorem{e}{\bf Exercise}
\newtheorem{prop}{\bf Proposition}
\newtheorem{thm}{\bf Theorem}

\begin{document}

\title{Introduction to algebra --- handout 1}
\maketitle

\section{binary relations}

\begin{ex}
``\ldots is a son of \ldots'', ``\ldots is a friend of \ldots'', ``\ldots knows \ldots '', ``\ldots likes\ldots'',  ``\ldots is smaller than \ldots'', `` \ldots is equal to\ldots'', 
``\ldots is similar to\ldots'', ``\ldots divides \ldots'', etc.   
\end{ex}

\begin{df}
$R$ is a {\bf binary relation between}  sets $X$ and $Y$ if $R\subseteq X\times Y$. 
\end{df}


\begin{df}
$R$ is a {\bf binary relation on} set $X$ if $R\subseteq X\times X$. 
\end{df}

Representations: set,  biparite graph, coordinate system, incidence matrix, directed graph.  

%\subsection{properties}
\begin{itemize}
\item {\bf reflexive}: $\langle x,x\rangle\in R$ for all $x\in X$. 
\item {\bf irreflexive}: $\langle x,x\rangle\not\in R$ for all $x\in X$. 
\item {\bf symmetric}: If $\langle x,y\rangle\in R$ then $\langle y,x\rangle\in R$ for all $x,y\in X$.
\item {\bf antisymmetric}: If $\langle x,y\rangle\in R$ then $\langle y,x\rangle\not\in R$ for all {\em distinct} $x,y\in X$.
\item {\bf asymmetric}: If $\langle x,y\rangle\in R$ then $\langle y,x\rangle\not\in R$ for all  $x,y\in X$.
\item {\bf transitive}: If $\langle x,y\rangle\in R$  and $\langle y,z\rangle\in R$, then $\langle x,z\rangle\in R$ for all $x,y, z \in X$.
\item {\bf trichotomous}: If exactly one of $\langle x,y\rangle\in R$, $\langle y,x\rangle \in R$ or $x = y$ holds for all $x,y\in X$.
\end{itemize}

\begin{e}
\begin{itemize}
\item[]
\item[(A)] Show that binary relation $R$ is {antisymmetric} iff (if and only if) $x=y$ whenever $\langle x, y\rangle\in R$ and $\langle y,x\rangle\in R$. 
\item[(B)] Show that a  binary relation asymmetric iff it is anti-symmetric and irreflexive.
\item[(C)] Show that a transitive relation is irreflexive iff it is asymmetric.
\end{itemize}
\end{e}

\begin{df}
The {\bf identity} relation is defined as 
\begin{equation*}
D_X:=\{\langle x,x\rangle : x\in X\}.
\end{equation*}
The {\bf inverse} of binary relation $R$ is defined as 
\begin{equation*}
R^{-1}:=\{\langle y,x\rangle: \langle x,y\rangle\in R\}.
\end{equation*}
The {\bf composition} of binary relations $R$ and $S$ is defined as 
\begin{equation*}
R\fatsemi S:=\{\langle x,z\rangle: \langle x,y\rangle\in R \text{ and
} \langle y,z\rangle\in S \text{ for some } y\in X \}.
\end{equation*}
\end{df}

\begin{e}
Show that binary relation $R$ is
\begin{enumerate}
\item irreflexive iff $D_x\cap R =\emptyset$,
\item reflexive iff $D_x\subseteq R$,
\item antisymmetric iff  $R\cap R^{-1}\subseteq D_x$,
\item transitive iff $R\fatsemi R \subseteq R$.
\end{enumerate}
\end{e}

\begin{df}
Binary relation $\le$ is a {\bf  partial order} if the following holds:
\begin{itemize}
\item  $x\le x$ ({\em reflexive})
\item  $x\le y\le z \Rightarrow x\le z$ ({\em transitive}) 
\item  $x\le y \le x\Rightarrow x=y$ ({\em antisymmetric}) 
\end{itemize}
\end{df}

\begin{e}
How many different partially orders are on a 3 element set?
\end{e}

\begin{ex}
$\langle \{0,1\}, \{\langle 0,0\rangle, \langle 0,1 \rangle, \langle 1,1\rangle\}\rangle$, 
$\langle \Z, \le\rangle$, $\langle\Q, \le\rangle$, $\langle\R, \le\rangle$, $\langle \N, \le \rangle$, $\langle \N, |\rangle$,  $\langle\mathcal{P}(A),\subseteq\rangle$
\end{ex}
\begin{ex}
Let $\mathcal{C}$ be the set of (continuous) functions from $\R$ to $\R$ and let 
\begin{equation*}
f\le g \defiff \forall x\, f(x) \le g(x)
\end{equation*}
Then $\langle \mathcal{C}, \le\rangle$ is a partially ordered set. 
\end{ex}



\begin{df}
Binary relation $<$ is a {\bf strictly partial order} iff the following holds:
\begin{itemize}
\item  $x\not< x$ ({\em irreflexive})
\item  $x< y \Rightarrow y\not<x$ ({\em asymmetric}) 
\item  $x<y<z \Rightarrow x< z$ ({\em transitive}) 
\end{itemize}
\end{df}

\begin{e} Show that strictly partial orders and partial orders are essentially the same (definitionally equivalent). 
That is the theory of partial orders extended with explicit definition   
\begin{equation*}
x<y\defiff x\le y \text{ and }x\neq y.
\end{equation*}
and the theory of strict partial orders extended with explicit definition
\begin{equation*}
x\le y\defiff x< y \text{ or }x=y.
\end{equation*}
have the same models.  
\end{e}



\begin{df}
$y$ {\bf covers} $x$ iff $x<y$ but there is no element $z$ such that $x<z<y$. 
\end{df}

{\em Hasse diagram}

\begin{df}
A partial order is called {\bf total order} it is trichotomous, i.e., exactly one of $x<y$, $y<x$ or $x=y$ holds. 
\end{df}




\begin{df}
$z$ is an {\bf upper bound} of set $H$ if $x\le z$ for all $x\in H$.  
$z$ is an {\bf lower bound} of set $H$ if $z\le x$ for all $x\in H$.  
\end{df}

\begin{df}
$x$ is {\bf maximal} if there is no element $y$ such that $x<y$.  
$x$ is {\bf minimal} if there is no element $y$ such that $y<x$.  
\end{df}

\begin{df}
$x$ is {\bf the greatest element} of a poset if $y\le x$ for all $y\in X$. 
$x$ is {\bf the least element}  of a poset if $x\le y$ for all $y\in X$. 
\end{df}

Note that the greatest/least element is unique and maximal, but there can be several distinct maximal/minimal elements which in a poset.

\begin{df}
A totally ordered subset of a poset is called {\bf chain}. A set of incomparable elements is called {\bf antichain}.
\end{df}


\begin{df}
The {\bf height} $h(X)$ of poset $\langle X,\le\rangle$ is the largest cardinality of a chain.  
The {\bf width} $w(X)$ of poset $\langle X,\le\rangle$ is the largest cardinality of an antichain.  
\end{df}


\begin{thm}[Dilworth]
For every finite poset $\langle X,\le\rangle$, there is a partition of $X$ into $w(X)$ chains.  
\end{thm}

{\em Zorn's Lemma}: If every chain has an upper bound in a poset, then it contains a maximal element.  

\begin{df}
A partial order is called {\bf directed} if every pair of elements has an upper bound. 
\end{df}

\begin{df}
Binary relation $\sim$ is an {\bf equivalence relation} iff  the following holds:
\begin{itemize}
\item  $x\sim x$ ({\em reflexive})
\item  $x\sim y \Rightarrow y\sim x$ ({\em symmetric}) 
\item  $x\sim y \sim z \Rightarrow x\sim z$ ({\em transitive}) 
\end{itemize}
\end{df}

\begin{ex}
  equality, similarity, congruence, lines being parallel, etc.
\end{ex}

\begin{df}
The {\bf equivalence class} of $a$ is the set of elements equivalent to $a$, i.e., $[a]:=\{b: a\sim b\}$.
Let the set of equivalence classes of $\sim$ be denoted by $X/\sim$. 
\end{df}

\begin{ex}
Vectors are equivalence classes of arrows.  
\end{ex}

\begin{df}
$\Pi\subseteq \mathcal{P}(X)$ is a {\bf partition} of $X$ iff the following hold 
\begin{itemize}
\item $A\neq \emptyset$ for all $A\in \Pi$,
\item $A\cap B =\emptyset$ for all distinct $A,B\in \Pi$,
\item $\cup \Pi=X$.
\end{itemize}
\end{df}



\begin{prop}
For any equivalence $\sim$ relation on $X$, the set of equivalence classes $X/\sim$ is a partition of $X$. 
For any partition $\Pi$ on $X$, the relation being in the same partition is an equivalence relation (whose equivalence classes are exactly the members of the partition $\Pi$).
\end{prop}

\begin{df}
Binary relation $\gets$ is a {\bf  preorder} if the following holds:
\begin{itemize}
\item  $x\gets x$ ({\em reflexive})
\item  $x\gets y\gets z \Rightarrow x\gets z$ ({\em transitive}) 
\end{itemize}
\end{df}

\begin{prop}
Let $\gets$ be a preorder on $X$. Define $\sim$ as 
\begin{equation*}
x\sim y \defiff x\gets y \text{ and } y\gets x.  
\end{equation*}
Then  $\sim$ is an equivalence relation on $X$. 
Furthermore, if $x\sim x'$, $y\sim y'$ and $x\gets y$, then $x'\gets y'$. $\leadsto$ {\em canonical quotient}   
\end{prop}
\end{document}