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

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.

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.

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.