24
$\begingroup$

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.)
$\endgroup$
7
  • 1
    $\begingroup$ This strikes me as a kind of opposite of Cantor diagonalization, BTW. $\endgroup$ Mar 24, 2013 at 2:17
  • $\begingroup$ @Steve: I agree on both counts. $\endgroup$ Mar 24, 2013 at 2:19
  • $\begingroup$ +1 for the Gromov-Hausdorff example. $\endgroup$ Mar 24, 2013 at 10:20
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 25, 2013 at 2:11
  • 1
    $\begingroup$ This sounds like of Hofstadter's concept of "strange loop", explored in his book GEB. $\endgroup$
    – user12265
    Mar 25, 2013 at 4:29

9 Answers 9

8
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 24, 2013 at 2:34
  • $\begingroup$ Correction: above, "size $\kappa$" should of course be "size $\le\kappa$." $\endgroup$ Mar 24, 2013 at 2:36
  • $\begingroup$ I've added the necessary finiteness assumption. $\endgroup$ Mar 24, 2013 at 3:03
  • 1
    $\begingroup$ @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. $\endgroup$ Mar 24, 2013 at 3:31
  • 1
    $\begingroup$ There are uncountable many isomorphism classes of 2-generated groups. $\endgroup$ Apr 8, 2013 at 3:04
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Mar 24, 2013 at 21:08
  • $\begingroup$ I've already mentioned this example in my answer (ordinal numbers). $\endgroup$ Mar 25, 2013 at 11:25
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Mar 24, 2013 at 3:52
  • $\begingroup$ 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.) $\endgroup$ Mar 24, 2013 at 3:56
  • $\begingroup$ (My first comment refers to the first three of the bullet-pointed examples.) $\endgroup$ Mar 24, 2013 at 3:57
  • $\begingroup$ 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. $\endgroup$ Mar 24, 2013 at 16:26
  • $\begingroup$ 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$. $\endgroup$ Mar 24, 2013 at 16:45
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Noah Stein
    Mar 28, 2013 at 21:01
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.