Why does this solution to Russell's Paradox not have a contradiction?

Question

Discrete Mathematics with Applications, 3rd ed., by Susanna Epp mentions that Russell's Paradox can be avoided by ensuring that any condition elements of a set are to satisfy must contain the restriction that they are elements of a known set. As for Russell's Paradox, the textbook gives this reason as to why this new definition/restriction of set theory no longer leads to a contradiction:

Let $U$ be a universal set and suppose that all sets under discussion are subsets of $U$. Let $S=\{A|A \subseteq U \text{ and } A \notin A \}$. ... [This leads to the conclusion] that $S \not\subseteq U$.

But as far as I can understand, the argument above still leads to a contradiction, namely, that $S \subseteq U$ and $S \not\subseteq U$. Here is my understanding that I would like to have checked:

So the conclusion is that $S$ does not exist in our universe. But $S$ is implicitly in $U$ by virtue of being in our discussion (as every set in our discussion is by definition in $U$) [why would this sentence be erroneous, if it is?]. Thus a contradiction is derived. But what led to the contradiction? The set $S$ is a perfectly valid set under the new axioms of set theory (because the condition of $S$ is valid under the new definition), so it must be that the new axioms of set theory are wrong.

The above argument seems very similar to the argument of Russell's Paradox, but I can't pinpoint what is wrong with it.

Answer 1

Here is what the author means by a "universal set" (see p. 314):

Most mathematical discussions are carried on within some context. For example, in a certain situation all sets being considered might be sets of real numbers. In such a situation, the set of real numbers would be called a universal set or a universe of discourse for the discussion.

Everything what is done in sequel only concerns subsets of such a universal set $U$ (union, intersection, ...).

This does no mean that one universal set suffices for all purposes. For example, if $U = \mathbb R$, then it is clear that there are also releavant sets which are no subsets of $U$ (for example $\mathbb R^n$ with $n > 1$).

When the author introduces the power set $\mathscr P(A)$ of a set $A$ and the Cartesian product $A_1 \times \ldots \times A_n$ of sets $A_1,\ldots, A_n$, it becomes very clear that certain natural constructions with sets produce new sets not belonging to a given universe $U$. For example, $\mathscr P(U)$ is never a subset of $U$.

What the author writes about Russell’s paradox is, in my opinion, misleading.

Let $U$ be a universal set and suppose that all sets under discussion are subsets of $U$.

It is not at all clear what this "suppose" means. Anyway, one can define the set $$S = \{A | A ⊆ U \text{ and } A \notin A\}$$ This is a well-defined subset of $\mathscr P(U)$. Since $\mathscr P(U)$ is no subset of $U$, we cannot expect that a given subset of $\mathscr P(U)$ is a subset of $U$ - but it is not impossible. If it were true that the above $S$ is a subset of $U$, we would again end with the contradiction that $S \in S$ implies $S \notin S$ and $S \notin S$ implies $S \in S$ (Russell’s paradox). Therefore we conclude that $S$ is no subset of $U$, and there is no contradiction.

Thus "suppose that all sets under discussion are subsets of $U$" is certainly intended to say the following:

As long as we stay in $U$, it is impossible to reproduce Russell’s paradox. This paradox is a consequence of a "naive", but illegitimate definition of the "set" of all sets $A$ with $A \notin A$.

Answer 2

I had a look at the book, and I wouldn't understand it either from what is written there.

