23
$\begingroup$

My background is in computer science, and I'm keeping the Java implementation in my mind as a model. Included in the Java language is the notion of sets.

Now I understand that this is different from the model Russell and Whitehead had in their minds when they were writing Principia Mathematica, but I don't completely understand why it is different.

To me, when you say "a set that contains a set," you have three ways you can "implement" this. You can say that it is "physically inside" (and draw it inside). You can say "it is just a logical concept" (which is what I think Russell was getting at). And you can say "it is a physical concept, but not physically inside — we link them together with pointers" (like in computer programming).

Taking this further into Russell's paradox: "The set of all sets that don't contain themselves," when talking about computer programming, is a relatively easy concept to implement (within the domain of the sets in a computer program).

I'm guessing there is a philosophical difference between sets in Java and Russell's sets. (I imagine there must be a name for Russell's sets, but I don't know what they are called.)

I can see that mathematics has other theories of sets like Zermelo–Fraenkel set theory and Quine's New Foundations.

My question is: Why can't Russell's Paradox be solved with references to sets instead of containment?

$\endgroup$
  • 2
    $\begingroup$ Good question. It has to do with the axiom that allows you to construct subsets, but it's not obvious how this paradox presents itself from the coding perspective. $\endgroup$ – Dustan Levenstein Feb 19 '17 at 3:34
  • 32
    $\begingroup$ I think you are mistaken in believing "The set of all sets that do not contain themselves" is "a relatively easy concept to implement". To begin with, try to implement simply "the set of all sets". $\endgroup$ – hardmath Feb 19 '17 at 3:35
  • 8
    $\begingroup$ Firstly, the Russell paradox is talking about membership ($\in$) not containment ($\subseteq$); every set contains itself (as a subset), so in that sense there is no point in talking about the set of sets that do not contain themselves (which would be the empty set). Secondly, membership in set theory is just a relation between two values (i.e., two sets) that may or may not hold for a given pair; there is no need to implement anything. The question is just whether a certain list of axioms about this relation can simultaneously be satisfied, and Russell's paradox proves that they cannot. $\endgroup$ – Marc van Leeuwen Feb 19 '17 at 5:12
  • 2
    $\begingroup$ @MarcvanLeeuwen Unfortunately, I'm not sure there is a consensus among mathematicians, and I'm pretty sure there is no unanimity, as to whether a set contains its subsets and includes its elements or whether it contains its subsets and includes its elements. $\endgroup$ – bof Feb 19 '17 at 6:43
  • 12
    $\begingroup$ You say it's a relatively easy concept to implement - I'd like to see your implementation. $\endgroup$ – immibis Feb 19 '17 at 10:24
73
$\begingroup$

On the contrary, Russell's set - interpreted in your computer-programming model - is not easily implemented (let alone possible). Actual "containment" is not an issue - in principle, mathematicians would be perfectly happy with a set that contained itself.

The issue is this: consider a (Java) Set that contains in it references to exactly those Sets currently in memory which do not contain references to themselves. Call this Set<Set> R. Suppose R contains a reference to itself. Then R does not meet the requirement for being referenced by a member of R, so R cannot be referenced by anything in R, contradicting our supposition. So suppose instead that R does not contain a reference to itself. Then R meets the requirement for being referenced in R (that is, it is a Set which does not contain a reference to itself) so it must have a reference in R, contradicting our supposition.

Again, whether or not containment actually means "containment" isn't relevant. In fact, modern set theory formally treats membership abstractly - the symbol $\in$ doesn't have any canonical meaning, it's just an arbitrary relationship that obeys certain axioms. It's helpful to visualize it as actual containment or as a system of Java-like references, because those visualizations obey the axioms, but the "physical" implementation isn't relevant to any of the logic.

