Functionally complete/universal basis for graph homomorphisms?

Functionally complete/universal basis for graph homomorphisms?

[Mike Stay]

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/ ]

Re: Functionally complete/universal basis for graph homomorphisms?

[Gershom B]

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/ ]

Re: Functionally complete/universal basis for graph homomorphisms?

[Patrik Eklund]

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/ ]

Re: Functionally complete/universal basis for graph homomorphisms?

[Mike Stay]

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/ ]

Re: Functionally complete/universal basis for graph homomorphisms?

[Vaughan Pratt]

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/ ]

Re: Functionally complete/universal basis for graph homomorphisms?

[John Baez]

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/ ]

Re: Functionally complete/universal basis for graph homomorphisms?

[Patrik Eklund]

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/ ]

Re: Functionally complete/universal basis for graph homomorphisms?

[John Baez]

[-- 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 --]

Re: Functionally complete/universal basis for graph homomorphisms?

[Vaughan Pratt]

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/ ]