A metaphysical prelude

Lately, I have been thinking (again) about foundational metaphysical issues and to me, ontic structural realism seems to be a compelling stance – maybe science is successful at describing the world, because the world is intrinsically “structure”? (I am also intrigued by the mathematical universe hypothesis, this would be the consequent further step, but it leaves many open questions) To me, structural realism seems more plausible than assuming that there are hidden intrinsic aspects of “how things are” that we have no chance to ever witness. As a bystander-fan of category theory it also seems natural to believe that structure, relationships between entities, etc. is everything (interesting) there is about the world. After all, one can develop category theory while avoiding any talk about any “objects”. The arrows, the connections are what matters, and knowing all arrows an object is source or target of we know everything about that object up to isomorphism - we cannot look inside the objects, so we cannot distinguish two objects which are in exactly the same kinds of relationships.

There is some philosophical debate about not only what kind of structure the world is made of, “relations” being a hot candidate, but also whether relations need relata – can we really abandon the primary status of objects, if the relations, arrows, etc. must be defined in terms of something object-like, even if just to be denied and ignored in the next step? But to me this seems only to be a matter of convention and familiarity. We are used to start with point-like objects and building structure around them, being trained in classical set-theoretic ways of thinking.

But do we really need objects that are distinct from the relations? I have been thinking about finding a kind of mathematical counter-example. The desired kind of object must be at the same time object-like and also relation-like. In math, the most natural way how this happens is due to some kind of duality. In a sense, what I want is to find a way to construct relations that relate (other) relations. Why shouldn’t this be possible?

Furthermore, if this is actually mostly about having evidence in a metaphysical argument, I want to bring in another “prejudice” of mine, namely that the real, existing physical world is inherently concrete and no two things are really exactly the same. To me, equality is an abstract concept and each equality requires an underlying equivalence relation to make any sense (often it is just implicit or trivial in mathematical discourse), things must be equated to be equal. So I think that all things are to be considered different, unless grouped together (usually due to some similarity or shared property) and claimed to be equal.

Even interpreting multiple uses of the same variable name in the same context as the same mathematical object is a kind of silently understood equality (“this $x$ is the same as that $x$”) that we learn during childhood. We all are educated to ignore the difference between a symbol and its meaning and learn various rules to understand which symbols mean the same “thing”, just as we learn the abstract concept of a tree, even though all trees are different (and the same is true of basically everything). All things that are concrete are distinct, our brain does the pattern-matching, abstracting and equating. But I disgress. In the context of my non-standard relational concept, I also want to find such entities where no two relation tuples/sets are equal.

A treasure hunt: self-dual hypergraphs

I started by naively playing around with directed graphs, trying to come up with a way to have a meaningful and natural 1-to-1 mapping between nodes and edges. After some time something clicked in my mind and I remembered – hypergraphs! What makes hypergraphs a great candidate for my purposes is that there is no asymmetry between nodes and edges like there is with “normal” graphs. If you try to dualize a graph, the incidence set of a node cannot be an edge in general. But when dualizing a hypergraph by taking the hyperedges as nodes, and incidence sets of nodes as edges, you get another hypergraph!

So now I am looking for hypergraphs with named nodes and named hyperedges, in order to identify nodes and hyperedges with the same name (metaphysically, this identification is to be understood as actually “real”, unlike the constructed equalities discussed above). For this, we need to require the very natural constraint of self-duality. If I can dualize a labelled hypergraph, and get the same hypergraph back, it means that I did the trick and turned nodes into exactly the hyperedges we had in the original hypergraph! Naturally, each hyperedge may appear only once in a hypergraph. This is true by default for hypergraphs, but another reason to have that property is that otherwise we would get indistinguishable hyperedges/nodes, and I want to avoid that. Also, it does not make sense to have empty hyperedges, so those also are also excluded.

Self-dual hypergraphs have the following property: node $x$ is contained in the hyperedge $y$ if and only if hyperedge $x$ contains node $y$. So by dualizing nodes and edges we basically “flip around” containment, but due to self-duality get back the same result! I think this is both pretty and interesting. To get a feel for such objects, it would be great to enumerate and look at them. But how? I came up with the first ones by hand and then remembered about a powerful tool I learned to use during my masters thesis - SMT solvers! I just needed to come up with an encoding for these things and let the magic SMT oracle machine find them, thanks to years of engineering very smart people put into these solvers.

While playing around with the small hypergraphs I quickly noticed that drawing them quickly becomes unwieldy. But by exploiting the properties of the self-dual hypergraphs we can get a more familiar representation, as plain and simple undirected graphs with self-loops. To understand the mapping, first notice that we can interpret a hyperedge called $x$ as a set of directed edges from $x$ to all the targets. To our convenience, our hypergraph already has nodes with the same names, so we can just use these and add the edges. Now the self-duality constraint basically ensures that for each directed edge from $x$ to $y$ we must also have an edge back (remember that the arrow indicates containment and by imposed self-duality it must go both ways). But when all edges are either bidirectional or self-loops, we can simply “merge them” to get undirected edges, et voila!

