= 27d567bc2d48d9f40e9ccc20ea370b15)
AlephNeil 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)
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.