On Jan 28, 2010, at 5:30 PM, Rob Freeman wrote:
> On Thu, Jan 28, 2010 at 4:52 PM, Christopher Menzel <cmenzel@xxxxxxxx> wrote:
>>
>> Russell's paradox has nothing whatever to do with decidability or
>irreducibility whatever you think that means). Do you even know what
>Russell's paradox is?
>
> There's one particular talk by Chaitin on the history of this which I always
>like: (01)
Fine, but do you know what Russell's paradox is? (02)
> "So there was a problem with set theory  that became increasingly
> clear. I think Russell helped to make it be recognized by everybody
> that we had a serious crisis and that methods of reasoning that seemed
> at first sight perfectly legitimate in some cases led to obvious
> disaster, to contradictions. There were a whole bunch of paradoxes
> that Russell advertised: the Berry paradox, the one I just mentioned
> is called the Russell paradox, and there's another paradox, the
> BuraliForti paradox.
>
> A lot of these paradoxes in fact were really brought to the attention
> of the world by Russell. Russell would typically have a footnote
> saying this paradox occurred to me while I was reading a paper by
> BuraliForti, so everyone calls it the BuraliForti paradox.
> BuraliForti I think spent his whole life trying to live down this
> attribution because he didn't believe that mathematics was in
> trouble!" (03)
Chaitin's history here is more or less correct. BF himself never interpreted
his result as a paradox (just as Cantor did not see any paradox in what is
usually called "Cantor's paradox")  although, unlike Cantor, the reason BF
did not see a paradox actually lay in a conceptual mistake on his part such
that, if he hadn't made it, he likely *would* have discovered the paradox
attributed to him. Cantor himself saw no paradox because he realized quite
clearly that there are collections that are in a certain sense "too big" to be
considered sets (which is essentially the solution to the paradox found in
modern set theory). (04)
> "So what happens when you start playing with this idea? What happens
> is, everywhere you turn, you get incompleteness and undecidability..."
>
> http://arxiv.org/html/nlin/0004007 (05)
Are you being intentionally disingenuous by suggesting that what Chaitin refers
to by "this idea" has something to do with Russell's paradox or did you really
not notice that this last quote comes in an entirely different, much later
section of his paper, a section on algorithmic information? And that "this
idea" in fact refers to the idea of algorithmic randomness? Chaitin does not
make ANY connection in his paper between Russell's paradox and
undecidability/incompleteness. (06)
Chris Menzel (07)
ps: On reflection, I will qualify my original claim that Russell's paradox has
*nothing* to do with undecidability. For there is in fact a similarity between
the usual argument given in presentations of Russell's paradox and the method
of diagonalization in computability theory  a method often used in proofs of
undecidability. Russell's argument can be used more generally to show that,
for any given set A, the set of all nonselfmembered members of A cannot
itself be a member of A and the proof is a clear instance of diagonalization.
The paradox itself ensues from this theorem if one also assumes (or one is able
to prove) that there is a universal set. (08)
So there is a similarity between the method of proof in Russell's paradox and a
common method of proof in computability theory. But, conceptually, the paradox
itself has nothing to do with undecidability/incompleteness/computability per
se. It's a paradox of set theory that arises if one adopts injudicious
principles of set existence (notably, the principle that, for every description
D, there exists a set containing exactly the things satisfying D). (09)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontologforum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontologforum/
Unsubscribe: mailto:ontologforumleave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgibin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontologforum@xxxxxxxxxxxxxxxx (010)
