* Functionally complete/universal basis for graph homomorphisms? @ 2017-09-26 4:17 Mike Stay 2017-09-26 16:49 ` Gershom B ` (2 more replies) 0 siblings, 3 replies; 9+ messages in thread From: Mike Stay @ 2017-09-26 4:17 UTC (permalink / raw) To: categories The Sheffer stroke / NAND gate suffices to implement any function from 2^n -> 2. I'm looking for a similar universal basis for graph homomorphisms from Omega^n -> Omega, where Omega is the subgraph classifier with two vertices t, f and five edges in:t->t, out1:t->t, out2:t->f, out3:f->t, out4:f->f. There's obviously a finite set of operations that covers all graph homomorphisms from Omega^n to Omega, because the set of all operations of that form is finite. But how small can that set be? I'd be satisfied with a formula parametric in n, but surprised if it actually depends on n; I'd expect it to be a finite set of binary operations. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Functionally complete/universal basis for graph homomorphisms? 2017-09-26 4:17 Functionally complete/universal basis for graph homomorphisms? Mike Stay @ 2017-09-26 16:49 ` Gershom B 2017-09-27 4:28 ` Patrik Eklund 2017-09-27 21:26 ` Mike Stay 2 siblings, 0 replies; 9+ messages in thread From: Gershom B @ 2017-09-26 16:49 UTC (permalink / raw) To: Mike Stay; +Cc: categories Dear Mike, I don't have an answer for this precise question, but, assuming I understand your question, I do have a reference for a general approach that can provide a potential lower bound on the number of such operations. Take a look at "Homological Computations for Term Rewriting Systems" by Philippe Malbos and Samuel Mimram: http://math.univ-lyon1.fr/~malbos/Art/hcTRS.pdf It uses some rather heavyweight abstract homology theory but produces a purely mechanical procedure for obtaining results (though the authors to my knowledge haven't yet implemented a computer program to perform this automatically). Cheers, Gershom On Tue, Sep 26, 2017 at 12:17 AM, Mike Stay <metaweta@gmail.com> wrote: > The Sheffer stroke / NAND gate suffices to implement any function from > 2^n -> 2. I'm looking for a similar universal basis for graph > homomorphisms from Omega^n -> Omega, where Omega is the subgraph > classifier with two vertices t, f and five edges > > in:t->t, out1:t->t, out2:t->f, out3:f->t, out4:f->f. > > There's obviously a finite set of operations that covers all graph > homomorphisms from Omega^n to Omega, because the set of all operations > of that form is finite. But how small can that set be? I'd be > satisfied with a formula parametric in n, but surprised if it actually > depends on n; I'd expect it to be a finite set of binary operations. > > -- > Mike Stay - metaweta@gmail.com > http://www.cs.auckland.ac.nz/~mike > http://reperiendi.wordpress.com > > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Functionally complete/universal basis for graph homomorphisms? 2017-09-26 4:17 Functionally complete/universal basis for graph homomorphisms? Mike Stay 2017-09-26 16:49 ` Gershom B @ 2017-09-27 4:28 ` Patrik Eklund 2017-09-28 5:50 ` Vaughan Pratt 2017-09-27 21:26 ` Mike Stay 2 siblings, 1 reply; 9+ messages in thread From: Patrik Eklund @ 2017-09-27 4:28 UTC (permalink / raw) To: Mike Stay; +Cc: categories I haven't looked at it in this way, but we have been looking into the notion of 'arity', when we deal with extensions to many-valued terms. In general, the category of signatures is tricky. Just mapping operators to operators, and respecting arities, is very shallow. That category being tricky is also seen in Goguen's institutions and Meseguer's entailment systems, where Sign is a black box. Benabou's definition is that shallow thing, and so is efforts to categorize trees as part of tree automata. Categorizing automata is hard enough as we see through Budach, Ehrig, Goguen, Manes, Adamek, etc. Note also that the stroke is a binary/boolean operator, so we are on the borderline between terms and sentences. Note also that extending 2 to a quantale, and even non-commutative ones, adds complexity, and involves questions related to your but different in their objectives. The category of graphs may also need revision. Defining a graph as mapping an edge to a pair of vertices hides arities and invites to defining paths. Nevertheless, vertices in trees are seen as operator names. Sorry for not precisely answering your question, and for being rather general and intuitive in my reflections, but they are related to our ongoing work on the foundations of many-valuedness. Our take is that unless we have something more innovative on Sign, we are unable to proceed with sentence functors (not extendable to monads!), and so towards more ingredients in logic machineries, separated "latively", as I have written before. Patrik On 2017-09-26 07:17, Mike Stay wrote: > The Sheffer stroke / NAND gate suffices to implement any function from > 2^n -> 2. I'm looking for a similar universal basis for graph > homomorphisms from Omega^n -> Omega, where Omega is the subgraph > classifier with two vertices t, f and five edges > > in:t->t, out1:t->t, out2:t->f, out3:f->t, out4:f->f. > > There's obviously a finite set of operations that covers all graph > homomorphisms from Omega^n to Omega, because the set of all operations > of that form is finite. But how small can that set be? I'd be > satisfied with a formula parametric in n, but surprised if it actually > depends on n; I'd expect it to be a finite set of binary operations. > > -- > Mike Stay - metaweta@gmail.com > http://www.cs.auckland.ac.nz/~mike > http://reperiendi.wordpress.com > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Functionally complete/universal basis for graph homomorphisms? 2017-09-27 4:28 ` Patrik Eklund @ 2017-09-28 5:50 ` Vaughan Pratt 2017-09-30 8:18 ` Patrik Eklund 2017-10-02 3:58 ` Vaughan Pratt 0 siblings, 2 replies; 9+ messages in thread From: Vaughan Pratt @ 2017-09-28 5:50 UTC (permalink / raw) To: categories On 09/26/17 9:28 PM, Patrik Eklund wrote: > The category of graphs may also need revision. Defining a graph as > mapping an edge to a pair of vertices hides arities and invites to > defining paths. Nevertheless, vertices in trees are seen as operator > names. Even though categories are not algebraic in sets, at least they are algebraic in graphs, which in turn are algebraic in sets. While I would have little or no quarrel with any revision of "the" category of graphs that preserved this fundamental relation between categories and sets, if the revision you have in mind does not then I would expect at least some of us here would be very interested in why you consider your contemplated revision an improvement. Vaughan Pratt [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Functionally complete/universal basis for graph homomorphisms? 2017-09-28 5:50 ` Vaughan Pratt @ 2017-09-30 8:18 ` Patrik Eklund 2017-09-30 18:25 ` John Baez 2017-10-02 3:58 ` Vaughan Pratt 1 sibling, 1 reply; 9+ messages in thread From: Patrik Eklund @ 2017-09-30 8:18 UTC (permalink / raw) To: Vaughan Pratt; +Cc: categories Dear Vaughan, I will under the CATLIST and at this point not reply more in detail, but let me just now say that your "categories are not algebraic in sets, at least they are algebraic in graphs, which in turn are algebraic in sets" is within the realm of "algebraic categories". My "Categorizing automata is hard enough as we see through Budach, Ehrig, Goguen, Manes, Adamek, etc." is in the realm of "categorical algebra" and monoidal categories. So with graphs understood as being useful also for representing terms with "vertices in trees seen as operator names", like it is done e.g. in tree automata, monoidal categories as underlying categories of term monads is another view and machinery as compared to dealing with the category of graphs as an algebraic category ("categories are algebraic in graphs"). Best, Patrik On 2017-09-28 08:50, Vaughan Pratt wrote: > On 09/26/17 9:28 PM, Patrik Eklund wrote: >> The category of graphs may also need revision. Defining a graph as >> mapping an edge to a pair of vertices hides arities and invites to >> defining paths. Nevertheless, vertices in trees are seen as operator >> names. > > Even though categories are not algebraic in sets, at least they are > algebraic in graphs, which in turn are algebraic in sets. > > While I would have little or no quarrel with any revision of "the" > category of graphs that preserved this fundamental relation between > categories and sets, if the revision you have in mind does not then I > would expect at least some of us here would be very interested in why > you consider your contemplated revision an improvement. > > Vaughan Pratt > > [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Functionally complete/universal basis for graph homomorphisms? 2017-09-30 8:18 ` Patrik Eklund @ 2017-09-30 18:25 ` John Baez 0 siblings, 0 replies; 9+ messages in thread From: John Baez @ 2017-09-30 18:25 UTC (permalink / raw) Cc: categories [-- Attachment #1: Type: text/plain, Size: 494 bytes --] I will under the CATLIST and at this point not reply more in detail, but > let me just now say that your "categories are not algebraic in sets, at > least they are algebraic in graphs, which in turn are algebraic in sets" > is within the realm of "algebraic categories". > That depends on your definition of "algebraic categories". There are a number of inequivalent definitions in common use: https://ncatlab.org/nlab/show/algebraic+category What definition are you using above? Best, jb [-- Attachment #2: Type: text/html, Size: 1279 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Functionally complete/universal basis for graph homomorphisms? 2017-09-28 5:50 ` Vaughan Pratt 2017-09-30 8:18 ` Patrik Eklund @ 2017-10-02 3:58 ` Vaughan Pratt 1 sibling, 0 replies; 9+ messages in thread From: Vaughan Pratt @ 2017-10-02 3:58 UTC (permalink / raw) To: John Baez; +Cc: categories Addressing the nLab article cited by John Baez, if we take "graph" to mean a heterogeneous algebra with two carriers V and E and two lawless operations s,t: E --> V, then I don't see any definition in that article that would make graphs algebraic in sets, contrary to my claim that they are.?? The article contains "inequivalent definitions" in about the same sense that Republican senators have inequivalent notions of climate change. A simple way to fix this (that should satisfy all Republicans) is to interpret "graph" as meaning "reflexive graph", namely a graph in the above sense further equipped with an operation i: V --> E satisfying sis = s and tit = t.?? By Morita (details later), this is equivalent to having just the one sort E with s,t: E --> E being two idempotents, ss = s, tt = t, satisfying in addition ts = s, st = t. With only one sort we clearly have an algebraic category of graphs of the kind envisaged in the nLab article.?? The underlying set U(G) of the graph G is simply its set of edges, and the free graph F(X) is a graph with X independent edges in the sense that the adjacency relation between their 2X endpoints of those edges is empty.?? Put differently, in the free graph no edge touches itself or any other edge, entirely dual to free love.?? Honest Republicans will understand. But this is not the only solution.?? Completely missing from the article is any mention of a functor A: T --> Set as an algebra in its own right, as distinct from a functor U: A --> V as a V-valued forgetful functor from an algebraic category A?? per section 5, References, of the article.???? Such a functor A: T --> Set is a heterogeneous "T-algebra" in the sense that it is a model of the (small) category T understood as a theory.?? We understand the objects of T as its sorts, and its morphisms as its (unary) operation symbols.?? The algebra A interprets the sorts ?? of T as sets A(??) and the operation symbols of T as unary operations acting on those sets.?? The functor category Set^T is the category of all T-algebras (in this sense) and their homomorphisms, namely their natural transformations. This logical development mirrors (literally) the geometric notion of a presheaf A: J' --> Set on a base J = T' = T^op, with the category Set^T of T-algebras (in this sense) being identical to the presheaf category Psh(J). Had we required T to have finite products it would be a Lawvere theory whose models are functors preserving those products.?? However products are not needed when all operations are unary.?? If we define a Lawvere theory to have *specified* products, and a model thereof to preserve only the specified ones, then T in this context is vacuously a Lawvere theory because no products have been specified. If Bill has a different suggestion I'm all ears.?? If this is already a standard convention however then hopefully it will find its way onto the appropriate nLab/Wikipedia/Mathworld/whatever articles. Bearing in mind that every presheaf category is a topos, respect for products is disrespectful to toposes so don't insist on the former if your point whatever it is doesn't need it. When T consists of two objects v and e and two morphisms s,t: e --> v, along with the obligatory identity morphisms at v and e required to round out T to a category, a graph G is simply a functor G: T --> Set interpreting v and e as sets G(v) and G(e) of respectively vertices and edges, and s and t as functions G(s), G(t): G(e) --> G(v) yielding respectively the source and target vertices of each edge in G(e).?? The functor category Set^T is then the category of graphs thus defined, representing graphs as functors and the homomorphisms between those graphs as the natural transformations between those functors. T-algebras being presheaves on T' (= T^op), the homfunctor T' x T --> Set transposes as the Yoneda embedding Y: T' --> Set^T (more usually written as Y: J --> Set^J').?? Y is a fully faithful functor that interprets T' as a small subcategory of Set^T consisting of primitive algebras, one per sort. In the case of graphs, Y interprets T' as two graphs, one consisting of a lone vertex Y(v), the other of a lone edge Y(e), and interprets s and t as graph homomorphisms mapping the lone vertex to respectively the source and target of the lone edge. Note the contravariance of Y in T, aka the covariance of Y in T'. This is an elementary example of the duality of word (a small theory T with operation symbols s and t) and object (a small category T' of fundamental graphs Y(v) and Y(e) and homomorphisms Y(s) and Y(t) from Y(v) to Y(e)). We don't need to go this route in order to make reflexive graphs algebraic in the sense of the nLab article, as noted earlier.?? But in the spirit of making mathematics difficult we should attempt that North Face, in the process explaining Morita equivalence as promised. Take T to be the three-element monoid (one-object category) {1,s,t} satisfying xy = y when y is not the identity. ?? This T is an idempotent monoid in the sense that every element is an idempotent. (But it is not the *free* idempotent monoid on generators s and t, which would also contain st, ts, sts, and tst as distinct elements, thanks to the additional equations st = t, ts = s.)?? The reflexive graphs of our second paragraph can be seen to be the functors from this T to Set, and as homogeneous algebras they are algebraic in the sense of the nLab article John cited.?? More generally, for any monoid M, the category of M'-sets, or models of M, is algebraic in that sense as well as in the sense of the functor category Set^M. (The opposite of a monoid M is of course a monoid M', so M-sets generally understood are the same thing whether you're thinking of some monoid either as a theory or as a base for presheaves.) Now if we split each of the idempotents s and t in T = {1,s,t} to give their respective retracts (the Karoubi envelope or free Cauchy completion of T), and then identify the two retracts as v (which therefore splits both s and t), we have a Cauchy completion T* of T with two objects and morphisms s,t: E --> V and i: V --> E. When Set^C and Set^D are equivalent we say that C and D are *Morita equivalent*.???? It is a theorem that splitting idempotents in a category C yields a category that is Morita equivalent to C.?? It therefore follows that Set^T* is equivalent to Set^T.?? This gets us to the two-sorted theory of reflexive graphs, but by Morita equivalence its category is still algebraic in the sense of that nLab article, even though it does not consist of homogeneous algebras. In general categories A of heterogeneous algebras with two or more sorts don't have forgetful functors U: A --> Set with left adjoints, but it's nice to have the occasional counterexample. Vaughan Pratt On 09/30/17 11:25 AM, John Baez wrote: > Patrik Eklund wrote: > > I will under the CATLIST and at this point not reply more in > detail, but > > let me just now say that your "categories are not algebraic in > sets, at > least they are algebraic in graphs, which in turn are algebraic in > sets" > is within the realm of "algebraic categories". > > > That depends on your definition of "algebraic categories".?? There are > a number > of inequivalent definitions in common use: > > https://ncatlab.org/nlab/show/algebraic+category > > What definition are you using above? > > Best, > jb [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Functionally complete/universal basis for graph homomorphisms? 2017-09-26 4:17 Functionally complete/universal basis for graph homomorphisms? Mike Stay 2017-09-26 16:49 ` Gershom B 2017-09-27 4:28 ` Patrik Eklund @ 2017-09-27 21:26 ` Mike Stay 2017-09-28 21:18 ` John Baez 2 siblings, 1 reply; 9+ messages in thread From: Mike Stay @ 2017-09-27 21:26 UTC (permalink / raw) To: categories Thanks for all the responses so far. It's been pointed out to me that my post used some terms in a vague way, so let me try to be a little more precise. Let B = {0,1} and NAND: B^2 -> B be the usual NAND function. Then any function B^n -> B can be expressed as the composition of a finite number of uses of the diagonal function D:B->B^2, projections, permutations, and NAND. Let Omega be the subgraph classifier described below. I'm working with the topos of reflexive directed multigraphs, that is, graphs whose vertices are equipped with a chosen self-edge and that allow multiple parallel directed edges between any pair of vertices. I suspect that any graph homomorphism from Omega^n to Omega (where finite powers are given by the categorical product) can be expressed as the composition a finite number of uses of the diagonal graph homomorphism D:Omega -> Omega^2, projections, permutations, and some finite number of operations with signature Omega^2 -> Omega. My best guess at a such a set of operations is 1. Map all vertices of Omega^2 to t and apply NAND to the edges, treating "in" as true and all the "outs" as false, 2. NAND together the vertices. Edges between any of (t,f), (f,t), and (f,f) map to in and the others map to the appropriate outs, and 3. (t,t) maps to t; the rest of the vertices map to f. (in, in) maps to in; the rest of the edges map to the appropriate outs. I would like to know if a. a single set of operations suffices for all n b. if so, what the smallest size of such a set is and an example of such a minimal set c. if not, how the size of the necessary set grows with n. Thanks! On Mon, Sep 25, 2017 at 10:17 PM, Mike Stay <metaweta@gmail.com> wrote: > The Sheffer stroke / NAND gate suffices to implement any function from > 2^n -> 2. I'm looking for a similar universal basis for graph > homomorphisms from Omega^n -> Omega, where Omega is the subgraph > classifier with two vertices t, f and five edges > > in:t->t, out1:t->t, out2:t->f, out3:f->t, out4:f->f. > > There's obviously a finite set of operations that covers all graph > homomorphisms from Omega^n to Omega, because the set of all operations > of that form is finite. But how small can that set be? I'd be > satisfied with a formula parametric in n, but surprised if it actually > depends on n; I'd expect it to be a finite set of binary operations. > > -- > Mike Stay - metaweta@gmail.com > http://www.cs.auckland.ac.nz/~mike > http://reperiendi.wordpress.com > -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Functionally complete/universal basis for graph homomorphisms? 2017-09-27 21:26 ` Mike Stay @ 2017-09-28 21:18 ` John Baez 0 siblings, 0 replies; 9+ messages in thread From: John Baez @ 2017-09-28 21:18 UTC (permalink / raw) To: Mike Stay; +Cc: categories Dear Categorists - Mike Stay's puzzle is quite nice. I won't answer it. Instead, I will generalize and extend it. Suppose we have a category C with finitely many objects and morphisms. Let C^ be the category of presheaves on C, and Omega the subobject classifier in C^. There is a Lawvere theory T whose n-ary operations are the morphisms from Omega^n to Omega. 1. Is T finitely generated? That is, can we find a finite collection of morphisms f: Omega^n -> Omega (for various choices of n) such that T is generated, as a category with finite products, by these? 2. Can we find an explicit set of generators for T? 3. Is T finitely presented? 4. Can we find an explicit set of generators and relations for T? My guess on 3 is "yes". Mike was interested in the case where C^ is the category of reflexive graphs, but I think the question would be interesting to study in detail for lots of other classic examples. Someone must have done it already, no? Best, jb [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2017-10-02 3:58 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-09-26 4:17 Functionally complete/universal basis for graph homomorphisms? Mike Stay 2017-09-26 16:49 ` Gershom B 2017-09-27 4:28 ` Patrik Eklund 2017-09-28 5:50 ` Vaughan Pratt 2017-09-30 8:18 ` Patrik Eklund 2017-09-30 18:25 ` John Baez 2017-10-02 3:58 ` Vaughan Pratt 2017-09-27 21:26 ` Mike Stay 2017-09-28 21:18 ` John Baez
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).