(defn irreducible-representation
[family elem]
(let [predecessors (direct-subdimembers family elem)]
(if (= (count predecessors) 1)
(let [predecessor (first predecessors)]
(let [dipredecessors (direct-subdimembers
family
predecessor)]
(if (= (count dipredecessors) 1)
(let [next-coll (frequencies
(irreducible-representation
family
predecessor))]
(Multiset. {(first (keys next-coll))
(inc (first (vals next-coll)))}))
(Multiset. {elem 1}))))
(Multiset. {}))))
(defn clan-representations
[family]
(set
(map
(fn [i]
(let [coll (subdimembers family i)]
(apply
join
(map
(fn [i]
(irreducible-representation family i))
coll))))
(apply union family))))Sunday, August 29, 2021
Multiset representations of partial orders
Every partial order can be embedded in a boolean algebra, by representing each element of the poset as sets. A natural generalisation of this is to represent each element of the poset as a multiset. In order to do this, we need to determine when an element is a multiple of another. This occurs when it has at most one irreducible predecessor. This is implemented below.
Thursday, August 26, 2021
Real representations of total orders
We previously scratched the surface of total order theory. Additional perspective is provided by embeddings in the real number line $(\mathbb{R},\leq)$. A fundamental theorem of Hausdorff states that every countable total order is embedded in $\mathbb{Q}$, and so that forms the basis of this subject.
The set of all total order types is preordered by inclusion. As a consequence, total order types can generally be understood by their location within this preorder. Although this forms a preorder in general, the subset of well orders forms a total order, as does the set of all inverse well orders.
An example of a total order type whose subtypes don't form a total order is $\mathbb{Z}$. The integral order $\mathbb{Z}$ has two predecessor order types: $\omega$ and $\omega^*$ both of which are incomparable to one another. The predecessors of $\mathbb{Z}$ still form a partial order. Finally, all countable total orders which are non-scattered are embeddable in one another by the theorem of Hausdorff.
A real representation embeds a total order in $\mathbb{R}$. The selection of $\mathbb{R}$ as the target for an order embedding is motivated by the fact that any countable total order can be embedded in it. With respect to its order topology, $\mathbb{R}$ is a complete dense topological space.
The notion of that total order types are preordered by size plays a role in our approach to embeddings. A key invariant is the sequence size, which is essentially the number of limit points that a given total order can have in an embedding. Sequence size is monotone over the embedding order.
The sequence size is one instance whereby we can get a better understanding of total orders by real embeddings. While $\mathbb{Z}$ and $\mathbb{N}$ are both topologically discrete, they have different topological behaviour with respect to embeddings. $\mathbb{Z}$ can have two limit points while $\mathbb{N}$ can only have one. While they have the same internal topological behaviour, they behave differently externally.
As a geometric realisation of a total order, an embedding function $f: T \to \mathbb{R}$ provides a total order with a one dimensional geometry. The fact that every countable order can be embedded in $\mathbb{R}$ means that any total order can be given a one dimensional geometric realisation.
A consequence of order embedding in the continuous real number line is that an embedded linear order can have limit points, while its total order doesn't have any. This gets around the limitations of studying total orders by their own order topologies.
Although the real number line $\mathbb{R}$ is among the simplest manifolds, its subsets can still exhbit remarkable behaviour because they are part of a continuum. Total orders which you might not otherwise consider to be related to $\mathbb{R}$ can be embedded within in it by going deep into its infinite continuum
The class of total orders with order embeddings between them forms a category. The preorder on isomorphism types of total orders we previously discussed is simply the object preorder of this category of total order embeddings modulo isomorphism. This provides an entirely categorical descriptive of the preorder on total order types.
Real representations $f: T \to \mathbb{R}$ form a comma category within the category of order embeddings. A real representation $f: T \to \mathbb{R}$ is embedded within another real representation $g: U \to \mathbb{R}$ provided there exists a morphism $h : T \to U$ such that $g \circ h = f$.
The real numbers $\mathbb{R}$ themselves are considered to form a complete Archimedean ordered field which is simultaneously a topological field by its order topology. Some of the basic field operations of $\mathbb{R}$ are useful in constructing real representations, and so we will need to make reference to some of their basic order-theoretic properties.
Two well orders of type $\omega+1$ are $\{1-\frac{1}{n},1\}$ and $\{ 1-\frac{1}{n},2 \}$. The distinction between the two is that the first includes its limit point and the second doesn't. So a distinctione xists between rather or not an embedding $f : \omega+1 \to \mathbb{R}$ includes its limit point or not.
A key realisation of real representation theory is that the sequence size determines the capability of a total order to have limits externally, even while the total order may not have any limits within itself internally. Total orders $\omega$ and $\omega^{*}$ both have a discrete order topology, but they still determining limit points in embeddings.
Consider the scattered total order $\rightarrow \leftarrow \rightarrow \leftarrow$ then this can have up to four limit points or it can have two bidirectional limit points. An example of this is the real representation $1\pm \frac{1}{n}, 2\pm \frac{1}{n}$. An example of the later is $1-\frac{1}{n},2+\frac{1}{n},3-\frac{1}{n},4-\frac{1}{n}$.
A finite ordinal like $n\omega$ can be visualized as a sequence of rightarrows $\rightarrow \rightarrow \rightarrow ...$. These can be constructed in the familiar manner we have done so far by subtracting an infinitesimal value from a limit point. So for example $4\omega$ can be represented by $1-\frac{1}{n},2-\frac{1}{n},3-\frac{1}{n},4-\frac{1}{n}$. Dually, an inverse ordinal $4\omega^*$ can be represented by adding an infinitesimal value to a sequence of values: $1+\frac{1}{n},2+\frac{1}{n},3+\frac{1}{n},4+\frac{1}{n}$.
We can represent $2\mathbb{Z}$, the order type of two integer order types by a series by adjoining a bidirectionally convergent limit point to the integers like $\{-n,1+\pm \frac{1}{n},n \}$. All these different methods together constitute a sufficient basis for the theory of representation of total orders of finite sequence size.
Infinite sequence size
As we can construct a total order embedding for any total order of finite sequence size $n$, we can continue this process to construct a total order with infinite sequence size. A first example is the order embedding $f : \omega^2 \to \mathbb{R}$ of the infinite sequence size ordinal $\omega^2$ into $\mathbb{R}$ determinined by subtracting an infinitesimal value from each positive integer: \[ \{n - \frac{1}{m} : n,m \in \mathbb{Z}_+ \} \] A natural dualization of this is to construct the ordinal $(\omega^2)^{*}$ by taking the set of negative integers and adding an infinitesimal value to each of them. Then this produces an embedding of the inverse ordinal $(\omega^2)^{*}$ in the real numbers $\mathbb{R}$. \[ -n + \frac{1}{m} : n,m \in \mathbb{Z} \] The integers squared $\mathbb{Z}^2$ can be constructed by taking each integer and adding and subtracting an infinitesimal value from it. In this case, each integer is the bidirectional limit point of both an infinite sequence asceding into it and an infinite sequence descending into it. \[ \{n \pm \frac{1}{m} : n \in \mathbb{Z}, m \in \mathbb{Z} - \{0\} \} \] In each case we can take a discrete set of points in $\mathbb{R}$ and we turn them into limit points by adding or subtracting a vanishing value from them. This works for any finite or discrete set of limit points, but more advanced methods are required to embed larger total order types in $\mathbb{R}$.
In the previous section of infinite sequence size total orders, we constructed the first examples of embeddings whose order types are infinite and they are all necessarily discrete and of the form $\omega$,$\omega^*$, or $\mathbb{Z}$. The limit points of these sets of limit points are all either positive or negative infinity.
The fact that the set of limit points of a total order can themselves have limit points, means that there exists a concept of higher limits. These are the limit points of the limit points of a total suborder of the real numbers. These higher limit points are the basis of the next step in the classification of the total suborders of the real numbers.
The higher limit points of a scattered total order don't need to be infinite as we will see. These higher limit points can represent any real number, furthermore they can be nested. So we can form higher limit points of higher limit points, and so on. These higher limit points form the next step in our classification of total orders.
The first ordinal larger then any exponential tower of ordinals is $\epsilon_0$, then any other ordinal number constructed so far can be embedded in $\epsilon_0$. In order to get a real representation of $\epsilon_0$ the reader is referred to the work of Jeff Erickson on fusible numbers [2].
The fusible numbers are constructed recursively so that a fusible number is $0$ or $\frac{a+b+1}{2}$ with $a$ and $b$ fusible numbers and $|a-b| \leq 1$. Then the fact that the fusible numbers are scattered ordered, any exponential tower can be constructed from them.
As fusible numbers are constructed recursively, the definition of real suborder with larger order types will require the use of recursive formulas. With this primitive recursive ordinals can be embedded in the continuum.
References:
[1] Real number line
[2] Fusible numbers
The set of all total order types is preordered by inclusion. As a consequence, total order types can generally be understood by their location within this preorder. Although this forms a preorder in general, the subset of well orders forms a total order, as does the set of all inverse well orders.
An example of a total order type whose subtypes don't form a total order is $\mathbb{Z}$. The integral order $\mathbb{Z}$ has two predecessor order types: $\omega$ and $\omega^*$ both of which are incomparable to one another. The predecessors of $\mathbb{Z}$ still form a partial order. Finally, all countable total orders which are non-scattered are embeddable in one another by the theorem of Hausdorff.
A real representation embeds a total order in $\mathbb{R}$. The selection of $\mathbb{R}$ as the target for an order embedding is motivated by the fact that any countable total order can be embedded in it. With respect to its order topology, $\mathbb{R}$ is a complete dense topological space.
The notion of that total order types are preordered by size plays a role in our approach to embeddings. A key invariant is the sequence size, which is essentially the number of limit points that a given total order can have in an embedding. Sequence size is monotone over the embedding order.
The sequence size is one instance whereby we can get a better understanding of total orders by real embeddings. While $\mathbb{Z}$ and $\mathbb{N}$ are both topologically discrete, they have different topological behaviour with respect to embeddings. $\mathbb{Z}$ can have two limit points while $\mathbb{N}$ can only have one. While they have the same internal topological behaviour, they behave differently externally.
Geometry of linear orders:
The real number line forms a topological manifold: the simplest example of such. In geometric topology, it is one of only two connected manifolds of dimension one, the other being the circle manifold.As a geometric realisation of a total order, an embedding function $f: T \to \mathbb{R}$ provides a total order with a one dimensional geometry. The fact that every countable order can be embedded in $\mathbb{R}$ means that any total order can be given a one dimensional geometric realisation.
A consequence of order embedding in the continuous real number line is that an embedded linear order can have limit points, while its total order doesn't have any. This gets around the limitations of studying total orders by their own order topologies.
Although the real number line $\mathbb{R}$ is among the simplest manifolds, its subsets can still exhbit remarkable behaviour because they are part of a continuum. Total orders which you might not otherwise consider to be related to $\mathbb{R}$ can be embedded within in it by going deep into its infinite continuum
Algebra of total orders:
A total order is a subtotal commutative semigroup: it is a commutative semigroup $S$ for which $Sub(S)$ is equal to $\wp(S)$. Every subset of a total order is a subsemilattice, because the join/meet of a finite set of elements of a total order is always contained within that set. This provides an internally semigroup-theoretic perspective on total order theory.The class of total orders with order embeddings between them forms a category. The preorder on isomorphism types of total orders we previously discussed is simply the object preorder of this category of total order embeddings modulo isomorphism. This provides an entirely categorical descriptive of the preorder on total order types.
Real representations $f: T \to \mathbb{R}$ form a comma category within the category of order embeddings. A real representation $f: T \to \mathbb{R}$ is embedded within another real representation $g: U \to \mathbb{R}$ provided there exists a morphism $h : T \to U$ such that $g \circ h = f$.
The real numbers $\mathbb{R}$ themselves are considered to form a complete Archimedean ordered field which is simultaneously a topological field by its order topology. Some of the basic field operations of $\mathbb{R}$ are useful in constructing real representations, and so we will need to make reference to some of their basic order-theoretic properties.
Finite total orders:
The smallest non-trivial total order is the total order on a single element $T_1$. Real representations of this form consist of the selection of a single element from $\mathbb{R}$. This could be anything from $1,2,3,4,1/2,2/3,-15/2,\sqrt{17},\sqrt{23},\frac{1+\sqrt{5}}{2}$ to something trascendental like $e,\pi,\frac{\pi^2}{6}$, etc \[ f : T_1 \to \mathbb{R} \] The next case is the total order on two elements $T_2$. A real representation of a total order on two elements is of course any pair of real numbers such as $\{1,2\}$. All pairs of real numbers are the same with respect to order type, but they can have different geometric properties such as distance. \[ f : T_2 \to \mathbb{R} \] To cut a long story short, every real representation of a finite total order on $n$ elements is equivalent to an $n$ element subset of $\mathbb{R}$. We can define a rank complete homogeneous family of sets $F$ consisting of all $n$ element subsets of $\mathbb{R}$. Then a bijection can be formed between $F$ and real representations in the hom class $Hom(T_n,\mathbb{R})$. \[ F = \{ s : s \subseteq \mathbb{R} \wedge |s| = n \} \] The bijection $f : F \to Hom(T_n,\mathbb{R})$ solves the classification of real embeddings of finite total orders completely. Finite total orders are basically a trivial case as far as the classification of total orders goes.Sequence size one
In the hierarchy of complexity of total orders, the simplest infinite total orders are those which are sequence size one. These are total orders whose real representations have no more then a single limit point. These finite limit points can be either finite of infinite. An example is $\omega$ which can be embedded in $\mathbb{R}$ by either $-\frac{1}{n}$ $\mathbb{Z}_+$. \[ -1,-\frac{1}{2},-\frac{1}{3},-\frac{1}{4}, ... \] \[ 1,2,3,4,5,6,7,8,9,... \] The dual concept is that of a decreasing sequence which has order type $\omega^{*}$. As before, these can be either diverging like the negative integers $\mathbb{Z}_{-}$ or converging like $\frac{1}{n}$. Increasing and decreasing sequences $\omega$ and $\omega^*$ are the simplest building blocks of all infinite total orders. \[ ...,\frac{1}{4},\frac{1}{3},\frac{1}{2},1 \] \[ ...,-9,-8,-,7,-6,-5,-4,-3,2,-1\] Of course, infinite total orders like these don't need to have trivial limits like zero. Any real number is a limit point of infinite and decreasing sequences in an infinite number of ways. For example, the infinite series formula for calculating $e$ determines an infinite increasing sequence with $\omega$ order type: \[ 1,2,2+\frac{1}{2},2+\frac{2}{3},2+\frac{17}{24},2+\frac{43}{60},... \] The addition of points beyond the limit like with $\omega+n$ and $n+\omega^{*}$ does nothing to change the number of limit points in the total order, so they are both technically of sequence size one. In either case, the addition of points beyond the limit necessitates that the total order is bounded because there are no points beyond infinity in an Archimedean totally ordered field.Two well orders of type $\omega+1$ are $\{1-\frac{1}{n},1\}$ and $\{ 1-\frac{1}{n},2 \}$. The distinction between the two is that the first includes its limit point and the second doesn't. So a distinctione xists between rather or not an embedding $f : \omega+1 \to \mathbb{R}$ includes its limit point or not.
A key realisation of real representation theory is that the sequence size determines the capability of a total order to have limits externally, even while the total order may not have any limits within itself internally. Total orders $\omega$ and $\omega^{*}$ both have a discrete order topology, but they still determining limit points in embeddings.
Sequence size two
The integers $\mathbb{Z}$ form a discrete total order, and so they are topologically isomorphic to $\omega$ and $\omega^*$ but they have a different behaviour under embedding because they can have two limit points. Therefore, we can say that $\mathbb{Z}$ has sequence size two. The limit points of $\mathbb{Z}$ can be either finite or infinite. $\mathbb{Z}$ has infinite limit points while $-1+\frac{1}{n},1-\frac{1}{n}$ has finite limit points $-1$ and $1$. \[ ...,-2,1,0,1,2,... \] \[ ...,-\frac{3}{4},-\frac{2}{3},-\frac{1}{2},0,\frac{1}{2},\frac{2}{3},\frac{3}{4},...\] The order type $\omega + \omega^*$ has two types of limiting behaviour: common convergence and separate convergence. Common converge means that the two sequences of the embedding produce the same limit point: an example is $\pm \frac{1}{n}$ which converges to zero from both sides. The total order $-1-\frac{1}{n},1+\frac{1}{n}$ on the other hand converges separately to one and negative one. \[ -1,-\frac{1}{2},-\frac{1}{3},-\frac{1}{4}...\frac{1}{4},\frac{1}{3},\frac{1}{2},1 \] \[ -2,-1-\frac{1}{2},-1-\frac{1}{3},1-\frac{1}{4},...,1+\frac{1}{4},1+\frac{1}{3},1+\frac{1}{2},2\] The previous two order types $\mathbb{Z}$ and $\omega + \omega^*$ are the two sequence size two order types that are neither well orders nor inverse well orders. The basic example of a well order with sequence size two is $2\omega$. These total orders can have either a limit point at infinity like $\{1-\frac{1}{n},n\}$ or two finite limit points $\{1-\frac{1}{n},2-\frac{1}{n}\}$. \[ 0,\frac{1}{2},\frac{2}{3},\frac{3}{4},...,1,2,3,..\] \[ 0,\frac{1}{2},\frac{2}{3},\frac{3}{4}...,1,1+\frac{1}{2},1+\frac{2}{3},...\] This naturally has a dualization the order transpose of the ordinal $2\omega$ consisting of two sequences both going in the decreasing direction. As before, these can have at most one infinite limit point and the other limit point must be finite. \[ ...-3,-2,-1,...-\frac{3}{4},-\frac{2}{3},-\frac{1}{2},0 \] \[ ...-1-\frac{2}{3},-1-\frac{1}{2},-1, ...,-\frac{3}{4},-\frac{2}{3},-\frac{1}{2},0 \] These four types consistute all the types of total order types that are sequence size two except for the inclusion of individual points along the infinite sequences. Only the order type $\omega + \omega^*$ can have bidirectional convergenece and only $\mathbb{Z}$ can have two infinite limit points.Finite sequence sizes:
The sequences of a total order can be represented as directions in the real number line so that $\omega$ is equal to $\rightarrow$, $\omega^*$ is $\leftarrow$, $\mathbb{Z}$ is $\leftrightarrow$, bidirectional converge is $\rightarrow \leftarrow$, $2\omega$ is $\rightarrow \rightarrow$, and ${2\omega}^*$ is $\leftarrow \leftarrow$. The order type of a finite sequence size total order can always be represented by a finite sequence of arrows.Consider the scattered total order $\rightarrow \leftarrow \rightarrow \leftarrow$ then this can have up to four limit points or it can have two bidirectional limit points. An example of this is the real representation $1\pm \frac{1}{n}, 2\pm \frac{1}{n}$. An example of the later is $1-\frac{1}{n},2+\frac{1}{n},3-\frac{1}{n},4-\frac{1}{n}$.
A finite ordinal like $n\omega$ can be visualized as a sequence of rightarrows $\rightarrow \rightarrow \rightarrow ...$. These can be constructed in the familiar manner we have done so far by subtracting an infinitesimal value from a limit point. So for example $4\omega$ can be represented by $1-\frac{1}{n},2-\frac{1}{n},3-\frac{1}{n},4-\frac{1}{n}$. Dually, an inverse ordinal $4\omega^*$ can be represented by adding an infinitesimal value to a sequence of values: $1+\frac{1}{n},2+\frac{1}{n},3+\frac{1}{n},4+\frac{1}{n}$.
We can represent $2\mathbb{Z}$, the order type of two integer order types by a series by adjoining a bidirectionally convergent limit point to the integers like $\{-n,1+\pm \frac{1}{n},n \}$. All these different methods together constitute a sufficient basis for the theory of representation of total orders of finite sequence size.
Infinite sequence size
As we can construct a total order embedding for any total order of finite sequence size $n$, we can continue this process to construct a total order with infinite sequence size. A first example is the order embedding $f : \omega^2 \to \mathbb{R}$ of the infinite sequence size ordinal $\omega^2$ into $\mathbb{R}$ determinined by subtracting an infinitesimal value from each positive integer: \[ \{n - \frac{1}{m} : n,m \in \mathbb{Z}_+ \} \] A natural dualization of this is to construct the ordinal $(\omega^2)^{*}$ by taking the set of negative integers and adding an infinitesimal value to each of them. Then this produces an embedding of the inverse ordinal $(\omega^2)^{*}$ in the real numbers $\mathbb{R}$. \[ -n + \frac{1}{m} : n,m \in \mathbb{Z} \] The integers squared $\mathbb{Z}^2$ can be constructed by taking each integer and adding and subtracting an infinitesimal value from it. In this case, each integer is the bidirectional limit point of both an infinite sequence asceding into it and an infinite sequence descending into it. \[ \{n \pm \frac{1}{m} : n \in \mathbb{Z}, m \in \mathbb{Z} - \{0\} \} \] In each case we can take a discrete set of points in $\mathbb{R}$ and we turn them into limit points by adding or subtracting a vanishing value from them. This works for any finite or discrete set of limit points, but more advanced methods are required to embed larger total order types in $\mathbb{R}$.
Higher limit points:
Any suborder of the real numbers $\mathbb{R}$ induces a set of limit points which is again a subset of $\mathbb{R}$. In the first part of this theory we can undertook the study the suborders of the reals with a finite number of limit points. Suppose that the limit points of $S \subseteq \mathbb{R}$ are infinite, then they form an infinite order type which can be used to study the suborder.In the previous section of infinite sequence size total orders, we constructed the first examples of embeddings whose order types are infinite and they are all necessarily discrete and of the form $\omega$,$\omega^*$, or $\mathbb{Z}$. The limit points of these sets of limit points are all either positive or negative infinity.
The fact that the set of limit points of a total order can themselves have limit points, means that there exists a concept of higher limits. These are the limit points of the limit points of a total suborder of the real numbers. These higher limit points are the basis of the next step in the classification of the total suborders of the real numbers.
The higher limit points of a scattered total order don't need to be infinite as we will see. These higher limit points can represent any real number, furthermore they can be nested. So we can form higher limit points of higher limit points, and so on. These higher limit points form the next step in our classification of total orders.
Finite depth total orders:
In order to form deeper total orders then the ones we have constructed so far, we need to some of the basic properties of the ordered field $\mathbb{R}$. In $\mathbb{R}$ the functions $\frac{1}{x}$ and $-x$ are both order reversing, so if we combine them together to get $-\frac{1}{x}$ we can an order embedding of $\mathbb{R}_{\ge 1}$ into $[-1,0)$. \[ \frac{1}{x} : \mathbb{R}_{\ge 1} \to [-1,0) \] We have already applied this to the positive integers to get $-\frac{1}{n}$ which has the same order type $\omega$ as the positive integers, and we then added it onto each positive integer to get an order type $\omega^2$. We can now take the negative reciprocal of this to get a bounded $\omega^2$ embedding. \[ -\frac{1}{n-\frac{1}{m}} \] We can get ordinals now like $2\omega^2$ by simply combining a $\omega^2$ ordinal in one interval with a $\omega^2$ ordinal in another. To get something like $\omega^2 + 2\omega + 1$ we simply combine a finite number of ordinals in separate intervals which have each of these order types: \[ 1-\frac{1}{n-\frac{1}{m}}, 2-\frac{1}{n-\frac{1}{m}}, 3-\frac{1}{n},4-\frac{1}{n}, 5\] This same process can be iterated to get an ordinal like $\omega^3$ which has an infinite set of higher limit points: \[ -\frac{1}{n-\frac{1}{m-\frac{1}{o}}} \] The embedding of $\omega^4$ and any larger ordinals in $\mathbb{R}$ can be achieved by further iterating this process: \[ -\frac{1}{n-\frac{1}{m-\frac{1}{o-\frac{1}{p}}}} \] This process is sufficient to construct any ordinal number that is less then some ordinal polynomial. Other scattered total orders of the same sort can be constructed in the same manner by simply switching around the signs of the some of the variables.Large ordinals:
The ordinal numbers constructed so far all have finite exponent e.g $\omega^2, \omega^3, \omega^4, etc$. The next is to construct an ordinal like $\omega^\omega$ which essentially has some ordinal depth and this can be continued to get $\omega^{\omega^\omega}$, $\omega^{\omega^{\omega^\omega}}$ and so on. Embedding these larger total orders in $\mathbb{R}$ is a bit more involved.The first ordinal larger then any exponential tower of ordinals is $\epsilon_0$, then any other ordinal number constructed so far can be embedded in $\epsilon_0$. In order to get a real representation of $\epsilon_0$ the reader is referred to the work of Jeff Erickson on fusible numbers [2].
The fusible numbers are constructed recursively so that a fusible number is $0$ or $\frac{a+b+1}{2}$ with $a$ and $b$ fusible numbers and $|a-b| \leq 1$. Then the fact that the fusible numbers are scattered ordered, any exponential tower can be constructed from them.
As fusible numbers are constructed recursively, the definition of real suborder with larger order types will require the use of recursive formulas. With this primitive recursive ordinals can be embedded in the continuum.
Non-scattered total orders:
The preorder on the isomorphism classes of total orders induced by the category of order embeddings has the property that all countable non-scattered orders are embedding equivalent to one another, so they can be embedded in one another. Therefore, there is no corresponding measure on the complexity of countable non-scattered total orders. A first example is $\mathbb{Q}$ itself, but there are several well known subsets with the same ordering:- All localisations of the PID $\mathbb{Z}$ in the field $\mathbb{Q}$ are densely ordered and have the same order type as $\mathbb{Q}$. For example, the dyadic rationals.
- All rings of real algebraic numbers like $\mathbb{Q}(\sqrt{2}), \mathbb{Q}(\sqrt{3})$, and so on are all denesly ordered and have the same order type as $\mathbb{Q}$.
References:
[1] Real number line
[2] Fusible numbers
Tuesday, August 24, 2021
Width and height of numerical semigroups
Every numerical semigroup is partially ordered by addition. A first step towards numerical semigroup theory is to classify the types of partial orders that they entail. The most basic properties of a poset are the size of maximal antichains and chains: the width and the height of the poset. These two properties will be determined for numerical semigroups.
Theorem. let $S$ be a numerical semigroup. Then $S$ has infinite height.
Proof. let $S$ be a numerical semigroup, then $S$ is idempotent-free. Therefore, let $x \in S$ then the semigroup generated by $(x)$ is equal to $\mathbb{Z}_+$ which forms an infinite chain as a poset. Therefore, $S$ has an infinite chain, so it is of infinite height. $\square$
The maximal chains of a numerical semigroup all have order type $\omega$, same as the order type of $\mathbb{Z}_+$ so the chain problem is completely solved for numerical semigroups. The determination of maximal antichains and the width of a numerical semigroup is a bit more involved because they can take on multiple values.
Theorem. let $S$ be a numerical semigroup. Then the width of $S$ is the multiplicity $m(S)$.
Proof. let $S$ be a numerical semigroup with $m(S)$ its multiplicity. Let $(m(S))$ be the subsemigroup of $\mathbb{N}$ that is generated by $m(S)$ then $(m(S))$ has width $m(S)$ with maximal antichains consisting of any maximal set of representatives modulo $m(S)$. Consider the preorder induced by $m(S)$ acting on $S$ then it is an induced suborder of $(m(S))$ acting on $\mathbb{N}$ and so must have width at most $m(S)$. The order type of $S$ is an order extension of the action preorder of $(m(S))$ acting on $S$, so its width must be less then $m(S)$.
This establishes an upper bound on the width of $S$. In order to get the lower bound, consider that every numerical semigroup is cofinite. Therefore, $S$ must have a maximal system of representatives modulo $m(S)$ because if it did not there would be an infinite set of terms modulo some value of $m(S)$ missing from $S$. Therefore, the width is greater then or equal to $m(S)$. Finally, because $m(S) \leq width(S) \leq m(S)$ we have that $width(S) = m(S)$. $\square$
Isomorphism types of commutative J-trivial semigroups of a given order type are partially ordered pointwise. Semilattices are always the least commutative J-trivial semigroup of a given order type, because they produce the least upper bound. Commutative J-trivial semigroups other then semilattices arise from producing non-minimal upper bounds on partial orders.
Proposition. a numerical semigroup is an upper bound producing function for a finite width and infinite height partial order.
The classification of the width and the height of a numerical semigroup is just the first step towards describing the order type of the semigroup. Of course, it is not enough to describe a commutative J-trivial semigroup by its order type because there are many isomorphism types of commutative J-trivial semigroups on a given partial order, but this is just a small part of the theory.
Definition. the lattice of numerical semigroups $L$ is the set of all cofinite submonoids of $\mathbb{N}$. $L$ is a completely join closed and finite intersection closed sublattice of $Sub(\mathbb{N})$.
It is not hard to see that $m : L \to \mathbb{Z}_+$ is antitone, so that equivalently the width of a numerical semigroup is antitone much like in the case of partial orders. Again, much like in the case of partial orders every numerical semigroup has a linear extension. Except in this case, there is only one linear extension of a numerical semigroup: $\mathbb{N}$.
Theorem. let $S$ be a numerical semigroup. Then $S$ has infinite height.
Proof. let $S$ be a numerical semigroup, then $S$ is idempotent-free. Therefore, let $x \in S$ then the semigroup generated by $(x)$ is equal to $\mathbb{Z}_+$ which forms an infinite chain as a poset. Therefore, $S$ has an infinite chain, so it is of infinite height. $\square$
The maximal chains of a numerical semigroup all have order type $\omega$, same as the order type of $\mathbb{Z}_+$ so the chain problem is completely solved for numerical semigroups. The determination of maximal antichains and the width of a numerical semigroup is a bit more involved because they can take on multiple values.
Theorem. let $S$ be a numerical semigroup. Then the width of $S$ is the multiplicity $m(S)$.
Proof. let $S$ be a numerical semigroup with $m(S)$ its multiplicity. Let $(m(S))$ be the subsemigroup of $\mathbb{N}$ that is generated by $m(S)$ then $(m(S))$ has width $m(S)$ with maximal antichains consisting of any maximal set of representatives modulo $m(S)$. Consider the preorder induced by $m(S)$ acting on $S$ then it is an induced suborder of $(m(S))$ acting on $\mathbb{N}$ and so must have width at most $m(S)$. The order type of $S$ is an order extension of the action preorder of $(m(S))$ acting on $S$, so its width must be less then $m(S)$.
This establishes an upper bound on the width of $S$. In order to get the lower bound, consider that every numerical semigroup is cofinite. Therefore, $S$ must have a maximal system of representatives modulo $m(S)$ because if it did not there would be an infinite set of terms modulo some value of $m(S)$ missing from $S$. Therefore, the width is greater then or equal to $m(S)$. Finally, because $m(S) \leq width(S) \leq m(S)$ we have that $width(S) = m(S)$. $\square$
Isomorphism types of commutative J-trivial semigroups of a given order type are partially ordered pointwise. Semilattices are always the least commutative J-trivial semigroup of a given order type, because they produce the least upper bound. Commutative J-trivial semigroups other then semilattices arise from producing non-minimal upper bounds on partial orders.
Proposition. a numerical semigroup is an upper bound producing function for a finite width and infinite height partial order.
The classification of the width and the height of a numerical semigroup is just the first step towards describing the order type of the semigroup. Of course, it is not enough to describe a commutative J-trivial semigroup by its order type because there are many isomorphism types of commutative J-trivial semigroups on a given partial order, but this is just a small part of the theory.
Definition. the lattice of numerical semigroups $L$ is the set of all cofinite submonoids of $\mathbb{N}$. $L$ is a completely join closed and finite intersection closed sublattice of $Sub(\mathbb{N})$.
It is not hard to see that $m : L \to \mathbb{Z}_+$ is antitone, so that equivalently the width of a numerical semigroup is antitone much like in the case of partial orders. Again, much like in the case of partial orders every numerical semigroup has a linear extension. Except in this case, there is only one linear extension of a numerical semigroup: $\mathbb{N}$.
Monday, August 23, 2021
Width and height of order extensions
Let $S(X)$ be the semilattice of posets on a set $X$. The height and width functions of $S(X)$ are monotone and antitone respectively. This allows us to place bounds on the height and width of extensions of posets.
Lemma. let $P,E$ be posets with $P \subseteq E$ then $width(E) \subseteq width(P)$.
Proof. let $A$ be an antichain in $E$. Then $\forall x,y \in A : x \not\subseteq y \wedge y \not\subseteq x$. Then let $A$ be the same set embedded in $P$. Suppose $A$ is not an antichain so there exists $x,y : x \subseteq y$ then because $P \subseteq E$ this means that $x \subseteq y$ in $E$ which contradicts the fact that $A$ is an antichain in $E$. So $A$ must be an antichain in $P$. $\square$
Lemma. let $P,E$ be posets with $P \subseteq E$ then $height(P) \subseteq height(E)$.
Proof. let $C$ be a chain in $P$ then $\forall x,y \in C : x \subseteq y \vee y \subseteq x$ in $P$. Then by extension $\forall x,y \in C : x \subseteq y \vee y \subseteq x$ with respect to $E$. It follows that $E$ preserves the chains of $P$. $\square$
These two lemmas immediately lead to the following theorem:
Theorem. let $S(X)$ be the semilattice of posets on a finite set $X$ then:
Total orders have the least width so they are the maximal elements of the semilattice of posets. That is why in dimension theory we study posets by the intersection of total orders. This theorem can now be used to establish bounds on the width of order extensions. For example, suppose we have a J-trivial semigroup extending some other semigroup $S$, then its width must be less then $S$.
Lemma. let $P,E$ be posets with $P \subseteq E$ then $width(E) \subseteq width(P)$.
Proof. let $A$ be an antichain in $E$. Then $\forall x,y \in A : x \not\subseteq y \wedge y \not\subseteq x$. Then let $A$ be the same set embedded in $P$. Suppose $A$ is not an antichain so there exists $x,y : x \subseteq y$ then because $P \subseteq E$ this means that $x \subseteq y$ in $E$ which contradicts the fact that $A$ is an antichain in $E$. So $A$ must be an antichain in $P$. $\square$
Lemma. let $P,E$ be posets with $P \subseteq E$ then $height(P) \subseteq height(E)$.
Proof. let $C$ be a chain in $P$ then $\forall x,y \in C : x \subseteq y \vee y \subseteq x$ in $P$. Then by extension $\forall x,y \in C : x \subseteq y \vee y \subseteq x$ with respect to $E$. It follows that $E$ preserves the chains of $P$. $\square$
These two lemmas immediately lead to the following theorem:
Theorem. let $S(X)$ be the semilattice of posets on a finite set $X$ then:
- $width : S(X) \to \mathbb{N}$ is antitone
- $height : S(X) \to \mathbb{N}$ is monotone
Total orders have the least width so they are the maximal elements of the semilattice of posets. That is why in dimension theory we study posets by the intersection of total orders. This theorem can now be used to establish bounds on the width of order extensions. For example, suppose we have a J-trivial semigroup extending some other semigroup $S$, then its width must be less then $S$.
Sunday, August 22, 2021
Algebraic operations on sets
Most ordered algebraic structures arise from the generalisation of algebra from operations on elements to operations on sets, but this is by no means exclusive. There are of course ordered rings and semirings like $\mathbb{N}$ and $\mathbb{Z}$ that emerge from basic arithmetic. In the former case, the algebra on sets will be constructed from the ground up from simple foundations.
The covariant power set functor
Let $f : A \to B$ be a function of sets. Then the power set functor converts $f$ into a function which takes the image of $f$ with respect to a set. Although this is a simple construction, it is the fundamental building block of all operations on sets: \[ \wp(f) : \wp(A) \to \wp(B) \] An important property is that $\wp$ is a union homomorphism. Therefore, $wp(f)(A \cup B) = \wp(f)(A) \cup \wp(f)(B)$. It also preserves identities $\wp(f)(\emptyset) = \emptyset$.
A property of cartesian products:
The cartesian product of sets distributes over unions and it preserves emptyness. This exactly matches the case of the power set functor, which also preserves unions and the empty set. \[ A \times \emptyset = \emptyset \times A = \emptyset \] \[ A \times (B \cup C) = A \times B \cup A \times C \] \[ (A \cup B) \times C = A \times C \cup B \times C \] This can be generalized to any number of variables, so that the cartesian product of sets always distributes over unions. An immediate consequence of this and the same property over images means that the algebraic operations on sets distribute over unions.
Algebraic operations on subsets:
Let $\circ : A^2 \to A$ be a semigroup. Let $S,T \subseteq A$ then the product is typically defined as $AB = \{ab : a \in A, b \in B\}$, but it is much more conventient to define it by using the image functor and the cartesian product: \[ AB = \wp_\circ(A \times B) \] It is now very easy to see that the product of subsets of a semigroup distributes over unions, and hence it forms an idempotent semiring. All we need to do is combine the fact that the image preserves unions and the product distributes over them.
Theorem. let $\circ : A^2 \to A$ be a semigroup then the product of sets $\wp(A)^2 \to \wp(A)$ distributes over unions.
Proof. let $S,T,U \subseteq A$ then we have the following sequence of equalities: \[ S(T \cup U) \] \[= \wp_{\circ}(S \times T \cup U) \] \[ = \wp_{\circ}(S \times T \cup S \times U) \] \[ = \wp_{\circ}(S \times T) \cup \wp_{\circ}(S \times U) \] \[ = ST \cup SU \] This can easily be dualized to the other order $(S \cup T)U$. Additionally, the product of sets preserves emptyness: $A\emptyset = \emptyset A = \emptyset$. $\square$
An important consequence of this formulation using the image functor and the distributivity of products over unions is that it can be generalized to any n-ary operation.
Theorem. let $f: A^n \to A$ be an n-ary operation. Then the power algebra $f' : \wp(A)^n \to \wp(A)$ distributes over unions and preserves emptyness.
A ternary operation on subsets produces a different kind of algebraic structures then the familiar idempotent semirings of structure like semigroups. In the case that we have a partial operation, then operations on subsets can be defined by intersection with the domain. For example, consider the partial semigroup composition function $\circ$ of a category: \[ \circ : Arrows(C)^2_* \to Arrows(C) \] In order to define the composition of morphism systems of a category, we simply get the image of morphism compsoition of $S \times T \cap Arrows(C)^2_*$. The intersection simply means that we don't want to return a value when a composition doesn't exist. This of course means that the idempotent semiring of a category can have non-trivial zero divisors.
Hyperoperations:
To make things a little bit interesting, I will cover hyperoperations here using the same idea of dealing with images over products. Let $f : A^2 \to \wp(A)$ be a hypermagma. Then we can define the the product of sets $S$ and $T$ in the hypermagma by the union of the image: \[ \bigcup \wp_f(S \times T) \] This produces a magma $f' : \wp(A)^2 \to \wp(A)$. It is often more convenient to work with hyperoperations by algebraic operations on sets then on elements, which creates a uniform process. Then $f'$ is simply a hypersemigroup provided that it is associative. This clearly has the same properties of preserving unions and emptyness.
The covariant power set functor
Let $f : A \to B$ be a function of sets. Then the power set functor converts $f$ into a function which takes the image of $f$ with respect to a set. Although this is a simple construction, it is the fundamental building block of all operations on sets: \[ \wp(f) : \wp(A) \to \wp(B) \] An important property is that $\wp$ is a union homomorphism. Therefore, $wp(f)(A \cup B) = \wp(f)(A) \cup \wp(f)(B)$. It also preserves identities $\wp(f)(\emptyset) = \emptyset$.
A property of cartesian products:
The cartesian product of sets distributes over unions and it preserves emptyness. This exactly matches the case of the power set functor, which also preserves unions and the empty set. \[ A \times \emptyset = \emptyset \times A = \emptyset \] \[ A \times (B \cup C) = A \times B \cup A \times C \] \[ (A \cup B) \times C = A \times C \cup B \times C \] This can be generalized to any number of variables, so that the cartesian product of sets always distributes over unions. An immediate consequence of this and the same property over images means that the algebraic operations on sets distribute over unions.
Algebraic operations on subsets:
Let $\circ : A^2 \to A$ be a semigroup. Let $S,T \subseteq A$ then the product is typically defined as $AB = \{ab : a \in A, b \in B\}$, but it is much more conventient to define it by using the image functor and the cartesian product: \[ AB = \wp_\circ(A \times B) \] It is now very easy to see that the product of subsets of a semigroup distributes over unions, and hence it forms an idempotent semiring. All we need to do is combine the fact that the image preserves unions and the product distributes over them.
Theorem. let $\circ : A^2 \to A$ be a semigroup then the product of sets $\wp(A)^2 \to \wp(A)$ distributes over unions.
Proof. let $S,T,U \subseteq A$ then we have the following sequence of equalities: \[ S(T \cup U) \] \[= \wp_{\circ}(S \times T \cup U) \] \[ = \wp_{\circ}(S \times T \cup S \times U) \] \[ = \wp_{\circ}(S \times T) \cup \wp_{\circ}(S \times U) \] \[ = ST \cup SU \] This can easily be dualized to the other order $(S \cup T)U$. Additionally, the product of sets preserves emptyness: $A\emptyset = \emptyset A = \emptyset$. $\square$
An important consequence of this formulation using the image functor and the distributivity of products over unions is that it can be generalized to any n-ary operation.
Theorem. let $f: A^n \to A$ be an n-ary operation. Then the power algebra $f' : \wp(A)^n \to \wp(A)$ distributes over unions and preserves emptyness.
A ternary operation on subsets produces a different kind of algebraic structures then the familiar idempotent semirings of structure like semigroups. In the case that we have a partial operation, then operations on subsets can be defined by intersection with the domain. For example, consider the partial semigroup composition function $\circ$ of a category: \[ \circ : Arrows(C)^2_* \to Arrows(C) \] In order to define the composition of morphism systems of a category, we simply get the image of morphism compsoition of $S \times T \cap Arrows(C)^2_*$. The intersection simply means that we don't want to return a value when a composition doesn't exist. This of course means that the idempotent semiring of a category can have non-trivial zero divisors.
Hyperoperations:
To make things a little bit interesting, I will cover hyperoperations here using the same idea of dealing with images over products. Let $f : A^2 \to \wp(A)$ be a hypermagma. Then we can define the the product of sets $S$ and $T$ in the hypermagma by the union of the image: \[ \bigcup \wp_f(S \times T) \] This produces a magma $f' : \wp(A)^2 \to \wp(A)$. It is often more convenient to work with hyperoperations by algebraic operations on sets then on elements, which creates a uniform process. Then $f'$ is simply a hypersemigroup provided that it is associative. This clearly has the same properties of preserving unions and emptyness.
Saturday, August 21, 2021
Geometry of commutative semigroups
Redei's theory of finitely generated commutative semigroups [1] describes a geometric embedding of the finitely generated free $\mathbb{N}$-semimodule $F(S)$. The first realisation is that the semimodule $\mathbb{N}$ can be completed to form the $\mathbb{Z}$ module $F^{\circ}(S)$. Then the points of a finitely generated $\mathbb{Z}$ module can be embedded in a $\mathbb{R}$ vector space, which is also the manifold $\mathbb{R}^n$.
\[ F(S) \hookrightarrow F^{\circ}(S) \hookrightarrow \mathbb{R}^n \]
Redei's embedding [1] will be briefly discussed. A consequence of this is that we can use geometric intuition in commutative semigroup theory. As embedded in $\mathbb{R}^n$ the free $\mathbb{N}$-semimodule is a set of "lattice points" in the sense of discrete geometry. In $\mathbb{R}^2$ this can visualized as a grid in the plane. In higher dimensions it is of course harder to perform a visualization.
As topological semimodules $F(S)$ are both $F^{\circ}(S)$ are both trivial, because they are discrete. On the other hand, as a topological vector space $\mathbb{R}^n$ is far more interesting because among other things it is also a manifold. The important thing for semigroup theory, is any finitely generated commutative semigroup is a quotient of $F(S)$.
If we consider $F(S)$ to consist of multisets, then the multiplicities in $F(S)$ are natural numbers, because $F(S)$ is a $\mathbb{N}$ semimodule. The extension from $F(S)$ to $\mathbb{R}^n$ can be seen as extending $\mathbb{N}$ to form a full continuum of multiplicities. The elements of $\mathbb{R}^n$ are real-valued sets.
Finally, it is worth asking why this approach works for commutative semigroups and if it can be generalized. In fact, it cannot be further generalized because both associativity and commutativity are fundamental to this construction. In a commutative magma all you would get are trees, and the words of the free non-commutative semigroup cannot be separated from one another to form points in a geometric space.
References:
[1] Finitely generated commutative semigroups
As topological semimodules $F(S)$ are both $F^{\circ}(S)$ are both trivial, because they are discrete. On the other hand, as a topological vector space $\mathbb{R}^n$ is far more interesting because among other things it is also a manifold. The important thing for semigroup theory, is any finitely generated commutative semigroup is a quotient of $F(S)$.
If we consider $F(S)$ to consist of multisets, then the multiplicities in $F(S)$ are natural numbers, because $F(S)$ is a $\mathbb{N}$ semimodule. The extension from $F(S)$ to $\mathbb{R}^n$ can be seen as extending $\mathbb{N}$ to form a full continuum of multiplicities. The elements of $\mathbb{R}^n$ are real-valued sets.
Finally, it is worth asking why this approach works for commutative semigroups and if it can be generalized. In fact, it cannot be further generalized because both associativity and commutativity are fundamental to this construction. In a commutative magma all you would get are trees, and the words of the free non-commutative semigroup cannot be separated from one another to form points in a geometric space.
References:
[1] Finitely generated commutative semigroups
Friday, August 20, 2021
Functional dependencies and set-valued functors
Let $R$ be an n-ary relation, then functional dependencies on $R$ are typically modeled as a preorder $P$ on sets. Additional information is provided by defining a set-valued functor on this preorder $f : P \to Sets$ which associates each pair of dependency sets with the function between them. This concept is related to function restriction sheaves and set-valued functors on preorders in general.
Dependency relationships:
A preorder can be considered as defining a system of relationships of dependencies between entities. These relationships are always transitive because if $A$ is dependent upon $B$ and $B$ is dependent upon $C$ then $A$ is dependent upon $C$. An example of a dependency ordering relationship like this, is the hierarchy of dependencies of files in a computer program.
Preorders are also used to model dependencies of events. In a familial preorder, a person is dependent upon his parents, who are dependent upon their parents and so on. In general, the events in spacetime are modeled by causal dependencies, so that each event is dependent upon its causes. Considering preorders as relationships of dependencies produces a slight change of perspective.
Functional dependencies:
If a preorder $P$ on a set $S$ models how the elements in the set are dependent upon one another, then a set-valued functor $F: P \to Sets$ can be considered to be a model of functional dependencies. The dependency on element upon another is associated with a function with realises the dependency. \[ F : P \to Sets \] There is another sense in functional dependencies appear: in the theory of relations. Functional dependencies are preorders on the sets of indices of relations. These functional dependencies in $\wp(I)^2$ have the following axioms:
Definition. let $R$ be a relation consisting of functions $I \to X$ then $S$ functionally determines $T$ provided that $\forall a,b \in R: a|_S = b|_S \Rightarrow a|_T = b|_T$.
This naturally produces a functional dependency relationship from a relation $R$. As these functional dependencies are thin categories, we can produce set-valued functors over them that how one variable determines another.
Set-valued functors from functional dependencies:
A set valued functor has two parts: an object function and a morphism function. To begin with, we define the object part of the set-valued functor. Let $R$ be a relation defined by a family of functions of the form $I \to X$.
Definition. let $S \subseteq I$ then the underlying set of $S$ is the image of the restriction function $|_S : Hom(I,X) \to Hom(S,X)$.
Definition. let $S,T \subseteq I$ such that $S \to T$ then the underlying function $f_{(S,T)} : Hom(S,X) \to Hom(T,X)$ is the function which takes $l \in Hom(S,X)$ and then it finds an edge $E$ in $R$ that has $E_S = l$ and produces from it its restriction $E_T$.
By combining these two components: the underlying set of an object and the underlying function of an edge, we can get a set-valued functor from functional dependencies: \[ F : P \to Sets \] If we have $A \to B$ and $B \to C$ as functional dependencies, then $F_{(A,C)} = F_{(A,B)} \circ F_{(B,C)}$. In either case, the function determines the restriction to $C$ from the restriction to $A$, the later just does it through an intermediary. So $F$ is a functor determined by the relation $R$.
Restriction presheaf:
The condition of reflexivity means that $A \subseteq B$ means that $B \to A$. So a set of values in an association functionally determines its parts. This determines a contravariant functor from a partially ordered family of sets of indices. \[ F : C^{op} \to Sets \] Although we can often produce interesting set-valued functors from functional dependencies on relations, the restriction presheaf is something we can produce for any relation. This applies to any family of sets, partially ordered by inclusion. It is helpful to add other extra conditions, like that the family of sets is a topology in order to define the gluing axiom of sheaves.
Underlying relations of some set-valued functors
We saw previously that we can get set-valued functors to describe the functional dependencies of some relations. We can also apply this process in the reverse direction to get the underlying relations of some set-valued functor. Let $P$ be a finite preorder and $F : P \to Sets$ a set-valued functor.
Definition. let $A_1,...A_n$ be the objects of $P$ then define the relation $R$ of $F$ to be the relation in $F(A_1) ... F(A_n)$ that has $E \in R$ provided that $\forall m: A_i \to A_o \in Arrows(P)$ with $F(m) : F(A_i) \to F(A_o)$ we have that $E_o = F(m)(E_i)$.
The relation simply consists of tuples of elements of the underlying sets of the objects of the preorder, such that the relation satisfies all the functional dependencies of the set-valued functor.
Example. the underlying binary relation of a function $f$ consists of all ordered pairs $(a,b)$ with $b = f(a)$. It fully determines the function up to image.
The underlying binary relation can be empty. Consider a set-valued functor from the cospan category $F : [2,1] \to Sets$. Then the fiber product of the two functions determined by the cospan functor could be empty, in which case the underlying relation is empty. Thus, the underlying relation doesn't fully determine the set-valued functor. There is one special case though for which this is the case.
Topoi of equivalence relations:
An equivalence relation $E$ can be presented as a thin groupoid. Then by this presentation, $Sets^E$ is a topos. As the topos of a groupoid, this topos is boolean. So this is a special case of a topos of set-valued functors, for which the set-valued functors are determined by relations.
Proposition. let $E$ be an equivalence relation. Then $Sets^E$ is a boolean topos.
The topoi that emerge from equivalence relations are boolean, and so they can truly be presented as sets. In particular, they can be considered to be special cases of relations. Let $E$ be a complete equivalence relation of order $n$, then $Sets^E$ can be considered to be a topos of $F: E \to Sets$ functors. These functors are fully detremined by one-to-one-to-one-to... relations.
The topos $Sets^{K_2}$, the topos of bijections, is fully determined by one to one relations. The subobjects in the topos of bijections are equivalente to subsets of the one to one relation. Then $Sets^{K_3}$ consists of one-to-one-to-one relations and subobjects are subsets of these relations. $Sets^{K_4}$ consists of one-to-one-to-one-to-one relations and so on. The distinguishing property of these relations is their complete set of functional dependencies.
The topos of functions $Sets^{T_2}$ is the smallest non-boolean topoi of a preorder. The reason that it is not boolean and equivalently the reason it is not fully determined by its underlying relation is that functions have images. While it is true that set-valued functors on preorders can typically be considered to be functional dependencies on relations, this is not always strictly the case because of the images of functions.
For example, consider a functor in the topos $Sets^{T_3}$ which takes the form $F : T_3 \to Sets$ then this is a pair of functions $f : A \to B$ and $g : B \to C$. If the function $f$ is not surjective, then there are pairs in $g$ that can never be recovered by the relation $A \times B \times C$.
A set-valued functor on a finite total order is fully determined by its relation, only provided that each of its function is surjective. We can therefore say that set-valued functors on preorders are related to the functional dependencies on relations, but they are not always determined by them such as when their output functions are not all surjective.
Set-valued span functors:
A span functor has signature $F: [1,2] \to Sets$. The index preorder of this functor is a height two lower tree, so by generalization we can consider any functor $F: [1,n] \to Sets$ that has its origin a height two lower tree partial order.
Then $F$ is essentially a product of functions on its initial index set. In the case of $[1,2]$ we have two functions $f : A \to B$ and $A \to C$ that can be expressed as a product $A \to B \times C$. This determines a ternary relation $(a,b,c)$ with $f(a) = b$ and $g(a) = c$. So these kind of set-valued functors are very much related to their underlying relations.
In order to address the lack of surjectivity, these relations can be considered by embedded relations and the parent sets the relation is embedded in, including elements not in their image can be determined by the embedding. So these functors can determined by their relations up to an embedding.
Fundamental topoi:
The fundamental topoi: the topos of sets, the topos of functions, the topos of bijections, etc can be considered to be determined by systems of functional dependencies. The distinction between the topos of functions and the topos of bijections is that the later has more functional dependencies. These additional functional dependencies determine different categorical logics as well as subobject and quotient lattices.
Perspective on set-valued functors:
The set-valued functors on preorders can be considered to be systems of functional dependencies, but these don't always correspond to the functional dependencies on relations especially if the preorder is not an equivalence relation. The distinction between functional dependencies of relations and set-valued functors on preorders arises because of the images of functions.
Functional logic synthesis:
The role of topoi theory is that it unifies logic and functions. It does this by providing a common language for dealing with sets and functions, provided by their topoi: $Sets$ and $Sets^{\to}$. Topoi theory can therefore serve as the foundations of functional logic programming.
Traditionally, sets and functions are treated separately in logic programming and functional programming languages. The topos perspective suggests that there is no reason that we cannot logic programming and functional programming techniques: after all predicates and functions are merely different types of topos objects.
Implementation of relations in functional logic programming languages:
A relation in a functional logic programming language can be defined by the combination of a computable predicate function and a set-valued functor determining its functional dependencies. The set-valued functor can be used to help complete terms of the relation.
Alternatively, a function can be defined by a set-valued functor and a relation can be defined from it by its set of ordered pairs. As a result, the functional approach and the logical approach can ultimately arrive at the same result in a system based upon topos theory.
See also:
[1] Topoi from preorders
References:
[1] Armstrong's axioms:
Dependency relationships:
A preorder can be considered as defining a system of relationships of dependencies between entities. These relationships are always transitive because if $A$ is dependent upon $B$ and $B$ is dependent upon $C$ then $A$ is dependent upon $C$. An example of a dependency ordering relationship like this, is the hierarchy of dependencies of files in a computer program.
Preorders are also used to model dependencies of events. In a familial preorder, a person is dependent upon his parents, who are dependent upon their parents and so on. In general, the events in spacetime are modeled by causal dependencies, so that each event is dependent upon its causes. Considering preorders as relationships of dependencies produces a slight change of perspective.
Functional dependencies:
If a preorder $P$ on a set $S$ models how the elements in the set are dependent upon one another, then a set-valued functor $F: P \to Sets$ can be considered to be a model of functional dependencies. The dependency on element upon another is associated with a function with realises the dependency. \[ F : P \to Sets \] There is another sense in functional dependencies appear: in the theory of relations. Functional dependencies are preorders on the sets of indices of relations. These functional dependencies in $\wp(I)^2$ have the following axioms:
- Reflexivity: if $A \subseteq B$ then $B \to A$
- Transitivity: if $A \to B$ and $B \to C$ then $A \to C$
- Composition: if $A \to C$ and $B \to D$ then $A \cup B \to C \cup D$
Definition. let $R$ be a relation consisting of functions $I \to X$ then $S$ functionally determines $T$ provided that $\forall a,b \in R: a|_S = b|_S \Rightarrow a|_T = b|_T$.
This naturally produces a functional dependency relationship from a relation $R$. As these functional dependencies are thin categories, we can produce set-valued functors over them that how one variable determines another.
Set-valued functors from functional dependencies:
A set valued functor has two parts: an object function and a morphism function. To begin with, we define the object part of the set-valued functor. Let $R$ be a relation defined by a family of functions of the form $I \to X$.
Definition. let $S \subseteq I$ then the underlying set of $S$ is the image of the restriction function $|_S : Hom(I,X) \to Hom(S,X)$.
Definition. let $S,T \subseteq I$ such that $S \to T$ then the underlying function $f_{(S,T)} : Hom(S,X) \to Hom(T,X)$ is the function which takes $l \in Hom(S,X)$ and then it finds an edge $E$ in $R$ that has $E_S = l$ and produces from it its restriction $E_T$.
By combining these two components: the underlying set of an object and the underlying function of an edge, we can get a set-valued functor from functional dependencies: \[ F : P \to Sets \] If we have $A \to B$ and $B \to C$ as functional dependencies, then $F_{(A,C)} = F_{(A,B)} \circ F_{(B,C)}$. In either case, the function determines the restriction to $C$ from the restriction to $A$, the later just does it through an intermediary. So $F$ is a functor determined by the relation $R$.
Restriction presheaf:
The condition of reflexivity means that $A \subseteq B$ means that $B \to A$. So a set of values in an association functionally determines its parts. This determines a contravariant functor from a partially ordered family of sets of indices. \[ F : C^{op} \to Sets \] Although we can often produce interesting set-valued functors from functional dependencies on relations, the restriction presheaf is something we can produce for any relation. This applies to any family of sets, partially ordered by inclusion. It is helpful to add other extra conditions, like that the family of sets is a topology in order to define the gluing axiom of sheaves.
Underlying relations of some set-valued functors
We saw previously that we can get set-valued functors to describe the functional dependencies of some relations. We can also apply this process in the reverse direction to get the underlying relations of some set-valued functor. Let $P$ be a finite preorder and $F : P \to Sets$ a set-valued functor.
Definition. let $A_1,...A_n$ be the objects of $P$ then define the relation $R$ of $F$ to be the relation in $F(A_1) ... F(A_n)$ that has $E \in R$ provided that $\forall m: A_i \to A_o \in Arrows(P)$ with $F(m) : F(A_i) \to F(A_o)$ we have that $E_o = F(m)(E_i)$.
The relation simply consists of tuples of elements of the underlying sets of the objects of the preorder, such that the relation satisfies all the functional dependencies of the set-valued functor.
Example. the underlying binary relation of a function $f$ consists of all ordered pairs $(a,b)$ with $b = f(a)$. It fully determines the function up to image.
The underlying binary relation can be empty. Consider a set-valued functor from the cospan category $F : [2,1] \to Sets$. Then the fiber product of the two functions determined by the cospan functor could be empty, in which case the underlying relation is empty. Thus, the underlying relation doesn't fully determine the set-valued functor. There is one special case though for which this is the case.
Topoi of equivalence relations:
An equivalence relation $E$ can be presented as a thin groupoid. Then by this presentation, $Sets^E$ is a topos. As the topos of a groupoid, this topos is boolean. So this is a special case of a topos of set-valued functors, for which the set-valued functors are determined by relations.
Proposition. let $E$ be an equivalence relation. Then $Sets^E$ is a boolean topos.
The topoi that emerge from equivalence relations are boolean, and so they can truly be presented as sets. In particular, they can be considered to be special cases of relations. Let $E$ be a complete equivalence relation of order $n$, then $Sets^E$ can be considered to be a topos of $F: E \to Sets$ functors. These functors are fully detremined by one-to-one-to-one-to... relations.
The topos $Sets^{K_2}$, the topos of bijections, is fully determined by one to one relations. The subobjects in the topos of bijections are equivalente to subsets of the one to one relation. Then $Sets^{K_3}$ consists of one-to-one-to-one relations and subobjects are subsets of these relations. $Sets^{K_4}$ consists of one-to-one-to-one-to-one relations and so on. The distinguishing property of these relations is their complete set of functional dependencies.
The topos of functions $Sets^{T_2}$ is the smallest non-boolean topoi of a preorder. The reason that it is not boolean and equivalently the reason it is not fully determined by its underlying relation is that functions have images. While it is true that set-valued functors on preorders can typically be considered to be functional dependencies on relations, this is not always strictly the case because of the images of functions.
For example, consider a functor in the topos $Sets^{T_3}$ which takes the form $F : T_3 \to Sets$ then this is a pair of functions $f : A \to B$ and $g : B \to C$. If the function $f$ is not surjective, then there are pairs in $g$ that can never be recovered by the relation $A \times B \times C$.
A set-valued functor on a finite total order is fully determined by its relation, only provided that each of its function is surjective. We can therefore say that set-valued functors on preorders are related to the functional dependencies on relations, but they are not always determined by them such as when their output functions are not all surjective.
Set-valued span functors:
A span functor has signature $F: [1,2] \to Sets$. The index preorder of this functor is a height two lower tree, so by generalization we can consider any functor $F: [1,n] \to Sets$ that has its origin a height two lower tree partial order.
Then $F$ is essentially a product of functions on its initial index set. In the case of $[1,2]$ we have two functions $f : A \to B$ and $A \to C$ that can be expressed as a product $A \to B \times C$. This determines a ternary relation $(a,b,c)$ with $f(a) = b$ and $g(a) = c$. So these kind of set-valued functors are very much related to their underlying relations.
In order to address the lack of surjectivity, these relations can be considered by embedded relations and the parent sets the relation is embedded in, including elements not in their image can be determined by the embedding. So these functors can determined by their relations up to an embedding.
Fundamental topoi:
The fundamental topoi: the topos of sets, the topos of functions, the topos of bijections, etc can be considered to be determined by systems of functional dependencies. The distinction between the topos of functions and the topos of bijections is that the later has more functional dependencies. These additional functional dependencies determine different categorical logics as well as subobject and quotient lattices.
Perspective on set-valued functors:
The set-valued functors on preorders can be considered to be systems of functional dependencies, but these don't always correspond to the functional dependencies on relations especially if the preorder is not an equivalence relation. The distinction between functional dependencies of relations and set-valued functors on preorders arises because of the images of functions.
Functional logic synthesis:
The role of topoi theory is that it unifies logic and functions. It does this by providing a common language for dealing with sets and functions, provided by their topoi: $Sets$ and $Sets^{\to}$. Topoi theory can therefore serve as the foundations of functional logic programming.
Traditionally, sets and functions are treated separately in logic programming and functional programming languages. The topos perspective suggests that there is no reason that we cannot logic programming and functional programming techniques: after all predicates and functions are merely different types of topos objects.
Implementation of relations in functional logic programming languages:
A relation in a functional logic programming language can be defined by the combination of a computable predicate function and a set-valued functor determining its functional dependencies. The set-valued functor can be used to help complete terms of the relation.
Alternatively, a function can be defined by a set-valued functor and a relation can be defined from it by its set of ordered pairs. As a result, the functional approach and the logical approach can ultimately arrive at the same result in a system based upon topos theory.
See also:
[1] Topoi from preorders
References:
[1] Armstrong's axioms:
Thursday, August 19, 2021
Algebraic operations on functions
Let $F$ be a family of common input $A$ functions then $F$ induces a family of partitions into the lattice $Part(A)$ defined by the kernel of a function. Suppose that $F$ is also equipped with pointwise algebraic operations, then these algebraic operations have an effect on the kernel. This will be today's subject of investigation.
\[ ker : F \to Part(A) \]
Let $(F,+)$ be an algebraic operation, whereby $f + g$ is the function $(f+g)(x) = f(x)+g(x)$. Then the algebraic operation is related to the meet of equivalence relations in $Part(A)$ by the following theorem:
Theorem. $ker(f) \wedge ker(g) \subseteq ker(f+g)$
Proof. if $(x,y) \in ker(f) \vee ker(g)$ this means that $f(x) = f(y)$ and $g(x) = g(y)$. Then suppose we have $f(x+y) = f(x) + f(y)$ then by substitution this is equal to $g(x) + g(y) = g(x+y)$. Therefore, $(x,y) \in ker(f+g)$. $\square$
It is not hard to see that by generalization if $+$ is any n-ary operation this same condition holds over abritrary meets of equivalence relations of functions. An application of this theorem, is that we can get a subalgebra of $+$ with respect to a principal filter in $Part(A)$.
Theorem. let $S$ be a principal filter in $Part(A)$ then the family of all functions for which $ker(f) \in S$ is a subalgebra in $Sub((F,+))$.
Proof. by the fact that $S$ is a principal filter, it is a sublattice of $Part(A)$ and so intersection closed. Therefore, $ker(f) \wedge ker(g) \in S$. By the fact that it is a filter, $ker(f) \wedge ker(g) \in S$ and $ker(f) \wedge ker(g) \subseteq ker(f+g)$ implies $ker(f+g)$ in $S$. Therefore, the family of all functions is $+$ closed. $\square$
We now have a naturally associated function from the lattice of partitions $Part(A)$ to the lattice of subalgebras $Sub(F)$, defined by taking the subset of functions that have partitions greater then $P$. \[ f : Part(A) \to Sub(F) \] This function is antitone, because if $P \subseteq Q$ then $f \in \uparrow P \Rightarrow f \in \uparrow Q$. This antitone relationship between the algebraic operations on functions and the lattice of partitions. Now consider a permutation group in $Sub(S_A)$. Any permutation group maps to a partition by its orbit. \[ o : Sub(S_A) \to Part(A) \] By simple composition, this extends to a function from the lattice of permutation groups to the lattice of subalgebras of the family of functions $F$. \[ f \circ o : Sub(S_A) \to Sub(F) \] The lattice theoretic foundations of invariant theory lie in the fact that any partition in $Part(A)$, such as one defined by a group action, can be extended to a subalgebra. The polynomial ring, $R[x_1,...x_n]$ is a family of functions, whose algebraic operations $+$ and $*$ are defined componentwise: so any principal filter of partitions induces a subalgebra of the polynomial ring.
It is is a basic fact of category theory that the increasing action preorder of composition of functions is the lattice of partitions, so it requires no proof to demonstrate the following.
Proposition. let $g,f$ be functions then $ker(f) \subseteq ker(g \circ f)$.
It follows that partitions induce not only subalgebras, but also left ideals in the composition monoid. By the fact that addition in an endomorphism ring is defined pointwise, this means that partitions of an endomorphism ring extend to right ideals.
Theorem. $ker(f) \wedge ker(g) \subseteq ker(f+g)$
Proof. if $(x,y) \in ker(f) \vee ker(g)$ this means that $f(x) = f(y)$ and $g(x) = g(y)$. Then suppose we have $f(x+y) = f(x) + f(y)$ then by substitution this is equal to $g(x) + g(y) = g(x+y)$. Therefore, $(x,y) \in ker(f+g)$. $\square$
It is not hard to see that by generalization if $+$ is any n-ary operation this same condition holds over abritrary meets of equivalence relations of functions. An application of this theorem, is that we can get a subalgebra of $+$ with respect to a principal filter in $Part(A)$.
Theorem. let $S$ be a principal filter in $Part(A)$ then the family of all functions for which $ker(f) \in S$ is a subalgebra in $Sub((F,+))$.
Proof. by the fact that $S$ is a principal filter, it is a sublattice of $Part(A)$ and so intersection closed. Therefore, $ker(f) \wedge ker(g) \in S$. By the fact that it is a filter, $ker(f) \wedge ker(g) \in S$ and $ker(f) \wedge ker(g) \subseteq ker(f+g)$ implies $ker(f+g)$ in $S$. Therefore, the family of all functions is $+$ closed. $\square$
We now have a naturally associated function from the lattice of partitions $Part(A)$ to the lattice of subalgebras $Sub(F)$, defined by taking the subset of functions that have partitions greater then $P$. \[ f : Part(A) \to Sub(F) \] This function is antitone, because if $P \subseteq Q$ then $f \in \uparrow P \Rightarrow f \in \uparrow Q$. This antitone relationship between the algebraic operations on functions and the lattice of partitions. Now consider a permutation group in $Sub(S_A)$. Any permutation group maps to a partition by its orbit. \[ o : Sub(S_A) \to Part(A) \] By simple composition, this extends to a function from the lattice of permutation groups to the lattice of subalgebras of the family of functions $F$. \[ f \circ o : Sub(S_A) \to Sub(F) \] The lattice theoretic foundations of invariant theory lie in the fact that any partition in $Part(A)$, such as one defined by a group action, can be extended to a subalgebra. The polynomial ring, $R[x_1,...x_n]$ is a family of functions, whose algebraic operations $+$ and $*$ are defined componentwise: so any principal filter of partitions induces a subalgebra of the polynomial ring.
It is is a basic fact of category theory that the increasing action preorder of composition of functions is the lattice of partitions, so it requires no proof to demonstrate the following.
Proposition. let $g,f$ be functions then $ker(f) \subseteq ker(g \circ f)$.
It follows that partitions induce not only subalgebras, but also left ideals in the composition monoid. By the fact that addition in an endomorphism ring is defined pointwise, this means that partitions of an endomorphism ring extend to right ideals.
Wednesday, August 18, 2021
Combinatorics on words by commuting graphs
Every cograph is associated with a laminar tree family, which determines the cograph up to complementation. This can be extended to any graph $G$, by hierarchically decomposing the graph by disjoint union and graph join operations.
Commuting graphs determine the extent to which ordering is relevant to algebraic operations. We will use the hierarchical decomposition of commuting graphs to partially order the words of a semigroup by commutativity.
Example 1. the dart graph
is associated with the following laminar tree family
Example 2. $p_3$ join $p_4$
is associated with the following laminar tree family
The distinguishing property of this second laminar tree family decomposition is that it doesn't entirely terminate in singleton sets. This is because $P_3$ join $P_4$ is not a cograph, as it includes $P_4$ as an induced subgraph. In general the hierarchical decomposition by graph joins and disjoint unions terminates in either singletons or graphs with a $P_4$ component.
Let $G$ be a connected graph, with non connected complement. Then $G$ is the graph join of connected components $C_1,...C_n$. These connected components form a set partition $C$ of the vertex set of $G$. Let $W$ be a word of the vertices of $G$.
Then we can decompose the word $W$ by $C$. Let $C_i$ be a connected component in $C$ then it consists of a set of values of $G$ and therefore $W$. We can form a susbesquence of $W$ by taking the filter of $W$ with respect to the set of elements in $C_i$. So map $C$ and for each component take the filter of $W$ by $C_i$ to get a set of subwords all of which commute with one another.
This decomposes the word into a set of subwords all of which commute with one another, and which therefore for all intents and purposes can be considered to be unordered. This can be turned into a multiset by taking any of the subwords and determining repetitions.
Ordered decomposition:
Let $G$ be a disconnected graph, then we can form a partition $C$ of the vertex set of $G$ by its connectivity. Then let $W$ be a word expressed in terms of the vertices of $G$.
We can partition $W$ by $C$ by indices. Let $W$ be any word input to $C$ then take the first element it belongs to some class $C_i$. So then we can get the maximal prefix subword $S$ of $C$ of elements all who belong to $C_i$, by looping through elements from the start until we get an element not in $C_i$. Remove the prefix subword and turn it into a component, and continue this recursively for the remaining word.
This decomposes a word into a list of consecutive subwords. This are all still ordered, but the relevance of this ordered decomposition is we can now use unordered decomposition on all the individual connected components produced by this process. By continuing the two approaches we can get a hierarchical decomposition of words.
The parsing algorithm:
Recall that a cograph is hierachically decomposed by the graph join and disjoint union operations, producing a laminar tree family. We can apply this to words in order to get a tree decomposition of a word by a commuting graph into ordered and unordered components.
Algorithm: let $G$ be a graph and $W$ a word then form a hierarchical decomposition by the following recursive process:
Example 1. let $G$ be the dart graph of example 1. Let $W$ be $abcdebcedcbeea$. Then we can form a partially ordered word of the form:
This might be implemented a collection of three Java classes like: PartiallyOrderedWord,UnorderedComponent, and OrderedComponent where the later two are protected classes dealing with the ordered and unordered parts of the partially ordered word. Outwardly, the partially ordered word data type would be appear as a collection, for example a Clojure wrapper over it might implemented seqable.
Common interfaces can be defined for lists, multisets, and partially ordered words. In fact, these partially ordered words subsume the other two as special cases. Lists emerge from empty commuting graphs and multisets emerge from complete commuting graphs. In any case, this produces a richer collection of data structures dealing with words in abstract algebra.
Commuting graphs determine the extent to which ordering is relevant to algebraic operations. We will use the hierarchical decomposition of commuting graphs to partially order the words of a semigroup by commutativity.
Example 1. the dart graph
is associated with the following laminar tree family
Example 2. $p_3$ join $p_4$
is associated with the following laminar tree family
The distinguishing property of this second laminar tree family decomposition is that it doesn't entirely terminate in singleton sets. This is because $P_3$ join $P_4$ is not a cograph, as it includes $P_4$ as an induced subgraph. In general the hierarchical decomposition by graph joins and disjoint unions terminates in either singletons or graphs with a $P_4$ component.
Parsing words:
Unordered decomposition:Let $G$ be a connected graph, with non connected complement. Then $G$ is the graph join of connected components $C_1,...C_n$. These connected components form a set partition $C$ of the vertex set of $G$. Let $W$ be a word of the vertices of $G$.
Then we can decompose the word $W$ by $C$. Let $C_i$ be a connected component in $C$ then it consists of a set of values of $G$ and therefore $W$. We can form a susbesquence of $W$ by taking the filter of $W$ with respect to the set of elements in $C_i$. So map $C$ and for each component take the filter of $W$ by $C_i$ to get a set of subwords all of which commute with one another.
This decomposes the word into a set of subwords all of which commute with one another, and which therefore for all intents and purposes can be considered to be unordered. This can be turned into a multiset by taking any of the subwords and determining repetitions.
Ordered decomposition:
Let $G$ be a disconnected graph, then we can form a partition $C$ of the vertex set of $G$ by its connectivity. Then let $W$ be a word expressed in terms of the vertices of $G$.
We can partition $W$ by $C$ by indices. Let $W$ be any word input to $C$ then take the first element it belongs to some class $C_i$. So then we can get the maximal prefix subword $S$ of $C$ of elements all who belong to $C_i$, by looping through elements from the start until we get an element not in $C_i$. Remove the prefix subword and turn it into a component, and continue this recursively for the remaining word.
This decomposes a word into a list of consecutive subwords. This are all still ordered, but the relevance of this ordered decomposition is we can now use unordered decomposition on all the individual connected components produced by this process. By continuing the two approaches we can get a hierarchical decomposition of words.
The parsing algorithm:
Recall that a cograph is hierachically decomposed by the graph join and disjoint union operations, producing a laminar tree family. We can apply this to words in order to get a tree decomposition of a word by a commuting graph into ordered and unordered components.
Algorithm: let $G$ be a graph and $W$ a word then form a hierarchical decomposition by the following recursive process:
- First, take the subgraph of $G$ with respect to the values of the word $W$, to ensure that we are only dealing with the minimum commuting graph necessary.
- Check if $G$ is connected. If it is disconnected, take the ordered decomposition of $W$ with respect to its connected components. This forms a partition of $W$ into consecutive subwords. Recursively compute the hierarchical decomposition of each connected component $C_i$ and then form an ordered component containing each of them
- If $G$ is connected, check if the complement graph $G^C$ is connected. If it is disconnected, $G$ is the graph join of components $C_1, ... C_n$. Then compute the hierarchical decomposition of each of these connected components. Form an unordered component of each of them.
- Finally, if both $G$ and $G^C$ are connected, then we can terminate this process and return back the original word. It cannot be decomposed further.
Example 1. let $G$ be the dart graph of example 1. Let $W$ be $abcdebcedcbeea$. Then we can form a partially ordered word of the form:
{a,a [{[c,d],b},{e},{b,c},{e},{b,[d,c]},{e,e}]}
Example 2. let $G$ be the dart graph of example. Let $W$ be $cdceacdce$. Then the subgraph containing these words is actually a star graph, and all we can do is pull out the central element:
{a,[c,d,c,e,c,d,c,e]}$
Example 3. let $G$ be the graph of example 2. Let $W$ be the word $aaededdae$ then the subgraph containing $W$ is a clique so this can be decomposed into a multiset:
{a,a,a,d,d,d,e,e,e}
Example 4. let $G$ be the graph of example 2. Let $W$ be the word $abcdef$ then this can be decomposed into a partially ordered word of the form:
{a,[b,c,{d,[e,f]}]}
Data structures:
The hierarchical decomposition of a word by a commuting graph produces a partially ordered word expressed as a tree of ordered and unordered components. This gives rise to a special class of data structure, which is like a collection by internally represented by a tree.This might be implemented a collection of three Java classes like: PartiallyOrderedWord,UnorderedComponent, and OrderedComponent where the later two are protected classes dealing with the ordered and unordered parts of the partially ordered word. Outwardly, the partially ordered word data type would be appear as a collection, for example a Clojure wrapper over it might implemented seqable.
Common interfaces can be defined for lists, multisets, and partially ordered words. In fact, these partially ordered words subsume the other two as special cases. Lists emerge from empty commuting graphs and multisets emerge from complete commuting graphs. In any case, this produces a richer collection of data structures dealing with words in abstract algebra.
Tuesday, August 17, 2021
Graph theoretic algebra
The techniques of algebraic graph theory (AGT): like the categories of graphs, lattices of cores, graph automorphisms, and graph related matrices are well known. The techniques of graph theoretic algebra (GTA) are comparatively less well known. The most important of these are the fibers of binary operations.
Fibers of binary operations:
Let $f : X^2 \to X$ be a binary operation and $x \in X$. Then the fiber $f{-1}(x)$ is a binary relation and so $(X, f^{-1}(X))$ forms a directed graph. In graph theoretic algebra, we will study the properties of binary operations by these fiber graphs.
If an operation is commutative, its fibers can be considered to be symmetric graphs. Aside from loops, the fibers of a cancellative commutative operation are a triangle free cluster. Likewise, aside from loops the fibers of a finite total order semilattice are star graphs. A tree has cocluster fibers, and so on. This produces an infinite range of graphs associated to binary operations to study.
Commuting graphs:
The commuting graph of a binary operation is a measure of the symmetry of the fibers of the operation. Let $sc$ be the operation which takes any binary relation to its symmetric component and $Com(f)$ be the symmetric commuting graph with $(a,b) \in Com(f) when ab = ba$. Then the commuting graph is the union of the symmetric components of the fibers of the binary operation $f$: \[ Com(f) = \bigcup_{x \in X} : sc(f^{-1}(x)) \] The characterization of the commuting graph as the union of the symmetric components of the fibers of the binary operation is a perfect example of how it is merely a mesaure of the symmetry of the fibers of the binary operation. The commuting graph is also an equivalence subrelation of the kernel of $f$ in the lattice $Part(X^2)$.
Peripheral topics
The basic organizing principle of graph-theoretic algebra is the realisation that the inverse images of a binary operation are binary relations, and so directed graphs. Inverse images are such a simple concept applicable to any function, that this makes for a perfect organizing principle for graph theoretic algebra.
There are a number of other directions you could take like action preorders, green's relations, closure graphs, comparability graphs of action preorders, power graphs, enhanced power graphs, etc but these would take us too far afield from the basic concept of the fibers inherent to a binary operation. The enhanced power graph is a subgraph of the commuting graph, so some of these concepts can be related back to the core of the subject.
References:
[1] Zero-divisor graphs
[2] Dedekind finiteness
Fibers of binary operations:
Let $f : X^2 \to X$ be a binary operation and $x \in X$. Then the fiber $f{-1}(x)$ is a binary relation and so $(X, f^{-1}(X))$ forms a directed graph. In graph theoretic algebra, we will study the properties of binary operations by these fiber graphs.
- A binary operation is called right cancellative, provided that each fiber is a single-valued binary relation. It is left cancellative if each fiber is inverse single-valued.
- A binary operation is cancellative if each fiber is a one to one binary relation.
- A magma is a quasigroup if each fiber is left total, right total, and one to one.
- A binary operation is commutative if each fiber is symmetric.
- A binary operation is anticommutative if each fiber is antisymmetric.
- A semigroup is a null semigroup iff it has a single fiber which is a complete relation.
- The fibers of a right zero semigroup are constant single valued binary relations, and the fibers of a left zero semigroup are inverse constant single valued binary operations.
- The fibers of a band all have a unique loop edge.
- The fiber of zero is the zero divisor graph of the binary operation, formed by all ordered pairs (a,b) that satisfy the condition ab = 0.
- The fiber of one is all inverse pairs. In the case of a monoid, this has the condition that $(b,a),(c,a) \in f^{-1}(1)$ implies that $b = c$ so that the fiber of the identity in a monoid is ordered triple free.
If an operation is commutative, its fibers can be considered to be symmetric graphs. Aside from loops, the fibers of a cancellative commutative operation are a triangle free cluster. Likewise, aside from loops the fibers of a finite total order semilattice are star graphs. A tree has cocluster fibers, and so on. This produces an infinite range of graphs associated to binary operations to study.
Commuting graphs:
The commuting graph of a binary operation is a measure of the symmetry of the fibers of the operation. Let $sc$ be the operation which takes any binary relation to its symmetric component and $Com(f)$ be the symmetric commuting graph with $(a,b) \in Com(f) when ab = ba$. Then the commuting graph is the union of the symmetric components of the fibers of the binary operation $f$: \[ Com(f) = \bigcup_{x \in X} : sc(f^{-1}(x)) \] The characterization of the commuting graph as the union of the symmetric components of the fibers of the binary operation is a perfect example of how it is merely a mesaure of the symmetry of the fibers of the binary operation. The commuting graph is also an equivalence subrelation of the kernel of $f$ in the lattice $Part(X^2)$.
Peripheral topics
The basic organizing principle of graph-theoretic algebra is the realisation that the inverse images of a binary operation are binary relations, and so directed graphs. Inverse images are such a simple concept applicable to any function, that this makes for a perfect organizing principle for graph theoretic algebra.
There are a number of other directions you could take like action preorders, green's relations, closure graphs, comparability graphs of action preorders, power graphs, enhanced power graphs, etc but these would take us too far afield from the basic concept of the fibers inherent to a binary operation. The enhanced power graph is a subgraph of the commuting graph, so some of these concepts can be related back to the core of the subject.
References:
[1] Zero-divisor graphs
[2] Dedekind finiteness
Monday, August 16, 2021
Commutative J-trivial semigroup presentations
Commutative semigroups have presentations in the lattice of multisets, by their description as quotients of the free semimodule $F(S)$. In the case of commutative groups, there is no uniqueness of presentation even for the cyclic group $C_3$ on three elements. However, for the other fundamental type of commutative semigroups it is often possible to find a unique minimal generating set.
Theorem. let $S$ be a finite commutative J-trivial semigroup, then $S$ has a unique minimal generating set.
Proof. the semigroup $S$ is finite, so it satisfies the ACC on principal ideals. By the maximal condition, let $M$ be the set of all maximal principal ideals of $S$. Then by J-triviality each of these maximal principal ideals is associated with a unique irreducible element $x$. Let $X$ be the set of irreducible elements that generate $M$.
Let $I$ be the current set of irreducibles and $C$ the set of remaining elements of $S$. Then union $X$ to $I$ and remove $(X)$ from $C$. Then we have a new set $C$, which again satisfies the ACC so take its maximal elements and add them to the irreducibles and remove the elements they generate from $C$. Repeat this process a finite number of times to produce the unique minimal generating set $I$. $\square$
The basis of this is the ACC on principal ideals of the commutative J-trivial semigroup. This clearly holds when $S$ is finite. Suppose that $S$ is instead a finitely generated commutative J-trivial semigroup. Then $S$ satisfies the ACC on principal ideals as well.
Theorem. finitely generated commutative semigroups satisfy the ACC on principal ideals
Proof. define $X$ to be any finite set of elements and consider the map \[ f : F(X) \to S \] Mapping any word expressed in $X$ to $S$. Then $f$ is monotone (from the multiset ordering on $F(X)$ words to the increasing action preorder on $S$). Let $T$ be the ascending chain of principal ideals. Then form the ideal closure of $T$ to get an ideal $I$ in $S$ that contains every element of the ascending chain of principal ideals.
Then by the monotonicity of $F$ the ideal $I$ in $S$ reflects back to an ideal in $F(X)$ of the form $f^{-1}(I)$. By Dickson's lemma, this ideal $f^{-1}(X)$ is finitely generated. Consider the finite generators of $f^{-1}(X)$ then they reflect to a set of maximal principal ideals in $T$, these in turn in have a maximal represpentative (their join), so they do not generate the entire ascending chain. $\square$
We can now use this theorem with a generalization of the first theorem, to get a unique minimal generating set for any finitely generated commutative semigroup. More generally, this works for any commutative semigroup satisfying the ACC on principal ideals: for example $(\mathbb{Z}_+,*)$ satisfies the ACC on principal ideals and has a minimal generating set the set of prime numbers.
Theorem. let $S$ be a commutative J-trivial semigroup satisfying the ACC on principal ideals then it has a unique minimal generating set
Proof. (1) the base case: by the maximum condition $S$ has a set of maximum proper principal ideals, which by maximality are not generated by any element so they must be in any minimal generating set (2) we can remove from $S$ the generators of its maximum proper principal ideals and the elements generated by them to get another suborder satisfying the ACC. By transfinite induction this terminates after some ordinal number of steps to produce a minimal generating set. $\square$
One could speculate that the existence of unique generators is applicable to any commutative J-trivial semigroups, but this is not the case. A counter example is $(\mathbb{Q}_+,+)$. This doesn't satisfy the ACC on principal ideals (or any chain condition of any kind because it is dense), so it need not have a unique minimal generating set. A generating set for $(\mathbb{Q},+)$ is any lower interval, but by density there is no minimal lower interval so it doesn't have a unique minimal generating set.
Numerical semigroups are an example of a class of commutative finitely generated J-trivial semigroups. Naturally, it is known that any such numerical semigroup has a unique minimal generating set, which is finite because numerical semigroups are finitely generated. The size of the minimum generating set of a numerical semigroup is its embedding dimension.
Proposition. let $S$ be a commutative finitely generated semigroup, then $\frac{S}{H}$ is finitely generated.
Proof. let $X$ be a finite generating set for $S$ and $\pi : S \to \frac{S}{H}$. Then get the image $\pi(X)$, then this forms a finite generating set for $\frac{S}{H}$. Let $x \in \frac{S}{H}$ then choose a representative in $S$ for it and form its factorisation $t$ in terms of $X$ then $\pi(t)$ is a factorisation of $x$ in $\frac{S}{H}$ expressed in terms of $\pi(X)$, so every term in $\frac{S}{H}$ has a unique factorisation by $\pi(X)$. $\square$
In general, there is not a unique minimal generating set for a finite semigroup. The first counter example is the cyclic group $C_3$ on three elements: it has two different unique generators. In general, the number of generators for a cyclic group is the totient $\phi(n)$. We have a general idea of what finitely generated commutative groups are and what they look like, but no inherent notion of what their generating sets need to be.
The preceding theorem for finitely generated commutative semigroups, demonstrates that every finitely generated commutative semigroup is associated with a condensation $\frac{S}{H}$ which has a unique minimal generating set. This tells you the minimal set of J classes necessary to generate $S$, but still doesn't tell you how to generate each of the classes, or even if other J classes are necessary.
We can now speak about presentations. Suppose that we have a commutative semigroup $S$ with generating set $X$ then we have a map from the free commutative semigroup $F(X)$ to $S$. The free commutative semigroup $F(X)$ is a lattice ordered family of multisets, and the commutative J-trivial semigroup $S$ is naturally partially ordered. As a first step, I would like to relate the order on $F(X)$ to $S$.
Theorem. let $S$ be a commutative semigroup and $C$ a congruence of $S$ then the algebraic preorder on $\frac{S}{C}$ is the ordinary precedence preorder on $C$ with respect to the ordering of $S$.
Proof. suppose $A \subseteq B$ in $\frac{S}{C}$ then $\exists C : AC = B$. By an appropriate choice of representatives, this means that $ac = b$ for some $a \in A, c \in C, b \in B$ so that $a \subseteq b$ which implies that $a \frac{\subseteq}{C} b$. Thus, algebraic precedence in $\frac{S}{C}$ implies ordinary precedence.
Conversely, suppose that $a \frac{\subseteq}{C} b$. This means that there exists some $x$ such that $ax = b$. Consider the projection $pi : S \to \frac{S}{C}$. Then we can get the projection $\pi(x)$ so that $\pi(A)\pi(x) = \pi(B)$ so that $\pi(A) \subseteq \pi(B)$ in $\frac{S}{C}$. Thusly, ordinary precedence applies algebraic precedence in the quotient. $\square$
This implies that in order for the congruence of a commutative J-trivial semigroup to again be J-trivial, all of its equivalence classes must be convex. This generalizes the case for semilattice congruences, lattice congruences, etc. In those cases the congruence classes also need other conditions (like being a subsemilattice or a sublattice). In the finite case, this implies upper or lower bounds, or in the case of congruences of finite lattice that each congruence class is an interval.
Corollary. let $S$ be a commutative J-trivial semigroup and $C$ a congruence with J-trivial quotient. Then the congruence classes of $C$ are convex.
In the case of a semilattice congruence, we have that each congruence class is a subsemilattice. In a finite join semilattice, this implies the existence of upper bounds. This has a further implication: each congruence class has a unique representative. In the case of a finite semilattice congruence, these are the principal filters of irreducibles. It would be nice if this process could pass over to commutative J-trivial semigroups.
We see though, that it does not. The exceptional commutative J-trivial semigroup has neither upper or lower bounds for the congruence class of its intermediate element in its presentation determined by its unique minimal generating set. Thusly, it won't be as easy to characterize the representatives of congruence classes of commutative J-trivial semigroups as it is for semilattices.
The presentations of commutative J-trivial semigroups are interestingly linked to the combinatorics of multiset lattices. This is a major motivation for the study of commutative J-trivial semigroups. The following construction describes how to finite commutative J-trivial semigroups in terms of finite multiset lattices.
Definition. let $S$ be a finite commutative J-trivial semigroup with finite generating set $X$. Then define a map $m : X \to \mathbb{N}$ that assigns each $X$ element to the cardinality of its monogenic semigroup. Then this map $m: X \to \mathbb{N}$ defines a multiset, by considering its outputs to be multiplicities.
Then consider the power multiset $\wp(m)$ consisting of all submultisets of $m$. Then $\wp(m)$ forms a finite multiset lattice. The words of $S^1$ can now be presented by congruence classes in the finite multiset lattice $\wp(m)$. Define the power multiset partition of $S^1$ to be the family of all congruences of terms in $\wp(m)$ by the unique minimal generating set of $S$.
This associates to any element in a finite commutative J-trivial semigroup a finite convex family of multisets. As an application, we can consider any element that is maximally presentable to be any element whose generating set equivalence class has an upper bound. The maximally presentable elements form a subset of $S$.
That subset of commutative J-trivial monoids that have maximal representatives for each element, can be associated to closure operations on finite multiset lattices. This generalisations the representation of semilattices with identity by closures on finite boolean algebras.
Theorem. let $S$ be a finite commutative J-trivial semigroup, then $S$ has a unique minimal generating set.
Proof. the semigroup $S$ is finite, so it satisfies the ACC on principal ideals. By the maximal condition, let $M$ be the set of all maximal principal ideals of $S$. Then by J-triviality each of these maximal principal ideals is associated with a unique irreducible element $x$. Let $X$ be the set of irreducible elements that generate $M$.
Let $I$ be the current set of irreducibles and $C$ the set of remaining elements of $S$. Then union $X$ to $I$ and remove $(X)$ from $C$. Then we have a new set $C$, which again satisfies the ACC so take its maximal elements and add them to the irreducibles and remove the elements they generate from $C$. Repeat this process a finite number of times to produce the unique minimal generating set $I$. $\square$
The basis of this is the ACC on principal ideals of the commutative J-trivial semigroup. This clearly holds when $S$ is finite. Suppose that $S$ is instead a finitely generated commutative J-trivial semigroup. Then $S$ satisfies the ACC on principal ideals as well.
Theorem. finitely generated commutative semigroups satisfy the ACC on principal ideals
Proof. define $X$ to be any finite set of elements and consider the map \[ f : F(X) \to S \] Mapping any word expressed in $X$ to $S$. Then $f$ is monotone (from the multiset ordering on $F(X)$ words to the increasing action preorder on $S$). Let $T$ be the ascending chain of principal ideals. Then form the ideal closure of $T$ to get an ideal $I$ in $S$ that contains every element of the ascending chain of principal ideals.
Then by the monotonicity of $F$ the ideal $I$ in $S$ reflects back to an ideal in $F(X)$ of the form $f^{-1}(I)$. By Dickson's lemma, this ideal $f^{-1}(X)$ is finitely generated. Consider the finite generators of $f^{-1}(X)$ then they reflect to a set of maximal principal ideals in $T$, these in turn in have a maximal represpentative (their join), so they do not generate the entire ascending chain. $\square$
We can now use this theorem with a generalization of the first theorem, to get a unique minimal generating set for any finitely generated commutative semigroup. More generally, this works for any commutative semigroup satisfying the ACC on principal ideals: for example $(\mathbb{Z}_+,*)$ satisfies the ACC on principal ideals and has a minimal generating set the set of prime numbers.
Theorem. let $S$ be a commutative J-trivial semigroup satisfying the ACC on principal ideals then it has a unique minimal generating set
Proof. (1) the base case: by the maximum condition $S$ has a set of maximum proper principal ideals, which by maximality are not generated by any element so they must be in any minimal generating set (2) we can remove from $S$ the generators of its maximum proper principal ideals and the elements generated by them to get another suborder satisfying the ACC. By transfinite induction this terminates after some ordinal number of steps to produce a minimal generating set. $\square$
One could speculate that the existence of unique generators is applicable to any commutative J-trivial semigroups, but this is not the case. A counter example is $(\mathbb{Q}_+,+)$. This doesn't satisfy the ACC on principal ideals (or any chain condition of any kind because it is dense), so it need not have a unique minimal generating set. A generating set for $(\mathbb{Q},+)$ is any lower interval, but by density there is no minimal lower interval so it doesn't have a unique minimal generating set.
Numerical semigroups are an example of a class of commutative finitely generated J-trivial semigroups. Naturally, it is known that any such numerical semigroup has a unique minimal generating set, which is finite because numerical semigroups are finitely generated. The size of the minimum generating set of a numerical semigroup is its embedding dimension.
Proposition. let $S$ be a commutative finitely generated semigroup, then $\frac{S}{H}$ is finitely generated.
Proof. let $X$ be a finite generating set for $S$ and $\pi : S \to \frac{S}{H}$. Then get the image $\pi(X)$, then this forms a finite generating set for $\frac{S}{H}$. Let $x \in \frac{S}{H}$ then choose a representative in $S$ for it and form its factorisation $t$ in terms of $X$ then $\pi(t)$ is a factorisation of $x$ in $\frac{S}{H}$ expressed in terms of $\pi(X)$, so every term in $\frac{S}{H}$ has a unique factorisation by $\pi(X)$. $\square$
In general, there is not a unique minimal generating set for a finite semigroup. The first counter example is the cyclic group $C_3$ on three elements: it has two different unique generators. In general, the number of generators for a cyclic group is the totient $\phi(n)$. We have a general idea of what finitely generated commutative groups are and what they look like, but no inherent notion of what their generating sets need to be.
The preceding theorem for finitely generated commutative semigroups, demonstrates that every finitely generated commutative semigroup is associated with a condensation $\frac{S}{H}$ which has a unique minimal generating set. This tells you the minimal set of J classes necessary to generate $S$, but still doesn't tell you how to generate each of the classes, or even if other J classes are necessary.
We can now speak about presentations. Suppose that we have a commutative semigroup $S$ with generating set $X$ then we have a map from the free commutative semigroup $F(X)$ to $S$. The free commutative semigroup $F(X)$ is a lattice ordered family of multisets, and the commutative J-trivial semigroup $S$ is naturally partially ordered. As a first step, I would like to relate the order on $F(X)$ to $S$.
Theorem. let $S$ be a commutative semigroup and $C$ a congruence of $S$ then the algebraic preorder on $\frac{S}{C}$ is the ordinary precedence preorder on $C$ with respect to the ordering of $S$.
Proof. suppose $A \subseteq B$ in $\frac{S}{C}$ then $\exists C : AC = B$. By an appropriate choice of representatives, this means that $ac = b$ for some $a \in A, c \in C, b \in B$ so that $a \subseteq b$ which implies that $a \frac{\subseteq}{C} b$. Thus, algebraic precedence in $\frac{S}{C}$ implies ordinary precedence.
Conversely, suppose that $a \frac{\subseteq}{C} b$. This means that there exists some $x$ such that $ax = b$. Consider the projection $pi : S \to \frac{S}{C}$. Then we can get the projection $\pi(x)$ so that $\pi(A)\pi(x) = \pi(B)$ so that $\pi(A) \subseteq \pi(B)$ in $\frac{S}{C}$. Thusly, ordinary precedence applies algebraic precedence in the quotient. $\square$
This implies that in order for the congruence of a commutative J-trivial semigroup to again be J-trivial, all of its equivalence classes must be convex. This generalizes the case for semilattice congruences, lattice congruences, etc. In those cases the congruence classes also need other conditions (like being a subsemilattice or a sublattice). In the finite case, this implies upper or lower bounds, or in the case of congruences of finite lattice that each congruence class is an interval.
Corollary. let $S$ be a commutative J-trivial semigroup and $C$ a congruence with J-trivial quotient. Then the congruence classes of $C$ are convex.
In the case of a semilattice congruence, we have that each congruence class is a subsemilattice. In a finite join semilattice, this implies the existence of upper bounds. This has a further implication: each congruence class has a unique representative. In the case of a finite semilattice congruence, these are the principal filters of irreducibles. It would be nice if this process could pass over to commutative J-trivial semigroups.
We see though, that it does not. The exceptional commutative J-trivial semigroup has neither upper or lower bounds for the congruence class of its intermediate element in its presentation determined by its unique minimal generating set. Thusly, it won't be as easy to characterize the representatives of congruence classes of commutative J-trivial semigroups as it is for semilattices.
The presentations of commutative J-trivial semigroups are interestingly linked to the combinatorics of multiset lattices. This is a major motivation for the study of commutative J-trivial semigroups. The following construction describes how to finite commutative J-trivial semigroups in terms of finite multiset lattices.
Definition. let $S$ be a finite commutative J-trivial semigroup with finite generating set $X$. Then define a map $m : X \to \mathbb{N}$ that assigns each $X$ element to the cardinality of its monogenic semigroup. Then this map $m: X \to \mathbb{N}$ defines a multiset, by considering its outputs to be multiplicities.
Then consider the power multiset $\wp(m)$ consisting of all submultisets of $m$. Then $\wp(m)$ forms a finite multiset lattice. The words of $S^1$ can now be presented by congruence classes in the finite multiset lattice $\wp(m)$. Define the power multiset partition of $S^1$ to be the family of all congruences of terms in $\wp(m)$ by the unique minimal generating set of $S$.
This associates to any element in a finite commutative J-trivial semigroup a finite convex family of multisets. As an application, we can consider any element that is maximally presentable to be any element whose generating set equivalence class has an upper bound. The maximally presentable elements form a subset of $S$.
That subset of commutative J-trivial monoids that have maximal representatives for each element, can be associated to closure operations on finite multiset lattices. This generalisations the representation of semilattices with identity by closures on finite boolean algebras.
Thursday, August 12, 2021
Bound sharing graphs
Let $P$ be a poset satisfying the ascending chain condition, then the maximal principal ideals of $P$ generate a graph: the bound sharing graph of $P$. This has $a \sim b \Leftrightarrow \exists z: a,b \subseteq z$. The relation of this graph to the maximal principal ideals is proven below:
Lemma 1. let $P$ be a poset satisfying the ACC and let $a,b \in P$ such that $\exists z : a,b \subseteq z$ then $a,b$ both share common membership in some maximal principal ideal of $P$.
Proof. let $a,b \in P$ and consider the set of upper bounds $U = \{c : a,b \subseteq c\}$. Then $z \in U$ so $U$ is not empty. By the maximal condition implied by the ACC, $U$ has maximal elements. Let $m$ be a maximal element in $U$, then $m$ is maximal in $P$. It follows that the principal ideal $\downarrow m$ is a maximal principal ideal. $\square$
The maximal principal ideals of $P$ form a sperner family, which doesn't necessarily need to be a maximal cliques family. It is a maximal cliques family provided that there is no triple of elements all of which piecewise belong in separate maximal principal ideals, such as in the six element crown. It in order to effectively reason about the bound sharing graph, we need to relate maximal prinicpal ideals to maximal cliques.
Lemma 2. let $m$ be a maximal element of $P$. Then the maximal principal ideal $\downarrow m$ is a maximal clique in the bound sharing graph.
Proof. let $m$ be maximal then any $a \sim m$ means that $a,m \subseteq z$ but $m$ is maximal so this means $a,m \subseteq z \subseteq m$ which can be reduced to $a \subseteq m$. Therefore, the neighbourhood of $m$ consists of all the elements of its principal ideal. Every element of a principal ideal is a clique of the bound sharing graph. To see that this is a maximal clique, suppose $C$ isa larger clique then $\downarrow m$ then there exists $x \not\in \downarrow m$ such that $x \sim m$ which is a contradiction. $\square$
Let $G$ be a graph, and $M$ be its hypergraph of maximal cliques. Then the degree of a vertex of the graph $G$ is different from the degree of its maximal cliques hypergraph. This leads to the following important definition:
Definition. let $G$ be a graph and $x$ a vertex of $G$. Then the maximal clique degree of $x$ is the number of maximal cliques containing $x$.
An important special case is when a vertex has maximal cliques degree one. For example, in a cluster graph every vertex must have maximal cliques degree one. These vertices have the following characterization:
Theorem. let $G$ be a graph and $x$ a vertex of $G$. Then $x$ has maximal cliques degree one iff the neighbourhood of $x$ is a clique.
Proof. (1) every clique containing $x$ is contained in the neighbourhood of $x$, because every element of clique a containing $x$ must adjacent to $x$. Therefore, if the neighbourhood $N(x)$ is a clique it is a maximal clique, since any other clique must be contianed in it.
(2) conversely, let $x$ have maximal clique degree and suppose that its neighbourhood is not a clique. Then there are elements $y,z$ such that $x \sim y,z$ and $y \not\sim z$ then $\{x,y\}$ and $\{x,z\}$ must belong to separate maximal cliques, so $x$ is not maximal clique degrees one which is a contradiction. $\square$
We saw that with respect to the bound sharing graph, the maximal elements have maximal clique degree one and they generate the entire graph. This leads to the following characterisation of bound sharing graphs:
Theorem. let $G$ be a graph then $G$ is the bound sharing graph of a poset $P$ provided that $G$ satisfies one of the following two conditions:
(2) conversely, let $G$ be a graph that satisfies either of these two equivalent conditions. Then we can construct a poset that has $G$ as its bound sharing graph. The elements with maximal clique degree greater then one will be our minimal elements. Then for each maximal clique $M$ of $G$ create a chain containing all the degree one elements of $M$ and make it greater then all the elements of maximal clique degree greater then one in $P$. $\square$
As an application, we will characterize the zero divisor graph of a finite semilattice $S$ in terms of bound sharing. In a finite semilattice $ab = 0$ means that $a,b$ do not share an upper bound less then $0$, so it translates into the characterization of the bound sharing graph.
Proposition. let $S$ be a finite semilattice, then the zero divisor graph $ab = 0$ is the complement of the upper bound sharing graph of non-zero elements with zero adjoined as a central element with loop.
Proof. let $S$ be a finite semilattice and $G$ its zero divisor graph. Then consider the complement $G^{C}$, we have $a \sim b$ in $G^{C}$ provided that $ab \not= 0$. First of all this means $a,b \not= 0$ so the complement can be restricted to the non-zero elements. Then among the non-zero elements $ab \not= 0$ means that there exists $z \not= 0$ such that $a,b \subseteq z$. It follows that $a,b$ share a non-zero upper bound.
In other words, they share an upper bound in the upper bound sharing graph of the poset with zero removed. Conversely, if they share a non-zero upper bound then their join cannot be zero, because their join is the least upper bound and the zero element is maximal. Finally, $ab = 0$ whenever $a = 0$ or $b = 0$ so we can adjoin $0$ as a central element and it has a loop because $0$ is idempotent. $\square$
The main application of these graphs is to characterize the bound sharing graphs of finite semilattices. As the principal filters of $S$ are also subsemilattices, all the different fibers $ab = x$ of a semilattice can be characterized in this way. So by this theorem, we have fully characterized the graph-theoretic properties of semilattices.
As an example, the fibers of any finite total order $T$ as a join semilattice are all star graphs whose central vertex has a loop. In a tree the fibers are always cocluster graphs, because the upper bound sharing graph of a forest is a cluster graph. Any finite graph satisfying these conditions can be formed as the fiber of a semilattice.
Lemma 1. let $P$ be a poset satisfying the ACC and let $a,b \in P$ such that $\exists z : a,b \subseteq z$ then $a,b$ both share common membership in some maximal principal ideal of $P$.
Proof. let $a,b \in P$ and consider the set of upper bounds $U = \{c : a,b \subseteq c\}$. Then $z \in U$ so $U$ is not empty. By the maximal condition implied by the ACC, $U$ has maximal elements. Let $m$ be a maximal element in $U$, then $m$ is maximal in $P$. It follows that the principal ideal $\downarrow m$ is a maximal principal ideal. $\square$
The maximal principal ideals of $P$ form a sperner family, which doesn't necessarily need to be a maximal cliques family. It is a maximal cliques family provided that there is no triple of elements all of which piecewise belong in separate maximal principal ideals, such as in the six element crown. It in order to effectively reason about the bound sharing graph, we need to relate maximal prinicpal ideals to maximal cliques.
Lemma 2. let $m$ be a maximal element of $P$. Then the maximal principal ideal $\downarrow m$ is a maximal clique in the bound sharing graph.
Proof. let $m$ be maximal then any $a \sim m$ means that $a,m \subseteq z$ but $m$ is maximal so this means $a,m \subseteq z \subseteq m$ which can be reduced to $a \subseteq m$. Therefore, the neighbourhood of $m$ consists of all the elements of its principal ideal. Every element of a principal ideal is a clique of the bound sharing graph. To see that this is a maximal clique, suppose $C$ isa larger clique then $\downarrow m$ then there exists $x \not\in \downarrow m$ such that $x \sim m$ which is a contradiction. $\square$
Let $G$ be a graph, and $M$ be its hypergraph of maximal cliques. Then the degree of a vertex of the graph $G$ is different from the degree of its maximal cliques hypergraph. This leads to the following important definition:
Definition. let $G$ be a graph and $x$ a vertex of $G$. Then the maximal clique degree of $x$ is the number of maximal cliques containing $x$.
An important special case is when a vertex has maximal cliques degree one. For example, in a cluster graph every vertex must have maximal cliques degree one. These vertices have the following characterization:
Theorem. let $G$ be a graph and $x$ a vertex of $G$. Then $x$ has maximal cliques degree one iff the neighbourhood of $x$ is a clique.
Proof. (1) every clique containing $x$ is contained in the neighbourhood of $x$, because every element of clique a containing $x$ must adjacent to $x$. Therefore, if the neighbourhood $N(x)$ is a clique it is a maximal clique, since any other clique must be contianed in it.
(2) conversely, let $x$ have maximal clique degree and suppose that its neighbourhood is not a clique. Then there are elements $y,z$ such that $x \sim y,z$ and $y \not\sim z$ then $\{x,y\}$ and $\{x,z\}$ must belong to separate maximal cliques, so $x$ is not maximal clique degrees one which is a contradiction. $\square$
We saw that with respect to the bound sharing graph, the maximal elements have maximal clique degree one and they generate the entire graph. This leads to the following characterisation of bound sharing graphs:
Theorem. let $G$ be a graph then $G$ is the bound sharing graph of a poset $P$ provided that $G$ satisfies one of the following two conditions:
- $G$ is generated by its principal adjacency filter maximal cliques
- Every edge of $G$ is contained in the clique neighbourhood of some element.
(2) conversely, let $G$ be a graph that satisfies either of these two equivalent conditions. Then we can construct a poset that has $G$ as its bound sharing graph. The elements with maximal clique degree greater then one will be our minimal elements. Then for each maximal clique $M$ of $G$ create a chain containing all the degree one elements of $M$ and make it greater then all the elements of maximal clique degree greater then one in $P$. $\square$
As an application, we will characterize the zero divisor graph of a finite semilattice $S$ in terms of bound sharing. In a finite semilattice $ab = 0$ means that $a,b$ do not share an upper bound less then $0$, so it translates into the characterization of the bound sharing graph.
Proposition. let $S$ be a finite semilattice, then the zero divisor graph $ab = 0$ is the complement of the upper bound sharing graph of non-zero elements with zero adjoined as a central element with loop.
Proof. let $S$ be a finite semilattice and $G$ its zero divisor graph. Then consider the complement $G^{C}$, we have $a \sim b$ in $G^{C}$ provided that $ab \not= 0$. First of all this means $a,b \not= 0$ so the complement can be restricted to the non-zero elements. Then among the non-zero elements $ab \not= 0$ means that there exists $z \not= 0$ such that $a,b \subseteq z$. It follows that $a,b$ share a non-zero upper bound.
In other words, they share an upper bound in the upper bound sharing graph of the poset with zero removed. Conversely, if they share a non-zero upper bound then their join cannot be zero, because their join is the least upper bound and the zero element is maximal. Finally, $ab = 0$ whenever $a = 0$ or $b = 0$ so we can adjoin $0$ as a central element and it has a loop because $0$ is idempotent. $\square$
The main application of these graphs is to characterize the bound sharing graphs of finite semilattices. As the principal filters of $S$ are also subsemilattices, all the different fibers $ab = x$ of a semilattice can be characterized in this way. So by this theorem, we have fully characterized the graph-theoretic properties of semilattices.
As an example, the fibers of any finite total order $T$ as a join semilattice are all star graphs whose central vertex has a loop. In a tree the fibers are always cocluster graphs, because the upper bound sharing graph of a forest is a cluster graph. Any finite graph satisfying these conditions can be formed as the fiber of a semilattice.
Wednesday, August 11, 2021
Elementary topos embeddings
In order theory, it is customary to embed posets in boolean algebras. It would be nice if topoi could play the role of boolean algebras in category theory: then preorders, monoids, and other categories can be embedded in elementary topoi. This is a vast generalisation of the representation of posets by set systems in order theory.
Order theory:
There are two fundamental ways of representing posets by embedding in $Sets$: (1) each element $x$ can be represented as a singleton sets $\{x\}$ with each $x \subseteq y$ represented by the unique function of singletons: $\{x\} \to \{y\}$ and (2) given a set theoretic representation (such as representation by principal ideals) each element can be represented by a set and each edge can be represented by the unique corresponding inclusion function.
Monoid theory:
Every monoid can be represented by its self-induced actions. Let $M$ be a monoid, then its left action $l : M \to Sets$ defined by $l_x(y) = xy$ is clearly a monoid action, and it is faithful because $M$ is a monoid. Self-induced actions on a semigroup don't need be faithful. As this equally well applies to groups, this reproduces Cayley's theorem from group theory.
Category theory:
The Yoneda embedding in category theory just generalizes the representation by self-induced actions in monoid theory. The interesting thing is this embedding $h : C \to [C^{op}, Sets]$ embeds any small category $C$ into it a set-valued functor topos, so it is safe to say that small categories are simply subcategories of elementary topoi. There are now two topos theoretic aspects of categories: (1) topos embeddings and (2) topos constituents of a category.
References:
[1] Yoneda embedding
Order theory:
There are two fundamental ways of representing posets by embedding in $Sets$: (1) each element $x$ can be represented as a singleton sets $\{x\}$ with each $x \subseteq y$ represented by the unique function of singletons: $\{x\} \to \{y\}$ and (2) given a set theoretic representation (such as representation by principal ideals) each element can be represented by a set and each edge can be represented by the unique corresponding inclusion function.
Monoid theory:
Every monoid can be represented by its self-induced actions. Let $M$ be a monoid, then its left action $l : M \to Sets$ defined by $l_x(y) = xy$ is clearly a monoid action, and it is faithful because $M$ is a monoid. Self-induced actions on a semigroup don't need be faithful. As this equally well applies to groups, this reproduces Cayley's theorem from group theory.
Category theory:
The Yoneda embedding in category theory just generalizes the representation by self-induced actions in monoid theory. The interesting thing is this embedding $h : C \to [C^{op}, Sets]$ embeds any small category $C$ into it a set-valued functor topos, so it is safe to say that small categories are simply subcategories of elementary topoi. There are now two topos theoretic aspects of categories: (1) topos embeddings and (2) topos constituents of a category.
References:
[1] Yoneda embedding
Tuesday, August 10, 2021
Topos constituents of a category
There are number of different ways to reason logically about a category. We could use methods of lattice theory, like lattices of subalgebras and congruences. Another approach is to relate categories to the ordered algebraic structures of mathematical logic like relation algebras. The decisive role is ultimately played by topos theory, which provides the logic for all algebraic structures.
The topos of quivers comes into play here, as one of the constituent topoi of a category. Every small category is associated with a forgetful functor to the topos of quivers, whose adjoint takes any quiver to the associated free category. The forgetful functor to the topos of sets is then a constituent part of this topos valued functor.
Proposition. let $F: Cat \to Quiv$ be the function which forgets the composition of the category, then $F$ is a functor.
Proof. let $f : A \to B$ be in $Arrows(Cat)$ then $F(f) : F(a) \to F(b)$ so that $F(s(f)) = F(a) = s(F(f))$ and $F(t(f)) = F(b) = t(F(f))$. This function splits a functor into its edge and vertex mappings so that $F(f) = (f_1,f_2)$ and so $F(f \circ g) = (f_1 \circ g_1, f_2 \circ g_2) = (f_1,g_1) \circ (f_2,g_2) = F(f) \circ F(g)$. Finally, $F(1_X) = (1_Ob(C),1_Arrows(c)) = 1_F(X)$. $\square$
Corollary. the map $G \circ F : Cat \to Quiv \to Sets$ makes $Cat$ into a concrete category. So $Sets$ is another one of the constituent topoi of $Cat$.
Much of the previous work in category theory, was done by considering $Cat$ to be a concrete category, and categories to be structured sets. In particular, this yields a significant simplification of the theory of functors. With this, we can consider functors to be a special type of function. In particular, we can apply the logic of functions provided by the topos of functions $Sets^{\to}$ to them. With this, we can conider categories to be structured quivers.
In the case of categories, they are certainly not just determined by the data of a quiver. They are compositional quivers: they also include a function object. So it also remains to show the forgetful functor from any category to its composition function is a functor.
Definition. let $\circ : Cat \to Sets^{\to}$. Then $\circ$ has two components (1) its map any category $C$ to its composition function $\circ_C : Arrows(C)^2_* \to Arrows(C)$ and (2) given any functor $F: C \to D$ it maps it to a morphism of functions $\circ(G) : \circ_C \to \circ_D$ defined by $((F|_{Arrows(C)})^2_*,F|_{Arrows(C)})$
Theorem. let $\circ : Cat \to Sets^{\to}$ be the functor that maps any category to its composition function. Then $\circ$ is a functor.
Proof. let $F$ be a functor then $F(g \circ_C h) = F(g) \circ_D F(h)$ so that we have a commutative diagram like
Which means that a functor is a morphism of functions $\circ_C$ to $\circ_D$. Then composition is defined componentwise over arrows, so this is a functor. $\square$
It follows that we can reason about categories using the topos $Quiv \times Sets^{\to}$ consisting of ordered pairs of a quiver and a function. This mirrors the process by which we considered all the algebraic structures of universal algebra in terms of elementary topoi. Here are the various constituent topoi of a category:
As $Cat$ can be embedded in the topos $Quiv \times Sets^{\to}$ the elements of its logic: the lattices of subcategories and congruences can now be in the larger context of topos theory. Naturally, the subalgebras and congruences are a subset of what is possible in the larger topos context, because we require that subobjects and quotients remains categories instead of other functional quivers.
Indeed, this shows that since $Cat$ is not a topos, it contains only a subset of reasoning about even categories. This is one reason one $Cat$ can never be used as a foundation of mathematics (e.g ETCS) because it is too weak to properly reason about its own objects, and what they are. The topos perspective reveals deeper properties of categories, and all other algebraic structures which makes it absolutely indispensible.
An example of the power of the topos perspective, is that if we consider $\circ$ as an object of the topos of functions $Sets^{\to}$, we can get non-standard congruences not possible in $Cat$. When working with functions, there is always a need to do all kinds of input/output analysis and no subset of input/output relations is ever sufficent. This way, we can take any partition of the morphism pairs relation to get a quotient.
The congruence $Con(C)$ of a category, is a subset of all input/output relation valid for a category. By the topos perspective, it can defined by an ordered pair $(P,Q)$ which forms a quiver congruence and for which $(Q^2,Q)$ is a function congruence, so they are a subset of $Quiv \times Sets^{\to}$ congruences. This puts congruences in the larger context.
In the case of $Sub(C)$ the lattice of subcategories of a category $C$, the underlying quiver of a subcategory is a subquiver of the underlying quiver of its parent category. Likewise, the composition function is a subfunction of the parent composition function. As before, not all subobjects arise in this way, so the full theory of categorical structure can only be provided by topos theory.
Classical mathematicians correctly understood the importance of set theory in mathematical foundations. Set theory has withstood the test of the time, and any foundational system that ignores the importance of sets is bound to fail. Topos theory is just close enough to set theory, that it can extend it to create new foundations.
External links
Categories - the stacks project
The topos of quivers comes into play here, as one of the constituent topoi of a category. Every small category is associated with a forgetful functor to the topos of quivers, whose adjoint takes any quiver to the associated free category. The forgetful functor to the topos of sets is then a constituent part of this topos valued functor.
Proposition. let $F: Cat \to Quiv$ be the function which forgets the composition of the category, then $F$ is a functor.
Proof. let $f : A \to B$ be in $Arrows(Cat)$ then $F(f) : F(a) \to F(b)$ so that $F(s(f)) = F(a) = s(F(f))$ and $F(t(f)) = F(b) = t(F(f))$. This function splits a functor into its edge and vertex mappings so that $F(f) = (f_1,f_2)$ and so $F(f \circ g) = (f_1 \circ g_1, f_2 \circ g_2) = (f_1,g_1) \circ (f_2,g_2) = F(f) \circ F(g)$. Finally, $F(1_X) = (1_Ob(C),1_Arrows(c)) = 1_F(X)$. $\square$
Corollary. the map $G \circ F : Cat \to Quiv \to Sets$ makes $Cat$ into a concrete category. So $Sets$ is another one of the constituent topoi of $Cat$.
Much of the previous work in category theory, was done by considering $Cat$ to be a concrete category, and categories to be structured sets. In particular, this yields a significant simplification of the theory of functors. With this, we can consider functors to be a special type of function. In particular, we can apply the logic of functions provided by the topos of functions $Sets^{\to}$ to them. With this, we can conider categories to be structured quivers.
- Structured quivers
- Structured sets
In the case of categories, they are certainly not just determined by the data of a quiver. They are compositional quivers: they also include a function object. So it also remains to show the forgetful functor from any category to its composition function is a functor.
Definition. let $\circ : Cat \to Sets^{\to}$. Then $\circ$ has two components (1) its map any category $C$ to its composition function $\circ_C : Arrows(C)^2_* \to Arrows(C)$ and (2) given any functor $F: C \to D$ it maps it to a morphism of functions $\circ(G) : \circ_C \to \circ_D$ defined by $((F|_{Arrows(C)})^2_*,F|_{Arrows(C)})$
Theorem. let $\circ : Cat \to Sets^{\to}$ be the functor that maps any category to its composition function. Then $\circ$ is a functor.
Proof. let $F$ be a functor then $F(g \circ_C h) = F(g) \circ_D F(h)$ so that we have a commutative diagram like
Which means that a functor is a morphism of functions $\circ_C$ to $\circ_D$. Then composition is defined componentwise over arrows, so this is a functor. $\square$
It follows that we can reason about categories using the topos $Quiv \times Sets^{\to}$ consisting of ordered pairs of a quiver and a function. This mirrors the process by which we considered all the algebraic structures of universal algebra in terms of elementary topoi. Here are the various constituent topoi of a category:
- Sets: the underlying set of a category makes $Cat$ into a concrete category
- $Sets^2$: the underlying set can also be considered to be two sets: the set of objects and the set of morphisms
- $Quiv$: the underlying quiver of a category
- $Sets^{\to}$: the composition function is a topos object
- The quiver of a category is preposetal, so that its underlying binary relation is a preorder.
- The composition function of a category is a partial semigroup, in the sense that if $(A \circ B) \circ C$ and $A \circ (B \circ C)$ both exist then they must coincide.
As $Cat$ can be embedded in the topos $Quiv \times Sets^{\to}$ the elements of its logic: the lattices of subcategories and congruences can now be in the larger context of topos theory. Naturally, the subalgebras and congruences are a subset of what is possible in the larger topos context, because we require that subobjects and quotients remains categories instead of other functional quivers.
Indeed, this shows that since $Cat$ is not a topos, it contains only a subset of reasoning about even categories. This is one reason one $Cat$ can never be used as a foundation of mathematics (e.g ETCS) because it is too weak to properly reason about its own objects, and what they are. The topos perspective reveals deeper properties of categories, and all other algebraic structures which makes it absolutely indispensible.
An example of the power of the topos perspective, is that if we consider $\circ$ as an object of the topos of functions $Sets^{\to}$, we can get non-standard congruences not possible in $Cat$. When working with functions, there is always a need to do all kinds of input/output analysis and no subset of input/output relations is ever sufficent. This way, we can take any partition of the morphism pairs relation to get a quotient.
The congruence $Con(C)$ of a category, is a subset of all input/output relation valid for a category. By the topos perspective, it can defined by an ordered pair $(P,Q)$ which forms a quiver congruence and for which $(Q^2,Q)$ is a function congruence, so they are a subset of $Quiv \times Sets^{\to}$ congruences. This puts congruences in the larger context.
In the case of $Sub(C)$ the lattice of subcategories of a category $C$, the underlying quiver of a subcategory is a subquiver of the underlying quiver of its parent category. Likewise, the composition function is a subfunction of the parent composition function. As before, not all subobjects arise in this way, so the full theory of categorical structure can only be provided by topos theory.
Classical mathematicians correctly understood the importance of set theory in mathematical foundations. Set theory has withstood the test of the time, and any foundational system that ignores the importance of sets is bound to fail. Topos theory is just close enough to set theory, that it can extend it to create new foundations.
External links
Categories - the stacks project
Sunday, August 8, 2021
Topos of quivers
I take the point of view that topos theory is the best foundation for algebra. This is based upon the point of view that the most important aspects of the theory of functions, like input/output analysis are understood by the topos of functions. The topoi of sets and functions are enough to interpret classical algebraic structures.
Another topos that can be used as the foundation of other algebraic structures, like categories, is the topos of quivers. These are defined by set-valued functors over the category with two objects $E$ and $V$ and parallel edges $s$ and $t$ between them:
As can be seen from this diagram, $X$ is neither a preorder nor a monoid. Indeed, $X$ can be considered to be the simplest category that is neither of these two simpler cases. Thus, $Quiv$ can be considered to be the first example of a topos that isn't produced by a preorder or a monoid.
This diagram explains the topos of quivers. The subobject classifier can be understood with a few more diagrams, which I have prepared for you next. After discussing the basic aspects of quivers, we will move on to discussing functors of quivers.
As well as the following lattice of edge truth values:
These are combined to produce an object of truth values $\Omega$ which is internal to the topos of quivers.
All that remains is to demonstrate that the working of the characteristic morphism, which maps a quivers to its vertex and edge truth values.
Definition. let $S \subseteq T$ be quivers. Then the characteristic morphism $\chi : T \to \Omega$ is the ordered pair of functions $(\chi_e,\chi_v)$. The first function $(\chi_e)$ maps an edge $(a,b)$ to a set of truth values containing the truth value $s$ iff the source element $a$ is in $T$, $t$ iff the target $b$ is in $T$, and $e$ iff $(a,b) \in T$. The second function $\chi_v$ is the characteristic function of sets.
Proposition. $(\chi_e,\chi_v) : T \to \Omega$ is a morphism of quivers.
Proof. let $e \in Hom(a,b)$. Then there are four cases (1) $f(e) = \emptyset$ then $f(e) \in Hom(\emptyset,\emptyset)$. (2) $f(e) = \{s\}$ then $f(e) \in Hom(\{v\},\emptyset)$ (3) $f(e) = \{t\}$ then $f(e) \in Hom(\emptyset,\{v\})$ (4) either $f(e) = \{s,t\}$ or $f(e) = \{s,t,e\}$ then $f(e) \in Hom(\{v\},\{v\})$. In each case $f(e) \in Hom(f(a),f(b))$. $\square$
Let $Q$ and $R$ be quivers. Then the coproduct $Q+R$ corresponds to the disjoint union of graphs. Then $Q$ and $R$ are in two separate connected components. The product $Q \times R$ has $(E_Q \times E_R, V_Q \times V_R)$ as its underlying set, and it corresponds to the product of graphs. All other limits/colimits are defined componentwise.
Lattice of subobjects:
Let $Q$ be a quiver, then $Sub(Q)$ is the distributive lattice defined by lower sets of the dependency ordering, whereby an edge is dependent upon the vertices it contains. It is fully determined by the subobject classifier.
Lattice of congruences:
Let $Q$ be a quiver. Then $Con(Q)$ is the intersection of $Con(s)$ and $Con(t)$, the congruence lattices of the source and target functions. In particular, given an ordered pair of equivalence relations $(E_1,E_2)$ then this ordered pair is a congruence of both the source and target functions. Any such ordered pair produces a quotient quiver.
Theorem. let $r: Quiv \to Rel$ the function that maps any quiver to its underlying binary relation. Then $r$ is a functor.
Proof. let $f : Q \to T$ be a morphism of quivers. Then suppose $Hom(a,b) \not= \emptyset$ then $\exists e \in Hom(a,b)$ so that $f(e) \in Hom(f(a),f(b)$. Thus, $Hom(f(a),f(b)) \not= \emptyset$. An edge $(a,b)$ is in $r(Q)$ provided that its hom class is not empty, so that $(a,b) \in r(Q) \Rightarrow (f(a),f(b)) \in r(T)$. It follows that $r(f)$ is a relation homomorphism. $r$ corresponds to the forgetful functor to the vertex set, so $r$ is a well defined functor. $\square$
Lemma. let $f: Q \to T$ be a morphism of quivers, such that $T$ is a thin quiver. Then $f$ is fully determined by its vertex mapping.
Proof. let $e$ be an edge of $Q$ which is in $Hom(a,b)$ then $f(e) \in Hom(f(a),f(b))$. There is a unique edge $e' \in Hom(f(a),f(b))$ by the fact that $T$ is a thin quiver, so that $f(e) = e$ for every edge in $Q$. $\square$
Theorem. let $Tq$ be the full subcategory of the topos of quivers consisting of thin quivers. Then $f : Tq \to Rel$ is an isomorphism of categories.
Proof. (1) by restriction of the relation functor, $f$ is a functor from thin quivers to relations (2) by the previous lemma, given any morphism of relations we can cast it to a morphism of quivers so we can form the inverse functor $f^{-1}$. These two functors are inverses of one another, so they are isomorphisms. $\square$
Corollary. the category of simple graphs can be embedded in the topos of quivers, by taking the full subcategory of thin symmetric irreflexive thin quivers.
This interprets the category of simple graphs in terms of the topos of quivers, which may be of interest in algebraic graph theory. The category of simple graphs is typically the appropriate category to do graph theory in because of its relation to the lattice of cores, graph colourings, and so on.
See also:
Topoi of preorders
Topoi of monoid actions
External links:
Quiv at nlab
Another topos that can be used as the foundation of other algebraic structures, like categories, is the topos of quivers. These are defined by set-valued functors over the category with two objects $E$ and $V$ and parallel edges $s$ and $t$ between them:
As can be seen from this diagram, $X$ is neither a preorder nor a monoid. Indeed, $X$ can be considered to be the simplest category that is neither of these two simpler cases. Thus, $Quiv$ can be considered to be the first example of a topos that isn't produced by a preorder or a monoid.
This diagram explains the topos of quivers. The subobject classifier can be understood with a few more diagrams, which I have prepared for you next. After discussing the basic aspects of quivers, we will move on to discussing functors of quivers.
Subobject classifier
Every set-valued functor topos $Sets^C$ is associated with a family of distributive lattices for each object in $Ob(C)$, which can be used to classify subobjects. The topos of quivers is associated with the following lattice of vertex truth values:
As well as the following lattice of edge truth values:
These are combined to produce an object of truth values $\Omega$ which is internal to the topos of quivers.
All that remains is to demonstrate that the working of the characteristic morphism, which maps a quivers to its vertex and edge truth values.
Definition. let $S \subseteq T$ be quivers. Then the characteristic morphism $\chi : T \to \Omega$ is the ordered pair of functions $(\chi_e,\chi_v)$. The first function $(\chi_e)$ maps an edge $(a,b)$ to a set of truth values containing the truth value $s$ iff the source element $a$ is in $T$, $t$ iff the target $b$ is in $T$, and $e$ iff $(a,b) \in T$. The second function $\chi_v$ is the characteristic function of sets.
Proposition. $(\chi_e,\chi_v) : T \to \Omega$ is a morphism of quivers.
Proof. let $e \in Hom(a,b)$. Then there are four cases (1) $f(e) = \emptyset$ then $f(e) \in Hom(\emptyset,\emptyset)$. (2) $f(e) = \{s\}$ then $f(e) \in Hom(\{v\},\emptyset)$ (3) $f(e) = \{t\}$ then $f(e) \in Hom(\emptyset,\{v\})$ (4) either $f(e) = \{s,t\}$ or $f(e) = \{s,t,e\}$ then $f(e) \in Hom(\{v\},\{v\})$. In each case $f(e) \in Hom(f(a),f(b))$. $\square$
Fundamental constructions:
Products and coproducts:Let $Q$ and $R$ be quivers. Then the coproduct $Q+R$ corresponds to the disjoint union of graphs. Then $Q$ and $R$ are in two separate connected components. The product $Q \times R$ has $(E_Q \times E_R, V_Q \times V_R)$ as its underlying set, and it corresponds to the product of graphs. All other limits/colimits are defined componentwise.
Lattice of subobjects:
Let $Q$ be a quiver, then $Sub(Q)$ is the distributive lattice defined by lower sets of the dependency ordering, whereby an edge is dependent upon the vertices it contains. It is fully determined by the subobject classifier.
Lattice of congruences:
Let $Q$ be a quiver. Then $Con(Q)$ is the intersection of $Con(s)$ and $Con(t)$, the congruence lattices of the source and target functions. In particular, given an ordered pair of equivalence relations $(E_1,E_2)$ then this ordered pair is a congruence of both the source and target functions. Any such ordered pair produces a quotient quiver.
Functors:
The topos of quivers is associated to a number of forgetful functors. There are forgetful functors to the vertex set, edge set, and source and target functions. In particular, there is a forgetful functor to $Sets$ defined by mapping a quiver to the coproduct $V + E$, which makes $Quiv$ into a concrete category. Furthermore, there is a forgetful functor to $Rel$.Theorem. let $r: Quiv \to Rel$ the function that maps any quiver to its underlying binary relation. Then $r$ is a functor.
Proof. let $f : Q \to T$ be a morphism of quivers. Then suppose $Hom(a,b) \not= \emptyset$ then $\exists e \in Hom(a,b)$ so that $f(e) \in Hom(f(a),f(b)$. Thus, $Hom(f(a),f(b)) \not= \emptyset$. An edge $(a,b)$ is in $r(Q)$ provided that its hom class is not empty, so that $(a,b) \in r(Q) \Rightarrow (f(a),f(b)) \in r(T)$. It follows that $r(f)$ is a relation homomorphism. $r$ corresponds to the forgetful functor to the vertex set, so $r$ is a well defined functor. $\square$
Lemma. let $f: Q \to T$ be a morphism of quivers, such that $T$ is a thin quiver. Then $f$ is fully determined by its vertex mapping.
Proof. let $e$ be an edge of $Q$ which is in $Hom(a,b)$ then $f(e) \in Hom(f(a),f(b))$. There is a unique edge $e' \in Hom(f(a),f(b))$ by the fact that $T$ is a thin quiver, so that $f(e) = e$ for every edge in $Q$. $\square$
Theorem. let $Tq$ be the full subcategory of the topos of quivers consisting of thin quivers. Then $f : Tq \to Rel$ is an isomorphism of categories.
Proof. (1) by restriction of the relation functor, $f$ is a functor from thin quivers to relations (2) by the previous lemma, given any morphism of relations we can cast it to a morphism of quivers so we can form the inverse functor $f^{-1}$. These two functors are inverses of one another, so they are isomorphisms. $\square$
Corollary. the category of simple graphs can be embedded in the topos of quivers, by taking the full subcategory of thin symmetric irreflexive thin quivers.
This interprets the category of simple graphs in terms of the topos of quivers, which may be of interest in algebraic graph theory. The category of simple graphs is typically the appropriate category to do graph theory in because of its relation to the lattice of cores, graph colourings, and so on.
See also:
Topoi of preorders
Topoi of monoid actions
External links:
Quiv at nlab
Subscribe to:
Posts (Atom)