Self-Containing Sets in Set Theory: Existence, Paradoxes, and Alternative Theories

The concept of self-containing sets, or sets that contain themselves as elements, may seem counterintuitive yet fascinating. This article explores the existence of such sets, their implications in various branches of set theory, and the role of alternative theories in addressing these concepts.

Introduction to Self-Containing Sets

Yes, it is possible to define a set S such that S in S. This type of set is known as a self-containing set or a self-referential set. A simple example to illustrate this is:

S {S}

In this case, S contains itself as its only element, which means S in S.

Paradoxes in Naive Set Theory

However, it is essential to note that self-containing sets can lead to paradoxes, particularly in naive set theory. One of the most famous examples is Russell's Paradox. This paradox arises when considering the set of all sets that do not contain themselves. Specifically, let's define a set R as follows:

R {x | x otin x}

Does R in R? If R in R, then by definition, R otin R, which is a contradiction. Conversely, if R otin R, then R in R, which is another contradiction. This paradox highlights the need for more rigorous foundations in set theory.

One solution to this issue is to use Zermelo-Fraenkel set theory with the Axiom of Choice (ZFC), where such self-referential sets are avoided. In ZFC, a set cannot directly contain itself as an element because it would lead to inconsistencies. However, in certain alternative set theories or frameworks, self-containing sets can be defined and used without leading to contradictions.

Alternative Set Theories and Accessible Pointed Graphs

Alternative set theories that allow for self-containing sets often replace the Axiom of Foundation, which implies no set can be an element of itself, with some form of anti-foundation axiom. These axioms assert the existence of such sets and can be formulated using the language of graph theory.

In ZFC, wellfounded sets are easily represented as graphs by trees. For example, the ordinals can be represented with trees like this:

Here, each ordinal is a root node that has all previous ordinals as child nodes. An edge between two nodes indicates that the source node contains the target node as an element.

An alternative approach to representing ordinals is to add a new node for each previous ordinal and draw edges from the new node to all other nodes. This results in more compact representations but introduces cycles in the graphs.

These graphs are known as accessible pointed graphs. In ZFC, these graphs do not contain any infinite paths, meaning there are no cycles. However, in alternative set theories, graphs containing cycles can represent self-containing sets.

For instance, the graph representing a set ( X ) where ( X in X ) can be described as:

In this graph, the interpretation of ( X ) is ( X {X, Y} ), where ( Y ) is another set in the graph.

The connection to graph theory is due to Aczel, whose work on this topic can be found in his paper linked below. Other mathematicians, such as Scott, Finsler, and Boffa, have formalized increasingly generalized anti-foundation axioms.

Applications and Further Reading

While anti-foundation theories are not mainstream, they do have some useful applications. For example, Aczel's paper describes an application to communicating/transition systems, which can be critical in computer science and system design.

Finally, it's important to note that any universe of set theory from an anti-foundation perspective can always contain a class of wellfounded sets as found in ZFC.

Further Reading:

P. Aczel, "Non-Well-Founded Sets(" P. Aczel, D.S. Scott, M. Finsler, and M. Boffa, "Anti-Foundation and Generalized Set Theories("