MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 edited body

1) No such sets exist under the usual axiomatization of set theory (ZF).

The axiom of foundation states that $\in$ is well-founded. The axiom states that if a set $A$ is non-empty, then it has at least one element $B$ with which it has no members in common. Intuitively, this means that there are no infinite descending sequences $x_0\ni x_1\ni x_2\ni\dots$ Of course, this rules out sets $A$ with $A=$ {$A$}.

I say "intuitively" because the restatement of foundation in terms of descending sequences actually requires DC, dependent choices, a weak version of DCAC.

2) As it has already been pointed out in other answers, Peter Aczel introduced an alternative to the axiom of foundation, which he considered more appropriate for modeling some structures from computer science.

To explain his axiom, note that if $A$ is a set, we can assign to $A$ a directed graph that represents it, with a distinguished node corresponding to $A$: Simply, given a node $n$ corresponding to a set $B$, draw coming out of $n$ as many arrows as elements of $B$, and tag each new node (=head of an arrow) with one of these elements. Of course, there are several ways of doing this. For example, (recall that in set theory, $0=\emptyset$ and $1$ is the singleton {$\emptyset$}), if $A=$ {$0,1$}, one way to represent $A$ is to have a graph with 4 vertices: One is $A$, which points at two nodes (0 and 1). Precisely one of these nodes (the one corresponding to 1) points at the fourth node (which also corresponds to 0), and that's it. Another way is to have the node $A$ pointing at $0$ and $1$, and $1$ also pointing at $0$.

One can easily define an equivalence class to capture the idea that two directed graphs with a distinguished node represent the same set. The question is now whether any such graph represents some set. The axiom of foundation says that this is not the case. The axiom of anti-foundation can be stated as saying that this is the case, and in fact, each such graph corresponds to a unique set. So, under this axiom, the equation $A=$ {$A$} has exactly one solution (call it $\Omega$). The system $A=$ {$B$} and $B=$ {$A$} has exactly one solution, namely $A=B=\Omega$, etc.

Aczel's axiom is quite interesting. Inside any model of set theory without the axiom of foundation one can define a submodel of set theory where foundation also holds by simply considering only the sets $x$ where $\in$ is well-founded when restricted to $x\cup\bigcup x\cup\bigcup\bigcup x\cup\dots$ This is the class WF. One can then show that if Aczel's axiom holds and $M,N$ are models of set theory with anti-foundation such that the class WF corresponding to $M$ coincides with the class WF corresponding to $N$, then in fact $M=N$. This canonicity' of the models makes this theory very interesting in my opinion. For example, one can use transfinite induction (carefully stated) to prove results, even though, in principle, no such thing should be possible in the presence of ill-founded structures.

3) As mentioned in another answer, there are yet other alternatives to the axiom of foundation, where one may allow many solutions to the equation $A=${$A$}. However, none of these alternatives has received as much attention as Aczel's or exhibits, as far as I know, the same kind of "canonicity." More popular, instead, is to consider "set theory with atoms" where one allows additional objects other than sets to begin with. Some non-trivial questions remain about how easily can one establish consistency results in one version if one can in the other.

2 added 19 characters in body

1) No such sets exist under the usual axiomatization of set theory (ZF).

The axiom of foundation states that $\in$ is well-founded. The axiom states that if a set $A$ is non-empty, then it has at least one element $B$ with which it has no members in common. Intuitively, this means that there are no infinite descending sequences $x_0\ni x_1\ni x_2\ni\dots$ Of course, this rules out sets $A$ with $A=$ {$A$}.

I say "intuitively" because the restatement of foundation in terms of descending sequences actually requires DC, dependent choices, a weak version of DC.

2) As it has already been pointed out in other answers, Peter Aczel introduced an alternative to the axiom of foundation, which he considered more appropriate for modeling some structures from computer science.

To explain his axiom, note that if $A$ is a set, we can assign to $A$ a directed graph that represents it, with a distinguished node corresponding to $A$: Simply, given a node $n$ corresponding to a set $B$, draw coming out of $n$ as many arrows as elements of $B$, and tag each new node (=head of an arrow) with one of these elements. Of course, there are several ways of doing this. For example, (recall that in set theory, $0=\emptyset$ and $1$ is the singleton {$\emptyset$}), if $A=$ {$0,1$}, one way to represent $A$ is to have a graph with 4 vertices: One is $A$, which points at two nodes (0 and 1). Precisely one of these nodes (the one corresponding to 1) points at the fourth node (which also corresponds to 0), and that's it. Another way is to have the node $A$ pointing at $0$ and $1$, and $1$ also pointing at $0$.

