\documentclass{amsart}

\usepackage{tikz}
\usepackage{ulem}
\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 3}
\maketitle

\section{Graphs}
\begin{df}
A $\langle V,E\rangle$ is a {\bf graph} iff $V$ is a set (of vertexes) and $E$ (edges) is a symmetric binary relation on $V$.   
\end{df}

\begin{df}
A graph is called {\bf $k$-colorable} if there is a coloring of the vertexes
such that no two adjacent vertices having the same color.
\end{df}

\begin{thm}[Erd\H os--De Bruijn]
A graph is $k$-colorable iff its every finite subgraph is $k$-colorable.
\end{thm}

\section{Partial orders}

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

\begin{proof}
Let $\langle X, \le \rangle$ be a poset. Let graph $\langle X,
E\rangle$ be defined as follows: $E(x,y)\iff x\not\le y \land y\not\le
x$, i.e., we connect the incomparable elements of $\langle X,\le\rangle$. Graph $\langle X,
E\rangle$ is $n$-colorable iff $\langle X,\le \rangle$ can be
partitioned into $n$ chains. Therefore, the statement follows from
(the finite version of) Dilworth theorem and Erd\H os--De Bruijn theorem.
\end{proof}


\begin{e}
Construct a partial order in which there is an $n$-element antichain for all natural number $n$, but it does not contain an infinite antichain. 
\end{e}

\begin{thm}[Wolk--Perles]
For all infinite cardinal $\kappa$ there is a partial order $P$ such
that $w(P)=\aleph_0$, but every chain partition of $P$ contains at least $\kappa$ chains.   
\end{thm}


\section{Binary relations}

\begin{df}
Let $X$ and $Y$ be two sets and let $R$ and $S$ be two binary
relations on them, respectively.  $\langle X, R\rangle$ is called {\bf
  isomorphic} to $\langle Y, S\rangle$ if there is a bijection
$f:X\rightarrow Y$ such that $\langle x,y\rangle\in R \iff \langle
f(x),f(y)\rangle\in S$. In this case, $f$ is called an {\bf
  isomorphism} between $\langle X, R\rangle$ and $\langle Y, S\rangle$.
\end{df}

\begin{ex}
Partial ordered sets  $\langle \N, \le\rangle$ and   $\langle \{2^n:n\in \N\}, |\rangle$  are isomorphic, and $f(n)=2^n$ is an isomorphism between them. 
\end{ex}

\section{latices}

\begin{e}
Show that $\langle \N,|\rangle$ is a lattice. 
\end{e}

\begin{e}
Draw the hasse diagrams of (up to isomorphism) all the lattices having at most 5 elements.  
\end{e}



\end{document}