Self-containing structures

Question

This question is partly inspired by this question: independently of the original context, I'm interested in the general claim* that an ill-founded set theory would represent certain mathematical objects more intuitively. That is, I'm looking for reasonably natural mathematical structures which, in some sense, "contain themselves" as an element (or element of some element, or etc.). I'm especially interested in whether there are natural examples of the form $a_0"\in" . . . "\in" a_n"\in" a_0$ for $n>0$, since I know of no natural such example.

To clarify, I'm looking for instances of "genuine" self-elementhood. Structures isomorphic to substructures of themselves don't really count; neither do things like the class of ordinals being a "class-sized ordinal."

---

*On, e.g., page 55 of Inter-universal Teichmuller Theory IV (http://www.kurims.kyoto-u.ac.jp/~motizuki/Inter-universal%20Teichmuller%20Theory%20IV.pdf).

---

(Nov 11, 2021: Since I bumped this post with a new answer anyways, I've taken the opportunity to remove a [very incorrect](https://mathoverflow.net/a/125842/8133) claim about the Gromov-Hausdorff metric and generally shorten this question substantially.)

Answer 1

Building off of Steve Huntsman's comment comparing self-containment with Cantor's diagonal argument, the set of partial computable functions can be viewed as containing itself (infinitely many times, in fact, in infinitely many ways) via the concept of a universal computable function. (By contrast, the standard diagonalization shows that the set of total computable functions does not contain itself in this way.) This actually works on the level of computable functionals: there is a single $e\in\omega$ such that for all $X\subseteq\omega$, $$ \Phi_e^X(\langle x, y\rangle)\cong \Phi_x^X(y)$$ (where $a\cong b$ means that either both $a$ and $b$ are defined and equal, or both $a$ and $b$ are undefined).

[Now as a side remark, consider the recursion theorem, which says that there is a single computable (partial) function $f$ such that for all total $\Phi_e$, $$\Phi_{\Phi_e(f(e))}= \Phi_{f(e)}.$$ The key technical step in proving this theorem is the construction of a total function $t$ such that $\Phi_e(e)\downarrow\implies \Phi_{\Phi_e(e)}=\Phi_{t(e)}$, and this in turn crucially uses the existence of universal computable functions. Moreover, the intuition behind the proof of the recursion theorem is that it is a failed attempt at diagonalization. At least to me, this reinforces the notion that self-containment can be thought of as a kind of anti-diagonalizability.]

Answer 2

In the same vein as your Gromov-Hausdorff example, the set of all isomorphism classes of finitely generated monoids is a monoid under direct sum. And this recent MO question concerns the skeleton-of-the-category of all skeletons-of-categories.

Answer 3

The class of isomorphism types of well-ordered sets, by a classical theorem of Cantor, is well-ordered under the natural relation $R$, where $xRy$ iff $x$ is isomorphic to an initial segment of $y$.

The infamous Burali-Forti Paradox arises from (mis)reading the above as "the class of ordinals is an element if itself".

Answer 4

It seems (to me, at least) natural to model a position in a game as the set of all positions that can be reached in one move. But then well-foundedness prevents you from using this representation to represent games with loops.

If you're interested in modelling connectivity in web pages, it seems natural to me to represent a web page as the set of web pages it links to. But links form cycles.

Computer science abounds with examples of types that can be awkward to model with well-founded sets. For example, in many computing environments elements of lists are represented by pointers to a block of data, not by the block of data itself. So it's often straightforward to construct a list, say, that contains itself, or at least contains loops of inclusions, because under the hood the self-containment is indirect. It'd be nice to model these with non-well founded sets because you'd like to abstract away from the fact that containment is implemented indirectly so you can reason directly about containment.

Answer 5

What about fractals? Or more general, objects with some kind of self similarity? They often arise as fixed points of a self-map. In category theory these are known as initial algebras or terminal coalgebras. For example, $\mathbb{N}=1+\mathbb{N}$, $[0,1] = [0,1] {\cup}_{0 \sim 1} [0,1]$, and the set of binary trees $T$ satisfies $T=1+T^2$. Another example which comes to my mind: There are abelian groups $A$ with $A^3 \cong A$ and $A^2 \not\cong A$. I have to admit that this does not quite fit to your question, since you want that "$X \\in X$", but in the above examples we have "$X \subsetneq X$". So let me add something else:

• The category of small categories, functors and morphism of functors $\mathsf{Cat}$ is a category (which is not small).
• The class of ordinal numbers $\mathrm{On}$ is with $\in$ the well-order of all isomorphism classes of small well-orders. Of course it is not small.
• Quite similar and trivial, but the von Neumann universe is just the set (or class if you don't work with universes) of all small sets.
• If $X$ is a set, the set of topologies on $X$ carries a topology. A subbase is given by those topologies containing some fixed subset of $X$.
• Uniform convergence spaces seem to be filters of filters(?).
• This paper discusses the graph of all graphs on $n$ vertices on page 8.
• The Rado graph contains a copy of every finite or countably infinite graph.

Answer 6

While you were asking about examples rather than foundations, you did mention the system NF. In the paper

http://math.stanford.edu/~feferman/papers/ess.pdf

Feferman discusses the merits and demerits of using the modified system NFU as a foundation supporting certain aspects of self-containment.

Answer 7

For any 2-category $C$ one has the 2-category $Mon(C)$ which has as objects the monads in $C$. This gives a functor of 2-categories $Mon\colon 2CAT\to 2CAT$ where $2CAT$ is the category of 2-categories.

Interestingly $Mon$ as an endofunctor of $2CAT$ can be given the structure of a monad. So $Mon$ can be thought of as an element of $Mon(2CAT)$.

Not sure if one can totally work around the size concerns here. In a way, this already uses the dubious fact that $2CAT$ contains itself, so is probably not what you were looking for.

Answer 8

Hi, I don't think that the example of Gromov-Hausdorff is really an example. I mean, that is certainly a bounded metric space but is not compact. To see why consider the sequence where the $n$-th term is the space of $n$ points each with distance 1 from each other. This has no convergent subsequence in the sense of GH.

A set of metric spaces si relatively compact w.r.t. GH if and only if is it uniformly totally bounded, i.e. for every $\epsilon$ there exists $N(\epsilon)$ such that every space in the set can be covered with at most $N(\epsilon)$ balls of radius $\epsilon$ (Gromov).

P.s. I would have liked to post this as a comment, but don't really know how to, first post here

ADDED. Perhaps not really obvious, but a quite short argument gives the answer: what is true is that their distance is always at least $1/2$ ($1/2$ is realized by your example taking as second space the one with 2 points). Indeed assume by contradiction that for $n< m$ the distance between $X_n$ and $X_m$ is less that $1/2$. This means that there exists a metric space $(Y,d_Y)$ containing (isometric copies of) the spaces $X_n,X_m$ such that the Hausdorff distance of $X_n$ and $X_m$ in $Y$ is less than $1/2$.

Let $x_1,...,x_n$ be the points in $X_n$ and observe that by assumption for every $x_i\in X_n$ there exists a $y_i\in X_m$ such that $d_Y(x_i,y_i)<1/2$. Given that distinct points in $X_m$ have distance 1, such $y_i$ is unique for every $i$. But given that $m>n$ there must be $y\in X_m$ which is not in the set $(y_i)_{i=1,...,n}$. Then the triangle inequality tells that it must hold $d_Y(y,x_i)>1/2$ for every $i=1,...,n$ contradicting the assumption

Answer 9

Here's a very elementary example: the set $\mathbb{T}$ of triangles in the plane up to similarity can naturally be construed as a triangle itself, and hence can be identified with an element of itself. This was initially observed by Gaspar (All triangles at once), and Stewart subsequently provided a more abstract analysis of the situation (Why do all triangles form a triangle?).