$\endgroup$
  • 1
    $\begingroup$ Brilliantly well said, and very enlightening. $\endgroup$ – Chandler Watson Feb 19 '17 at 6:27
  • 1
    $\begingroup$ To rephrase your last paragraph, given any collection of objects (even real-world objects) and any predicate $P(x, y)$, there is no object $R$ such that $P(x, R)$ if and only if $\neg P(x, x)$. Here the collection of objects is the collection of Java sets in memory and $P(x, y)$ is "$x$ contains a reference to $y$". $\endgroup$ – Jack M Feb 19 '17 at 12:32
  • $\begingroup$ Typical mathematics - you think something's trivially easy to understand and that you understand it, and then: 'In fact, modern set theory formally treats membership abstractly - the symbol $\in$ doesn't have any canonical meaning, it's just an arbitrary relationship that obeys certain axioms.' $\endgroup$ – OJFord Feb 19 '17 at 13:29
  • $\begingroup$ What's funny is making sets manifest provides an unexpected and completely rational resolution of the paradox. Let R = the set of all sets that contain themselves (R contains itself). We then construct Russel by taking (U - R). Whether or not Russel contains itself depends on how exactly U works; that is whether or not it can get a reference to a half-constructed Russel or not. $\endgroup$ – Joshua Feb 20 '17 at 17:20
  • $\begingroup$ @Joshua Interesting idea, but the $U - R$ you specify can't be Russell's set. If it includes $U - R$, then it can't be Russell's set because it contains at least one set that contains itself. If it does not include $U - R$, then it can't be Russell's set because it does not include all sets that do not contain themselves. Russell's paradox is about one particular point in time; it doesn't matter whether the set contains what Russell's set "used to" be, only whether it contains it now. $\endgroup$ – Reese Feb 20 '17 at 17:57
24
$\begingroup$

Let me present a different perspective. Instead of modeling a set using a container object consisting of pointers/references, which can be limiting, suppose we choose to model sets as a function which

  • will accept any set, and
  • always returns a boolean.

How this is to be implemented in any specific language, such as Java, isn't really relevant. There are structural issues to overcome; Java presents the difficulty that a function is not an object, for example, and my code does not address this issue. This is, however, not a serious hurdle for the concept.

The important thing is we can certainly implement the universal set:

bool Universe(Object X) { return true; }

and we can implement what ostensibly should be the set of all things which do not contain themselves:

bool Russell(Object X) { return !X(X); }

So what's wrong with this set Russell? Well, if you plug Russell into itself, then it will call itself, creating an infinite recursive loop. Therefore, Russell fails to return anything when plugged into itself as a parameter, so it cannot be a set.

$\endgroup$
  • 3
    $\begingroup$ Awesome. Thankyou for speaking my language! $\endgroup$ – hawkeye Feb 19 '17 at 4:29
  • 1
    $\begingroup$ Glad to help! There are, of course, issues with any attempt to model mathematical sets in a computer science setting, and this is certainly no exception. In fact, the only ZFC set that can be faithfully implemented by this model is the empty set - all other sets require discerning between sets based on what they contain, which cannot be done in a finite amount of time. But I do nevertheless suspect that this idea does a better job of capturing the essence of the mathematical notion than any container based model can do. $\endgroup$ – Dustan Levenstein Feb 19 '17 at 4:36
  • 6
    $\begingroup$ I'm not sure that this really gets to the heart of Russell's paradox. Consider the set of all sets that do contain themselves, bool notRussell(Object X) { return X(X); }. There's nothing paradoxical about this set, but using the analogy here, trying to run it will also result in an infinite loop. $\endgroup$ – Hong Ooi Feb 19 '17 at 14:21
  • 1
    $\begingroup$ One way or another, it means that the analogy isn't that enlightening after all. $\endgroup$ – Hong Ooi Feb 19 '17 at 14:31
  • 4
    $\begingroup$ @HongOoi I think there is something interesting about "the set of all sets that do contain themselves" - I can claim that set contains itself (without contradiction), but I can also claim that set doesn't contain itself (without contradiction). I think this definition of notRussell is incomplete, and so the question "does notRusself contain itself?" actually is under-specified. So it's reasonable that notRussell(notRussell) fails to return anything. $\endgroup$ – Ord Feb 20 '17 at 3:23
