
\documentclass{article}
\usepackage{amsfonts, amssymb}
\usepackage{amsmath}
\usepackage{latexsym}
\addtolength{\textwidth}{3.5cm}
\addtolength{\oddsidemargin}{-2cm}
\addtolength{\topmargin}{-3.cm}
\addtolength{\textheight}{3.25cm}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mbb}[1]{\mathbb{#1}}
\newcommand{\alp}{\alpha}
\newcommand{\bet}{\beta}
\pagestyle{empty}
\begin{document}

\hfill \textbf{September 12, 2014}

\vspace{1 cm}
\centerline{ \textbf{\large{Homework 2 \hspace{1 cm} Math  6302}}}

\vspace {1 cm}
\begin{enumerate}



\medskip
\item
Let $A$ be any set. We assume that all of its elements $a$ are sets.   Show that the set $R(A) = \{ a|a \in A,a \notin a\} $
 is not an element of $A$. 
\item For any set $A$, let $B$ be the set of all
 second coordinates of ordered pairs that belong to $A$. Then let $C = \{ (a,R(B))|a \in A\} .$
 Show that $A \cap C = \emptyset .$
 Hence, for any set $A$  there is a set $C$ that is disjoint and equipotent to $A$.


\item An injective $\varphi$  map from the partially ordered set $(P,\leq)$ to the partially ordered set $(Q,\leq)$ is called an order embedding if $\varphi(x)\leq \varphi(y)$ iff $x\leq y$. A bijective order embedding is an order isomorphism.  That is, $\varphi^{-1}$ is monotone. Prove:  Any ordered set can be embedded into an ordered set that has a minimum and a maximum.
\item
Any  partial order on a finite  set can be extended  to  a total order.  This "process"  is called topological sorting.

\item Assume that every subset of the partially ordered set $(L,\leq)$ has an infimum. Prove that  every subset has a supremum.


\item  A reflexive and transitive relation $R$ on a set $S$ is called a \textit{quasi-order}.
 Show that $$a \sim_R b \Leftrightarrow a\; R\; b\mbox{ and }b\;R\;a$$
 is an equivalence  relation on $S$. On $S/ \!\sim_R$
 a partial order $\leq_R$ can be
  defined
 \[
 [s]\leq[t]\;\mbox{ iff } sRt
 \]
 $(S,\leq_R)$ is called the \textit{contraction} of the quasiorder $R$.


\medskip
\item
Let $
f:(S,R) \twoheadrightarrow (S/ \sim_R , \leqslant )
$
, $
s \mapsto [s]
$
, be the contraction-map
 of the quasi-order $
(S,R)$
. Then $f$ is increasing , i.e., $
s_1 Rs_2  \Rightarrow [s_1 ] \leqslant [s_2 ]
$
 , and any increasing map $
h:\;(S,R) \to (T, \leqslant )
$
 from $
(S,R)
$
 into an ordered set $
(T, \leqslant )
$
 factors over f, i.e., $
h = g \circ f
$
 for a \textbf{ uniquely determined} increasing map $
g:\,(S/ \sim_R , \leqslant ) \to (T, \leqslant )
$
. One says, $
f:\,(S,R) \twoheadrightarrow  (S/ \sim_R , \leqslant )
$
is \textit{universal} for all increasing maps $
h:\,(S,R) \to (T, \leqslant )
$
. Show: If $
f':\,(S,R) \to (C, \leqslant )
$
 is also universal for all increasing maps from $
(S,R)$ into ordered sets $
(T, \leqslant )
$
, then one has that $
(S/_R , \leqslant ) \cong (C, \leqslant ).
$
\end{enumerate}
\end{document}.
