# From Metaphysics via Self-Dual Hypergraphs to Non-Well-Founded Set Theory

## 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:

# of nodes | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|

w/o asymmetry | 1 | 2 | 6 | 31 | 230 | 2683 |

with asymmetry | 1 | 1 | 2 | 11 | 94 | 1409 |

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.