One can easily define an equivalence class to capture the idea that two directed graphs with a distinguished node represent the same set. The question is now whether any such graph represents some set. The axiom of foundation says that this is not the case. The axiom of anti-foundation says can be stated as saying that this is the case, and in fact, each such graph corresponds to a unique set. So, under this axiom, the equation $A=$ {$A$} has exactly one solution (call it $\Omega$). The system $A=$ {$B$} and $B=$ {$A$} has exactly one solution, namely $A=B=\Omega$, etc.

Aczel's axiom is quite interesting. Inside any model of set theory without the axiom of foundation one can define a submodel of set theory where foundation also holds by simply considering only the sets $x$ where $\in$ is well-founded when restricted to $x\cup\bigcup x\cup\bigcup\bigcup x\cup\dots$ This is the class WF. One can then show that if Aczel's axiom holds and $M,N$ are models of set theory with anti-foundation such that the class WF corresponding to $M$ coincides with the class WF corresponding to $N$, then in fact $M=N$. This canonicity' of the models makes this theory very interesting in my opinion. For example, one can use transfinite induction (carefully stated) to prove results, even though, in principle, no such thing should be possible in the presence of ill-founded structures.

3) As mentioned in another answer, there are yet other alternatives to the axiom of foundation, where one may allow many solutions to the equation $A=${$A$}. However, none of these alternatives has received as much attention as Aczel's or exhibits, as far as I know, the same kind of "canonicity." More popular, instead, is to consider "set theory with atoms" where one allows additional objects other than sets to begin with. Some non-trivial questions remain about how easily can one establish consistency results in one version if one can in the other.

1

1) No such sets exist under the usual axiomatization of set theory (ZF).

The axiom of foundation states that $\in$ is well-founded. The axiom states that if a set $A$ is non-empty, then it has at least one element $B$ with which it has no members in common. Intuitively, this means that there are no infinite descending sequences $x_0\ni x_1\ni x_2\ni\dots$ Of course, this rules out sets $A$ with $A=$ {$A$}.

I say "intuitively" because the restatement of foundation in terms of descending sequences actually requires DC, dependent choices, a weak version of DC.

2) As it has already been pointed out in other answers, Peter Aczel introduced an alternative to the axiom of foundation, which he considered more appropriate for modeling some structures from computer science.

To explain his axiom, note that if $A$ is a set, we can assign to $A$ a directed graph that represents it, with a distinguished node corresponding to $A$: Simply, given a node $n$ corresponding to a set $B$, draw coming out of $n$ as many arrows as elements of $B$, and tag each new node (=head of an arrow) with one of these elements. Of course, there are several ways of doing this. For example, (recall that in set theory, $0=\emptyset$ and $1$ is the singleton {$\emptyset$}), if $A=$ {$0,1$}, one way to represent $A$ is to have a graph with 4 vertices: One is $A$, which points at two nodes (0 and 1). Precisely one of these nodes (the one corresponding to 1) points at the fourth node (which also corresponds to 0), and that's it. Another way is to have the node $A$ pointing at $0$ and $1$, and $1$ also pointing at $0$.

One can easily define an equivalence class to capture the idea that two directed graphs with a distinguished node represent the same set. The question is now whether any such graph represents some set. The axiom of foundation says that this is not the case. The axiom of anti-foundation says that this is the case, and in fact, each such graph corresponds to a unique set. So, under this axiom, the equation $A=$ {$A$} has exactly one solution (call it $\Omega$). The system $A=$ {$B$} and $B=$ {$A$} has exactly one solution, namely $A=B=\Omega$, etc.

Aczel's axiom is quite interesting. Inside any model of set theory without the axiom of foundation one can define a submodel of set theory where foundation also holds by simply considering only the sets $x$ where $\in$ is well-founded when restricted to $x\cup\bigcup x\cup\bigcup\bigcup x\cup\dots$ This is the class WF. One can then show that if Aczel's axiom holds and $M,N$ are models of set theory with anti-foundation such that the class WF corresponding to $M$ coincides with the class WF corresponding to $N$, then in fact $M=N$. This `canonicity' of the models makes this theory very interesting in my opinion. For example, one can use transfinite induction (carefully stated) to prove results, even though, in principle, no such thing should be possible in the presence of ill-founded structures.

3) As mentioned in another answer, there are yet other alternatives to the axiom of foundation, where one may allow many solutions to the equation $A=${$A$}. However, none of these alternatives has received as much attention as Aczel's or exhibits, as far as I know, the same kind of "canonicity." More popular, instead, is to consider "set theory with atoms" where one allows additional objects other than sets to begin with. Some non-trivial questions remain about how easily can one establish consistency results in one version if one can in the other.