Sniffnoy comments on But Somebody Would Have Noticed - Less Wrong

36 Post author: Alicorn 04 May 2010 06:56PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (250)

Comments (250)

Sort By: Best

Show:

You are viewing a single comment's thread. Show more comments above.

Comment author: Sniffnoy 05 May 2010 12:57:47AM * 3 points [-]

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.

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 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.

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.

Comment author: JoshuaZ 05 May 2010 01:19:42AM 0 points [-]

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.

Comment author: PhilGoetz comment score below threshold [+] (23 children)

Comment author: Sniffnoy 05 May 2010 04:44:43AM * 2 points [-]

OK, so what you're saying is that any predicate that uses a variable in multiple places is recursive. That seems a very unusual notion of "recursive". Such situations are very common and not at all problematic. What if you're working with digraphs, with the possibility of self-loops? You can't handle talking about which nodes do or don't have edges pointing to themselves? That's fundamentally all that's going on here. Not being able to handle that, not being able to look at diagonal conditions, seems pretty broken. Not to mention that any predicate that is a conjuction or disjunction may well include the same variable in multiple places!

Comment author: JoshuaZ 05 May 2010 05:46:15AM 0 points [-]

It may be possible to make what he is doing more precise or more usable. If he's objecting to impredicativity then maybe's he be ok with ZFC or NBG but not KM? (I know that KM is proper with respect to NBG but don't know much else about it. I'm not sure how relevant this is.)

Comment author: Tyrrell_McAllister 05 May 2010 07:24:01PM * 1 point [-]

I'm pretty sure it's recursive under any framework. It asks about "x (now a free, unquantified variable) such that x (still a completely free variable) is not a member of x (whoops!)".

Your assertions about when x is free aren't right. The variable x is being bound in its first appearance, and it is already bound (and so not "completely free") in its second and third appearance.

And, to restate what Sniffnoy is saying in terms of Russell's own example: Are you really not allowed to talk about all the barbers who shave themselves?

Comment author: PhilGoetz 05 May 2010 09:50:16PM * -1 points [-]

Your assertions about when x is free aren't right. The variable x is being bound in its first appearance, and it is already bound (and so not "completely free") in its second and third appearance.

The third appearance of x assumes that x is already bound, so that you can evaluate whether something is a member of it. But when processing the second appearance of x, you are testing candidate values of x, to find out whether they satisfy the predicate not(member(X,X)). Within that predicate, you assume that the second argument is already bound, and look for instantiations of the first argument for which the predicate is true.

To evaluate this, you would have to write it as

Find X1, X2, X3 such that not(member(X1,X2)), equals(X1,X2), member(X2, X3), equals(X2, X3). (Finding a binding asserts that the set of all sets that are not members of themselves is a member of itself.)

But if you try to evaluate this, it's not going to run into any paradoxes; it's going to depend on how you define the predicate "not".

You can see a problem in writing it down if you think about how, computationally, it would be evaluated. If you start by asking for the set X,Y such that not(member(X,Y)), that's not a computable set; it keeps generating members forever. I don't think there's any way to write Russell's paradox in Prolog such that it would be possible to compute an answer.

Comment author: Tyrrell_McAllister 05 May 2010 10:16:51PM * 0 points [-]

Your assertions about when x is free aren't right. The variable x is being bound in its first appearance, and it is already bound (and so not "completely free") in its second and third appearance.

The third appearance of x assumes that x is already bound, so that you can evaluate whether something is a member of it. But when processing the second appearance of x, you are testing candidate values of x, to find out whether they satisfy the predicate not(member(X,X)). Within that predicate, you assume that the second argument is already bound, and look for instantiations of the first argument for which the predicate is true.

You are not using the word "bound" in the way that it is used in formal logic. The two occurances of 'X' in not(member(X,X)) are either both bound or both free. You cannot have one lying within the scope of a quantifier while the other is not.

Comment author: PhilGoetz 05 May 2010 10:35:46PM * -1 points [-]

You aren't disagreeing with me! I'm just additionally pointing out that the semantics of member(X,Y) require either X or Y to be bound in order for the statement to be unified, and for the entire quantified statement to be meaningful. To find X that satisfy Russell's paradox, you would have to violate the rule you just stated.

