<p>Let X be the set of all sets that do not contain themselves. Is X a member of X?</p>

[{'answer_id': 35371, 'author': 'Tyler', 'author_id': 3561, 'author_profile': 'https://Stackoverflow.com/users/3561', 'pm_score': 2, 'selected': False, 'text': '<p>The question is ill-posed in the standard <a href="http://en.wikipedia.org/wiki/Zermelo-Fraenkel_set_theory" rel="nofollow noreferrer">ZFC</a> (Zermelo-Fraenkel + axiom of Choice) set theory because the object thus defined is not a set.</p>\n\n<p>Since (again, assuming standard ZFC) your <em>class</em> {x : x\\not\\in x} is not a set, the answer becomes no, it\'s not an element of itself (even as a class) since only sets can be elements of classes or sets.</p>\n\n<p>By the way, as soon as you agree to the <a href="http://en.wikipedia.org/wiki/Axiom_of_foundation" rel="nofollow noreferrer">axiom of foundation</a>, no set can be an element of itself.</p>\n\n<p>Of course the nice thing about math is you can choose whichever axioms you want :) but believing in paradoxes is just weird.</p>\n'}, {'answer_id': 35409, 'author': 'Domenic', 'author_id': 3191, 'author_profile': 'https://Stackoverflow.com/users/3191', 'pm_score': 4, 'selected': True, 'text': '<p>In <strong>ZFC</strong>, either the axiom of foundation [as mentioned] or the axiom (scheme) of comprehension will prohibit this. The first, for obvious reasons; the second, since it basically says that for given <em>z</em> and first-order property <em>P</em>, you can construct { <em>x</em> ∈ <em>z</em> : <em>P</em>(<em>x</em>) }, but to generate the Russell set, you would need <em>z</em> = <em>V</em> (the class of all sets), which is not a set (i.e. cannot be generated from any of the given axioms).</p>\n\n<p>In New Foundations (<strong>NF</strong>), "<em>x</em> ∉ <em>x</em>" is not a stratified formula, and so again we cannot define the Russell set. Somewhat amusingly, however, <em>V</em> <em>is</em> a set in <strong>NF</strong>.</p>\n\n<p>In von Neumann--Bernays--Gödel set theory (<strong>NBG</strong>), the class <em>R</em> = { <em>x</em> : <em>x</em> is a set and <em>x</em> ∉ <em>x</em> } is definable. We then ask whether <em>R</em> ∈ <em>R</em>; if so, then also <em>R</em> ∉ <em>R</em>, giving a contradiction. Thus we must have <em>R</em> ∉ <em>R</em>. But there is no contradiction here, since for any given class <em>A</em>, <em>A</em> ∉ <em>R</em> implies either <em>A</em> ∈ <em>A</em> or <em>A</em> is a proper class. Since <em>R</em> ∉ <em>R</em>, we must simply have that <em>R</em> is a proper class.</p>\n\n<p>Of course, the class <em>R</em> = { <em>x</em> : <em>x</em> ∉ <em>x</em> }, without the restriction, is simply not definable in <strong>NBG</strong>.</p>\n\n<p>Also of note is that the above procedure is formally constructable as a proof in <strong>NBG</strong>, whereas in <strong>ZFC</strong> one has to resort to meta-reasoning.</p>\n'}, {'answer_id': 207041, 'author': 'Federico A. Ramponi', 'author_id': 18770, 'author_profile': 'https://Stackoverflow.com/users/18770', 'pm_score': 2, 'selected': False, 'text': "<p>The most elegant proof I've ever seen resembles Russell's paradox closely.</p>\n\n<p><strong>Theorem</strong> (Cantor, I suppose).\nLet X be a set, and 2^X the set of its subsets. Then card(X) &lt; card(2^X).</p>\n\n<p><strong>Proof</strong>. Surely card(X) &lt;= card(2^X), since there is a trivial bijection between X and the singletons in 2^X. We must prove that card(X) != card(2^X).</p>\n\n<p>Suppose there is a bijection between X and 2^X. Then each xk in X is mapped to a set Ak in 2^X.</p>\n\n<ul>\n<li>x1 ---> A1</li>\n<li>x2 ---> A2</li>\n<li>...</li>\n<li>xk ---> Ak</li>\n<li>...</li>\n</ul>\n\n<p>For each xk the chances are: either xk belongs to Ak, or it does not. Let M be the set of all those xk that do <em>not</em> belong to their corresponding set Ak. M is a subset of X, thus there must exist an element m of X which is mapped to M by the bijection.</p>\n\n<p>Does m belong to M? If it does, then it does not, for M is the set of those x that do <em>not</em> belong to the set they're mapped to. If it does not, then it does, for M contains <em>all</em> such x's. This contradiction stems from the assumption that a bijection exists. Thus a bijection cannot exist, the two cardinalities are different, and the theorem is proved.</p>\n"}]
['https://Stackoverflow.com/questions/35339', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/658/']