JoshuaZ 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)
Tags: contrarianism disagreement

Comments (250)

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

Comment author: JoshuaZ 05 May 2010 04:03:52PM 0 points [-]

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.

Comment author: cousin_it 05 May 2010 04:14:00PM *  1 point [-]

I can't seem to work out for myself what you mean. Can you spell it out in more detail?

Comment author: JoshuaZ 05 May 2010 04:37:17PM 2 points [-]

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.

Comment author: cousin_it 05 May 2010 07:22:13PM *  0 points [-]

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.

Comment author: JoshuaZ 05 May 2010 07:24:39PM 0 points [-]

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

Comment author: cousin_it 05 May 2010 07:35:54PM 0 points [-]

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.

Comment author: JoshuaZ 05 May 2010 08:12:21PM 0 points [-]

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.

Comment author: Thomas 05 May 2010 07:04:16PM *  0 points [-]

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

  • x is a member of x

and

  • x is not a member of x

And that is the original form of the paradox.

Comment author: JoshuaZ 05 May 2010 07:17:31PM 0 points [-]

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.

Comment author: jimrandomh 05 May 2010 06:55:59PM *  0 points [-]

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

A: t=>bool
P(A): (t=>bool)=>bool

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:

t[i] = t[i-1]=>bool + T
A[i]: t[i]=>bool
P(A[i]) = A[i+1]

Then when we take the limit,

t = lim i->inf t[i]
A = lim i->inf A[i]
P(A) = lim i->inf P(A[i])

Then suddenly, paradoxes based on the cardinality of A and P(A) go away, because those cardinalities diverge!

Comment author: JoshuaZ 05 May 2010 07:07:23PM 0 points [-]

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.

Comment author: Sniffnoy 06 May 2010 02:28:02AM 0 points [-]

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

Comment author: JoshuaZ 06 May 2010 02:35:36AM 0 points [-]

Huh. Did I say that? I don't know almost anything about type theory. When did I say that?

Comment author: jimrandomh 05 May 2010 04:39:21PM *  0 points [-]

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?

Comment author: JoshuaZ 05 May 2010 04:52:49PM 0 points [-]

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.

Powered by Reddit Powered by Reddit