Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
10  
    
This question has a related meta thread concerning the link to Halmos's book - tea.mathoverflow.net/discussion/552/… –  François G. Dorais Jul 26 '10 at 14:38
add comment

7 Answers 7

up vote 29 down vote accepted

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\}$.

share|improve this answer
2  
perhaps your last sentence is supposed to be "...such that $x = \{x\}$"? –  Willie Wong Jul 25 '10 at 15:27
1  
Thanks for your swift answer. That's was all I asked for. (Edit the second link, please.) –  Unknown Jul 25 '10 at 15:28
add comment

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.

share|improve this answer
1  
Thanks for exposition. Now I have more to learn than staying contented with the first answer. –  Unknown Jul 25 '10 at 16:09
2  
In your third paragraph, you probably mean that DC is a weak version of AC, right? –  Willie Wong Jul 25 '10 at 16:31
8  
@Willie: Ha! Yes, unfortunately. It would have been cute if instead it was an ill-founded joke. –  Andres Caicedo Jul 25 '10 at 16:34
6  
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.‘ –  Peter LeFanu Lumsdaine Jul 25 '10 at 20:00
5  
I've always liked that joke, but never managed to tell it without its falling flat. –  gowers Jul 25 '10 at 21:46
add comment

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.

share|improve this answer
6  
Hi Thomas! Welcome. –  Andres Caicedo Jul 25 '10 at 21:33
1  
Welcome, Dr. T.E. Forster! –  Unknown Jul 26 '10 at 7:38
add comment

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…

share|improve this answer
1  
Thanks, Quine atoms is the right word. –  Unknown Jul 25 '10 at 15:37
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

This is an aside note: We don't have an established notation that extracts the content of a one-element set. E.g., how do you define the inverse of an injective map by a formula?

share|improve this answer
3  
Welcome, Professor. I think the aside note can be made another MO question. –  Unknown Jul 26 '10 at 9:48
4  
You can extract the content of a one-element set with the usual sum-set notation: $\bigcup\{a\}=a$ (well, in the standard setup where every object is a set, anyway). –  Emil Jeřábek Feb 22 '11 at 15:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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