Isn't Russel's "Paradox" really a proof that the "set of all sets that are not members of themselves" does not exist?

No, it's much deeper than that.

First, define S as the set of all sets that are members of themselves. That is, self-referential. The S set is well defined, and easy to see that it exists.

Next is the hard part. Define R as the set of all sets not in S. Clearly this is where the trouble comes in. Whether R contains itself is undecidable, which leads back to what it means to be in a set.

Can something be both in the set and not in the set? Can someone be half-pregnant?

So to follow your logic, we can't even define a set properly, at least not completely. We can only say what is in certain kinds of sets, and not what isn't in them. This is starting to sound like the halting problem!? We know if a program halts after the fact, but we don't necessarily know if it doesn't, because maybe we just haven't waited long enough.

All of these are related. And they won't go away, even if someone comes up with a new idea of "set" or "computable" or "decidable". Some other concept in the new system would become undecidable, and we'll have just traded in one problem for another.

-QM
--
Quantum Mechanics: The dreams stuff is made of

First, define S as the set of all sets that are members of themselves. That is, self-referential. The S set is well defined, and easy to see that it exists.

I disagree: your definition of S is insufficient for me to deduce whether S contains S. It contains exactly the same hole as the definition of R, except that in the case of S it is consistent either way.

More precisely, I read your definition as:

  S := A \in A => A \in S
[download]

.. and evaluating that for A = S gives the uninformative:

  S \in S => S \in S
[download]

.. and analogously:

  R \notin R => R \in R
[download]

I'd say therefore that these sets are not well-defined unless they additionally specify self-membership:

  S := (A = S | A \in A) => A \in S
  or S := (A != S & A \in A) => A \in S
  R := (A = R | A \notin A) => A \in R
  or R := (A != R & A \notin A) => A \in R
[download]

.. and then everything is simultaneously hunky and dory.

Hugo

So to follow your logic, we can't even define a set properly, at least not completely.

By my logic we can't define that particuar set, because it doesn't exist.

Next is the hard part. Define R as the set of all sets not in S.

Is there any reason to assume that R will exist simply because S exists? Is there an axiom in set theory to the effect that "Every set must have a complement"? I'm not being glib or rhetorical in those two questions, and those questions are really the meat of the issue. There has to be a reason why R should exist for Russel's Paradox to truly be a paradox. I didn't notice the reason in the linked articles, and I'm curious.

Can something be both in the set and not in the set?

No it can't, and that's the proof that R doesn't exist.

So to follow your logic, we can't even define a set properly, at least not completely. We can only say what is in certain kinds of sets, and not what isn't in them.

This comes back to assuming that R should exist. There isn’t a problem with being unable to define non-existent sets. Heck, I don't define non-existent sets in my sleep! If there is a reason that R should exist, then we’ve got a problem.

I think you are muddling the concepts of infinity, as in the digits of pi; and undecidability

Perhaps, but in practice, aren't there cases where the difference doesn't actually matter? If we don't know whether a lazy function will halt for all possible inputs, wouldn't we just give it the input we've got and let it run until either it does halt or the user takes some action to cause us to stop it (either by way of the program's own interface or an OS process management facility)?

Don't get me wrong -- I think lazy evaluation is a great idea. But it's not going to solve any unsolveable problems, just golf down some of the solveable ones.

Right, I agree with that entirely. This is what I meant when I said that lazy eval doesn't create GLooP (a theoretical more-than-Turing language), but nonetheless can be terribly convenient.

(Hmmm... OTOH, if we wanted to let something run in the background, we'd probably use fork rather than lazy. Still, I think lazy will be useful.)

OK, how about the difference between a program computing the digits of pi, and the program trying to decide Russell's Paradox? The first one keeps churning out digits (aka, "progress"). The second one never achieves any progress (or in some formulations, positive and negative progress in infinite alternation).

You can compute pi to any arbitrary precision. You can't get anywhere with the other.

-QM
--
Quantum Mechanics: The dreams stuff is made of