What is a hypergraph consisting of one edge leading from itself to itself?

86 Views Asked by At

Is this indeterminate? Undefined? Meaningless?

I became confused when I looked at it by starting with

$$(A \to B) \to (A \to B). \qquad\label{1}(1)$$

Since both ends of this edge are this edge, it's clear that the whole expression is equivalent itself to $A \to B$, implying $$A=B=A\to B. \qquad \label{2}(2) $$

This seems all well and good, but then you should be able to rewrite $(1)$ as

$$(A\to A)\to (A\to A) \qquad\label{3}(3).$$

But $A\to A$ is a simple loop, which seems valid; and a simple loop connected from itself to itself forming another loop (leading from $A\to A$ to $A\to A$) also seems valid, and moreover, distinct from $A\to A$ itself. If that's true, it seems to disprove $(2)$.

Obviously there's something inconsistent here; what is it that's prohibited or that I have mistaken? Or is a hypergraph consisting of an edge leading to itself a reasonable structure if approached the right way?

1

There are 1 best solutions below

0
On

It turns out Wikipedia speculatively addresses this situation, in particular here:

Alternately, edges can be allowed to point at other edges, irrespective of the requirement that the edges be ordered as directed, acyclic graphs. This allows graphs with edge-loops, which need not contain vertices at all. For example, consider the generalized hypergraph consisting of two edges $e_1$ and $e_2$, and zero vertices, so that $e_1 =\{e_2\}$ and $e_2 = \{e_1\}$. As this loop is infinitely recursive, sets that are the edges violate the axiom of foundation. In particular, there is no transitive closure of set membership for such hypergraphs. Although such structures may seem strange at first, they can be readily understood by noting that the equivalent generalization of their Levi graph is no longer bipartite, but is rather just some general directed graph.

The generalized incidence matrix for such hypergraphs is, by definition, a square matrix, of a rank equal to the total number of vertices plus edges. Thus, for the above example, the incidence matrix is simply

$$\left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right]$$