Comment author: Tyrrell_McAllister 06 May 2010 12:11:39AM 2 points [-]

To find X that satisfy Russell's paradox, you would have to violate the rule you just stated.

Do you mean that I can't verify that a set is not an element of itself? But the empty set, for example, is not an element of itself. I can confirm this by noting that no thing is an element of the empty set (which is a finite check). Hence, the empty set, in particular, is not an element of the empty set. Therefore, by setting X = the empty set, I have an X such that X is not an element of X.

Note that in the above use of the predicate not(member(X,X)), both occurrences of 'X' were bound. So I'm not sure what you mean when you say that I "would have to violate the rule [I] just stated."

Comment author: PhilGoetz 06 May 2010 01:46:59AM * -2 points [-]

Oops, you're right. I was thinking of cases where you are trying to generate answers to a query, which is different from testing one candidate answer.

Let me start over:

My suspicion, which I haven't proved, is that Russell's Paradox is a result of specifying a logic, and not specifying the algorithms used to evaluate statements in that logic or to answer queries. In any complete specification of a logic, including both the rules and the computational steps taken to evaluate or query-answer, you will probably find that you can prove what the outcome of the Russell's paradox query is.

In other words, "formal logic" is too sloppy; my intuition is that in Russell's paradox, it hides problems with order of execution.

Comment author: JoshuaZ 06 May 2010 01:56:29AM 2 points [-]

Not really. In most standard axiomatic descriptions of set theory, like say ZFC, one doesn't need to think at all about computability of set relations. This is a good thing. We want for example the Busy Beaver function to be well-defined. And we want to be able to talk about things like the behavior of Turing machines when connected to non-computable oracles. If we insist that our set theoretic relationships be computable this sort of thing becomes very hard to talk about.

Comment author: PhilGoetz 07 May 2010 07:53:01PM * -1 points [-]

Huh? The Busy Beaver function is all about computability. The function itself is not computable; but you know that only because you've spelled out how the computation works, and can show that there is an answer but that it is not computable.

ZFC was designed to avoid Russell's Paradox; it does this by getting closer to a computable description of set theory. The definition itself is actually computational; a set of axioms of implication are just rewrite rules. It is ambiguous only in that it fails to specify what order rewrite rule applies first.

I have no problem with using non-computable oracles. But the way Turing machines interact with those oracles is computationally explicit. The view I'm expressing suggests you could run into troubles if you posed an oracle a question that hid ambiguities that would be resolved by a computational specification of the oracle. But I've never seen any use of an oracle that did that. People don't use oracles for Russell's paradox-like problems; they typically use them for non-computable functions.

continue this thread »

Comment author: Tyrrell_McAllister 06 May 2010 12:03:59AM 0 points [-]

You aren't disagreeing with me! I'm just additionally pointing out that the semantics of member(X,Y) require either X or Y to be bound in order for the statement to be unified, and for the entire quantified statement to be meaningful.

I'm not sure how you're using these words. In formal logic, boundedness has nothing to do with semantics. Boundedness is a purely syntactic notion. And I don't know what "unified" means in this context.

Comment author: PhilGoetz 06 May 2010 01:55:19AM * -1 points [-]

The "member" predicate is not a predicate like "shaves"; it is a primitive predicate, like "and", with special semantics. If you want to generate the set of X for which member(X,Y) is true, you need Y to be bound. To generate the set of Y for which member(X,Y) is true, you need X to be bound. That's what I meant.

Asking for the set of all <X,Y> for which member(X,Y) is true is going to get stuck in an infinite loop without ever generating any results. There is some connection between Russell's paradox, and queries that generate a useless infinite loop in a query language. You can look at a statement of the paradox and feel that it leads to two contradictory proofs; but if you define set theory and the algorithms used to answer queries, I think (but am not sure) you will find that you can prove what the algorithm will produce when run.

Comment author: thomblake 06 May 2010 01:24:12PM 1 point [-]

Asking for the set of all <X,Y> for which member(X,Y) is true is going to get stuck in an infinite loop without ever generating any results.

