# Doesn't statement 'S is a set of all sets that are not elements of themselves.' hold true by reductio ad absurdum?

The simplest of the logical paradoxes is Russell's paradox, which can be described as follows:

Let $S$ denote the set of all sets that are not elements of themselves. Is $S$ an element of itself?

• Well, if $S$ is an element of $S$, then - by the very definition of $S$ - $S$ is not an element of $S$.

• If $S$ is not an element of $S$, then (again, because of the way $S$ is defined) $S$ is an element of $S$.

Thus, we have proven that $S$ is an element of $S$ if and only if $S$ is not an element of $S$ - a contradiction of the most fundamental sort.

Source: Set Theory by Charles C. Pinter, p.5 [Formatting not withstanding].

From the above explanation, reductio ad absurdum can be applied to the statement '$S$ is a set of all sets that are not elements of themselves.'as follows: \begin{align} S \in S &\Rightarrow S \notin S\\ &\Rightarrow S\in S\\ &\therefore S\in S \Leftrightarrow S\notin S \end{align}

Since the statement leads to a contradictin, $\color{purple}{ S\in S \Leftrightarrow S\notin S}$, doesn't the statement '$S$ is a set of all sets that are not elements of themselves.' hold true?

[Edit Ahh. I'm starting to understand it a bit more]

The quote "Let $S$ denote the set of all sets that are not elements of themselves. Is $S$ an element of itself?" can be rephrased as 'If S denote the set of all sets that are not elements of themselves, then $S$ an element of itself'.

'S is a set of all sets that are not elements of themselves" is both the hypothesis and the statement. Kevin Houston, page 64:

"Statement A is called the hyothesis or assumption" - Susanna S. Epp, page 390: "Euclidean Algorithm 1. Let A and B be integers with $A≥B≥0$."...recall that we assumed $A≥B≥0$ • Other than creating broken CSS, eyestrain and the feeling that I'm looking at a drawing of a child, what point is there to the colors? – Asaf Karagila May 30 '16 at 8:37
• @AsafKaragila The colors are there for increasing the readability of my question. :) By the way, what does CSS mean? – buzzee May 30 '16 at 8:41
• Cascaded Style Sheets. The design of the website. Currently broken, courtesy of the colored text overflowing from the question box. – Asaf Karagila May 30 '16 at 8:42
• @buzzee What is the point of pasting page 43 of your textbook? – 5xum May 30 '16 at 8:46
• @5xum I compared it with answers. – buzzee May 30 '16 at 8:53

## 2 Answers

NO: the statement

"there exists the set $S$ of all sets that are not elements of themselves"

has been proved to be false.

The "logical analysis" of Russell's Paradox starts from the seemingly harmless principle [called: unrestricted Comprehension Axiom] that:

for any formula $φ(x)$ containing $x$ as a free variable, there will exist the set $\{ x \mid φ(x) \}$.

Russell manufactured his paradox considering as $\varphi$ the predicate : $\lnot (x \in x)$.

Thus, according to the above principle, we are licensed to make the assumption:

$\exists S \ \forall x \ (x \in S \leftrightarrow \lnot (x \in x))$ --- (*)

Applying inference rules, and instantiating the universal quantifier with $S$ we get:

$S \in S \leftrightarrow \lnot (S \in S)$.

This is the contradiction.

Thus, applying reductio to the initial assumption (*), we conclude with:

$\lnot \exists S \ \forall x \ (x \in S \leftrightarrow \lnot (x \in x))$.

And so we have to conclude that the unrestricted Comprehension Axiom is not a "sound" principle: we have to leave it, or to "restrict" in a suitable way its application.

See Axiom schema of specification for a way to "fix" it.

You're misreading the structure of the argument. The structure is:

• Suppose $S$ has the property $\forall x(x \in S \iff x \notin x)$.

• Then $S \in S \iff S \notin S$, a contradiction.

• Therefore, the assumption that $S$ has the property $\forall x(x \in S \iff x \notin x)$ was absurd.

• In other words, no set $S$ has the property $\forall x(x \in S \iff x \notin x).$

• Symbolically:

$$\forall S( \neg \forall x(x \in S \iff x \notin x))$$

• I have tried putting it as "It is illogical to claim that there exists a widget that doodles all those and only those widgets that do not doodle themselves." – DanielWainfleet May 30 '16 at 18:53