What does it mean in reality? I'm interested in down to earth examples of that concept that serve as motivation or inspiration for its introduction into mathematics. Being a programmer, to me there is nothing more well founded, intuitive or natural than a structure or an object that contains a pointer to itself to begin with. Or an indexed list that is a set of entries, plus one special entry, its index, which contains pointers to its "proper" entries. Reading "Mathematical foundations of consciousness", by Miranker and Zuckerman, I'm aware of some less down to earth possible applications of that concept. Also, from pedagogical point of view, if we say that a set contains itself as a non proper subset, we should say that a set can contain itself as a non proper, self referencing element, ie previously mentioned pointer. Such terminology underpins nicely the difference between relations "contains as a subset" vs "contains as an element", and it also implies that the first relation always stands, ie whenever a subset proposition merely doesn't exclude any element of the original set, the subset is not proper, ie it is equal to the original set, while the other relation may or may not be the case, depending on the presence of the self referencing element, and unless there is an axiom of regularity included in theory, which specifically forbids such possibility. If there is no other, proper elements in the set, besides self reference element, such set is called Quine atom. Does that make any sense to you, or do you have some better interpretation of that notion?

  • 1
    $\begingroup$ "nothing more well founded" hehe. $\endgroup$ – Noah Schweber Apr 3 '18 at 21:05
  • 3
    $\begingroup$ It is highly unclear what you are asking, but Barwise and Moss's excellent book Vicious Circles probably contains the answer. More specifically, their presentation of non-well founded set theory is very sympathetic to computer science applications, with non-well founded sets viewed as various kinds of non-terminating processes (like a process that outputs the digits of $\pi$). $\endgroup$ – Rob Arthan Apr 3 '18 at 21:08
  • $\begingroup$ OK, thanks for the book recommendation, but this proves that the question was not that unclear to you, as you said at first. When I was 6 years old, negative numbers were unintuitive to me, so yeah, I must admit that even today the notion of "a set containing itself as an element" isn't that much intuitive to me as I said at first, hence the question. $\endgroup$ – hdjur_jcv Apr 3 '18 at 22:24
  • $\begingroup$ @NoahSchweber I said that ironically, considering the fact that this notion only exists in a "Non-well-founded set theory". $\endgroup$ – hdjur_jcv Apr 3 '18 at 22:27
  • $\begingroup$ How about some paragraph breaks, eh? $\endgroup$ – Asaf Karagila Apr 3 '18 at 23:03

There are no real "down to earth" examples. The first problem here is that "down to earth" is not a mathematical notion, but rather an informal notion that describes something akin to "how technically involved do you need to be in order to understand something". In the context of your question, I feel like this should be interpreted as "naive set theory".

But now we run into the second problem. Naive set theory, on its own, is flatly inconsistent. So we need some set of axioms. The problem is that choosing that set of axioms will invariably make our answer different. Okay, so how about we pick some strong candidates: Zermelo–Fraenkel (the standard set theory) and Quine's New Foundations (which might be considered fringe, but I'll explain why I chose it later), and agree that naive set theory should have natural interpretation in both theories.

Okay, so we got over the first two problems. Now we get to the main one. Zermelo–Fraenkel proves that no set is an element of itself. So no theory that is naturally interpreted by it can have a "down to earth" example of a set which is an element of itself.

You might want to retort: we know that the only reason for the above is that the Axiom of Regularity (or Foundation) is part of Zermelo–Fraenkel. How about we just remove it? Well, that's great, but it's still consistent with the rest of the axioms, so just removing it won't let you have a provable and nice smooth interpretation of a set which is an element of itself.

So what can we deduce from this? Well, we need to look back at the sets we can actually write. We can write $\varnothing$, the empty set. That's easy. We can write all of its subsets, and the set of these subsets which is just $\{\varnothing\}$. We can continue, and show that if we can write a set by hand, completely and in full, then we can write any of its subsets and the set of all of its subsets.

But here's something peculiar. None of these sets above are elements of themselves. Surely $\varnothing$ is not an element of itself, it has no elements; and $\{\varnothing\}$ is not an element of itself either since its only element is the empty set but $\{\varnothing\}$ is not empty; and so on and so forth. This means that the sets that we can come up with and describe "all the way down" are never elements of themselves, they are never elements of their elements, and so on. So Mirimanoff observed that and called these "regular sets", and the Axiom of Regularity in fact states that all sets are regular. That's great.

Okay. I brought up Quine's New Foundation before. What about that theory? Well, that's a peculiar theory. It sort of imbibes the ideas from type theory into the basic notions of sets. But it does it in a way that allows you to have a universal set. So you have the set of all sets. And I'll be damned if that is not a down to earth example of a set which is an element of itself.

So maybe Zermelo–Fraenkel is not a good set theory? Well, you could argue that. But you'd have to fight a century of research that stacks the deck very much against you. We know that Zermelo–Fraenkel is rather intuitive to work with, much more than Quine's theory which requires you to keep constant fingers on the pulse of your logic. We know that Zermelo–Fraenkel is a fairly strong theory, and it has a nice family of extending principles (choice principles, large cardinals, forcing axioms) which all come up naturally from the rest of mathematics. New Foundations on the other hand, is probably only as strong as arithmetic, which is not that much, as far as foundations go.

So what did we learn here? Well, we learned that there is no "down to earth" example, because it's simply consistent that there isn't. And a "down to earth" example is almost always one where you can always prove exist (so you don't need any additional technical hypotheses). On the other hand, there is one in the case of some non-traditional set theories, but this is definitely not down to earth.

Let me make one last remark, that ill-founded relations can easily be found in type theoretic settings. Which is the sort of thing you refer to as a programmer, "a pointer to an object which points to itself", but a set is more of a directory in a filesystem tree, it cannot be an object inside itself (while it can have a symbolic link to itself, but that's not the same object!). But type theory is not set theory. Just like C is not Common Lisp, even if it sometimes wants to be (see Greenspun's Tenth Rule).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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