11
$\begingroup$

Does there exist a set $A$ such that $A=\{A\}$ ?

Edit(Peter LL): Such sets are called Quine atoms.

Naive set theory By Paul Richard Halmos On page three, the same question is asked.

Using the usual set notation, I tried to construct such a set: First with finite number of brackets and it turns out that after deleting those finite number of pairs of brackets, we circle back to the original question.

For instance, assuming $A=\{B\}$, we proceed as follows: $\{B\}=\{A\}\Leftrightarrow B=A \Leftrightarrow B=\{B\}$ which is equivalent to the original equation.

So the only remaining possibility is to have infinitely many pairs of brackets, but I can't make sense of such set. (Literally, such a set is both a subset and an element of itself. Further more, It can be shown that it is singleton.)

For some time, I thought this set is unique and corresponded to $\infty$ in some set-theoretic construction of naturals.

To recap, my question is whether this set exists and if so what "concrete" examples there are. (Maybe this set is axiomatically prevented from existing.)

$\endgroup$
2

6 Answers 6

34
$\begingroup$

In standard set theory (ZF) this kind of set is forbidden because of the axiom of foundation.

There are alternative axiomatisations of set theory, some of which do not have an equivalent of the axiom of foundation. This is called non-well-founded set theory. See e.g. Aczel's anti-foundation_axiom, where there is a unique set such that $x = \{x\}$.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for your swift answer. That's was all I asked for. (Edit the second link, please.) $\endgroup$
    – Unknown
    Commented Jul 25, 2010 at 15:28
23
$\begingroup$

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

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.

$\endgroup$
6
  • 1
    $\begingroup$ Thanks for exposition. Now I have more to learn than staying contented with the first answer. $\endgroup$
    – Unknown
    Commented Jul 25, 2010 at 16:09
  • 2
    $\begingroup$ In your third paragraph, you probably mean that DC is a weak version of AC, right? $\endgroup$ Commented Jul 25, 2010 at 16:31
  • 8
    $\begingroup$ @Willie: Ha! Yes, unfortunately. It would have been cute if instead it was an ill-founded joke. $\endgroup$ Commented Jul 25, 2010 at 16:34
  • 8
    $\begingroup$ This is starting to sound like Jourdain's The Hierarchy of Jokes: ‘...$A$ remarked on this joke that no joke could penetrate the head of the Scotchman to whom the joke of the first order was told, even if it were fired into his head with a gun. The Scotchman, after severe thought, replied: “But ye couldn’t do that, ye know!” $A$ repeated the whole story, which constituted a joke of the third order, to a third Scotchman. This last Scotchman again, after prolonged thought, replied: “He had ye there!” This whole story is a joke of the fourth order.‘ $\endgroup$ Commented Jul 25, 2010 at 20:00
  • 5
    $\begingroup$ I've always liked that joke, but never managed to tell it without its falling flat. $\endgroup$
    – gowers
    Commented Jul 25, 2010 at 21:46
14
$\begingroup$

Yes, these things are called Quine atoms, tho' i think there is a literature about them that goes back earlier than Quine. Yes, Forti-Honsell's antifoundation axiom (written about and popularised by Aczel) does indeed say that there is one and that it is unique. It is known that relative to Quine's set theory NF their existence is consistent and independent.

$\endgroup$
2
  • 8
    $\begingroup$ Hi Thomas! Welcome. $\endgroup$ Commented Jul 25, 2010 at 21:33
  • 1
    $\begingroup$ Welcome, Dr. T.E. Forster! $\endgroup$
    – Unknown
    Commented Jul 26, 2010 at 7:38
11
$\begingroup$

Such sets are interesting — they're known as Quine atoms. As Dan says, they're forbidden in ZFC by the axiom of foundation (or equivalent axioms such as regularity), but they can exist in various nonstandard set theories.

Under Aczel's anti-foundation axiom, there's a unique Quine atom.

On the other hand, with neither foundation nor anti-foundation assumed, lots of things are consistent iirc: there can be any number of Quine atoms you want, even a proper class (and there's a very cute consistency proof for this, using permutation models, which I can't quite recall).

Everything I used to know about Quine atoms, I learned from Thomas Forster, who is rather keen on them! I don't think he's on MO, but I'll see if he has anything to add on the matter…

$\endgroup$
0
5
$\begingroup$

(This is intended as a comment on Thomas Forster’s point above, “i think there is a literature about them that goes back earlier than Quine,” but I’m over the character limit.)

    Much earlier than Quine; Frege uses the trick in §10 of the Grundgesetze, setting (loosely, in modern terms) the True and False to their own singletons. He considers using the trick in greater generality, à la Quine, in footnote 17: “A natural suggestion is to generalize our stipulation so that every object is regarded as a course-of-values, viz., as the extension of a concept under which it and it alone falls.” I would be stunned if this did not influence Quine’s use, either directly or indirectly, subconsciously or consciously.

    Richard Heck discusses the stipulation is great detail in Part I of Reading Frege’s Grundgesetze, as part of his treatment of The Julius Caesar Problem, i.e., how can we be sure that the extension of some concept is not equal to Julius Caesar?

    Personally, I feel that it is still too soon for Frege to worry about The Julius Caesar Problem. As he pointed out elsewhere, discussing a language that hasn’t yet been fully formalized is fraught with peril, and “Julius Caesar” is not yet a precisely-defined term in a formal language.  (Perhaps Caesar will end up being formalized as the extension of a concept after all—I don’t want to pre-judge the formalization of zoology.)  And obviously his proof of referentiality in §10 has to break down somewhere, or it would have been a consistency proof for naïve set theory.

$\endgroup$
1
3
$\begingroup$

I would like to further refer to The Liar:an essay on truth and circularity by Jon Barwise who elucidates hypersets (sets that can contain themselves) and Ben Goertzel in Chaotic Logic: Chapter VII Self-Generating System discusses this at length which can be accessed here.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .