You are currently browsing the tag archive for the ‘russell’s paradox’ tag.

The axiom of extension (discussed in Section 1) is unique in the sense that it postulates the existence of a relation between belonging and equality. All the other axioms of set theory, on the other hand, are designed to create new sets out of old ones!

The axiom of specification, loosely speaking, states that given some arbitrary (but well-defined) set $U$ (our universe), if we can make some “intelligent” assertion about the elements of $U$, then we specify or characterize a subset of $U$. An intelligent assertion about the elements of $U$ could, for example, specify a property that is shared by some elements of $U$ and not shared by the other elements. In the end, we will take up an example about an assertion that is tied to the famous Russell’s paradox.

For now, let us discuss a simple example. Suppose $A$ is the set of all (living) women. If we use $x$ to denote an arbitrary element of $A$, then the sentence$x$ is married” is true for some of the elements of $A$ and false for others. Thus, we could generate a subset of $A$ using such a sentence. So, the subset of all the women who are married is denoted by $\{ x \in A: x \mbox{ is married}\}$. To take another example, if $N$ is the set of natural numbers, then $\{x \in N: 1 < x \leq 5 \} = \{ 2, 3, 4, 5 \}$. Now, note that the subset $\{ 2 \}$ of $N$ is not the same as the number $2.$ Loosely speaking, a box containing a hat is not the same thing as the hat itself.

Now, we only need to define what a sentence is before we can precisely formulate our axiom of specification. The following rules would be a formal way to (recursively) define a sentence:

$x \in A$” is a sentence.”

$A = B$” is a sentence.

If $X$ is a sentence, then $(\mbox{not}(X))$ is a sentence.

If $X, Y$ are sentences, then $(X \mbox{ and } Y)$ is a sentence.

If $X, Y$ are sentences, then $(X \mbox{ or } Y)$ is a sentence.

If $X, Y$ are sentences, then $(\mbox{if } X \mbox{ then } Y)$ is a sentence.

If $X, Y$ are sentences, then $(X \mbox{ if and only if } Y)$ is a sentence.

If $X$ is a sentence, then $(\mbox {for some }y (X) )$ is a sentence.

If $X$ is a sentence, then $(\mbox {for all }y (X))$ is a sentence.

Note that the two types of sentences, “$x \in A$” and “$A = B$“, stated in the first two rules, are what we would call atomic sentences, while the rest of the other rules specify (valid) ways of generating (infinitely) many sentences from those two atomic sentences using the usual logical operators. Also, note that some of the rules above are rather redundant because it is possible to convert certain sentences having a set of logical operators to another sentence having a different set of logical operators. For example, “$X \mbox{ or } Y$” can be written as “$\mbox{not ( not(X) and not(Y))}$“, and so on. Anyway, we are digressing too far from our objective.

Having defined what a sentence is, we can now formulate the major principle of set theory, often referred to by its German name Aussonderungsaxiom.

Axiom of specification: To every set $A$ and to every condition $S(x)$, there corresponds a set $B$ whose elements are exactly those elements $x$ of $A$ for which $S(x)$ holds.

A “condition” here just means a sentence. The letter $x$ is free in the sentence $S(x)$, meaning $x$ occurs in $S(x)$ at least once without occurring in the phrases “for some $x$” or “for all $x$“. Now, the axiom of extension guarantees us that the axiom of specification determines the set B uniquely, and we usually write $B = \{ x \in A: S(x) \}$.

This finally brings us to the example we mentioned in the beginning of this section. Let us define $S(x) := x \not\in x$. Suppose $A$ is some arbitrary set. Let $B = \{ x \in A: x \not\in x \}$. Then for all $y$,

$(*) \,\, y \in B \mbox{ if and only if } (y \in A \mbox{ and } y \not\in y)$.

Can we have $B \in A$? The answer is no, and here’s why. Suppose, for the sake of contradiction, $B \in A$. Then, we have either $B \in B$, or $B \not\in B$. If $B \in B$, then using $(*)$, we have $B \not\in B$, a contradiction. And, if $B \not\in B$, then using $(*)$ again, the assumption $B \in A$ yields $B \in B$, a contradiction. This proves that $B \in A$ is false, and hence we conclude $B \not\in A$. Note that our set $A$ was an arbitrary one, and we just showed that there is something (viz. B) that does not belong to $A$. We have, thus, essentially proved that

there is no universe.

Here, “universe” means “universe of discourse”, a set that contains all the objects that enter into that discussion.

It was mentioned earlier that the above example has something to do with Russell’s paradox. We shall see why. In the earlier pre-axiomatic approaches to set theory, the existence of a universe was taken for granted. Now, in the above example, we just showed that $B \not\in A$ implies the non-existence of a universe. So, if we assume that a universe exists, then it implies that $B \in A$, but we have already shown that this leads to a contradiction! And this was exactly the content of Russell’s paradox. In Halmos’ own words:

The moral is that it is impossible , especially in mathematics, to get something for nothing. To specify a set, it is not enough to pronounce some magic words (which may form a sentence such as “$x \not\in x$“); it is necessary also to have at hand a set whose elements the magic words apply.

• 355,659 hits