In particular, I have in mind the generalization of the properties of universal algebra to individual functions. In total, these are some of the properties I would like to see from a model of functions:
- It should be close to the set theoretic model of functions as sets of ordered pairs, even though it is not necessarily the same as it.
- The various aspects of universal algebra should be applicable to it: homomorphisms, subalgebras, congruences, products, varieties, etc.
The problem with the set of ordered pairs account is that does not address the different properties of functions. If functions were just sets, algebra wouldn't be a different branch of mathematics distinguished from set theory. Yet it is, and that can be addressed with the topos $Sets^{\to}$.
This account is different from other earlier categorical accounts of universal algebra like Lawvere theories, because I explicitly intend for it to be done from the ground up. Before setting out into abstract algebra, I want to first figure out what functions are, and then we can use that to account for the properties of structures built out of them.
Functions as algebraic structures:
Universal algebra is concerned with the properties of algebraic structures built of functions, and so a starting point for the theory of universal algebra is the theory of individual functions $f : A \to B$. The properties of algebraic structures that are truly universal, should be applicable to these individual functions.Homomorphisms:
Let $f : A \to B, g : C \to D$ be functions. Then a homomorphism $h : f \to g$ of functions is an ordered pair of functions $(i : A \to C, o : B \to D)$ that satisfies the following commutative diagram:
Isomorphisms:Two functions $f : A \to B, g : C \to D$ in $Sets^{\to}$ are isomorphic, provided that the distribution of cardinalities of their fibers are the same.
Automorphisms:
Let $f: A \to B$ be a function, then $Aut(f)$ is its group of automorphisms. A function is associated with a kernel, which is the equivalence relation determined on inputs of $f$ and an image in $B$. The image in turn determines a complement of non-image values. $Aut(f)$ is the direct product of the automorphism group of the kernel equivalence relation and the symmetric group on the complement of the image. It is therefore a direct product of wreath products of symmetric groups by symmetric groups.
Subalgebras:
Let $f : A \to B$ be a function then subalgebras of $f$ are simply restrictions $(S,T) \subseteq (A,B)$ that respect images. It is in this setting, that the old idea of a function as a set of ordered pairs is partially restored, but there is more to functions then that as demonstrated by their congruences.Set images:
The subalgebras of a function are defined with respect to images, so that $(S,T)$ is a subobject provided that $f(A) \subseteq B$. In particular, the covariant power set functor associates to any function its image function $\wp(f) : \wp(A) \to \wp(B)$.
Set inverse images:
The dual operation for functions is the contravariant inverse image function. This takes $f : A \to B$ to $\overline{\wp}(f) : \wp(B) \to \wp(A)$. It is the largest set which produces a given image.
Lattice of subalgebras:
Let $f: A \to B$ be a function, then $Sub(f)$ is a distributive lattice of subobjects of $f$ consisting of all ordered pairs $(S,T)$ for which $f(A) \subseteq T$. Then this distributive lattice is associated to a closure operation by the image.
Subobject classifier:
As a topos, functions are associated with a trivalent logic. Let $f : A \to B$ be a function and $(S,T)$ be a subobject. Then its input truth value for $a \in A$ is zero if $f(a) \not\in T$, $\frac{1}{2}$ if $f(a) \in T \wedge a \not \in S$ and $1$ if $a \in S$. Its output truth value is $1$ if $b \in T$ and zero otherwise. The input and output truth values form an ordered pair $(i,o)$ which is the characteristic function of a function.
Congruences:
It often appears in applications that the classical definition of congruences is too restrictive. In order to handle generalized congruences in their appropriate context we need to have ordered pairs of equivalence relations $(P,Q)$. An ordered pair $(P,Q)$ of a function $f: A \to B$ is a congruence provided that: \[ x =_P y \Rightarrow f(x) =_Q f(y) \] We can consider equivalence relations as stores of information. For example, each function is associated with an equivalence relation in which $x =_f y$ when $f(x) = f(y)$ which determines the information provided by the function.In this setting, a congruence of a function captures the intuitive idea that pieces of information mapped by a function can determine pieces of information about the output. This distinguishes functions from sets of ordered pairs, because it explicitly uses the fact that functions are specific types of maps from inputs to outputs.
Information image:
The dual of the subset image, which determines the congruences of a function is the information image. It takes a partition of the input set, and it produces an output partition so that the two form a congruence. Let $f: A \to B$ be a function and $P$ a partition of $A$. Then define a partition $Q$ of $B$ by: \[ x =_Q y \Leftrightarrow \exists a_1, a_2 \in A : a =_P b \wedge f(a) = x \wedge f(b) = y \] Information inverse image:
We can also dualize the concept of a subset inverse image, in order to form an inverse image function for the lattice of partitions. This is the smallest piece of information that produces a given output. Let $f : A \to B$ be a function and $Q$ a partition of $B$ then define a partition $P$ of $A$ by: \[ a =_P b \Leftrightarrow f(a) =_Q f(b) \] Lattice of congruences:
Let $f : A \to B$ be a function, then its lattice of congruences $Con(f)$ consists of all ordered pairs $(P,Q)$ for which $a =_P b \Rightarrow f(a) =_Q f(b)$. In other words, it consists of all $(P,Q)$ for which $Q$ is a larger equivalence relation then $f(P)$.
Quotients:
Let $f: A \to B$ be a function and $(P,Q)$ a congruence of $f$. Then $\frac{f}{(P,Q)}: P \to Q$ is the function which associates each $P$ class to its unique $Q$ along $f$. This means that we can form quotients of individual functions by congruences.
Limits and colimits:
The basic operations of universal algebra are homomorphisms, subalgebras, congruences, and products. As it happens, products can also be defined on the level of individual functions.Products:
Let $f: A \to B, g : C \to D$ be functions. Then their product is $f \times g : A \times C \to B \times D$. With $(f \times g)(a,b) = (f(a),g(b))$. It is clear that $(first,first)$ and $(second,second)$ form congruences of the product function, producing the two underlying functions as quotients.
Coproducts:
Let $f : A \to B$ and $g : C \to D$ be functions. Then $f+g : A + C \to B + D$ is their coproduct. Then the two functions $f$ and $g$ are both subobjects defined by restriction to $(A,B)$ or $(C,D)$.
Other limits and colimits:
Equalizers and coequalizers can be defined piecewise. Then any other limits/colimits can be defined from them and coproducts/coproducts.
Equational classes:
The definition of subobjects, quotients, and products of functions means that we can define equational classes. In particular, a pseudovariety of functions is a class of functions closed under subobjects, quotients, and finite products. An example is constant functions: the product of constant functions is constant, as is any subobject or quotient.Composite structures:
Composite algebraic structures will be created from the ground-up from simpler components like sets and functions. This is done with product topoi.Homomorphisms:
Take magmas as an example: a magma is a set $S$ with a function $*$ or an ordered pair $(S,*)$. Then magmas are members of the product topos $Sets \times Sets^{\to}$, containing simpler components of a set and a function. A momorphism of $Sets \times Sets^{\to}$ is a morphism of a set and a function both.Magmas aren't just any pair of a set and a function. A magma $(S,*)$ is a set $S$ any a function $*$ specifically with the signature $* : S^2 \to S$. We can form a full subcategory of $Sets \times Sets^{\to}$ of objects of this form, but this doesn't recover the algebraic category: morphisms must take the form $(f, (f^2,f))$. This yields the following commutative diagram:
If we have a function $f: (S,*) \to (T,*)$ then this commutative diagram yields an expression of the form: $f(a*b) = f(a)*f(b)$. This means that a homomorphism of magmas is simply a special type of morphism of functions. So the topos $Sets^{\to}$ is truly a building block of magmas.
Magma is a subcategory of $Sets\times Sets^{to}$ consisting of objects $(S,* : S^2 \to S)$ and morphisms $(f,(f^2,f))$. This can be seen to be a subcategory because $(f,(f^2,f)) \circ (g,(g^2,g))$ is equal to $(f \circ g, (f^2 \circ g^2, f \circ g))$ and $f^2 \circ g^2$ can be rewritten as $(f \circ g)^2$ to get $(f \circ g, ((f \circ g)^2, f \circ g)$. This yields to an algebraic embedding of magma in a topos.
Semigroups are then a full subcategory of magmas. The basic point of this approach is that algebraic categories are constructed from the ground up from their constitutient topoi. It will be seen that topoi provide a more powerful logic then their subcategories, yielding all kinds of possibilities which wouldn't be available otherwise.
Subalgebras:
Let $(M,*)$ be a magma and $S$ a closed subset of $M$. Then a subalgebra of $M$ can be defined as a subobject of its set and of its function $(S,*|_{(S^2,S)})$. This a special type of subobject of $Sets \times Sets^{\to}$ but as magma is a subcategory, not all subobjects are revealed this way.Missing from this construction is all partial magmas, which are a special type of subobject which could be constructed from non-closed sets. Likewise, out of semigroups we can construct partial semigroups. This demonstrates that the subalgebras constructed in algebraic subcategories are only a subset of what is possible.
Congruences:
Let $(M,*)$ be a magma and $C$ an equivalence relation on $M$. Then it is a congruence provided that $(C^2,C)$ is a generalized congruence of the function $*$. Congruences of this from $(C^2,C)$ yield a subset of the possible congruences and quotients.Missing is the commutative part of a magma. Let $(M,* : M^2 \to M)$ be a magma. Define an equivalence relation $E$ on $M^2$ that identifies dual pairs $(a,b)$ and $(b,a)$ together. Then form the information image of $E$ to get an ordered pair $(E,Im(E))$. This ordered pair forms a generalized congruence of $*$, and so its quotient is the commutative quotient of the magma.
In categorical parlance, any other property that is invariant under reordering filters through the commutative quotient. As an example, the characteristic polynomial is invariant under change in ordering of matrix multiplication $p(AB) = p(BA)$. This means that it filters through the commutative quotient.
Additional quotients can be formed by the information images of the first and second parts of the ordered pair of the input of the magma operation, or any other equivalence relation of ordered pairs. The topos settings invites you to consider all kinds of non-standard of subalgebras and congruences like these that wouldn't be possible otherwise.
Algebraic categories like the category of magmas emerge by restricting the full power of a topos, yielding a subset of possible morphisms, subalgebras, congruences, and so on. The category of magmas has the restriction that its subobjects and quotients must again be magmas.
Topoi are the perfect categories, but much like with how suborders of a lattice need not be lattices, subcategories of topoi don't need to be topoi. Nonetheless, we can use category theory to study special cases and restrictions of topoi, which themselves don't need to be topoi anymore.
Algebraic categories:
It can easily be seen that the construction applied to magmas can be generalized to any algebraic structure addressed in universal algebra. Monoids can be embedded in $Sets \times (Sets^{\to})^2$, the identity is defined by an element function. Morphisms have the following form: $(f, (f^2,f),(f^0,f))$. Groups are embedded in $Sets \times (Sets^{\to})^3$.The signature not only tells you what a topos to be embedd an algebra in, but how to do it as well. The parent topos is simply determined by the number of terms in the signature. A number of algebraic structures composed of sets and functions can be built up this way:
- Ring with identity: $Sets \times (Sets^{\to})^5$
- Semiring with identity : $Sets \times (Sets^{\to})^4$
- Lattice : $Sets \times (Sets^{\to})^2$
- Lattice ordered semigroup: $Sets \times (Sets^{\to})^3$
- Residuated lattice: $Sets \times (Sets^{\to})^6$
As these topoi are simply constructed from sets and functions, they are not that far from foundations. To get to something a little bit more advanced, let $R$ be a unital ring then its category of R-modules can also be associated to a topos of monoid actions.
References:
Topoi categorical analysis of logic
Robert Goldblatt
No comments:
Post a Comment