Many of you know such paradox...
" $\exists y \forall x (x \in y \Longleftrightarrow \Phi(x)$" for any function $\Phi(x)$ substitute $x \notin x$ for $\Phi(x)$ Then by existential instantiation (reusing the symbol y) and universal instantiation we have $ y \in y$ and $y \notin y$."
Could anyone elaborate on what this paradox is saying?

Source A Brief History of the Paradox, Philosophy, and Labyrinths of the Mind

  • 1
    $\begingroup$ You're considering "the set of all sets that are not members of themselves." Calling this $y$, we can ask, "does $y\in y$?" If "yes," then $y\not\in y$ and similarly if "no," then $y\in y$ $\endgroup$ – yoyo Sep 17 '13 at 3:30

Forget about barbers -- they give rise to no paradox (there can't be a barber in the village who shaves all and only those who do not shave themselves, end of story).

We get a paradox when plausible premisses we have independent reasons to believe lead by reasoning we have independent reasons to think is compelling to a contradictory conclusion. (We have no independent reason to suppose that there is [or even can be] a village with a barber who shaves all and only those who do not shave themselves, so there's no paradox in proving there can't be one.)

So back to Russell's Paradox proper. Here the background plausible assumption is that whenever we can sensibly talk of the $F$'s (or the objects which have the property $F$) then there is a set which contains just such objects. What could be more natural, than to think that when we can pick out some things, we can talk about a totality, collection, or set, containing just those things?

Suppose the predicate $\phi$ expresses the particular property $F$. Then the claim that there is a corresponding set $\sigma$ containing just the $F$s is the claim that there is a $\sigma$ such that $\forall x(x \in \sigma \leftrightarrow \varphi(x))$. Usually this is just fine. But the plausible principle is that this is fine whatever predicate we take, expressing any property we choose. In other words, the plausible "Naive Comprehension" principle is that every instance of the schema $\exists y\forall x(x \in y \leftrightarrow \Phi(x))$ is true.

And what the argument of Russell's Paradox shows is that if you accept standard logic and allow $\Phi$ to be substituted by expressions which themselves contain $\in$, then contradiction ensues.

What to do? Revise logic? A few extremists want to! Not allow substitution of $\Phi$ by expressions which themselves contain $\in$? But that would seem not to be taking sets seriously as things that can be mentioned in defining genuine properties. So it seems we have to reject Naive Comprehension. But that's initially very puzzling (although we can learn quickly to live with it): for the idea that if we can talk about the $F$s we can talk about a collection of just those things initially seems so very natural and compelling.

  • 2
    $\begingroup$ +$\pi$ for forgetting about barbers. I always found those analogies to end up as misleading if you want to get into the actual mathematics later on (if you just explain it to someone over beer, it's fine though). $\endgroup$ – Asaf Karagila Sep 17 '13 at 8:48

Another form of this is called the barber paradox:

In the town of Chelm there is a barber who shaves every man who does not shave himself, and the barber does not shave anyone else. Who shaves the barber?

The resolution to the paradox, of course, is that the barber is not a man. In the language of class-set theory, the class of all sets is a proper class. But in the language of set theory without classes, the paradox says "every person who does not shave zirself", the only resolution being that the statement is false and there is no such barber.

  • 1
    $\begingroup$ Shouldn't it be said that the barber shaves exactly those men who do not shave themselves? Otherwise, it's not paradoxical for the barber to shave himself and still be a man. $\endgroup$ – Dan Ramras Sep 17 '13 at 3:58
  • $\begingroup$ Corrected, hopefully. $\endgroup$ – dfeuer Sep 17 '13 at 4:15
  • $\begingroup$ I've added two words so that the sentence cannot be wrongly read. $\endgroup$ – Marc van Leeuwen Sep 17 '13 at 5:24
  • 4
    $\begingroup$ The original formulation by Russell appears to be sex-neutral "one who shaves all those, and those only, who do not shave themselves". $\endgroup$ – Marc van Leeuwen Sep 17 '13 at 5:30
  • $\begingroup$ Just remember to use the barber with the worst shave. $\endgroup$ – marty cohen Sep 17 '13 at 5:33

The contradiction in Russell's Paradox arose from an early attempt by Frege to axiomatize set theory. Using his axiom of comprehension (section 1.3), you could prove that $$\exists r: \forall x:[x\in r \iff x\notin x]$$

Using ordinary logic (a simple proof by contradiction), you could prove this was false as you have outlined in your question.

Various patches on this problem were proposed, some banning proof by contradiction, others introducing an infinite hierarchies of types that effectively banned constructs like $x\in x$. The most popular alternative among set theorists is the Zermelo-Fraenkel axioms of set theory .


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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