= 27d567bc2d48d9f40e9ccc20ea370b15)
cousin_it comments on But Somebody Would Have Noticed - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (250)
As it happens, I am currently in "somebody would have noticed" territory. About a week ago I abruptly switched to believing that Russell's paradox doesn't actually prove anything, and that good old naive set theory with a "set of all sets" can be made to work without contradictions. (It does seem to require a weird notion of equality for self-referring sets instead of the usual extensionality, but not much more.) Sorry to say, my math education hasn't yet helped me snap out of crackpot mode, so if anybody here could help me I'd much appreciate it.
I am seeing substantial amounts of both sense and nonsense in this thread. I suggest that anyone who wants to talk about set theory first learn what it is.
The Wikipedia article is somewhat wordy (i.e. made of words, rather than mathematics), and Mathworld is unusably fragmented. The Stanford Encyclopedia is good, but for anyone seriously interested I would suggest a book such as Devlin's "The Joy of Sets".
I assume you're talking about Peter Aczel's antifoundation axiom (because you mentioned bisimulation); that doesn't allow a set of all sets (barring inconsistencies, and that particular system can't be inconsistent unless ordinary set theory is). The same applies to other similar systems. Russell's paradox isn't dependent on foundation in any way; as long as you have a set of all sets and the ability to take subsets specified by properties, you get Russell's paradox.
Edit: Since people seem to be asking about how this works in general, I should just point you all to Aczel's book on this and other antifoundational set theories, which you can find at http://standish.stanford.edu/pdf/00000056.pdf
Yes, that's true. What I have in mind is restricting the latter ability a bit, by the minimum amount required to get rid of paradoxes. Except if you squint at it the right way, it won't even look like a restriction :-)
I will use the words "set" and "predicate" interchangeably. A predicate is a function that returns True or False. (Of course it doesn't have to be Turing-computable or anything.) It's pretty clear that some predicates exist, e.g. the predicate that always returns False (the empty set) or the one that always returns True (the set of all sets). This seems like a tiny change of terminology, but to me it seems enough to banish Russell's paradox!
Let's see how it works. We try to define the Russell predicate R thusly:
R(X) = not(X(X))
...and fail. This definition is incomplete. The value of R isn't defined on all predicates, because we haven't specified R(R) and can't compute it from the definition. If we additionally specify R(R) to be True or False, the paradox goes away.
To make this a little more precise: I think naive set theory can be made to work by disallowing predicates, like the Russell predicate, that are "incompletely defined" in the above sense. In this new theory we will have "AFA-like" non-well-founded sets (e.g. the Quine atom Q={Q}), and so we will need to define equality through bisimilarity. And that's pretty much all.
As you can see, this is really basic stuff. There's got to be some big idiotic mistake in my thinking - some kind of contradiction in this new notion of "set" - but I haven't found it yet.
EDITED on May 13 2010: I've found a contradiction. You can safely disregard my theory.
Well, others have had this same idea. The standard example of a set theory built along those lines is Quine's "New Foundations" or "NF".
Now, Russell's paradox arises when we try to work within a set theory that allows 'unrestricted class comprehension'. That means that for any predicate P expressed in the language of set theory, there exists a set whose elements are all and only the sets with property P, which we denote {x : P(x) }
In ZF we restrict class comprehension by only assuming the existence of things of the form { x in Y : P(x)} and { f(x) : x in Y } (these correspond respectively to the Axiom of Separation and the Axiom of Replacement ).
On the other hand, in NF we grant existence to anything of the form { x : P(x) } as long as P is what's called a "stratified" predicate. To say a predicate is stratified is to say that one can assign integer-valued "levels" to the variables in such a way that for any subexpression of the form "x is in y" y's level has to be one greater than x's level.
Then clearly the predicate "P(x) iff x is in x" fails to be stratified (because x's level can't be one greater than itself). However, the predicate "P(x) iff x = x" is obviously stratified, and {x : x = x} is the set of all sets.
I know New Foundations, but stratification is too strong a restriction for my needs. This weird set theory of mine actually arose from a practical application - modeling "metastrategies" in the Prisoner's Dilemma. See this thread on decision-theory-workshop.
How is it that the paradox "goes away"? If you "additionally specify R(R) to be True or False", don't you just go down one or the other of the two cases in Russell's paradox?
Suppose we decide to specify that R(R) is true. Then, by your definition, not(R(R)) is true. That means that R(R) is false, contrary to our specification. Similarly, if we instead specify that R(R) is false, we are led to conclude that R(R) is true, again contradicting our specification.
The conclusion is that we can't specify any truth value for R(R). Either truth value leads to a contradiction, so R(R) must be left undefined. Is that what you mean to say?
No, in this case R(X) = not(X(X)) for all X distinct from R, and additionally R(R) is true. This is a perfectly fine, completely defined, non-self-contradictory predicate.
Why is R(X) = not(X(X)) only for R =/= X? In Russell's version, X should vary over all predicates/sets, meaning when instance X with R, we get
R(R) = ¬R(R)
as per the paradox.
Okay, I see. I see nothing obviously contradictory with this.
From a technical standpoint, the hard part would be to give a useful criterion for when a seemingly-well-formed string does or does not completely define a predicate. The string not(X(X)) seems to be well-formed, but you're saying that actually it's just a fragment of a predicate, because you need to add "for X not equal to this predicate", and then give an addition clause about whether this predicate satisfies itself, to have a completely-defined predicate.
I guess that this was the sort of work that was done in these non-foundational systems that people are talking about.
No, AFA and similar systems are different. They have no "set of all sets" and still make you construct sets up from their parts, but they give you more parts to play with: e.g. explicitly convert a directed graph with cycles into a set that contains itself.
I didn't mean that what you propose to do is commensurate with those systems. I just meant that those systems might have addressed the technical issue that I pointed out, but it's not yet clear to me how you address this issue.
I can't say anything about this specific construction, but there is a related issue in Turing machines. The issue was whether you could determine a useful subset S of the set of all Turing machines, such that the halting problem is solveable for all machines in S, and S was general enough to contain useful examples.
If I remember correctly, the answer was that you couldn't. This feels a lot like that - I'd bet that the only way of being sure that we can avoid Russel's paradox is to restrict predicates to such a narrow category that we can't do much anything useful with them.
I think you are going to run into serious problems. Consider the predicate that always returns true. Then if I'm following Russell's original formulation of the paradox involving the powerset of the set of all sets will still lead to a contradiction.
I can't seem to work out for myself what you mean. Can you spell it out in more detail?
Original form of Russell's paradox: Let A be the set of all sets and let P(A) be the powerset of A. By Cantor, |P(A)| > |A|. But, P(A) is a subset of A, so |P(A)|<=|A|. That's a contradiction.
Cantor's theorem breaks down in my system when applied to the set of all sets, because its proof essentially relies on Russell's paradox to reach the contradiction.
Hmm, that almost seems to be cutting off the nose to spite the cliche. Cantor's construction is a very natural construction. A set theory where you can't prove that would be seen by many as unacceptably weak. I'm a bit fuzzy on the details of your system, but let me ask, can you prove in this system that there's any uncountable set at all? For example, can we prove |R| > |N| ?
Yes. The proof that |R| > |N| stays working because predicates over N aren't themselves members of N, so the issue of "complete definedness" doesn't come up.
Hmm, this make work then and not kill off too much of set theory. You may want to talk to a professional set theorist or logician about this (my specialty is number theory so all I can do is glance at this and say that it looks plausible). The only remaining issue then becomes that I'm not sure that this is inherently better than standard set theory. In particular, this approach seems much less counterintuitive than ZFC. But that may be due to the fact that I'm more used to working with ZF-like objects.
The original form of Russell's (Zermelo's in fact) paradox is not this. The original form is {x|x not member of x}.
That leads to both
and
And that is the original form of the paradox.
No. See for example This discussion. The form you give where it is described as a simple predicate recursion was not the original form of the paradox.
Ok, I've read up on Cantor's theorem now, and I think the trick is in the types of A and P(A), and the solution to the paradox is to borrow a trick from type theory. A is defined as the set of all sets, so the obvious question is, sets of what key type? Let that key type be t. Then
We defined P(A) to be in A, so a t=>bool is also a t. Let all other possible types for t be T. t=(t=>bool)+T. Now, one common way to deal with recursive types like this is to treat them as the limit of a sequence of types:
Then when we take the limit,
Then suddenly, paradoxes based on the cardinality of A and P(A) go away, because those cardinalities diverge!
I'm not sure I know enough about type theory to evaluate this. Although I do know that Russell's original attempts to repair the defect involved type theory (Principia Mathematica uses a form of type theory however in that form one still can't form the set of all sets). I don't think the above works but I don't quite see what's wrong with it. Maybe Sniffnoy or someone else more versed in these matters can comment.
I don't know anything about type theory; when I wrote that I heard it has philosophical problems when applied to set theory, I meant I heard that from you. What the problems might actually be was my own guess...
Huh. Did I say that? I don't know almost anything about type theory. When did I say that?
I'm not deeply familiar with set theory, but cousin_it's formulation looks valid to me. Isn't the powerset of the set of all sets just the set of all sets of sets? (Or equivalently, the predicate X=>Y=>Z=>true.) How would you use that to reconstruct the paradox in a way that couldn't be resolved in the same way?
The powerset of the set of all sets may or may not be the set of all sets (it depends on whether or not you accept atoms in your version of set theory). However, Cantor's theorem shows that for any set B, the power set of B has cardinality strictly larger than B. So if B=P(B) you've got a problem.
If you are talking about things that are set-like, except that they don't satisfy the extensionality axiom, then you just aren't talking about sets. The things you're talking about may be set-like in some respect, but they aren't sets.
There are other set-like things that don't satisfy extensionality. For example, two different properties or predicates might have the same extension.
To be clear - Aczel's ZFA and similar systems do satisfy extensionality; they'd hardly be set theories if they didn't. It's just that when you have sets A and B such that A={A} and B={B}, you're going to need stronger tools than extensionality to determine whether they are equal.
Interesting. I'm not familiar with Aczel's system. But is that what cousin_it is talking about doing? That looks like an adjustment to Foundation rather than to Extensionality.
It's both at once. (Though, as I said, you don't throw out extensionality. Actually, that raises an interesting question - could you discard extensionality as an axiom, and just derive it from AFA? I hadn't considered that possibility. Edit: You probably could, there's no obvious reason why you couldn't, but I honestly don't feel like checking the details...)
If you just throw out foundation without putting in anything to replace it, you have the possibility of ill-founded sets, but no way to actually construct any. But the thing is, if all you do is say "Non-well-founded sets exist!" without giving any way to actually work with them, then, well, that's not very helpful either. Hence any antifoundational replacement for foundation is going to have to strengthen extensionality if you want the result to be something you want to work with at all.
I think you mean to say is "non-Well-founded sets exist!" since you are talking about the antifoundational case (and even with strong anti-foundation axioms I still have well-founded sets to play with also).
Oops. Fixed.
How do you mean bisimulation in this case? This seems to be a reduction down to decidable predicates, e.g. a Turing machine for each set. Without a type theory, many obvious algorithms will fail to converge.
Isn't "the set of all sets" (SAS) ill-defined? Suppose we consider it to be for some set A (maybe the set of all atoms) the infinite regression of power sets SAS = P(P(P(P....(A)))...)
In which case SAS = P(SAS) by Cantor-like arguments?
And Russell's paradox goes away?
So, is the set of all sets that aren't members of themselves, a member of itself, or not?
Insufficient data to answer your question :-) See my reply to Sniffnoy.
I'd like to hear more about this. It doesn't sound necessarily crackpottish to me to come up with an alternate set theory: von Neumann and Godel did. How do you avoid contradictions?
Wait, how is NBG set theory relevant to this? NBG is just a conservative extension of ZFC, and only allows something resembling a set of all sets by insisting that this collection is not, in fact, a set. Which after all, it has to in order to avoid Russell's paradox.
Yes, and I'm guessing cousin_it's version of set theory is possibly equivalent to something similar. I'd love to hear more about it.
Well I mean, I imagine it shouldn't be too hard to take ZFA (or similar) and tack proper classes onto it. Logic is not really my thing so I'm not actually familiar with how you show that NBG conservatively extends ZFC. The result would be a bit odd, though, in that classes would act very differently from sets - well, OK, more differently than they already do in NBG...
I don't know the proof either. The other weird thing to note is that even though NBG is a conservative extension of ZFC, some proofs in NBG are much shorter than proofs in ZFC. So in some sense it is only weakly conservative. I don't know if that notion can be made at all more precise.
Edit: Followup thought, most interesting conservative extensions are only weakly conservative in some sense. Consider for example finite degree field extensions of Q. If axiomatized these become conservative extensions of Z. (That's essentially why for example we can prove something in the Gaussian integers and know there's a proof in Z).
Russell's paradox, as usually stated, doesn't actually prove anything, because it's usually given as a statement in English about set theory.
I don't know whether Russell originally stated it in mathematical terms, in which case it would prove something. I've read numerous accounts of it, yet never seen a mathematical presentation. Google fails me at present.
I don't count a statement of the form "x such that x is not a member of x" as mathematical, because my intuition doesn't want me to talk about sets being members of themselves unless I have a mathematical formalism for sets and set membership for which that works. It's also not happy about the quantification of x in that sentence; it's a recursive quantification. Let's put it this way: Any computer program I have ever written to handle quantification would crash or loop forever if you tried to give it such a statement.
By the way, quick history of Russell's paradox and related matters, with possible application to the original topic. :)
Russell first pointed out his namesake paradox in Frege's attempt to axiomatize set theory. So yes, it was a mathematical statement, and, really, it's pretty simple to state it. Why nobody noticed before this paradox before then, I have no idea, but it does seem to be worth noting that nobody noticed it until someone actually attempted to sit down and actually formalize set theory.
However, Russell was not the first to notice a paradox in naïve set theory. (Not sure to what extent you can talk about paradoxes in something that hasn't been formalized, but it's pretty clear what's meant, I think.) Cesare Burali-Forti noticed earlier that considering the set of all ordinals leads to a paradox. And yet, despite this, people still continued using naïve set theory until Russell! Part of this may have been that, IIRC, Burali-Forti was convinced that what he found could not actually be a paradox, even though, well, in math, a paradox is always a paradox unless you can knock out one of the suppositions. I have to wonder if perhaps his reaction on finding this may have been along the lines of "...but somebody would have noticed". :)
And note also that even Russell's paradox was not phrased originally in this way. His original phrasing as I understand it rested on taking the set of all sets A and then looking at the cardinality of that set's powerset P(A). Then we have |P(A)| > |A| but P(A) <= A so |P(A)| <= |A| which is a contradiction. This is essentially the same as Russell's paradox when one expands out the details (particularly, the details in the proof that in general a set has cardinality strictly less than its powerset).
Ah, good point. I'd forgotten about that part. IIRC he first noted that and then expanded out the details to see where the problem was.
The problem is, how do you exclude it from working? If you're just working in first-order logic and you've got a "membership" predicate, of course it's a valid sentence. Russell and Whitehead tried to exclude it from working with a theory of types, but, I hear that has philosophical problems. (I admit to not having read their actual axioms or justification for such. I imagine the problem is basically as follows - it's easy enough to be clear about what you mean for finite types, but how do you specify transfinite types in a way that isn't circular?) The modern solution with ZFC is not to bar such statements; with the axiom of foundation, such statements are perfectly sensible, they're just false. Replace it with an antifoundational axiom and they won't always be false. However, in either case - or without picking a case at all - Russell's paradox still holds; allowing there to be sets that are members of themselves, does not allow there to be a set of all such sets. That is always paradoxical.
It's not recursive unless you're already working from a framework where there are objects and sets of objects and sets of etc. In the framework of first-order logic, there are just sets, period. Quantification is over the entire set-theoretic universe. No recursion, just universality. In ZFC sets can indeed be classified into this hierarchy, but that's a consequence of the axiom of foundation, not a feature of the logic.
I prefer to not have either foundation or an anti-foundational axiom. (Foundation generally leads to a more intuitive universe with sets sort of being like boxes but anti-foundational axioms lead to more interesting systems).
I'm also confused by cousin it's claim. I don't see how bisimulation helps one deal with Russell's paradox but I'd be interested in seeing a sketch of an attempt. As I understand it, if you try to use a notion of bisimilarity rather than extensionality and apply Russell's Paradox, you end up with essentially a set that isn't bisimilar to itself. Which is bad.
What encoding scheme would you use to encode arbitrary, possibly infinite, sets in a computer?
I could, worst case, use the encoding scheme you use to write them down on paper when you prove things about them.
It is presented that way to make a point that naive set theory isn't workable.
It is presented rigorously in most intro set theory text books. In ZFC or any other standard set of set theory axioms, Russell's paradox ceases to be a paradox and the logic is instead a theorem of the form "For any set A, there exists a set B such B is not an element of A."
Well, a standard formalism (again such as ZFC) is perfectly happy talking about sets that recur on themselves this way. Indeed, it is actually difficult to make a system of set theory that doesn't allow you to at least talk about sets like this.
I'm curious, do you consider Cantor's diagnolization argument to be too recursive? What about Turing's Halting Theorem?