6
$\begingroup$

It seems to me that Russell's paradox rather is a "paradox" concerning relations.

Suppose we want to construct a graph (with finite or infinite number of nodes) and want some node to be adjacent to exactly those nodes that are not adjacent to them selves.

It's the same problem, which seems to arise from the fact that it is not possible to define relations with nodes of certain adjacent specifications.

And there are a lot of other examples of impossible constructions of relations.

Suppose we want to construct a graph and want some node $s$ to be adjacent to exactly those nodes $x$ such that:

  • all chains $x\to x_1\to x_2\to x_3\to\cdots$ are finite;
  • given a surjection $f$ for the construction, $f(x)\nrightarrow x$. $($Set $s=f(x)\dots)$

It seems to be necessary to point out that I don't mean that there is a paradox of Russell (it was just a paradoxical consequence of a construction), and that I don't know if mathematicians really mean that the construction of Russell say something about sets as such.

But I do believe that a lot of people think that Russell's paradox really is just about sets.

$\endgroup$
  • 8
    $\begingroup$ Well, relations are sets. $\endgroup$ – Timbuc Dec 31 '14 at 13:35
  • 1
    $\begingroup$ @Timbuc: yes, but just in set theory and then not just sets in general. $\endgroup$ – Lehs Dec 31 '14 at 13:37
  • 9
    $\begingroup$ Relations are not sets; they are modeled by sets. $\endgroup$ – MJD Dec 31 '14 at 13:56
  • 1
    $\begingroup$ @Timbuc There is also no reason to think, that relations ARE sets. They don't need to be sets, except in ZF(C) everything is a set. For example, a relation could be a morphism in the (or a) category of sets $f : A \times B \rightarrow 2$, where $2$ is any $2$-element set and $A\times B$ denotes ANY (categorical) product of the objects $A$ and $B$. In this case, depending on our foundations, $f$ does not even need to be set. $\endgroup$ – Stefan Perko Dec 31 '14 at 21:21
  • 1
    $\begingroup$ @Timbuc Many (not all) mathematicians do not really give much thought to foundations. If pressed on foundations, they may instinctively say "ZF (+/-Z) without too much thought. Even those who can name half of the axioms, much of the work can be done in many very different systems, of which ZFC is one of. So to say that most mathematicians work in ZFC might only be true in a nominal way. It may be more accurate to say that all the work one does can be carried out in ZFC (or in some occasions an extension, if one need Grothendieck universes for some things that require category theory). $\endgroup$ – Baby Dragon Jan 1 '15 at 4:22
28
$\begingroup$

The interesting thing about Russell's paradox is not that it involves an object that can't exist, but that that object is embedded in a theory that seemed sound until Russell pointed out the contradictory object.

Certainly one can invent all sorts of false principles about nonexistent objects. For example, let $V$ be a village in which there live two men, $A$ and $B$, where $A$ is taller than $B$ and $B$ is taller than $A$. Now build a theory of such villages.

Well, nobody cares, because it is obvious that there are no such villages and that any theory of such villages is a waste of time. Or similarly, a graph $G$ with a node $n$ that is adjacent to all the nodes that are not adjacent to themselves. But there is obviously no such graph, so why would you do that?

The historical crisis caused by Russell's paradox was that mathematicians as a group were taken in by the seductive general comprehension principle that

for each property $\Phi$ there is a collection $\{x\mid \Phi(x)\}$ of everything with property $\Phi$

and then later it transpired (as shown by Russell) that this principle is false.

If everyone was fooled by the general comprehension principle then how can you be sure that they are not still fooled by some other plausible-seeming idea? 20th-century mathematicians have done a lot of work on algebraic geometry. Bézout's theorem says that, given the right context, two algebraic curves of degree $m$ and $n$ have exactly $mn$ intersections. How can you be sure that some new Russell won't find an argument tomorrow that actually, no such curves exist and the whole theoretical edifice of algebraic geometry is complete nonsense? But that's just what happened in set theory.

It's easy to construct objects with contradictory properties. People appear on this web site every week to ask about the largest real number less than 5. (1 2) These questions do not precipitate theoretical crises. The crisis of Russell's paradox was not the paradoxical object, but the failure of the theory in which that object was embedded.

$\endgroup$
  • $\begingroup$ Some conditions are more obvious paradoxical than others and perhaps the historical crisis (if there was one?) told mathematicians that constructions must be proved consistent before used. $\endgroup$ – Lehs Dec 31 '14 at 14:46
  • 2
    $\begingroup$ it seemed so for a while. Unfortunately, Gödel's second incompleteness theorem shows that that is impossible. $\endgroup$ – MJD Dec 31 '14 at 14:53
  • $\begingroup$ some constructions can be proved consistent relative some basic axioms. $\endgroup$ – Lehs Dec 31 '14 at 15:11
  • 2
    $\begingroup$ @Lehs The issue is not whether or not the constructions are consistent relative to the axioms, it is whether the axioms are consistent relative to themselves. In general, a contradiction in a construction simply shows that the thing constructed does not exist. In Russell's case, the existing set theory said that the set he constructed did exist. This contradiction is the paradox, not the set construction itself. $\endgroup$ – KSmarts Dec 31 '14 at 15:47
  • 2
    $\begingroup$ @MJD Gödel's second incompleteness theorem tells us that we hope it is impossible. It is obviously possible in the case of inconsistent axioms to vacuously prove themselves to be consistent. $\endgroup$ – DanielV Dec 31 '14 at 18:59
