\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*{Lawvere theory} \hypertarget{context}{}\subsubsection*{{Context}}\label{context} \hypertarget{higher_algebra}{}\paragraph*{{Higher algebra}}\label{higher_algebra} [[!include higher algebra - contents]] \hypertarget{contents}{}\section*{{Contents}}\label{contents} \noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak \noindent\hyperlink{definition}{Definition}\dotfill \pageref*{definition} \linebreak \noindent\hyperlink{remarks}{Remarks}\dotfill \pageref*{remarks} \linebreak \noindent\hyperlink{variations}{Variations}\dotfill \pageref*{variations} \linebreak \noindent\hyperlink{examples}{Examples}\dotfill \pageref*{examples} \linebreak \noindent\hyperlink{TheoryOfSets}{The theory of sets}\dotfill \pageref*{TheoryOfSets} \linebreak \noindent\hyperlink{the_theory_of_groups}{The theory of groups}\dotfill \pageref*{the_theory_of_groups} \linebreak \noindent\hyperlink{OtherExamples}{Other examples}\dotfill \pageref*{OtherExamples} \linebreak \noindent\hyperlink{CharacterizationOfExamples}{Characterization of examples}\dotfill \pageref*{CharacterizationOfExamples} \linebreak \noindent\hyperlink{SomeNonExamples}{Some non-examples}\dotfill \pageref*{SomeNonExamples} \linebreak \noindent\hyperlink{properties}{Properties}\dotfill \pageref*{properties} \linebreak \noindent\hyperlink{coequalizers_of_algebras}{Coequalizers of $T$-algebras}\dotfill \pageref*{coequalizers_of_algebras} \linebreak \noindent\hyperlink{FreeAlgebras}{Free $T$-algebras and underlying sets}\dotfill \pageref*{FreeAlgebras} \linebreak \noindent\hyperlink{AdjCatAlgs}{Adjunctions of relatively free $T$-algebras}\dotfill \pageref*{AdjCatAlgs} \linebreak \noindent\hyperlink{CoLimitsOfTAlgebras}{Limits and colimits of $T$-algebras}\dotfill \pageref*{CoLimitsOfTAlgebras} \linebreak \noindent\hyperlink{an_open_problem}{An open problem}\dotfill \pageref*{an_open_problem} \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} The notion of \emph{Lawvere theory} is a joint generalization of the notions of [[group]], [[ring]], [[associative algebra]], etc. In his [[Functorial Semantics of Algebraic Theories|1963 doctoral dissertation]], Bill Lawvere introduced a new categorical method for doing [[universal algebra]], alternative to the usual way of presenting an algebraic concept by means of its logical [[signature (in logic)|signature]] (with generating operations satisfying equational axioms). The rough idea is to define an [[algebraic theory]] as a [[category]] with finite [[product]]s and possessing a ``generic algebra'' (e.g., a generic [[group]]), and then define a [[model]] of that [[theory]] (e.g., a group) as a product-preserving [[functor]] out of that [[category]]. This type of category is what is nowadays called a \emph{Lawvere algebraic theory}, or just Lawvere theory. \hypertarget{definition}{}\subsection*{{Definition}}\label{definition} \begin{udefn} A \textbf{Lawvere [[theory]]} or \textbf{finite-product theory} is (equivalently encoded by its [[syntactic category]] which is) a [[category]] $T$ with finite [[products]] in which every [[object]] is [[isomorphism|isomorphic]] to a finite cartesian power $x^n = x \times x \times \cdots \times x$ of a distinguished object $x$ (called the \emph{generic object} for the theory $T$). A \emph{[[homomorphism]]} of such theories $T \to T'$ is a product-preserving [[functor]]. \end{udefn} \begin{uremark} For $T$ a Lawvere theory, we are to think of the [[hom-set]] $T(n,1) := T(x^n, x)$ as the set of $n$-ary operations definable in the theory. For instance for $T$ the theory of [[abelian group]]s, $T(2,1)$ includes operations like $+ \colon (x, y) \mapsto x + y$, $- \colon (x, y) \mapsto x-y$, and $(x, y) \mapsto 2 x - 3 y$. For $0$-ary or nullary operations, we have $T(0,1) = \{0\}$. \end{uremark} \begin{udefn} A \textbf{[[model]]} of $T$ -- an \textbf{[[algebra over a Lawvere theory|algebra over the Lawvere theory]]} or simply \textbf{$T$-algebra} -- is a product-preserving [[functor]] \begin{displaymath} A : T \to Set \,, \end{displaymath} and \emph{homomorphism of $T$-algebras} is a [[natural transformation]] between such functors. \end{udefn} \begin{uremark} Such a functor picks out a single [[set]] $U(A) := A(1)$ and picks for every $n$-ary abstract operation $\phi \in T(n,1)$ an actual $n$-ary operation on the elements of this set \begin{displaymath} A(\phi) : U(A)^n \to U(A) \end{displaymath} such that these operations are all compatible with each other in the way governed by the composition rules of morphisms in $T$. \end{uremark} \hypertarget{remarks}{}\subsubsection*{{Remarks}}\label{remarks} \begin{enumerate}% \item It is common to adopt the ([[principle of equivalence]] violating) convention that every object of $T$ is \emph{equal} to a chosen power of $x$. Thus, if $Fin$ is the category of finite cardinals and functions between them, then the unique (up to isomorphism) product-preserving functor $Fin^{op} \to T$ that takes the 1-element cardinal to $x$ is commonly supposed to be surjective on objects (rather than, in better accord with equivalence, [[essentially surjective functor|essentially surjective]]), or even an isomorphism on objects so that each morphism $x^n \to x$ has a well-defined [[signature (in logic)|arity]] $n$. \item Some people use `finite-product theory' to mean any (small) category with [[finite products]], reserving `Lawvere theory' to refer to finite product theories with the property that every object is isomorphic to a product of finitely many copies of a given object $x$. Finite-product theories $C$ can be regarded as a special case of \href{https://ncatlab.org/toddtrimble/published/multisorted+Lawvere+theories}{multisorted Lawvere theories} (see below) where the set of sorts is $Ob(C)$ itself. Some, but not all, the above discussion generalizes to this case. \item As \emph{finite-product theories}, Lawvere theories are at one end of a spectrum of [[theory|theories]] of differing logical strengths. For example, there are left exact theories, [[regular theory|regular theories]], geometric theories, and so on, which require for their interpretation categories of differing degrees of strength in their [[internal logic]]. See also [[classifying topos]]. \item If $C$ is a category with finite products, then a group (object) in $C$ may be defined as a product-preserving functor $T_{Grp} \to C$. For example, a topological group may be identified with a functor $T_{Grp} \to Top$, and a Lie group with a product-preserving functor $T_{Grp} \to Man$ into the category of smooth [[manifold]]s. An analogous statement holds for any finitary algebraic theory, when formulated in terms of its Lawvere theory $T$. \end{enumerate} \hypertarget{variations}{}\subsubsection*{{Variations}}\label{variations} \begin{itemize}% \item A \textbf{multisorted} or multityped Lawvere theory for a given set of sorts $S$ is a category with finite products $C$ together with a function $i: S \to Ob(C)$ such that every object of $C$ is isomorphic to a finite product of objects of the form $i(S)$. An example is the theory for ring-module pairs, which may be regarded as a two-sorted theory in which one sort is interpreted as a ring and the other as a module over that ring. \item An [[infinitary Lawvere theory]] allows for infinitary operations. An example is the theory of [[suplattices]], where we have, for every [[cardinal number]] $n$, an operation to take the [[supremum]] of $n$ elements. While Lawvere theories correspond to finitary monads on $Set$, infinitary Lawvere theories correspond to arbitrary monads. \item A [[Fermat theory]] is a Lawvere theory equipped with a notion of differentiation. \item A finite-product theory can also be presented without including all the products of the basic types as actual objects. This yields the notion of [[cartesian multicategory]]. \end{itemize} \hypertarget{examples}{}\subsection*{{Examples}}\label{examples} \hypertarget{TheoryOfSets}{}\subsubsection*{{The theory of sets}}\label{TheoryOfSets} The tautological example of a Lawvere theory is the algebraic theory of \emph{no} operations. This is also called the \textbf{theory of equality}. Its syntactic category is the category $\mathcal{S}$ on objects $n \in \mathbb{N}$ with morphisms generated by the projections $\pi_i : n \to 1$. This is the [[opposite category]] of the category [[FinSet]] \begin{displaymath} \mathcal{S} \simeq FinSet^{op} \,. \end{displaymath} This is the [[initial object]] in the category of Lawvere theories. An algebra over this theory is just a bare [[set]]: \begin{displaymath} \mathcal{S} Alg \simeq Set \,. \end{displaymath} For $T$ any Lawvere theory, there is a canonical morphism $\mathcal{S} \to T$. On categories of algebras this induces the functor \begin{displaymath} U_T : T Alg \to \mathcal{S}Alg \simeq Set \,. \end{displaymath} This sends each algebra to its \emph{underlying set} . For more on this see the section \hyperlink{FreeAlgebras}{Free T-algebras} below. \hypertarget{the_theory_of_groups}{}\subsubsection*{{The theory of groups}}\label{the_theory_of_groups} We consider here the theory of [[group]]s (defined however you like). To get the corresponding Lawvere theory $T$, let $F(n)$ (for any natural number $n \geq 0$) be a free group on $n$ generators, and define the Lawvere theory $T_{Grp}$ to be the category [[opposite category|opposite]] to the category of free groups $F(n)$ and group homomorphisms. The generic object $x$ of $T_{Grp}$ is taken to be $F(1)$. The category of free groups has finite coproducts since $F(m) + F(n) \cong F(m+n)$ (in other words, the inclusion \begin{displaymath} FreeGroup \hookrightarrow Group \end{displaymath} creates coproducts in $FreeGroup$), so $T_{Grp}$ has finite products, and we have $F(n) = x^n$ in $T_{Grp}$. Any group $G$ defines a product-preserving functor \begin{displaymath} T_{Grp} = FreeGroup^{op} \hookrightarrow Group^{op} \stackrel{\hom(-, G)}{\to} Set \end{displaymath} since contravariant hom-functors take coproducts to products. Thus any group gives a model of $T_{Grp}$. The other direction is more interesting. Let \begin{displaymath} M: T_{Grp} \to Set \end{displaymath} be a model of $T_{Grp}$, i.e., a product-preserving functor. We will define a group structure on $G = M(x)$, the underlying set of the group. To understand this, let's consider how group multiplication would be defined. The idea is that $x$ in $T_{Grp}$ is a ``generic group'', so we first need to understand how multiplication works there. The idea is that the product in the generic group \begin{displaymath} m: x^2 \to x^1 \end{displaymath} corresponds to a homomorphism \begin{displaymath} F(1) \to F(2) \end{displaymath} which by freeness corresponds to an element $1 \to F(2)$, and the element we are after should be the product $a b$ of the generators $a, b$ of the free group $F(2) = F(a, b)$. The generators $a, b$ themselves correspond to the two coproduct inclusions \begin{displaymath} i_1: F(1) \to F(1) + F(1) = F(2) \qquad i_2: F(1) \to F(1) + F(1) = F(2) \end{displaymath} Then, since $M$ is assumed to [[exact functor|preserve products]], we obtain a map \begin{displaymath} G \times G = M(x) \times M(x) \cong M(x^2) \stackrel{M(m)}{\to} M(x) = G \end{displaymath} and this defines the group multiplication on $G$. The group identity and group inversion on $G$ are defined by following similar recipes. It may be checked that the notion of homomorphism of $T_{Grp}$-models (as defined above) coincides with the usual notion of group homomorphism. In summary, the category of groups is equivalent to the category of models of $T_{Grp}$. In particular, any hom-functor \begin{displaymath} \hom_{T_{Grp}}(x^n, -): T_{Grp} \to Set \end{displaymath} preserves products, and so defines a group. This group is precisely the free group on $n$ generators, and a little thought shows that the $n$ generators correspond to the natural transformations \begin{displaymath} \hom_{T_{Grp}}(x, -) \to \hom_{T_{Grp}}(x^n, -) \end{displaymath} induced by the $n$ projection maps $x^n \to x$. All of the discussion above for the case of groups generalizes to any finitary [[algebraic theory]] (i.e., any single-sorted theory whose signature consists of function symbols of finite arity, subject to universally quantified equational axioms). In summary: \begin{itemize}% \item The Lawvere theory $T$ is the category opposite to the category of free algebras on finitely many generators, \item The category of algebras is in turn equivalent to the category of product-preserving functors $T \to Set$, and \item The free algebras are retrieved as the representable functors $T \to Set$. \end{itemize} As discussed in the article on [[operad|operads]], the notion of Lawvere theory may also be formulated in terms of operads relative to the theory of [[cartesian monoidal category|cartesian monoidal categories]]. \hypertarget{OtherExamples}{}\subsubsection*{{Other examples}}\label{OtherExamples} Most of the standard structures that are considered in [[algebra]] indeed are models of algebraic/Lawvere theories in the precise sense. The following list gives a few familiar examples and a few not so familiar ones, but there are many more. Beware though that there are also some familiar examples that seem to be algebraic but are not, these we discuss \hyperlink{SomeNonExamples}{below}. \begin{itemize}% \item For $k$ a [[field]], the category of \emph{free $k$-associative algebras} is the (syntactic category of the) theory of ordinary [[associative algebras]] over $k$. \item for $G$ a fixed [[group]], then $G$-[[actions]] ([[permutation representations]]) are an example of algebras over a Lawvere theory \item for $R$ a fixed [[ring]], then $R$-[[modules]] are an example \item for $k$ a [[field]], then [[Lie algebras]] over $k$ are an example \item The category of say [[distributive lattices]] is the category of algebras of a Lawvere theory. So is the category of [[Heyting algebras]]. \item The category [[CartSp]] is the (syntactic category of the) theory of [[smooth algebras]] (as used in [[synthetic differential geometry]]). This is also a [[Fermat theory]]. \item The terminal Lawvere theory has exactly one morphism $f \colon m \to n$ for each $m,n$. This is apparently the theory of idempotent commutative monoids. \end{itemize} \hypertarget{CharacterizationOfExamples}{}\subsubsection*{{Characterization of examples}}\label{CharacterizationOfExamples} If $T$ is any [[theory]] given by a [[signature]] consisting of finitary [[operations]] (but no [[relations]]) on a single [[sort]], and a set of [[axioms]] all of which are [[universal quantifier|universally quantified]] [[equations]] between terms, then a model of $T$ can be described as an algebra of a Lawvere theory. This includes most cases arising in a typical undergraduate course in modern algebra, as the examples \hyperlink{OtherExamples}{above} suggest. There are also well-known criteria for a category of single-sorted structures $C$, with underlying set-functor $U: C \to Set$, to be the category of algebras of a Lawvere theory. \begin{theorem} \label{RecognizingAConcreteCategoryAsAlgebrasOverALawvereTheory}\hypertarget{RecognizingAConcreteCategoryAsAlgebrasOverALawvereTheory}{} A [[concrete category]] $U \colon C \to Set$ is a category of algebras over a Lawvere theory precisely if $U$ \begin{enumerate}% \item is [[monadic functor|monadic]] \item is \emph{finitary} in that it preserves [[filtered colimits]]. \end{enumerate} \end{theorem} Another characterization is: \begin{example} \label{BirkhoffHSP}\hypertarget{BirkhoffHSP}{} \textbf{([[Birkhoff's HSP theorem]])} Suppose given a [[language]] $L$ generated by a set of (single-sorted) finitary operations, and a [[class]] $C$ of [[structures]] for $L$. Then $C$ is the class of models for a set of universally quantified equations between terms of $L$ if and only if \begin{enumerate}% \item (H) The class is closed under homomorphic [[images]], \item (S) The class is closed under subalgebras, \item (P) The class is closed under taking products. \end{enumerate} \end{example} \hypertarget{SomeNonExamples}{}\subsubsection*{{Some non-examples}}\label{SomeNonExamples} Here are some notable examples of mathematical structures that look algebraic, but are not models of an algebraic theory in the present sense: \begin{itemize}% \item The class of [[fields]] is not the class of algebras of a Lawvere theory. \item Neither is the class of [[integral domains]]. \end{itemize} This might seem obvious since multiplicative inversion in fields is not a global operation, or otherwise the cancellation law of multiplication in integral domains is not a universally quantified axiom (since we have to make an exception of $0$). But one should be careful that there isn't some sneaky alternative axiomatization for these structures which counters these objections! The first clause in Theorem \ref{RecognizingAConcreteCategoryAsAlgebrasOverALawvereTheory} already rules out fields, since $U$ in that case will create [[limits]] in $C$, but the category of fields does not even have [[products]]. Similarly for [[integral domains]]. The second clause in Theorem \ref{RecognizingAConcreteCategoryAsAlgebrasOverALawvereTheory} suggests another type of non-example: \begin{itemize}% \item The category $SLat$ of [[sup-lattices]] is not the category of algebras of a (finitary) Lawvere theory. \end{itemize} There is a whole class of infinitary sup-operations for sup-lattices (one for every arity = cardinal), but again one may wonder how one rules out any alternative finitary axiomatizations. But this is fairly clear by invoking the second clause and considering the following example: if $U: SLat \to Set$ created filtered colimits, then the countable copower $\mathbb{N} \cdot \mathbf{2}$ of 2-element sup-lattices (which turns out to be the power set $P(\mathbb{N})$ with its usual order) would be the filtered colimit (in fact a union) over finite subsets $S$ of finite copowers $S \cdot \mathbf{2}$, hence a countable union of finite sup-lattices, which is clearly impossible. \hypertarget{properties}{}\subsection*{{Properties}}\label{properties} \hypertarget{coequalizers_of_algebras}{}\subsubsection*{{Coequalizers of $T$-algebras}}\label{coequalizers_of_algebras} \begin{udef} Let $T$ be a Lawvere theory and $A$ a $T$-algebra. A \textbf{[[congruence]]} on $A$ is an [[equivalence relation]] on the set $A(1)$ such that whenever for all $n \in \mathbb{N}$ whenever any $(a_i \in A(1))_{i=1}^n$ and $(b_i \in A(1))_{i=1}^n$ are pairwise eqivalent, $a_i \sim b_i$, then also for every operation $f \in T(n,1)$ the results are equivalent: $f(a_1, \cdot, a_n) \sim f(b_1, \cdots , b_n)$. \end{udef} \begin{ulemma} For $A$ a $T$-algebra and for every [[relation]] $R \subset A(1) \times A(1)$ there is a smallest \hyperlink{congruence}{congruence} on $A$ containing $R$. Write $\langle R \rangle \subset A(1) \times A(1)$ for this smallest congruence. \end{ulemma} \begin{uprop} For $A$ a $T$-algebra and $C$ a congruence on $A$, the relation $A/C(f) \subset (A/C)^n \times A/C$ induced by $A(f)$ for each $f : \in T(n,1)$ are functions and define a $T$-algebra structure on $A(1)/C$. \end{uprop} \begin{uprop} For $f,g : A \to B$ two morphisms of $T$-algebras, the canonical morphism $B \to B/\langle \f(a)\sim g(a) | a \in A(1)\rangle$ is the [[coequalizer]] of $f$ and $g$. \end{uprop} \hypertarget{FreeAlgebras}{}\subsubsection*{{Free $T$-algebras and underlying sets}}\label{FreeAlgebras} Write $\mathcal{S}$ for the (syntactic category of the) algebraic theory of sets (described \hyperlink{TheoryOfSets}{above}). Then for $T$ any other (syntactic category of a) Lawvere theory, there is a canonical morphism \begin{displaymath} i_T : \mathcal{S} \to T \,. \end{displaymath} By precomposition with $i_T$ we obtain a corresponding functor on $T$-algebras, which we write \begin{displaymath} U_T : T Alg \to Set \end{displaymath} and call the \textbf{underlying set} functor. \begin{ulemma} The functor $U_T$ has a [[left adjoint]] $F_T : Set \to T Alg$. \end{ulemma} This is a standard example of a [[free functor]], called the \textbf{free $T$-algebra functor}. \begin{proof} For $S \in$ [[Set]], let $F_T(S)$ be the $T$-algebra whose underlying set is the set of formal expressions $\{f(s_1, \cdots, s_n) | f \in T(n,1), s_i \in S\}$ with the evident composition operation. \end{proof} \begin{ulemma} For $S = (n) \in$ [[FinSet]] a \emph{finite set} with $n$ elements , the free $T$-algebra on $S$ is just the [[representable functor|representable]] \begin{displaymath} F_T(S) = T(n,-) : T \to Set \,. \end{displaymath} The adjunction isomorphism \begin{displaymath} T Alg(F_T(S), A) \simeq Set(S, U_T(A)) \simeq (A(1))^n \simeq A(n) \end{displaymath} is in this case just the [[Yoneda lemma]]. \begin{displaymath} T Alg(T(n,-),A) \simeq A(n) \,. \end{displaymath} Notice that this extends to a functor \begin{displaymath} F_T(-) : FinSet \to T Alg \end{displaymath} which is the composite \begin{displaymath} F_T(-) : FinSet \stackrel{i_T^{op}}{\to} T^{op} \stackrel{j}{\to} T Alg \end{displaymath} of the [[Yoneda embedding]] with the opposite of the canonical functor $i_T : FinSet^{op} \simeq \mathcal{S} \to T$ from the theory of sets, described \hyperlink{TheoryOfSets}{above}. More generally, for $S \in Set$ not necessarily finite, let $Sub(S)$ be the [[poset]] of finite subsets of $S$ and their inclusions. Then $F_T(S)$ is the [[filtered colimit]] of the representables corresponding to the finite subsets \begin{displaymath} F_T(S) \simeq {\lim_{\to}}_{{n \in Sub(S)}} T(n,-) \,. \end{displaymath} As discussed \hyperlink{CoLimitsOfTAlgebras}{below}, these filtered colimits of $T$-algebras are computed objectwise. \end{ulemma} \hypertarget{AdjCatAlgs}{}\subsubsection*{{Adjunctions of relatively free $T$-algebras}}\label{AdjCatAlgs} The following establishes that more generally any morphism of Lawvere theories leads to an adjunction between their categories of algebras. Let $T_1$ and $T_2$ be Lawvere theories and $f : T_1 \to T_2$ a morphism. Write $f^* : T_2 Alg \to T_1 Alg$ for the functor on categories of algebras induced by precomposition with $f$. \begin{ulemma} The functor $f^*$ has a [[left adjoint]] $f_* : T_1 Alg \to T_2 Alg$. \end{ulemma} \begin{proof} Here is an elementary proof: Let $F_{T_i} \dashv U_{T_i}$ be the two \hyperlink{FreeAlgebras}{free algebra/underlying-set adjunctions}. For $A$ a $T_1$-algebra there is a $T_1$-\hyperlink{congruence}{congruence} $\Gamma$ such that \begin{displaymath} A \simeq F_{T_1} U_{T_1}(A) / \Gamma \,. \end{displaymath} Since for any set $S$ we have $U_{T_1} F_{T_1}(S) \subset U_{T_2} F_{T_2}(S)$ it follows that $\Gamma \subset T_{T_2} F_{T_2} U_{T_1}(A)$. For $\langle \Gamma \rangle$ the smallest $T_2$-congruence containing $\Gamma$ we have that $F_{T_2} U_{T_1}(A) / \langle \Gamma \rangle$ is a $T_2$-algebra. This one checks is $f_* A$. Here is a more high-powered way to obtain this using the [[monad]]s $K_i$ whose algebras are $T_i$-algebras: for $A$ a $T_1$-algebra let $f_* A := K_2 \circ_{K_1} A$ the the evident reflexive [[coequalizer]] \begin{displaymath} K_2 K_1 A \stackrel{\to}{\to} K_2 A \to K_2 \circ_{K_1} A \end{displaymath} in $T_2 Alg$. \end{proof} \hypertarget{CoLimitsOfTAlgebras}{}\subsubsection*{{Limits and colimits of $T$-algebras}}\label{CoLimitsOfTAlgebras} \begin{uprop} For $T$ a Lawvere theory, the category $T Alg$ has all small [[limit]]s and [[colimit]]s. The [[limit]]s and the [[filtered colimit]]s in $T Alg$ are computed pointwise. \end{uprop} \hypertarget{an_open_problem}{}\subsection*{{An open problem}}\label{an_open_problem} A [[Higman's embedding theorem|famous result by G. Higman]] in group theory says that a finitely generated group can be embedded in a finitely presented group precisely if it has a presentation whose defining relations are a recursively enumerable set of words. Clearly, this question can be asked for every similar algebraic theory and it has been in fact conjectured by the group theorist W. Boone that the same result holds more generally for every single-sorted algebraic theory. It has been urged by [[F. W. Lawvere]] on several occasions that this [[Boone conjecture]] should be settled by the category theory community. \hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts} \begin{itemize}% \item [[algebraic theory]] / [[generalized algebraic theory]] / \textbf{Lawvere theory} / [[2-Lawvere theory]] [[(∞,1)-algebraic theory]] \item [[enriched Lawvere theory]] \item [[globular theory]] \item [[lambda theory]] \item [[monad]] / [[(∞,1)-monad]] \item [[operad]] / [[(∞,1)-operad]] \item [[PRO]] \item [[PROP]] \item [[C-systems]] \item [[Boone conjecture]] \item [[Freyd category]] \end{itemize} \hypertarget{references}{}\subsection*{{References}}\label{references} The origin of the categorical formulation of [[algebraic theories]] as Lawvere theories is in \begin{itemize}% \item [[William Lawvere]], [[Functorial Semantics of Algebraic Theories]] , Ph.D. thesis Columbia University (1963). Published with an author's comment and a supplement in: Reprints in Theory and Applications of Categories \textbf{5} (2004) pp 1--121. (\href{http://www.tac.mta.ca/tac/reprints/articles/5/tr5abs.html}{abstract}) \end{itemize} The concept was then streamlined in \begin{itemize}% \item [[Samuel Eilenberg]], J. B. Wright, \emph{Automata in General Algebras} , Information and Control \textbf{11} (1967) pp.452-470. \end{itemize} Also still worthwhile reading are the following early papers: \begin{itemize}% \item [[Gavin Wraith]], \emph{Algebraic Theories} , Aarhus Lecture Notes Series no.22 (1969). (\href{http://homepages.inf.ed.ac.uk/s0894694/scans/wraith-algebraic-theories.pdf}{pdf, 3,7MB}) \item [[Gavin Wraith]], \emph{Algebras over Theories} , Colloquium Mathematicum \textbf{XXIII} no.2 (1971) pp.181-190. (\href{https://eudml.org/doc/archive%5Cdsc_569f%5Cdsc_40fc%5C/bwmeta1.element.desklight-374f9cbc-939c-4bdb-8b0c-c21872987c9a/full-text/cm23_2_01.pdf}{pdf}) \end{itemize} An early textbook treatment was in \begin{itemize}% \item [[Bodo Pareigis]], \emph{Categories and Functors} , New York: Academic Press 1970. (chap. 3; \href{https://epub.ub.uni-muenchen.de/7244/}{link}) \end{itemize} Modern textbook treatments are \begin{itemize}% \item [[Francis Borceux]], \emph{Handbook of categorical algebra 2 -- Categories and structures} , Encyclopedia of Mathematics and its Applications, Cambridge UP 1994. (chap. 3) \item M. C. Pedicchio, F. Rovatti, \emph{Algebraic Categories} , pp.269-310 in Pedicchio, Tholen (eds.), \emph{Categorical Foundations} , Encyclopedia of Mathematics and its Applications \textbf{97}, Cambridge UP 2004. \end{itemize} A recent monograph is \begin{itemize}% \item [[Jiri Adamek|J. Adámek]], [[Jiri Rosicky|J. Rosicky]], [[Enrico Vitale|E. M. Vitale]], \emph{Algebraic Theories - a Categorical Introduction to General Algebra} , Cambrige UP 2010. (\href{http://www.iti.cs.tu-bs.de/~adamek/algebraic_theories.pdf}{draft}) \end{itemize} The concept of an internal algebraic theory in topos theory is dicussed in \begin{itemize}% \item [[Peter Johnstone]], [[Gavin Wraith]], \emph{Algebraic theories in toposes} , pp.141-242 in LNM \textbf{661} Springer Heidelberg 1978. \item [[Peter Johnstone]], \emph{Topos Theory} , Academic Press New York 1977. (Dover reprint 2014; sec. 6.4, pp.190-198) \end{itemize} For a comparison with the concept of monads see \begin{itemize}% \item [[Martin Hyland]], [[John Power]], \emph{The Category Theoretic Understanding of Universal Algebra: Lawvere Theories and Monads} , Electronic Notes in Theor. Comp. Sci. \textbf{172} (2007) pp.437-458. (\href{https://www.dpmms.cam.ac.uk/~martin/Research/Publications/2007/hp07.pdf}{preprint}) \end{itemize} [[distributive law|Distributive laws]] for algebraic theories are discussed in \begin{itemize}% \item [[Eugenia Cheng]], \emph{Distributive laws for Lawvere theories} , arXiv:1112.3076 (2011). (\href{http://arxiv.org/abs/1112.3076}{abstract}) \end{itemize} Voevodsky proves an equivalence between Lawvere theories and l-bijective [[C-systems]] here: \begin{itemize}% \item [[Vladimir Voevodsky]] , Lawvere theories and C-systems, arXiv:1512.08104 (2015). (\href{http://arxiv.org/abs/1512.08104}{abstract}) \end{itemize} Other references are \begin{itemize}% \item M. Jibladze, T. Pirashvili, \emph{Cohomology of Algebraic Theories} , J. Algebra \textbf{137} no.2 (1991) pp.253--296. \item [[Steve Lack]], [[Jiri Rosicky]], \emph{Notions of Lawvere theory} , arXiv:0810.2578. (\href{http://arxiv.org/abs/0810.2578}{abstract}) \item [[Enrico Vitale]], \emph{Localization of Algebraic Categories} , JPAA \textbf{108} (1996) pp.315-320. \item [[Enrico Vitale]], \emph{Localization of Algebraic Categories 2} , JPAA \textbf{133} (1998) pp.317-326. \end{itemize} Lawvere theories, and finitary monads, are identified with certain [[enriched categories]] and the passage from one to the other with a [[cocompletion]], in \begin{itemize}% \item [[Richard Garner]], \emph{Lawvere theories, finitary monads and Cauchy-completion}, 2013, \href{https://arxiv.org/abs/1307.2963}{arxiv} \item [[Richard Garner]] and [[John Power]], \emph{An enriched view on the extended finitary monad--Lawvere theory correspondence}, 2017, \href{https://arxiv.org/abs/1707.08694}{arxiv} \end{itemize} [[!redirects lawvere theory]] [[!redirects Lawvere theory]] [[!redirects Lawvere theories]] [[!redirects finitary Lawvere theory]] [[!redirects finitary Lawvere theories]] [[!redirects finite-product theory]] [[!redirects finite-product theories]] [[!redirects finite product theory]] [[!redirects finite product theories]] [[!redirects finite-products theory]] [[!redirects finite-products theories]] [[!redirects finite products theory]] [[!redirects finite products theories]] \end{document}