7
$\begingroup$

While the answers by Reese and Dustan have explained the set-theoretic paradox in terms of Java, they do not answer the part of the question about how exactly Set data structures (not just in Java) avoid the paradox, nor do they show how the paradox can be avoided in a manner consistent with programming.

Firstly, the type system of programming languages are different from the usual set theories and type theories in foundations of mathematics. I would even go so far as to say that a programming language ought to have a universal type, and indeed Java comes close (the only exceptions I am aware of are the native data types, which are there for performance reasons). But you see, most programming languages do not have any 'specification axiom', unlike set/type theories. In other words, you cannot create a data type or class that includes as members all objects that satisfy a particular property. So you just cannot construct a Russell-like data type in most programming languages.

However, you could say, why not use a program to specify a type? Namely, a type is simply a program $P$ (a procedure with no internal state in most programming languages) and define its members as all inputs on which $P$ halts and outputs $true$. In a modern programming language such as Java, this corresponds to saying that a type is a (partial) function P with signature bool P(Object x). This notion is extremely intuitive (after all, how else do we classify things?) and also fits perfectly with the basic intuitive notions including the universal type (which is simply bool U(Object x) { return true; }) and existence of universal complements (the complement of P is just bool notP(Object x) { return !P(x); }. In a more abstract framework this could be denoted by $U = ( obj\ x \mapsto true )$ and $P' = ( obj\ x \mapsto \neg P(x) )$ respectively.

Moreover, under this programs-as-types paradigm we can indeed construct the Russell type. If the abstract framework (programming language) allows run-time type coercion (like Javascript) then it is just $R = ( obj\ x \mapsto \neg x(x) )$. If not then we need some kind of reflection (like in Java) to define $R = ( obj\ x \mapsto type(x) \ ? \ \neg x(x) : false )$. Either way, we can then prove that $R(R) = \neg R(R)$ in the sense that both expressions have the same output behaviour. In this case, both do not halt, so the statement is true and does not cause contradiction!

So you can see that the idea that a set must be an indicator function on the entire universe is the key feature of set theories that face Russell's paradox, as the paradox vanishes once you permit a truth-value gap and do not permit the system to form types based on what falls into that gap. See this post for one possible way of handling such constructions. In fact, Kripke described a similar notion of groundedness and also showed that one can circumvent Tarski's undefinability theorem in a certain sense using Kleene's 3-valued logic in his theory of truth.

Finally, I would note that all this has little to do with whether objects are handled by value or by reference. The major issue is whether you can capture meta-theoretic properties in the system itself. In the case of set theory, it is the notion that you can construct a set that precisely divides the universe into two parts with no gap, depending on some property that only makes sense from the 'outside'. $\{ x : \neg x \in x \}$ depends on evaluating "$\neg x \in x$" for each object $x$, which can be answered for any given model of set theory, but the answer is in the meta-theory and is not always captured by the theory itself. Similarly Tarski's undefinability theorem shows that truth (a meta-property) cannot always be captured by a formal system. The model in Kripke's theory of truth does not answer affirmatively about the truth of every sentence; some of these questions fall into the truth-value gap.

$\endgroup$
  • $\begingroup$ Also, one can reasonably extend this notion of types-as-programs via oracles such as described in this post. Adding all finite Turing jumps and full induction gives a system called ACA that can do a vast amount of ordinary mathematics even though it is still far weaker than ZF. $\endgroup$ – user21820 Feb 19 '17 at 15:21
  • 1
    $\begingroup$ +0.5 for mention of Kripke, and +0.5 for focusing on the issue of data types. $\endgroup$ – hardmath Feb 19 '17 at 17:47

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.