[Top] [All Lists]

Re: [ontolog-forum] Can Syntax be Semantic?

To: "[ontolog-forum] " <ontolog-forum@xxxxxxxxxxxxxxxx>
From: Christopher Menzel <cmenzel@xxxxxxxx>
Date: Thu, 28 Jan 2010 20:16:51 -0600
Message-id: <E9495CDB-879E-4CE3-8636-6648B257FC46@xxxxxxxx>
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
> Burali-Forti 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
> Burali-Forti, so everyone calls it the Burali-Forti paradox.
> Burali-Forti 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.  B-F 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 B-F 
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 non-self-membered 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/ontolog-forum/  
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/  
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/ 
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx    (010)

<Prev in Thread] Current Thread [Next in Thread>