It looks like you're using a computational model to understand Russell's paradox. Should you be thinking of Kleene-Rosser?

Comment author: PhilGoetz 07 May 2010 04:25:42PM 0 points [-]

Thanks for the pointer. I was saying that my guess is that Russell's paradox reduces to something like the Kleene-Rosser paradox, which is resolved when you spell out the order of execution; and that we shouldn't worry about paradoxes that are resolved when you spell out the order of execution, because a "formal logic" without the details for performing computations spelled out is not sufficiently formal.

Comment author: Tyrrell_McAllister 06 May 2010 03:46:59AM * 1 point [-]

The "member" predicate is not a predicate like "shaves"; it is a primitive predicate, like "and", with special semantics. If you want to generate the set of X for which member(X,Y) is true, you need Y to be bound. To generate the set of Y for which member(X,Y) is true, you need X to be bound. That's what I meant.

That's not a problem, because, like I said, both arguments of member(X,X) are bound in Russell's paradox. They are both bound by the phrase "The set of all X such that. . ." that precedes them.

Asking for the set of all <X,Y> for which member(X,Y) is true is going to get stuck in an infinite loop without ever generating any results.

Again, I need to know how you are encoding sets before I can answer any question about what an algorithm would do on given input.

but if you define set theory and the algorithms used to answer queries, I think (but am not sure) you will find that you can prove what the algorithm will produce when run.

One wouldn't want all queries within set theory to be decidable by some algorithm. If that were the case, then set theory would not be able to capture enough of arithmetic.

Comment author: PhilGoetz 07 May 2010 04:16:45PM -1 points [-]

One wouldn't want all queries within set theory to be decidable by some algorithm.

I'm aware of that. This particular paradox, though, is one where the question seems to be decidable both ways, not one where it's undecidable.

Comment author: PhilGoetz 07 May 2010 04:20:19PM -1 points [-]

My talk of "primitive predicates" makes sense only if you're talking about a computational implementation.

In a truly formal logic, you do determine the definitions of the predicates purely by the axioms they are found in, including a set of axioms that are production rules, which therefore spell out execution (although order of execution is still usually ambiguous). ZF set theory is like that.

But I've never seen a presentation of Russell's paradox which defined what "not" and "member-of" mean in an axiomatic way. I don't think that had even been done for set theory at the time Russell proposed his paradox. The presentations I've seen always rely on your intuition about what "not" and "member of" mean.

Comment author: PhilGoetz 05 May 2010 09:40:54PM * -2 points [-]

The predicate shaves(X,X) is very different from the predicate member-of(X,X). To find values of X that satisfy the first, you simply enumerate all of your facts about

shaves(al, fred) shaves(al, joe) shaves(al, al)

and look for one that unifies with shaves(X,X).

You aren't going to find the X that satisfy member(X,X) by unification. It isn't even ever true for finite sets, except by convention for the empty set.

Comment author: Tyrrell_McAllister 05 May 2010 10:12:07PM * 1 point [-]

It isn't even ever true for finite sets, except by convention for the empty set.

I think that you're confusing the element-of relation with the subset-of relation. Or something. But then, all sets are subsets of themselves, including finite ones, so I'm not sure what you were thinking.

At any rate, the empty set is not an element of itself according to any convention that I've ever seen.

You aren't going to find the X that satisfy member(X,X) by unification.

I'm not sure how to respond to this until you answer my question in this comment.

Comment author: PhilGoetz 08 May 2010 05:10:16AM * 0 points [-]

At any rate, the empty set is not an element of itself according to any convention that I've ever seen.

You're right; I was mis-remembering. It can't be, or 1 := 0 u {0} wouldn't work.

Sniffnoy comments on But Somebody Would Have Noticed - Less Wrong

Article Navigation

Comments (250)

Nearest Meetups

Virtual Study Room

Recent Comments

Recent Posts

Recent Rationality Quotes

Recent Wiki Edits

Top Contributors, 30 Days

Recent Karma Awards

Comments (250)

Top Contributors, 30 Days

You'll need to login or register to do that

(Don't worry, it only takes a few seconds)

Create

Login