\documentclass{amsart}

\usepackage{tikz}

\usepackage{amsthm}

\usepackage{stmaryrd}%\fatsemi
\newcommand{\dom}{\mathrm{Dom}}
\newcommand{\ran}{\mathrm{Ran}}
\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}
\newtheorem{lem}{\bf Lemma}
\newtheorem{cor}{\bf Corollary}

\begin{document}

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

\section{Binary relations}
\begin{df}
Binary relation $R$ is a {\bf function} iff $\langle x,y \rangle\in R$
and $\langle x,z \rangle \in R$ imply that $y=z$. Binary relation $R$
is {\bf injective} iff $\langle x,y \rangle\in R$ and $\langle w,y
\rangle \in R$ imply that $x=y$. 
\end{df}

Note that $R$ is a function iff $R^{-1}$ is injective. 

\begin{df}
{\bf Domain} of $R$ is defined as:
%\begin{equation*}
$\dom R := \{ x :\exists y\, \langle x,y\rangle \in R\} $.
%\end{equation*}
{\bf Range} of $R$ is defined as:
%\begin{equation*}
$\dom R := \{ x :\exists y\, \langle x,y\rangle \in R\} $.
%\end{equation*}
\end{df}

\begin{df}
$R$ is called {\bf connected} iff $\langle x,y \rangle\in R$ or
$\langle y,x \rangle\in R$ for all {\em distinct} $x,y\in X$.  $R$ is called
{\bf strongly connected} iff $\langle x,y \rangle\in R$ or $\langle y,x
\rangle\in R$ for all  $x,y\in X$.
\end{df}

If  $R$ is symmetric, transitive and  $\dom R \cup \ran R = X$, then $R$ is reflexive. 

\begin{e}
What is the logical connection between the followings:
\begin{itemize}
\item $R$ is connected. 
\item $\dom R \cup \ran R = X$.
\item $R$ is strongly connected and irreflexive. 
\end{itemize}
\end{e}

\section{Preorders}

\begin{ex}
Let $Form$ be the set of all first-order logic sentences on a language
$\mathcal{L}$, let $T$ be a theory on $\mathcal{L}$ and let
$\models_T$ be the relation of logical consequence $T\models \varphi
\rightarrow \psi$. Then $\langle Form, \models_T\rangle$ is a
preorder. The canonical quotient of this preorder is called {\it
  Tarski-Lindenbaum algebra}.
\end{ex}
\section{Partial ordered sets}

\begin{df}
A $a$ and $b$ are called {\bf incompatible} if $a\not\le b$ and
$b\not\le a$.
\end{df}
\begin{lem}\label{lem-ext} Let $\langle X, \le\rangle$ be a partial order, and let $a$ and $b$ be incompatible elements of $X$. Then there is a partial order $\preceq$ extending $\le$ such that $a\prec b$. 
\end{lem}

\begin{proof}
Let $A:=\{x : x\le a\}$ and let $B:=\{y : b\le y\}$. Sets $A$ and $B$ are disjoint since $b\not \le a$.  
Let $x\preceq y$
iff $x\le y$ or $\langle x,y\rangle \in A\times B$. 

$\preceq$ is reflexive because $\le$ is so. 

$\preceq$ is antisymmetric: 4 simple cases.  

$\preceq$ is transitive: 4 simple cases.
\end{proof}

\begin{df}
$\preceq$ is an {\bf extension} of $\le$ iff $x\le y$ imply $x\preceq y$.  
\end{df}

\begin{thm}[Szpilrajn] 
Every partial order has a total order extending it. 
\end{thm}

\begin{proof}
Let $P$ be a partial ordered set.  Consider the partial ordered set of
partial orders extending $P$  with respect to extension.  The union of a chain of
posets is a poset. Therefore, by Zorn Lemma, there is a maximal poset
containing $P$. This maximal poset have to be a
total order by Lemma~\ref{lem-ext}.
\end{proof}

\begin{cor}
Every partial order is the intersection of the total orders extending it. 
\end{cor}

\begin{df}
The {\bf dimension} of partial ordered set $\langle X,\le \rangle$ is the minimum number of total orders on $X$ whose intersection is $\le$.
\end{df}


\begin{df}
The {\bf $2n$-vertex crown} $S_n$ is defined as the intersection of all partial
orders on $\{a_1,\ldots, a_n,b_1,\ldots,b_n\}$ satisfying $a_i\le b_j$
if $i\neq j$. See, Figure~\ref{S3} for $S_3$. 
\end{df}

\begin{center}
\begin{figure}
\begin{tikzpicture}[scale=1.5]
\tikzset{doboz/.style={rectangle, draw, very thick, rounded corners=1mm, fill=red!10!blue!10, inner sep=0.2cm, text centered}}
\node[doboz] (b1) at (-2,1) {$b_1$};
\node[doboz] (b2) at (0,1) {$b_2$};
\node[doboz] (b3) at (2,1) {$b_3$};
\node[doboz] (a1) at (-2,-1) {$a_1$};
\node[doboz] (a2) at (0,-1) {$a_2$};
\node[doboz] (a3) at (2,-1) {$a_3$};
\draw[thick] (a1) -- (b2);
\draw[thick] (a1) -- (b3);
\draw[thick] (a2) -- (b1);
\draw[thick] (a2) -- (b3);
\draw[thick] (a3) -- (b1);
\draw[thick] (a3) -- (b2);
\end{tikzpicture}
\caption{\label{S3} $S_3$}
\end{figure}
\end{center}


\begin{prop}
The dimension of crown $S_n$ is $n$ if $n\ge 2$.
\end{prop}

\section{Lattices}

\begin{df}
Let $\langle X,\le\rangle$ be a partial ordered set and let
$H\subseteq X$. The {\bf least upper bound} or {\bf supremum} of $H$ is $b$ iff $b$ is
an upper bound (i.e., $x\le b$ for all $x\in H$) and $b\le c$ for every
upper bound $c$ of $H$ (i.e., if $x\le c$ for all $x\in H$, then $b\le c$).
 The {\bf greatest lower bound} or {\bf infimum} of $H$ is $b$ iff $b$ is
a lower bound (i.e., $a\le x$ for all $x\in H$) and $c\le a$ for every
lower bound $c$ of $H$ (i.e., if $c\le x$ for all $x\in H$, then $c\le a$).
\end{df}


\begin{df}
The least upper bound of $\{a,b\}$ is denoted by $a\lor b$ and called {\bf join}.   
The greatest lover bound of $\{a,b\}$ is denoted by $a\land b$ and called {\bf meet}.   
\end{df}



\begin{df}
A {\bf lattice} is a partially ordered set in which every two elements have a supremum and an infimum.
\end{df}

\begin{df}
A {\bf complete lattice} is a partially ordered set in which every subset has a supremum.
\end{df}

\begin{e}
Show that every subset has an infimum in a complete lattice. 
\end{e}
\end{document}