6
$\begingroup$

Your graph theory version is not paradoxical, because there was never any reason in the first place to believe that such a graph exists.

By contrast, Frege's set theory did imply that a set with the Russell property exists, hence the paradox.

$\endgroup$
  • $\begingroup$ But $\in$ is a relation and a "graph". And I only use graphs to be concrete. Relations in first order logic works as well. $\endgroup$ – Lehs Dec 31 '14 at 13:49
  • $\begingroup$ @Lehs: I don't understand why you think this is relevant. Yes, in Frege's theory, we can think of the collection of all sets, together with the $\epsilon$ relation, as a graph. Frege's theory makes certain predictions about that particular graph. It does not make any predictions about graphs in general. $\endgroup$ – WillO Dec 31 '14 at 13:54
  • 6
    $\begingroup$ @Lehs: Yes, you can use this construction to show that no graph has a particular property. But you don't get to call that construction "paradoxical" unless there was some reason to think that there was a graph with that property in the first place. Likewise, I know how to prove that there is no even prime number greater than two, but I don't get to call that a paradox, because nobody ever had any reason to expect the existence of such a number in the first place. $\endgroup$ – WillO Dec 31 '14 at 14:05
  • 6
    $\begingroup$ @Lehs: Frege would have been very relieved to hear that. Instead, he abandoned several years of work. But maybe he just hadn't thought about this as deeply as you have. $\endgroup$ – WillO Dec 31 '14 at 14:08
  • 8
    $\begingroup$ @Lehs: If you take this point of view, then nothing can be said to be mathematics, because we cannot accomplish the prerequisite of proving what we study doesn't lead to paradox. $\endgroup$ – Hurkyl Dec 31 '14 at 14:32
5
$\begingroup$

If it is of interest to you, you can translate Russell's paradox into lambda calculus logic to avoid sets completely:

$$P = \{Q ~\mid~ Q \not \in Q\}$$

becomes

$$\text{define } P \text{ as } \bigg(\lambda ~ Q .\lnot Q(Q)\bigg)$$

or more easily read as $P(Q) = \lnot Q(Q)$.

To follow the logic, set $P$ as the argument to get $P(P) = \lnot P(P)$, which isn't actually paradoxical in lambda calculus. It is only a problem when you add the (appropriated encoded...) assumption that $\forall x~~\bigg( P(x) \in \{\text{true}, \text{false}\}\bigg)$. Translating this assumption back into set language, it would be

$$\forall A,B ~~\bigg((A \in B) \in \{\text{true}, \text{false}\}\bigg)$$

The question of "what causes Russell's paradox" or "what is it really about" is an opinion question. For my opinion, it comes from not carefully distinguishing when the declaration of an axiom is actually grammatically a definition and when it isn't. But I agree with your sentiment that the paradox doesn't have to be stated in terms of sets.

$\endgroup$
  • $\begingroup$ How is ¬ defined in (λQ.¬Q(Q))? Are you using an embedding of boolean logic in the lambda calculus? $\endgroup$ – Thom Smith Dec 31 '14 at 17:51
  • $\begingroup$ @ThomSmith Yes, IIRC Church's lambda calculus defined true as $\lambda AB.A$ and false as $\lambda AB.B$ (before currying), so writing out negation is tricky but there was a standard definition. $\endgroup$ – DanielV Dec 31 '14 at 18:53
  • $\begingroup$ @ThomSmith (Had some sleep) I think $\lnot$ in lambda calculus is then defined as $\lambda FAB.\lambda AB.FBA$ (before currying), in other words if you give it the function $\lambda AB.A$ it will return to you the function $\lambda AB.B$ and the reverse as well. I never cared too much to use lambda calculus at an application layer, but I do find it interested from an "assembly language of logic" point of view, it's very neatly packaged. $\endgroup$ – DanielV Jan 1 '15 at 2:34
  • $\begingroup$ Hey I just came upon this old thread. =) I think you may be interested in this post, which explores a natural way of resolving Russell's paradox along the line of not assuming that every statement is either true or false. $\endgroup$ – user21820 Aug 2 '18 at 16:02
-2
$\begingroup$

Technically, Russell's paradox points to a rather interesting proof-technique to show that a certain mathematical object does not exists:

To prove that it doesn't exist a surjection $p:A\to\mathcal P(A)$, define the set $B=\{x\in A|x\notin p(x)\}$. Obviously, $B\notin\mathrm{Im}\; p$.

Historically, Russell's paradox shows that the traditional trust in the correspondence between classes and predicates was faulty. Even in the sixties I was taught in philosophy lessons that there was a correspondence between a property and the class of subjects having that property, a fallacy that of course had influence on early set theory.

$\endgroup$

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.