Can we have A={A} ? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T18:09:40Z http://mathoverflow.net/feeds/question/33282 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/33282/can-we-have-aa Can we have A={A} ? To be cont'd 2010-07-25T15:11:48Z 2013-05-09T19:34:02Z <p>Does there exist a set $A$ such that $A=\{A\}$ ? </p> <p>Edit(Peter LL): Such sets are called Quine atoms.</p> <p><a href="http://dc108.4shared.com/download/YNLXDssM/Halmos_-_Naive_set_theory.djvu?tsid=20100725-105252-871bd162" rel="nofollow">Naive set theory By Paul Richard Halmos</a> On page three, the same question is asked.</p> <p>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.</p> <p>For instance, assuming $A=\{B\}$, we proceed as follows: $\{B\}=\{A\}\Leftrightarrow B=A \Leftrightarrow B=\{B\}$ which is equivalent to the original equation.</p> <p>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.)</p> <p>For some time, I thought this set is unique and corresponded to $\infty$ in some set-theoretic construction of naturals. </p> <p>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.)</p> http://mathoverflow.net/questions/33282/can-we-have-aa/33283#33283 Answer by Dan Petersen for Can we have A={A} ? Dan Petersen 2010-07-25T15:20:59Z 2013-05-09T19:34:02Z <p>In standard set theory (ZF) this kind of set is forbidden because of the <a href="http://en.wikipedia.org/wiki/Axiom_of_foundation" rel="nofollow">axiom of foundation</a>.</p> <p>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. <a href="http://en.wikipedia.org/wiki/Aczel%27s_anti-foundation_axiom" rel="nofollow">Aczel's anti-foundation_axiom</a>, where there is a unique set such that <code>$x = \{x\}$</code>.</p> http://mathoverflow.net/questions/33282/can-we-have-aa/33284#33284 Answer by Peter LeFanu Lumsdaine for Can we have A={A} ? Peter LeFanu Lumsdaine 2010-07-25T15:29:56Z 2010-07-25T15:29:56Z <p>Such sets are interesting — they're known as <strong><em>Quine atoms</em></strong>. 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.</p> <p>Under Aczel's <a href="http://en.wikipedia.org/wiki/Aczel%27s_anti-foundation_axiom" rel="nofollow">anti-foundation axiom</a>, there's a unique Quine atom.</p> <p>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).</p> <p>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…</p> http://mathoverflow.net/questions/33282/can-we-have-aa/33288#33288 Answer by Andres Caicedo for Can we have A={A} ? Andres Caicedo 2010-07-25T15:56:44Z 2010-07-25T16:35:43Z <p>1) No such sets exist under the usual axiomatization of set theory (ZF). </p> <p>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$}.</p> <p>I say "intuitively" because the restatement of foundation in terms of descending sequences actually requires DC, dependent choices, a weak version of AC. </p> <p>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. </p> <p>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$. </p> <p>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.</p> <p>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. </p> <p>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. </p> http://mathoverflow.net/questions/33282/can-we-have-aa/33327#33327 Answer by Thomas Forster for Can we have A={A} ? Thomas Forster 2010-07-25T21:27:16Z 2010-07-25T21:27:16Z <p>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.</p> http://mathoverflow.net/questions/33282/can-we-have-aa/33371#33371 Answer by Christian Blatter for Can we have A={A} ? Christian Blatter 2010-07-26T08:29:29Z 2010-07-26T08:29:29Z <p>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?</p> http://mathoverflow.net/questions/33282/can-we-have-aa/78872#78872 Answer by Zeeshan Mahmud for Can we have A={A} ? Zeeshan Mahmud 2011-10-23T06:44:35Z 2011-10-23T06:44:35Z <p>I would like to further refer to <em>The Liar:an essay on truth and circularity</em> 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 <a href="http://www.goertzel.org/books/logic/chapter_seven.htm" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/33282/can-we-have-aa/130187#130187 Answer by Flash Sheridan for Can we have A={A} ? Flash Sheridan 2013-05-09T16:18:39Z 2013-05-09T16:18:39Z <p>(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.)</p> <p>    <em>Much</em> earlier than Quine; Frege uses the trick in §10 of the <em>Grundgesetze</em>, 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. </p> <p>    Heck discusses the stipulation is great detail in Part I of <em>Reading Frege’s Grundgesetze,</em> 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?</p> <p>    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 <em>somewhere,</em> or it would have been a consistency proof for naïve set theory.</p>