(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:
Subscribe to:
Comments (Atom)