\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*{cyclic order} \hypertarget{cyclic_orders}{}\section*{{Cyclic orders}}\label{cyclic_orders} \noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak \noindent\hyperlink{definition}{Definition}\dotfill \pageref*{definition} \linebreak \noindent\hyperlink{monotone_functions}{Monotone functions}\dotfill \pageref*{monotone_functions} \linebreak \noindent\hyperlink{remarks}{Remarks}\dotfill \pageref*{remarks} \linebreak \hypertarget{idea}{}\subsection*{{Idea}}\label{idea} If a [[linear order]] is a way of arranging the elements of a set `on a line' (with a direction), then a \emph{cyclic order} is a way of arranging them `on a circle' (with a chosen direction, say clockwise or counterclockwise). Unlike a linear order (and most other things called `order') which are defined as a sort of binary relation, a cyclic order is defined as a sort of \emph{ternary} [[relation]], since on a circle we can't say ``$x$ comes before (or after) $y$'' only ``$x$, $y$, and $z$ come in clockwise (or counterclockwise) order.'' \hypertarget{definition}{}\subsection*{{Definition}}\label{definition} A \textbf{cyclic relation} on a [[set]] $S$ is a ternary [[relation]] $R$ on $S$ such that, if $R(x,y,z)$ for any elements $x, y, z$ of $S$, then $R(y,z,x)$ (and hence also $R(z,x,y)$). Then a \textbf{cyclic order} on $S$ is a cyclic relation $R$ that satisfies ternary versions of the properties of a [[linear order]]: \begin{itemize}% \item Cyclic [[irreflexive relation|irreflexivity]]: If $R(x,y,z)$, then $y \ne z$. \item Cyclic [[asymmetric relation|asymmetry]]: If $R(x,y,z)$ and $R(x,z,w)$, then $y \ne w$. \item Cyclic [[transitive relation|transitivity]]: If $R(x,y,z)$ and $R(x,z,w)$, then $R(x,y,w)$. \item Cyclic [[comparison]]: If $R(x,y,z)$, then for any $w$, $R(x,y,w)$ or $R(x,w,z)$ or $R(w,y,z)$. \item Cyclic [[connected relation|connectedness]]: If $x \ne y$, $x \ne z$, and $y \ne z$, then $R(x,y,z)$ or $R(x,z,y)$. \end{itemize} Actually, none of these order axioms (except for comparison) is really complete as stated; any cyclic permutation of the axiom should also be assumed. However, these permutations all follow automatically for a cyclic relation. Note that for a [[constructive mathematics|constructive]] version, the set $S$ needs to be already equipped with a (tight) [[apartness relation]] for the connectedness axiom to make sense; unlike with a linear order, we can't recover the apartness relation from the cyclic order. For a similar reason, it's difficult to state [[antisymmetric relation|antisymmetry]] correctly for a nonstrict (like a [[total order]]) version of a cyclic order. [[Mike Shulman|Mike]] and [[Toby Bartels|Toby]]: If anyone wants to have a go at a cyclic analogue of a total order, be our guest. As with a linear order, not all of these axioms are needed. In particular, using [[excluded middle]], it's enough if a cyclic relation is transitive and satisfies \begin{itemize}% \item Cyclic trichotomy: For all $x, y, z$, ($x = y$ or $x = z$ or $y = z$) xor $R(x,y,z)$ xor $R(x,z,y)$. \end{itemize} \hypertarget{monotone_functions}{}\subsection*{{Monotone functions}}\label{monotone_functions} An [[injection|injective]] function $f:S\to T$ between cyclically ordered sets is \textbf{strictly monotone} if it preserves the ternary relation $R$, i.e. if $R_S(x,y,z)$ implies $R_T(f(x),f(y),f(z))$. This is the cyclic counterpart of a strictly monotone function between linear orders (one which preserves the relation $\lt$). As in that case, irreflexivity then implies that $f$ is injective as long as $S$ has at least three distinct elements; but in general, this should be stated explicitly (and interpreted in the strongest sense for constructive mathematics). We say that $f$ is merely \textbf{monotone} if it satisfies (either of) the following \emph{equivalent} conditions: \begin{itemize}% \item $f$ reflects the ternary relation $R$, i.e. if $R_T(f(x),f(y),f(z))$ then $R_S(x,y,z)$. \item $f$ preserves the ternary relation $R$ for elements with pairwise distinct images, i.e. if $R_S(x,y,z)$ holds and $f(x)$, $f(y)$, and $f(z)$ are pairwise distinct, then $R_T(f(x),f(y),f(z))$. \end{itemize} This is the cyclic counterpart of a monotone function between linear orders (one which reflects the relation $\lt$). [[Mike Shulman|Mike]]: I just made this up, but it seems right. With a $\le$-version of cyclic orders we could maybe recover monotone functions more directly. Whatever the definition of monotone function is, it should let us recover $\Lambda$ as below. \emph{Toby}: Doubting a $\le$ version and believing that reflecting linear orders is quite natural, I've phrased this entirely in those terms. Also, fixed (in my opinion) the definition of strict monotone function. (It's interesting that this suggests that $\Delta$ should be seen as a category of linearly ordered sets; being finite sets, this is equivalent even constructively.) \hypertarget{remarks}{}\subsection*{{Remarks}}\label{remarks} \begin{itemize}% \item One would like the [[cycle category]] $\Lambda$ to be the category of [[finite set|finite]] [[inhabited set|nonempty]] cyclically ordered sets and monotone functions, just as the [[simplex category]] $\Delta$ is the category of finite nonempty linearly ordered sets and monotone functions. However, this seems to fail for the $0$-cycle, which has a nontrivial loop and is therefore not [[terminal object|terminal]] (unlike the cyclically ordered [[singleton]], which is terminal). \end{itemize} [[Todd Trimble|Todd]]: Guys, I may be confused here, but I'm having a problem: it seems that the empty relation on the 1-element set 1 is a cyclic order (in fact the only one on 1), and therefore (under the definition that monotone functions are those which reflect the cyclic order) that 1 is terminal. But then the category of finite (nonempty) cyclically ordered sets and monotone sets would have to be contractible. How does this square with the homotopy type of Connes' cyclic category (which I'm told is the same as that of $S^1$)? This is the point that I stumbled on in the blog discussion on the cyclic category almost exactly two years ago, when I attempted to give my own description of $\Lambda$ (but using a cyclic analogue of total orders, which you two have challenged readers to give). You can see my attempted description \href{http://golem.ph.utexas.edu/category/2007/06/the_curious_incident_of_the_do.html#c010503}{here}, and my retraction \href{http://golem.ph.utexas.edu/category/2007/06/the_curious_incident_of_the_do.html#c010511}{here}. \emph{Toby}: The problem is that the $0$-cycle (unlike the $[0]$-simplex) should not be a point but instead have a nontrivial loop, is that right? And so it's not terminal, since a map to it from $[n]$ really consists of $n + 1$ binary choices (whether to be a degeneracy or to map to the nontrivial loop). \emph{Todd}: I'm sorry -- I must be making some embarrassingly stupid mistake -- but I still don't follow. What loop? For the 1-element set \{t\}, there are only two ternary relations. The relation consisting of the point (t, t, t) cannot be a cyclic order by irreflexivity. So the only cyclic order is the empty one (which seems to be vacuously allowed by the axioms). And it seems that the condition that the unique map f: C --{\tt \symbol{62}} \{t\} is monotone by Mike's definition, for any cyclically ordered set C, is vacuously satisfied. Trust me -- I want you guys to be right, because I think that the definition of $\Lambda$ I attempted two years ago is (in classical logic) equivalent to yours (although I should check that carefully) -- and I was disappointed when I thought it failed. \emph{Toby}: It's also possible that I'm making an embarrassingly stupid mistake, but if you're making one, then it's probably missing my word `should'. I agree with you that there is a unique cyclic order (as defined here) on the $1$-element set and that this gives the terminal cyclically ordered set. What I'm not certain about is that I understand what the cycle category is supposed to be, but is it right that the $1$-element cycle (the $0$-cycle) \emph{should} have a nontrivial loop? Because if so, then I understand what your objection is! \emph{Todd}: Part of the problem is that I don't have a deep feeling myself for Connes' $\Lambda$. But David Ben-Zvi (I believe) mentioned on the blog that $\Lambda$ has the homotopy type of a circle, meaning I guess that the classifying space of the nerve $B N \Lambda$ has this homotopy type. But the classifying space of a category with a terminal object is contractible. That's the point where I got worried about my own construction, and it's a worry for me here as well: terminal objects would seem to be fatal. \emph{Toby}: OK, so neither of us understands it well enough to be sure. Still, if I get the description as an ordered graph, then I see that there is a problem with maps to the $0$-cycle. The good news is that, looking at your definition of a cyclically reflexive notion of cyclic order, I can no longer imagine why I might have thought that such a thing would not work. Indeed, applying [[de Morgan duality]] to the axioms above for an irreflexive version, we immediately get a reflexive version that is (classically, and even constructively for finite sets) equivalent to your definition. (It's still true that the irreflexive version is probably better from a constructive perspective, much as is true for linear/total orders, because cyclic totality fails for the reflexive ternary order relation on the unit circle in the located Dedekind complex plane, but that's not what was concerning me before, nor is it relevant for finite sets.) [[Mike Shulman]]: Probably this whole discussion should be taking place at [[cycle category]]. According to \href{http://arxiv.org/abs/0809.3341}{Berger-Moerdijk}`s characterization of the cycle category (Example 2.7), I think the $0$-cycle is not terminal. They describe it as the ``total category'' of a certain ``crossed $\Delta$-group'' which is a presheaf $n\mapsto G_n$ of groups on $\Delta$ with certain extra structure; in this case the relevant presheaf sends each set $[n] = \{0,1,\dots,n\}$ to $C_n$, the cyclic group on $n$ letters. The total category of a crossed $\Delta$-group has the same objects as $\Delta$, and the morphisms $[m]\to [n]$ are pairs $(\alpha,g)$ where $\alpha:[m]\to [n]$ in $\Delta$ and $g\in G_m$. Thus, in particular, the morphisms $[m]\to [0]$ in $\Lambda$ can be identified with elements $g\in C_m$, so there is more than one of them. I think I have just lost whatever geometric intuition I used to think I had for the cycle category. [[David Corfield]]: I think I understood it \href{http://golem.ph.utexas.edu/category/2007/06/cohomology_and_computation_wee_6.html#c010094}{once} as ``$\Lambda$ is the category whose objects $[n]$ are circles marked by the sets of $n$ th roots of unity. Maps are degree 1 mappings between circles which send marked points to marked points, and are increasing. This is quite like $\Delta$ but where you are allowed to cycle round the domain before you choose an order-preserving map.'' It's good to see how the morphisms are counted. So $\Lambda$ is a kind of \href{http://golem.ph.utexas.edu/category/2006/10/euler_characteristic_of_a_cate.html#c010304}{product} between $\Delta$ and the groupoid which is a union of one copy of each finite cyclic group. [[!redirects cyclic orders]] [[!redirects cyclic ordering]] [[!redirects cyclic orderings]] [[!redirects cyclically ordered]] [[!redirects cyclically ordered set]] [[!redirects cyclically ordered sets]] \end{document}