Having now a mapping between self-dual hypergraphs and undirected graphs with loops we gain two things – a more familiar visualization, and maybe even more importantly, we can use all knowledge about undirected graphs we have, as well as their representation as an adjacency matrix. If we look at the adjacency matrix of such a graph, we can interpret each row as a hyperedge, which is equal to the “outgoing” part of the undirected edges. But because the graph is undirected, we know that the matrix is symmetric, so we basically just need a half of the values, e.g. just the lower triangular matrix. So we are almost there – to look for self-dual hypergraphs we can simply encode this as a constraint satisfaction problem for the matrix. More specifically, for a hypergraph of size $n$ we need variables for triangular matrix with “side length” $n$, such that:

• the rows of the induced symmetric matrix are all not the null-vector
• the rows of the induced symmetric matrix are all different

There are two additional constraints that I deemed necessary – I only want solutions where the resulting graph is connected, as it is not interesting to find a solution that is just juxtaposing two smaller solutions. Another restriction that I added was considering only asymmetric graphs, i.e. where the automorphism group is trivial and consists only of the identity mapping. I added this constraint, because having two hyperedges that are isomorphic and basically same up to renaming the nodes felt like violating the “aesthetics”. So:

• the resulting graph must be connected
• the resulting graph must be asymmetric

So with this laid out, I took pysmt, coded up the constraints in simple quantifier-free propositional logic and launched MathSAT (Z3 was much slower). For each solution it spit out, I computed all equivalent matrices (permutations applied to both rows and columns), which correspond to renaming of nodes, and then excluded all the solutions from further search. Furthermore I kept only solutions where the undirected graph is connected, and as I was computing all permutations anyway, for the asymmetry restriction I only needed to count the automorphisms, i.e. permutations yielding exactly the same matrix as before, and keeping those where the count is exactly 1.

The solver is able to find all such (hyper)graphs up to size of 6 within less than an hour on my laptop, so the statistics are as follows:

I’ve also looked in OEIS for both sequences, and to my surprise found nothing. Apparently nobody bothered to look for (asymmetric) undirected graphs with self-loops yet! This is not too surprising, as an inventory of “weird” graphs is probably nothing publishable, unless there is something interesting to prove or observe about them. And this is the next step - looking for patterns in these things.

I have already tried to “compose” such graphs in the usual way - replacing a node with another graph and copying each edge that connected to the substituted node such that it points to each node of the inserted graph. For self-loops, this always turns the inserted graph into a clique, which introduces lots of symmetry into the result, which I want to avoid. So I consider nodes with self-loops to be “fixed”, they cannot be used for substitutions.

When trying to insert asymmetric graphs into other asymmetric graphs (expanding non-self-looping nodes) in that way, you will notice that sometimes the result will be symmetric (and thus forbidden), and sometimes yield another asymmetric graph. This opens up some directions for curious minds:

• map out the connections between asymmetric graphs by “node expansion”, like expanding node $a$ in $G$ into graph $G’$ yields another graph $G’’$
• What are the “prime” graphs that cannot be obtained by this substitution?
• Are there natural operations on these graphs that are “closed”, i.e. combining two asymmetric graphs will yield another asymmetric graph?

Towards non-well-founded set theory

While thinking about and doing all this, I noticed one problem – a hyperedge is not a relation, it is more like a relation tuple! So what I actually wanted was to have a mapping such that each node again can be interpreted as a complete hypergraph. But we are almost there – by having an identification between nodes and hyperedges, we can also do the following: take any hyperedge, and expand the nodes inside it to hyperedges as well! Now our hyperedge turned into a hypergraph by just using the same mapping that we already have. So here we are – each node can be interpreted as a hyperedge of nodes and also as a hypergraph based on those same hyperedges/nodes itself.

Now take any self-dual hypergraph, e.g. the one with $$a := \{b\}, b := \{a,b,c\}, c := \{b,c\}$$

Observe how, in a sense, it is a Quine, it “reproduces itself”! Start by drawing the undirected graph representing this hypergraph, i.e. a graph with the edges/loops $a - a, a - b, b - b, b - c, c - c$. Below it, “expand” each node by drawing the hyperedges corresponding to the symbol names (e.g. just draw the sets as circles around the corresponding letters). Now connect each symbol inside each hyperedge with the corresponding hyperedge (i.e. outside of it). The directed edges will basically “cross” the hyperedge boundary. Finally merge the bidirectional directed edges into undirected ones. You will see that you look at the same graph that you initially started with!

Playing around with these ideas, it struck me again – a long while ago I superficially read about non-well-founded set theory, and this smelled like something similar. These kinds of set theories deny the principle of well-foundedness (roughly, that each “set inclusion chain” must eventually end) and instead adds some notion of principled non-well-foundedness, allowing for things like sets that contain themselves – very interesting territory! After noticing the connection, I read a bit and quickly understood that I was already on the way of half-reinventing a variant of this myself. I even already came up with the canonical representation of these things as graphs (more specifically, accessible pointed graphs) and was thinking about defining equivalence of hyperedges/sets in terms of bisimulations, so I already was on the right track, but still doing it on a very intuitive level. Now I probably need to have a serious look into Aczel’s book to pick up some tricks, ideas, results, if I want to learn to formalize such things more rigorously.