Meaning of Monotone Maps in the context of algebraic theory of boolean circuits

81 Views Asked by At

In the paper, Towards an Algebraic Theory of Boolean Circuits, by Yves Lafont, section 2.2 is Monotone maps.

In general, monotone maps mean functions that always increase/ always decrease with increasing input, and I am not able to map that definition to the treatment of monotone maps in this paper. What do they mean in this context?

I understand that they are morphisms and have two generators, one that takes {1,2} to {1} and another that takes {} to {1}.

I don't understand what these do exactly and what the general definition of a monotone map is here. In the previous section on permutations, it was easy to understand what each morphism was doing, and I would like to have a similar understanding here.

1

There are 1 best solutions below

0
On BEST ANSWER

In that paper the author seems to use "monotone map" to mean "non-decreasing map". So the monotone maps are the functions $f:\{1,\dots, p\}\to \{1,\dots, q\}$ such that $f(x)\leq f(y)$ whenever $x\leq y$. Note that allowing non-decreasing and non-increasing functions wouldn't define a subcategory of the category of finite sets $\{1,\dots, n\}$, since their composition need not be monotone.

The two generators are the maps $\mu:\{1,2\}\to \{1\}$ and $\eta:\{\}\to \{1\}$ (there is only one for each type). The claim that these are generators amount to the fact that every monotone map (in the sense described above) can be described as a composition of a surjective map and an injective one. The surjective map identifies certain numbers, and thus it can be obtained as a composition of factors obtained from $\mu$, while the monotone map skips certain numbers, and thus can be obtained as a composition of factors like $\eta$.

The category described in that section is often called the augmented simplex category, and it is used to define augmented simplicial sets or objects. The augmented part comes from the empty set; if you remove the empty set you get the simplex category (see also the nlab or Wikipedia). Sometimes they are also called the algebraists' simplex category (with the empty set) and the topologists' simplex category (without the empty set).