# Self-containing structures

(This question is partly inspired by What is inter-universal geometry?.)

I have absolutely no background in Teichmuller theory or any related subject, but what I can follow of Mochizuki's description of inter-universal Teichmuller theory fascinates me. In particular, I'm very interested in what I perceive as his general claim* that an ill-founded set theory would represent certain mathematical objects more intuitively, and I'd like to get a handle on this, independently of his specific work.

I'm looking for reasonably natural mathematical structures which, in some sense, "contain themselves" as an element (or element of some element, or etc.). (This is obviously a fairly soft question, and I apologize in advance if it is inappropriate for MO.)

To clarify what I mean, I know of basically two specific examples. The first is the universal set in the set theory $NF$; the second is the set of (isometry types of) compact metric spaces of diameter $\le 1$, which under the Gromov-Hausdorff metric forms a compact metric space of diameter $\le 1$. Both of these, I imagine, can be expanded: the former could be replaced with any other consistent notion of universal set, or universal category; and my understanding is that there are a number of moduli spaces which are also naturally elements of themselves. This is the sort of thing I'm looking for: well-defined mathematical structures which can naturally be thought of as containing themselves as "elements," or "points," etc.

EDIT: what I say here about the Gromov-Hausdorff metric appears to be very wrong: see Nicola Gigli's answer below. Can this would-be example be fixed?

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.

ADDED: An interesting observation is that - uniquely out of all examples and near-examples that I know - the Gromov-Hausdorff example above is not naturally "maximal" among its own elements. That is, there is no sense (that I'm aware of, at least) in which the space of all compact metric spaces of diameter $\le 1$ is the largest such metric space. This is obviously not the case for the universal set (in set theories which allow such objects), or the set of computable partial functions, or any variants of these. So a sub-question: does anyone have an example of a self-containing structure which is not somehow "maximal" amongst its elements?

*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).

-
Community wiki? – Steve Huntsman Mar 24 '13 at 2:13
This strikes me as a kind of opposite of Cantor diagonalization, BTW. – Steve Huntsman Mar 24 '13 at 2:17
@Steve: I agree on both counts. – Noah Schweber Mar 24 '13 at 2:19
Pseudo-example: the modular curve $X_0(11)$, say over $\mathbb{C}$, parametrizes elliptic curves together with a subgroup of order 11. It has genus one, so is itself an elliptic curve after choosing some base point. Thus it ''contains'' 12 copies of itself. – Kevin Ventullo Mar 25 '13 at 2:11
This sounds like of Hofstadter's concept of "strange loop", explored in his book GEB. – user12265 Mar 25 '13 at 4:29

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

-

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.

-
One crucial difference between this example and the GH-example: here, the "set" of isomorphism classes of monoids is actually a proper class, so not really an element of itself, whereas there are only set-many isomorphism types of compact metric spaces. Can there be some cardinal $\kappa$ such that there are at most $\kappa$-many monoids of size $\kappa$, up to isomorphism? This seems extremely unlikely, but if so, that would fix the problem. – Noah Schweber Mar 24 '13 at 2:34
Correction: above, "size $\kappa$" should of course be "size $\le\kappa$." – Noah Schweber Mar 24 '13 at 2:36
I've added the necessary finiteness assumption. – Martin Brandenburg Mar 24 '13 at 3:03
Is the set of all isomorphism classes of finitely generated monoids a finitely generated monoid under direct sum, though? – Noah Schweber Mar 24 '13 at 3:05
@Noah S: No, consider $\langle x : x^n=1\rangle$. But the set of isomorphism classes of finitely presented monoids is countable. I'm not sure about finitely generated monoids. – Martin Brandenburg Mar 24 '13 at 3:31

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".

-
So again, this isn't quite an example; rather, it fits into the same category as "class of all sets," "class of all monoids," etc. of objects which are essentially "limit points" of themselves. This is still an interesting category; just not quite self-containment. – Noah Schweber Mar 24 '13 at 21:08
I've already mentioned this example in my answer (ordinal numbers). – Martin Brandenburg Mar 25 '13 at 11:25

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.
-
Your latter class of examples all aren't properly elements of themselves because of the set/class issue. We can get around this by adopting a set theory which allows the universal set, as opposed to $ZF$, and this is basically my first example from the question. – Noah Schweber Mar 24 '13 at 3:52
In your second-to-last example, the set of topologies on $X$ is not a topology on $X$, but rather the set of points of a new topological space. (Sorry to keep nitpicking - I'm just really looking for a specific kind of self-containment.) – Noah Schweber Mar 24 '13 at 3:56
(My first comment refers to the first three of the bullet-pointed examples.) – Noah Schweber Mar 24 '13 at 3:57
I still think this is not what I'm looking for. The graph of all graphs on $n$ vertices is not a graph on $n$ vertices, and there is no interpretation of the random graph where each point in the graph corresponds to a countable graph. – Noah Schweber Mar 24 '13 at 16:26
I'm sorry for that. You really want to know situations where some $X$ consists of all $X$es, and not just that something made up out of special $X$es is again some $X$. – Martin Brandenburg Mar 24 '13 at 16:45

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.

-

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.

-

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.

-

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

-
Should this be obvious? I don't know much about Gromov-Hausdorff distance and when you first mentioned this sequence I assumed all the pairwise distances were 1. But having thought about it a little more, I see that it is not quite that simple. For example the distance from the one-point space to the $n$-point space is less than one because you can embed them both into $\mathbb{R}^{n−1}$ with the latter as a standard simplex and the former as its center. – Noah Stein Mar 28 '13 at 21:01