(I'm using $\{\ldots|\ldots\}$ as a placeholder for anything that is defined using braces and a vertical bar.)

If it is an axiom that every set is a subset of $U$, then the discussion in the book and also your argument in the question shows that $\{\ldots|\ldots\}$ sometimes does not define a set. So, if we want to define a set by $\{\ldots|\ldots\}$, we have to prove $\{\ldots|\ldots\}\subset U$. But that's meaningless if $\{\ldots|\ldots\}$ is not a set. This is often remedied by introducing another category of "things", namely classes, which are not sets, but for which things like $\subset$ still make sense. But I'm not sure if that's all that's needed to rescue the exposition in the book.

The most common set theory (ZFC) does not have a universal set (or classes), and I don't know anything about the set theories that do. Since this is only a very small section in a (possibly quite good) book that is not about set theory, I'd suggest you look to other sources for a basic introduction to set theory (or decide that you don't need it).

Answer 3

What Susanna Epp is showing in the textbook is very simple.
Here is the Summary:

"When Assumption/Premises $P$ gives use a Contradiction like $S \iff \lnot S$ , then we can see that Assumption/Premises $P$ is not true"
Here Assumption/Premises $P$ is "$A \subseteq U$" always & throughout.
When-ever we get a Contradiction , we can claim that Assumption/Premises $P$ is not true via DeMorgans laws.

---

Here is Page 420 fifth edition :

---

When we think about what is the Core Issue with Russells Paradox , we see that we are going to get something like this :
$$(A \subseteq S) \land (A \not \subseteq S) \tag{1}$$
$$(A \subseteq S) \iff (A \not \subseteq S) \tag{2}$$

That is a "Very Big Issue" : we can not have something true & false at the same time (1) where both Cases imply each other (2). It is a Contradiction at the heart of Mathematical Logic & Set Theory.

Now , when say that all sets & elements have to be in Universal Set $U$ & then we use various other Conditions & Predicates to make new sets , then we can see that Russells Paradox will give something like this :
$$[(A \subseteq U) \land (A \subseteq S)] \land [(A \subseteq U) \land (A \not \subseteq S)] \tag{3}$$
$$[(A \subseteq U) \land (A \subseteq S)] \iff [(A \subseteq U) \land (A \not \subseteq S)] \tag{4}$$
That is a concern now : It is not a Contradiction at all. Statement (3) is necessarily false.

The Conclusion we then get is : Statement (4) is true because $(A \not \subseteq U)$ via DeMorgans laws
No more Contradictions !

---

Susanna Epp used these words in the text Book ( fifth edition ) itself , on which I based my Answer & thinking :
The way used in this text requires that , [...] , whenever a set is defined using a predicate as a defining property , the stipulation must also be made that the set is a subset of a known set.
[...]
In other words, the only conclusion we can draw is that the seeming "definition" of $S$ is faulty — in other words , $S$ is not a set in $U$.

---

OP : "... the argument above still leads to a contradiction, namely, that $S \subset U$ and $S \not \subset U$ . Here is ..."

There is no Contradiction there. What we would have got with Russells Paradox or your line of thinking will be written like this :
$(S \subseteq U) \land S \subseteq U \text{ and } (S \subseteq U) \land S \not \subseteq U \tag{5}$
The Conclusion we can then get via DeMorgans laws is :
$\lnot (S \subseteq U) \tag{6}$
There is no Contradiction now.

Answer 4

Let us avoid the philosophical discussion what a universal set is. So let us assume that we are given a certain set $U$.

We can form the power set $\mathfrak P(U)$ whose elements are the subsets of $U$. Then we define

$$S = \{ A \in \mathfrak P(U) \mid A \notin A\}.$$

As lonza leggiera comments, in the Zermelo-Fraenkel axiomatics one can prove that $S = \mathfrak P(U)$, but that is irrelevant here.

Russell's Paradox arose by forming the "set"

$$R = \{ A \mid A \text{ is a set such that } A \notin A\}.$$ The paradox lies in the assumption that this definition actually produces a set $R$. Then we must have both $R \in R$ and $R \notin R$ which is absurd.

In contrast we properly defined a set $S$. A "Russel contradiction" would in fact arise if $S \in \mathfrak P(U)$. Thus we got a proof $S \notin \mathfrak P(U)$.

Actually we defined $S$ as an element of $\mathfrak P(\mathfrak P(U))$, so it is perhaps not a big surprise to see that $S \notin \mathfrak P(U)$.

Nevertheless, observe that $\mathfrak P(U) \cap \mathfrak P(\mathfrak P(U)) \ne \emptyset$. The intersection always contains $\emptyset$ nd sometimes also non-empty sets. For example, for $U = \emptyset$ we get $\mathfrak P(U) =\{\emptyset\}$ and $\mathfrak P(\mathfrak P(U)) =\{\emptyset,\{\emptyset\} \}$ in which case we even have $\mathfrak P(U) \subset \mathfrak P(\mathfrak P(U))$. But it is impossible that $\mathfrak P(U) = \mathfrak P(\mathfrak P(U))$; there is not even a surjection $\phi : \mathfrak P(U) \to \mathfrak P(\mathfrak P(U))$.$^1$

Thus there are always sets in $\mathfrak P(\mathfrak P(U))$ which do not belong to $\mathfrak P(U)$, and we proved that one of these sets is our abve $S$.

Footnote:

$^1$ For no set $X$ there exists a surjection $\phi :X \to \mathfrak P(X)$. In fact, let $\phi : X \to \mathfrak P(X)$ be any function. Define $S(\phi) = \{ x \in X \mid x \notin \phi(x) \} \in \mathfrak P(X)$. Assume that $S(\phi) = \phi(y)$ for some $y \in X$. Then either $y \in S(\phi)$ which means $y \notin \phi(y) = S(\phi)$, a contradiction. Or $y \notin S(\phi) = \phi(y)$ which means $y \in S(\phi)$, again a contradiction. Thus $S(\phi) \notin \phi(X)$ which shows that $\phi$ is not surjective.

You see that the above argument generalizes our proof that $S \notin \mathfrak P(U)$.

Answer 5

The contradiction in Russell's Paradox is derived from Frege's early attempt to formalize set theory. That contradiction can be stated as follows:

$~~~~~~[\exists r: \forall x: [x \in r \iff x\notin x]]~ \land ~\neg[\exists r: \forall x: [x \in r \iff x\notin x]] $

It has nothing to do with a universal set.

The left conjunct could be derived from Frege's axiom schema of unrestricted comprehension that, for any unary predicate $P$, there exists a set $\{ x : P(x)\}$. In this case, we have $P(x) \equiv x\notin x$.

The ZFC axioms do not allow this. Instead they have a restricted form of comprehension that, for any set $S$ and unary predicate $P$, there exists a subset $\{ x: x\in S \land P(x)\}$ thus avoiding the left conjunct.

The right conjunct can be derived from classical predicate logic that is used in both systems.

Answer 6

In addition to the given set-theoretical answers to the question, I shall touch on several complementary, but for a comment, too spacious aspects, for this is a worthwhile question that unfolds quite instructive aspects to consider. These may appear pedantic; nevertheless, can be extremely critical in mathematical logic.

Since, as demonstrated by Russell's argument, an unrestricted comprehension leads to paradox, some restriction that would weaken the naive comprehension is required. The restrictive idea that Epp employs is formulated as Axiom Schema of Separation (Aussonderungsschema) in the Zermelo-Fraenkel system. Thomas Jech's version in his Set Theory (2nd edition, p. 1) is as follows:

1.3. Axiom Schema of Separation. If $\phi$ is a property (with parameter $p$), then for any $X$ and $p$ there exists a set $Y =\{u\in X :\phi(u, p)\}$ that contains all those $u\in X$ that have property $\phi$.

Thus, we do not build a set anew, but separate a subset of an already existing set $X$ by a property $\phi$; hence the name of the axiom schema. To phrase in a way closer to its original German name, we pick out (i.e., Aussonderung) the elements of $X$ that satisfy the given property $\phi$ into a set $Y$. Certainly, $Y$ can be $\emptyset$. Notice that the set $X$ is there ante factum, legitimately formed.

How this restriction avoids Russell’s paradox is explained in other answers. I shall dwell on the mathematical discourse in Epp's treatment. It is worth a remark that the Axiom Schema of Separation immediately entails non-existence of a universal set, hence, $\{x\vert x = x\}$ does not exist, but this should not be confused with Epp's use of the universal set $U$; she refers to a restricted set, viz., a particular domain of discourse.

We want to pursue set theory primarily on an extensional basis as possible in contrast to intensionally defined objects. Thus, the elements of a set $S$ comprise the entire necessary and sufficient condition for the definition of the set $S$. However, the Axiom Schema of Separation seems to let in some intensional content, citing a definite property (a monadic predicate) $\phi$. This concern is removed when we notice that, from the purely set-theoretical point of view, the formal language associated with set theory contains $\in$ as the only non-logical predicate (if $=$ is admitted as a logical predicate). Therefore, the properties that can be expressed in the formal language are only the ones defined through $\in$ alongside $=$.

Epp argues at a derivative level over $\subseteq$ which is a derived predicate. That approach needs to call in also the Axiom of Power Set (ibid.):

1.5. Axiom of Power Set. For any $X$ there exists a set $Y = P(X)$, the set of all subsets of $X$.

More significantly, she gives a basically intensional definition stating that “all sets under discussion are subsets of $U$,” bypassing the priority of extensionality: $S\subseteq U$ is not a separation, but a stipulation. Accordingly, she concludes with the statement that $S$ is ill-defined.

Just by itself, the definition $S=\{A\vert A\subseteq U\text{ and }A\in A\}$ is legitimate. The point is that what this definition proves are merely that $S\not\in S$ and $S\not\subseteq U$, which do not lead to a paradox.