\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}} \input{tcilatex} \begin{document} \section*{Problems and Comments For Section 4} \vspace{1pt} \textbf{Problems: }4.4, 4.9, 4.10, 4.15, 4.17, \vspace{1pt} \textbf{Comments: }For integers $m$ and $n$ we define that \textit{\ }$m$% \textit{\ divides }$n$\textit{, }written \textit{\ }$m|n,$ in case that there is some $k$ such that $k\cdot m=n.$ We have, \begin{enumerate} \item $1|n;n|0.$ \item $n|m$ and $m|n$ if and only if $n=\pm m.$ \item If $a|b$ and $a|c$ then $a|(b+c)$ \end{enumerate} Instead of saying that $a$ divides $b$ we also say that $b$\textit{\ is a multiple of }$a.$ \vspace{1pt} The \textit{greatest common divisor }(g.c.d.) $d=(m,n)$ of $m$ and $n$ is defined by \begin{enumerate} \item $d|m$ and $d|n.$ \item If $e|m$ and $e|n$ the $e|d.$ \end{enumerate} The g.c.d. is unique up to its sign. After you have read section 4, you should be able to prove the following \begin{proposition} The g.c.d $d\ $of $m$ and $n$ is the only common divisor of $m$ and $n$ which is of the form $d=am+bn.$ \end{proposition} The \textit{lowest common multiple }(l.c.m.) $u=[m,n]$ of $m$ and $n$ is defined by \begin{enumerate} \item $m|u$ and $n|u.$ \item If $m|v$ and $n|v$ then $u|v.$ \end{enumerate} The l.c.m. is unique up to its sign. A \textit{partial order} $\leq $ on a set $P$ is a \textit{reflexive, anti-symmetric and transitive }relation\textit{. }That is, for all $a,b,c\in P$ we have that: \begin{enumerate} \item $a\leq a.$ \item If $a\leq b$ and $b\,\leq a$ then $a=b.$ \item If $a\,\,\leq b$ and $b\leq c$ then $a\leq c.$\newline $(P,\leq )$ is called a \textit{poset}, or \textit{partially ordered} set. A poset is called a \textit{totally ordered} set, or a \textit{chain}, if in addition we have \item $a\,\,\leq b$ $\ $or $b\leq a.$ \end{enumerate} \vspace{1pt} Divisibility restricted to the non-negative integers is a partial order. All real numbers form with respect to ordinary ordering a chain. An element $u\in P$ is called an \textit{upper bound} of the subset $S$ of $% P $ if $u\geq s$ holds for all $s\in S.$An upper bound for $S$ that belongs to $S$ is called the \textit{maximum} of $S.$ Prove that a set $S$ can have at most one maximum. \textit{Lower bounds} and \textit{minima} are similarly defined. \vspace{1pt} A subset $S$ of the poset $P$ is \textit{bounded above} if it admits an upper bound. A bounded subset is one that admits an upper as well as a lower bound. For the open interval $(0,1)$ of the totally ordered set $(% %TCIMACRO{\U{211d} }% %BeginExpansion \mathbb{R} %EndExpansion ,\leq )$ of real numbers, every number $r\geq 1$ is an upper bound and $1$ is the \textit{least upper bound}. Similarly, $0$ is the \textit{largest lower bound} for $(0,1).$ \vspace{1pt} If we restrict divisibility to non-negative integers, then any common divisor of $a$ and $\ b$ is a lower bound of $S$ and the greatest common divisor is the largest lower bound. Similarly, any common multiple of $a$ and $b$ is an upper bound for $S$ and the lowest common multiple is the least upper bound. \vspace{1pt} The least upper bound of a subset $S$ of $P$ is called the \textit{supremum} or \textit{join} of $S:$ \[ \sup (S)=\bigvee \{s|~s\in S\} \] The largest lower bound of a subset $S$ of $P$ is called the \textit{infimum } or \textit{meet} of $S:$ \[ \inf (S)=\bigwedge \{s|~s\in S\} \] \vspace{1pt} A partially ordered set $(L,\leq )$ is called a \textit{lattice} if every two-element subset $S=\{a,b\}$ of $L$ has a join, denoted as $a\vee b$ and meet, denoted as $a\wedge b.$We have that the set $(% %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion ^{+},|)$ of non-negative numbers together with divisibility is a lattice; $0$ is the maximum of this lattice where $1$ is the minimum. (This is the only case where $a|b$ but $a>b$) \vspace{1pt} A \textit{complete lattice} is a bounded partially ordered set where every non-empty subset has an infimum as well as a supremum. The power set of a set $X$ is a complete lattice under set inclusion $\subseteq :$ For any system $\mathbf{S}$ of subsets of $X$ the join is the union of the sets in $% \mathbf{S}$ while the meet is the intersection: \[ \bigvee \mathbf{S=}\dbigcup \mathbf{S,}\dbigwedge \mathbf{S}=\dbigcap \mathbf{S} \] If $\mathbf{S=\{}A,B\}$ then the intersection $D=A\cap B$ of $\mathbf{S=\{}% A,B\}$ is the largest subset of $X,$ which is contained in $A$ and $B.$ Similarly, the union $U=A\cup B$ is the smallest \ subset of $X$ which contains $A$ and $B.$ \vspace{1pt} In a complete lattice $L$, the infimum of $\mathbf{S}=\emptyset $ is defined as the maximum of $L$ while the supremum of $\mathbf{S}=\emptyset $ is defined as the minimum of $L.$With this convention in mind, we can drop boundedness in the definition of a complete lattice. In particular, for the powerset lattice $(\mathbf{P}(X),\subseteq )$ of a set $X,$ we define: \[ \bigvee \emptyset =\emptyset ,\dbigwedge \emptyset =X \] The following is not very difficult to prove: \begin{theorem} A bounded poset $(P,\leq )$ is already a complete lattice if every subset has an infimum. \end{theorem} \end{document}