\documentclass[12pt,titlepage]{article} \usepackage{amsmath} \usepackage{mathrsfs} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{mathtools} \usepackage{graphicx} \usepackage{color} \usepackage{ucs} \usepackage[utf8x]{inputenc} \usepackage{xparse} \usepackage{hyperref} %----Macros---------- % % Unresolved issues: % % \righttoleftarrow % \lefttorightarrow % % \color{} with HTML colorspec % \bgcolor % \array with options (without options, it's equivalent to the matrix environment) % Of the standard HTML named colors, white, black, red, green, blue and yellow % are predefined in the color package. Here are the rest. \definecolor{aqua}{rgb}{0, 1.0, 1.0} \definecolor{fuschia}{rgb}{1.0, 0, 1.0} \definecolor{gray}{rgb}{0.502, 0.502, 0.502} \definecolor{lime}{rgb}{0, 1.0, 0} \definecolor{maroon}{rgb}{0.502, 0, 0} \definecolor{navy}{rgb}{0, 0, 0.502} \definecolor{olive}{rgb}{0.502, 0.502, 0} \definecolor{purple}{rgb}{0.502, 0, 0.502} \definecolor{silver}{rgb}{0.753, 0.753, 0.753} \definecolor{teal}{rgb}{0, 0.502, 0.502} % Because of conflicts, \space and \mathop are converted to % \itexspace and \operatorname during preprocessing. % itex: \space{ht}{dp}{wd} % % Height and baseline depth measurements are in units of tenths of an ex while % the width is measured in tenths of an em. \makeatletter \newdimen\itex@wd% \newdimen\itex@dp% \newdimen\itex@thd% \def\itexspace#1#2#3{\itex@wd=#3em% \itex@wd=0.1\itex@wd% \itex@dp=#2ex% \itex@dp=0.1\itex@dp% \itex@thd=#1ex% \itex@thd=0.1\itex@thd% \advance\itex@thd\the\itex@dp% \makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}} \makeatother % \tensor and \multiscript \makeatletter \newif\if@sup \newtoks\@sups \def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}% \def\reset@sup{\@supfalse\@sups={}}% \def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else% \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}% \else \append@sup#2 \@suptrue \fi% \expandafter\mk@scripts\fi} \def\tensor#1#2{\reset@sup#1\mk@scripts#2_/} \def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2% \reset@sup\mk@scripts#3_/} \makeatother % \slash \makeatletter \newbox\slashbox \setbox\slashbox=\hbox{$/$} \def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$} \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa \copy\slashbox \kern-\@tempdima \box\@tempboxa} \def\slash{\protect\itex@pslash} \makeatother % math-mode versions of \rlap, etc % from Alexander Perlis, "A complement to \smash, \llap, and lap" % http://math.arizona.edu/~aprl/publications/mathclap/ \def\clap#1{\hbox to 0pt{\hss#1\hss}} \def\mathllap{\mathpalette\mathllapinternal} \def\mathrlap{\mathpalette\mathrlapinternal} \def\mathclap{\mathpalette\mathclapinternal} \def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}} \def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}} \def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}} % Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2} \let\oldroot\root \def\root#1#2{\oldroot #1 \of{#2}} \renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}} % Manually declare the txfonts symbolsC font \DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n} \SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n} \DeclareFontSubstitution{U}{txsyc}{m}{n} % Manually declare the stmaryrd font \DeclareSymbolFont{stmry}{U}{stmry}{m}{n} \SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n} % Manually declare the MnSymbolE font \DeclareFontFamily{OMX}{MnSymbolE}{} \DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n} \SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n} \DeclareFontShape{OMX}{MnSymbolE}{m}{n}{ <-6> MnSymbolE5 <6-7> MnSymbolE6 <7-8> MnSymbolE7 <8-9> MnSymbolE8 <9-10> MnSymbolE9 <10-12> MnSymbolE10 <12-> MnSymbolE12}{} % Declare specific arrows from txfonts without loading the full package \makeatletter \def\re@DeclareMathSymbol#1#2#3#4{% \let#1=\undefined \DeclareMathSymbol{#1}{#2}{#3}{#4}} \re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46} \re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12} \re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64} \re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6} \re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77} \re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77} \makeatother % \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE \makeatletter \def\Decl@Mn@Delim#1#2#3#4{% \if\relax\noexpand#1% \let#1\undefined \fi \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}} \def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}} \def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}} \Decl@Mn@Open{\llangle}{mnomx}{'164} \Decl@Mn@Close{\rrangle}{mnomx}{'171} \Decl@Mn@Open{\lmoustache}{mnomx}{'245} \Decl@Mn@Close{\rmoustache}{mnomx}{'244} \makeatother % Widecheck \makeatletter \DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}} \def\@widecheck#1#2{% \setbox\z@\hbox{\m@th$#1#2$}% \setbox\tw@\hbox{\m@th$#1% \widehat{% \vrule\@width\z@\@height\ht\z@ \vrule\@height\z@\@width\wd\z@}$}% \dp\tw@-\ht\z@ \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@ \setbox\tw@\hbox{% \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box \tw@}}}% {\ooalign{\box\tw@ \cr \box\z@}}} \makeatother % \mathraisebox{voffset}[height][depth]{something} \makeatletter \NewDocumentCommand\mathraisebox{moom}{% \IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{% \IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}% }{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}% \mathpalette\@temp{#4}} \makeatletter % udots (taken from yhmath) \makeatletter \def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.} \mkern2mu\raise4\p@\hbox{.}\mkern1mu \raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}} \makeatother %% Fix array \newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}} %% \itexnum is a noop \newcommand{\itexnum}[1]{#1} %% Renaming existing commands \newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}} \newcommand{\widevec}{\overrightarrow} \newcommand{\darr}{\downarrow} \newcommand{\nearr}{\nearrow} \newcommand{\nwarr}{\nwarrow} \newcommand{\searr}{\searrow} \newcommand{\swarr}{\swarrow} \newcommand{\curvearrowbotright}{\curvearrowright} \newcommand{\uparr}{\uparrow} \newcommand{\downuparrow}{\updownarrow} \newcommand{\duparr}{\updownarrow} \newcommand{\updarr}{\updownarrow} \newcommand{\gt}{>} \newcommand{\lt}{<} \newcommand{\map}{\mapsto} \newcommand{\embedsin}{\hookrightarrow} \newcommand{\Alpha}{A} \newcommand{\Beta}{B} \newcommand{\Zeta}{Z} \newcommand{\Eta}{H} \newcommand{\Iota}{I} \newcommand{\Kappa}{K} \newcommand{\Mu}{M} \newcommand{\Nu}{N} \newcommand{\Rho}{P} \newcommand{\Tau}{T} \newcommand{\Upsi}{\Upsilon} \newcommand{\omicron}{o} \newcommand{\lang}{\langle} \newcommand{\rang}{\rangle} \newcommand{\Union}{\bigcup} \newcommand{\Intersection}{\bigcap} \newcommand{\Oplus}{\bigoplus} \newcommand{\Otimes}{\bigotimes} \newcommand{\Wedge}{\bigwedge} \newcommand{\Vee}{\bigvee} \newcommand{\coproduct}{\coprod} \newcommand{\product}{\prod} \newcommand{\closure}{\overline} \newcommand{\integral}{\int} \newcommand{\doubleintegral}{\iint} \newcommand{\tripleintegral}{\iiint} \newcommand{\quadrupleintegral}{\iiiint} \newcommand{\conint}{\oint} \newcommand{\contourintegral}{\oint} \newcommand{\infinity}{\infty} \newcommand{\bottom}{\bot} \newcommand{\minusb}{\boxminus} \newcommand{\plusb}{\boxplus} \newcommand{\timesb}{\boxtimes} \newcommand{\intersection}{\cap} \newcommand{\union}{\cup} \newcommand{\Del}{\nabla} \newcommand{\odash}{\circleddash} \newcommand{\negspace}{\!} \newcommand{\widebar}{\overline} \newcommand{\textsize}{\normalsize} \renewcommand{\scriptsize}{\scriptstyle} \newcommand{\scriptscriptsize}{\scriptscriptstyle} \newcommand{\mathfr}{\mathfrak} \newcommand{\statusline}[2]{#2} \newcommand{\tooltip}[2]{#2} \newcommand{\toggle}[2]{#2} % Theorem Environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{prop}{Proposition} \newtheorem{cor}{Corollary} \newtheorem*{utheorem}{Theorem} \newtheorem*{ulemma}{Lemma} \newtheorem*{uprop}{Proposition} \newtheorem*{ucor}{Corollary} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{example}{Example} \newtheorem*{udefn}{Definition} \newtheorem*{uexample}{Example} \theoremstyle{remark} \newtheorem{remark}{Remark} \newtheorem{note}{Note} \newtheorem*{uremark}{Remark} \newtheorem*{unote}{Note} %------------------------------------------------------------------- \begin{document} %------------------------------------------------------------------- \section*{partial order} \hypertarget{context}{}\subsubsection*{{Context}}\label{context} \hypertarget{category_theory}{}\paragraph*{{$(0,1)$-Category theory}}\label{category_theory} [[!include (0,1)-category theory - contents]] \hypertarget{category_theory_2}{}\paragraph*{{Category theory}}\label{category_theory_2} [[!include category theory - contents]] \hypertarget{contents}{}\section*{{Contents}}\label{contents} \noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak \noindent\hyperlink{definitions}{Definitions}\dotfill \pageref*{definitions} \linebreak \noindent\hyperlink{as_a_set_with_extra_structure}{As a set with extra structure}\dotfill \pageref*{as_a_set_with_extra_structure} \linebreak \noindent\hyperlink{as_a_preorder_with_antisymmetry}{As a preorder with antisymmetry}\dotfill \pageref*{as_a_preorder_with_antisymmetry} \linebreak \noindent\hyperlink{AsACategoryWithExtraProperties}{As a category with extra properties}\dotfill \pageref*{AsACategoryWithExtraProperties} \linebreak \noindent\hyperlink{monotone_functions}{Monotone functions}\dotfill \pageref*{monotone_functions} \linebreak \noindent\hyperlink{intervals}{Intervals}\dotfill \pageref*{intervals} \linebreak \noindent\hyperlink{kinds_of_posets}{Kinds of posets}\dotfill \pageref*{kinds_of_posets} \linebreak \noindent\hyperlink{in_higher_category_theory}{In higher category theory}\dotfill \pageref*{in_higher_category_theory} \linebreak \noindent\hyperlink{properties}{Properties}\dotfill \pageref*{properties} \linebreak \noindent\hyperlink{ExtensionToLinearOrder}{Extension to linear order}\dotfill \pageref*{ExtensionToLinearOrder} \linebreak \noindent\hyperlink{LocalesFromPosets}{Locales from posets -- Alexandroff topology}\dotfill \pageref*{LocalesFromPosets} \linebreak \noindent\hyperlink{cauchy_completion}{Cauchy completion}\dotfill \pageref*{cauchy_completion} \linebreak \noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak \noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak \hypertarget{idea}{}\subsection*{{Idea}}\label{idea} A \emph{partial order} on a set is a way of ordering its elements to say that some elements precede others, but allowing for the possibility that two elements may be incomparable without being the same. This is the fundamental notion in [[order theory]]. By regarding the ordering $\leq$ as the existence of a unique [[morphism]], preorders may be regarded as certain [[categories]] (namely, [[thin categories]]). This category is sometimes called the \emph{order category} associated to a partial order; see \hyperlink{AsACategoryWithExtraProperties}{below} for details. \hypertarget{definitions}{}\subsection*{{Definitions}}\label{definitions} \hypertarget{as_a_set_with_extra_structure}{}\subsubsection*{{As a set with extra structure}}\label{as_a_set_with_extra_structure} A poset may be understood as a [[set]] with [[extra structure]]. Given a [[set]] $S$, a \textbf{partial order} on $S$ is a (binary) [[relation]] $\leq$ with the following properties: \begin{itemize}% \item [[reflexive relation|reflexivity]]: $x \leq x$ always; \item [[transitive relation|transitivity]]: if $x \leq y \leq z$, then $x \leq z$; \item [[antisymmetric relation|antisymmetry]]: if $x \leq y \leq x$, then $x = y$. \end{itemize} A \textbf{poset} is a set equipped with a partial order. \hypertarget{as_a_preorder_with_antisymmetry}{}\subsubsection*{{As a preorder with antisymmetry}}\label{as_a_preorder_with_antisymmetry} A poset is precisely a [[proset]] satisfying the extra condition that $x \leq y \leq x$ implies that $x = y$. \hypertarget{AsACategoryWithExtraProperties}{}\subsubsection*{{As a category with extra properties}}\label{AsACategoryWithExtraProperties} A poset may be understood as a [[category]] with [[extra property]], sometimes called its \emph{order category}. A \textbf{poset} is a [[category]] such that: \begin{itemize}% \item for any pair of objects $x, y$, there is at most one morphism from $x$ to $y$ \item if there is a morphism from $x$ to $y$ and a morphism from $y$ to $x$ (which by the above implies that $x$ and $y$ are [[isomorphic]]), then $x = y$. \end{itemize} Equivalently, this says that a poset is a [[skeletal category|skeletal]] [[thin category|thin]] category, or equivalently a skeletal [[category enriched]] over the [[cartesian monoidal category]] of [[truth values]] or equivalently a skeletal [[(0,1)-category]]. When we do this, we are soon led to contemplate a slight generalization of partial orders: namely [[preorder|preorders]]. The reason is that the antisymmetry law, saying that $x \le y$ and $y \le x$ imply $x = y$, violates the [[principle of equivalence]] in a certain sense. (On the other hand, it does not violate it if taken as a \emph{definition} of [[equality]].) \hypertarget{monotone_functions}{}\subsubsection*{{Monotone functions}}\label{monotone_functions} The morphisms of partially ordered sets are [[monotone functions]]; a \textbf{monotone function} $f$ from a poset $S$ to a poset $T$ is a [[function]] from $S$ to $T$ (seen as [[structured sets]]) that preserves $\leq$: \begin{displaymath} x \leq y \;\Rightarrow\; f(x) \leq f(y) . \end{displaymath} Equivalently, it is a [[functor]] from $S$ to $T$ (seen as certain categories). In this way, posets form a [[category]] [[Pos]]. \hypertarget{intervals}{}\subsubsection*{{Intervals}}\label{intervals} A (closed bounded) \textbf{[[interval]]} in a poset $C$ is a set of the form \begin{displaymath} [x,y] = \{r\in C|x\le r\le y\}. \end{displaymath} A poset is \textbf{[[locally finite poset|locally finite]]} if every closed bounded interval is finite. \hypertarget{kinds_of_posets}{}\subsubsection*{{Kinds of posets}}\label{kinds_of_posets} A poset with a [[top element]] and [[bottom element]] is called \textbf{bounded}. (But note that a \emph{[[subset]]} of a poset may be bounded without being a bounded as a poset in its own right.) More generally, it is \textbf{bounded above} if it is has a top element and \textbf{bounded below} if it has a bottom element. A poset with all finite [[meets]] and [[joins]] is called a \textbf{[[lattice]]}; if it has only one or the other, it is still a \textbf{[[semilattice]]}. A poset in which every finite set has an upper bound (but perhaps not a \emph{least} upper bound, that is a join) is a \textbf{[[directed set]]}. As remarked above, a poset in which each interval $[x,y]$ is a [[finite set]] is called \textbf{locally finite} or a \textbf{[[causet]]}. A poset with a bounding [[countable set|countable subset]] is called \textbf{$\sigma$-bounded}. That is, the poset is $\sigma$-bounded above if there exists a sequence $(x_n)_{n=1}^{N}$ (where $N$ is a natural number or infinity) such that for every $y$ in the poset there is an $x_m$ with $y \leq x_m$. (The poset is $\sigma$-bounded below if we have $x_m \leq y$ instead.) Note that every bounded poset is $\sigma$-bounded, but not conversely. Note that some authorities require $N = \infty$; this makes a difference only for the empty poset (we say it is $\sigma$-bounded, they say it is not). \hypertarget{in_higher_category_theory}{}\subsubsection*{{In higher category theory}}\label{in_higher_category_theory} A poset can be understood as a [[(0,1)-category]]. This suggests an obvious [[vertical categorification]] of the notion of poset to that of [[n-poset]]. \hypertarget{properties}{}\subsection*{{Properties}}\label{properties} \hypertarget{ExtensionToLinearOrder}{}\subsubsection*{{Extension to linear order}}\label{ExtensionToLinearOrder} \begin{prop} \label{LinearExtension}\hypertarget{LinearExtension}{} On a [[finite set]], every [[partial order]] may be [[linear extension of a partial order|extended]] to a [[linear order]]. For non-finite sets this still holds with the [[axiom of choice]]. \end{prop} See at \emph{[[linear extension of a partial order]]} \href{linear+extension+of+a+partial+order#LinearExtensionOfAPartialOrder}{this Prop.}. \hypertarget{LocalesFromPosets}{}\subsubsection*{{Locales from posets -- Alexandroff topology}}\label{LocalesFromPosets} \begin{defn} \label{}\hypertarget{}{} For $P$ a poset, write $Up(P)$ for the [[topological space]] whose underlying [[set]] is the underlying set of $P$ and whose [[open subset]]s are the \emph{upward closed subsets} of $P$: those subsets $U \subset P$ with the property that \begin{displaymath} ((x \in U) and (x \leq y)) \Rightarrow (y \in U) \,. \end{displaymath} This is called the \textbf{[[Alexandroff topology]]} on $P$. \end{defn} \begin{prop} \label{UpIfFFAndPreservesLimits}\hypertarget{UpIfFFAndPreservesLimits}{} This construction naturally extends to a [[full and faithful functor]]. $Up :$ [[Poset]] $\to$ [[Top]] $\to$ [[Locale]]. \end{prop} \begin{prop} \label{}\hypertarget{}{} For $P$ a poset, there is a [[natural equivalence]] \begin{displaymath} Sh(Up(P)) \simeq [P,Set] \end{displaymath} between the [[category of sheaves]] on the [[locale]] $Up(P)$ and the category of [[copresheaves]] on $P$. \end{prop} For more see [[Alexandroff topology]]. \hypertarget{cauchy_completion}{}\subsubsection*{{Cauchy completion}}\label{cauchy_completion} Every poset is a [[Cauchy complete category]]. Posets are the Cauchy completions of [[prosets]]. (\hyperlink{Rosolini}{Rosolini}) \hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts} \begin{itemize}% \item [[preorder]] \item [[continuous poset]] \item [[Noetherian poset]] \item [[specialization topology]] \item [[prefix order]] \end{itemize} \hypertarget{references}{}\subsection*{{References}}\label{references} \begin{itemize}% \item Richard P. Stanley, Enumerative [[combinatorics]], vol I \href{http://www-math.mit.edu/~rstan/ec/ec1.pdf}{pdf} \end{itemize} [[Cauchy completion]] of prosets and posets is discussed in \begin{itemize}% \item G. Rosolini, \emph{A note on Cauchy completeness for preorders} (\href{http://www.disi.unige.it/person/RosoliniG/notccp.pdf}{pdf}) \end{itemize} Here are some references on [[directed homotopy theory]]: \begin{itemize}% \item [[Marco Grandis]], \emph{Directed homotopy theory, I. The fundamental category} (\href{http://arxiv.org/abs/math.AT/0111048}{arXiv}) \item [[Tim Porter]], \emph{Enriched categories and models for spaces of evolving states}, Theoretical Computer Science, 405, (2008), pp. 88--100. \item [[Tim Porter]], \emph{Enriched categories and models for spaces of dipaths. A discussion document and overview of some techniques} (\href{http://drops.dagstuhl.de/opus/volltexte/2007/898/pdf/06341.PorterTimothy.Paper.898.pdf}{pdf}) \end{itemize} [[!redirects poset]] [[!redirects posets]] [[!redirects partial orders]] [[!redirects partial ordering]] [[!redirects partial orderings]] [[!redirects partially ordered]] [[!redirects partially ordered set]] [[!redirects partially ordered sets]] [[!redirects partially-ordered]] [[!redirects partially-ordered set]] [[!redirects partially-ordered sets]] [[!redirects bounded poset]] [[!redirects bounded posets]] [[!redirects order category]] [[!redirects order categories]] \end{document}