6 ms·

> I have a sneaky suspicion the answer to a great many philosophical questions are hidden in there. Godel's incompleteness theorem had a profound affect on me

> I have a sneaky suspicion the answer to a great many philosophical questions are hidden in there. Godel's incompleteness theorem had a profound affect on me that I find hard to quantify. I grew up starry eyed, thinking that our minds have virtually limitless capabilities and that mathematics could answer everything (naive, I know). Then I came across Russell's paradox and the incompleteness theorems and for the first time (late high school) got confronted by the limits of our 'tools' (with proof!). And then encountering Heisenberg's uncertainty principle was just depressing and I took to computer science. I think better than just looking up seemingly random mathematical concepts is to go through the history of the development of set theory.

Shaniqua 11y ago
But Russel's Paradox is easy to fix. Let x be a set. Then, V = {x| x not in x} is the set that causes Russel's Paradox. We can easily define a new set S = {x| p(x) and x in U} where p(x) is some property and U is the universal set. Then S easily fixes the contradiction.
- voidz 11y ago
  Why is this downvoted? Is the statement incorrect?
  - banachtarski 11y ago
    Yes
    - voidz 11y ago
      Ah, I see you explained. Thanks. I love the subject, but I'm still a neophyte.
    - Shaniqua 11y ago
      By the way, I forgot to ask do you object to my post about "killing" the Russel set because you don't accept the existence of universal set or because you don't understand how {x in S| x not x} helps here? If it's the former, can you assume that U exists and explain how {x in S| x not x} solves the problem? So that I know you're not simply "saying things".
- banachtarski 11y ago
  I have no idea where you got this from but your statements don't follow any form of logic I'm familiar with. If V = {x | x not in x}, then if V contains itself, V is not in V (and vice versa) is an obvious contradiction. Your new set S doesn't help in the slightest. Fixing it is emphatically "not easy" and mathematicians generally rely on the ZFC axiomation (although several other possibilities were proposed).
  - Shaniqua 11y ago
    It's no big deal if you don't admit universal set or anything other than ZFC.
    - johntb86 11y ago
      It took 16 years (1901-1917) to get from russell's paradox to a set theory which didn't allow it, but which was able to create a lot of interesting and useful sets (ZF). So it seems like a big deal. And we still can't talk about "the set/collection/whatever of all sets" in the language of ZFC, so we're still missing out.
- defen 11y ago
  > universal set But now you're talking about non-standard set theory[1] which is fine but you are kind of side-stepping the issue. [1] https://en.wikipedia.org/wiki/Axiom_of_regularity https://en.wikipedia.org/wiki/Axiom_of_regularity
  - Shaniqua 11y ago
    Well, it's not that difficult to fix it in ZF. If you define S to be S = {x in U: x not in x}, then it simply means S is not in U.
    - defen 11y ago
      There is no U in ZF so I really don't understand what you are saying.
      - Shaniqua 11y ago
        You can call U anything you want. It's by axiom schema of specification: for any set A, there some set B with a set C in B iff C in A.
- dvt 11y ago
  Having a universal set [in naive set theory] is a sufficient condition for Russel's paradox. See Naive Set Theory[1] bottom of page 6. This is why we can have no Universe in any consistent set theory. Edit: @mafribe makes the point that there are some set theories that can still have universal sets by culling other features that ZF-style set theories have. I was mostly referring to ZF-style set theory (hence my citation). Indeed, one could even make a ZF-style set theory paraconsistent and still have Universal sets. [1] http://sistemas.fciencias.unam.mx/~lokylog/images/stories/Alexandria/Logica%20y%20Conjuntos/Paul%20R.Halmos%20-%20Naive%20Set%20Theory.pdf http://sistemas.fciencias.unam.mx/~lokylog/images/stories/Al...
  - mafribe 11y ago
    Having a universal set is a sufficient condition for Russel's paradox. That's not true. There are set-theories, e.g. Quine's NF [1] which allow universal sets, and other things like the set of all ordinals, that are forbidden in ZF-style set-theories. The problem in ZF is caused by unlimited comprehension. NF circumvents this by restricting comprehension. Tom Forster [2] has written a great deal about set theories with universal sets, including the wonderful [3]. He makes the historical point that set theory was born with universal sets. [1] http://plato.stanford.edu/entries/quine-nf/ http://plato.stanford.edu/entries/quine-nf/ [2] https://www.dpmms.cam.ac.uk/~tf/ https://www.dpmms.cam.ac.uk/~tf/ [3] T. E. Forster, Set Theory with a Universal Set. http://ukcatalogue.oup.com/product/9780198514770.do http://ukcatalogue.oup.com/product/9780198514770.do
    - dvt 11y ago
      True, I was mostly referring to ZF-style set theories (which is what the thread is mainly about). Your point could even be extended by saying that there are proofs for a paraconsistent ZF with a universal set. Your [3] link doesn't work by the way, I'm interested in reading Forster!
      - mafribe 11y ago
        [3] works on my browser. Anyway, the link was to the publisher's page for the book. Here is another one: http://www.amazon.co.uk/Set-Theory-Universal-Exploring-Universe/dp/0198514778 http://www.amazon.co.uk/Set-Theory-Universal-Exploring-Unive... .
Sirenos 11y ago
Isn't Russell's paradox more like a problem with naive set theory? By analogy to a software framework, the paradox would be considered a bug in the framework and say nothing about how useful it is.
- tikhonj 11y ago
  In a sense. But it's interesting because naive set theory appears so simple and natural: it's a concrete example of how human ideas that seem platonic and inviolate can actually be inconsistent. So it's less like finding a bug in a software framework and more like finding a bug in your understanding of how computers can work.
valera_rozuvan 11y ago
Best article I read on the history of development of set theory is by José Ferreirós: "The Early Development of Set Theory". It can be found at http://plato.stanford.edu/entries/settheory-early/ http://plato.stanford.edu/entries/settheory-early/ .
sbilstein 11y ago
I just finished reading Godel's Proof (a non-textbook account of the proof recommended by Hofstader in GEB) and it was mind-blowing. I really recommend that and David Foster Wallace's Beyond Infinity. Beyond Infinity is great history of set theory and written in an exciting and fun style. I came across the ideas the opposite way...I loved math as child and as engineer but I always felt like systems of rationalization had to be limited in some way. I think I started feeling this way when I'd get into debates with other students in school about arguments and we'd have equally rational but contradictory viewpoints. Fast forward a few years later and I learn some genius had actually proved that we can't answer everything with these systems...or that there isn't a system that can say it all.
- valera_rozuvan 11y ago
  > Fast forward a few years later and I learn some genius had actually proved that we can't answer everything with these systems...or that there isn't a system that can say it all. So true...
- EvaK_de 11y ago
  The book by DFW sounds interesting, but all I could find is "Everything and More: A Compact History of Infinity". Is that it?
  - sbilstein 11y ago
    Sorry yea, I misremembered the title when I was commenting.
pjungwir 11y ago
I felt similar amazement at Gödel's proof, and even suspect that Penrose must be on to something when he says the mind must therefore not be computable. . . . But the book Gödel's Theorem: An Incomplete Guide to its Use and Abuse by Törkel Franzén is very good at explaining that the conclusions we should draw are fairly limited, e.g. that the proof doesn't apply to anything other than arithmetic. I'm not sure I'm totally convinced, but it's a great perspective to dispel some of the more mystical interpretations.
- GeneTT 11y ago
  Dennet also has a pretty good take down of Penrose in chapter 15 of Darwins Dangerous Idea.
OJFord 11y ago
> I grew up starry eyed, thinking that our minds have virtually limitless capabilities ... and for the first time (late high school) got confronted by the limits of our 'tools' ... was just depressing and I took to computer science. Alas, not even safe there. Thanks a lot, Turing.

Shaniqua 11y ago

But Russel's Paradox is easy to fix. Let x be a set. Then, V = {x| x not in x} is the set that causes Russel's Paradox. We can easily define a new set S = {x| p(x) and x in U} where p(x) is some property and U is the universal set. Then S easily fixes the contradiction.

voidz 11y ago
Why is this downvoted? Is the statement incorrect?
- banachtarski 11y ago
  Yes
  - voidz 11y ago
    Ah, I see you explained. Thanks. I love the subject, but I'm still a neophyte.
  - Shaniqua 11y ago
    By the way, I forgot to ask do you object to my post about "killing" the Russel set because you don't accept the existence of universal set or because you don't understand how {x in S| x not x} helps here? If it's the former, can you assume that U exists and explain how {x in S| x not x} solves the problem? So that I know you're not simply "saying things".
banachtarski 11y ago
I have no idea where you got this from but your statements don't follow any form of logic I'm familiar with. If V = {x | x not in x}, then if V contains itself, V is not in V (and vice versa) is an obvious contradiction. Your new set S doesn't help in the slightest. Fixing it is emphatically "not easy" and mathematicians generally rely on the ZFC axiomation (although several other possibilities were proposed).
- Shaniqua 11y ago
  It's no big deal if you don't admit universal set or anything other than ZFC.
  - johntb86 11y ago
    It took 16 years (1901-1917) to get from russell's paradox to a set theory which didn't allow it, but which was able to create a lot of interesting and useful sets (ZF). So it seems like a big deal. And we still can't talk about "the set/collection/whatever of all sets" in the language of ZFC, so we're still missing out.
defen 11y ago
> universal set But now you're talking about non-standard set theory[1] which is fine but you are kind of side-stepping the issue. [1] https://en.wikipedia.org/wiki/Axiom_of_regularity https://en.wikipedia.org/wiki/Axiom_of_regularity
- Shaniqua 11y ago
  Well, it's not that difficult to fix it in ZF. If you define S to be S = {x in U: x not in x}, then it simply means S is not in U.
  - defen 11y ago
    There is no U in ZF so I really don't understand what you are saying.
    - Shaniqua 11y ago
      You can call U anything you want. It's by axiom schema of specification: for any set A, there some set B with a set C in B iff C in A.
dvt 11y ago
Having a universal set [in naive set theory] is a sufficient condition for Russel's paradox. See Naive Set Theory[1] bottom of page 6. This is why we can have no Universe in any consistent set theory. Edit: @mafribe makes the point that there are some set theories that can still have universal sets by culling other features that ZF-style set theories have. I was mostly referring to ZF-style set theory (hence my citation). Indeed, one could even make a ZF-style set theory paraconsistent and still have Universal sets. [1] http://sistemas.fciencias.unam.mx/~lokylog/images/stories/Alexandria/Logica%20y%20Conjuntos/Paul%20R.Halmos%20-%20Naive%20Set%20Theory.pdf http://sistemas.fciencias.unam.mx/~lokylog/images/stories/Al...
- mafribe 11y ago
  Having a universal set is a sufficient condition for Russel's paradox. That's not true. There are set-theories, e.g. Quine's NF [1] which allow universal sets, and other things like the set of all ordinals, that are forbidden in ZF-style set-theories. The problem in ZF is caused by unlimited comprehension. NF circumvents this by restricting comprehension. Tom Forster [2] has written a great deal about set theories with universal sets, including the wonderful [3]. He makes the historical point that set theory was born with universal sets. [1] http://plato.stanford.edu/entries/quine-nf/ http://plato.stanford.edu/entries/quine-nf/ [2] https://www.dpmms.cam.ac.uk/~tf/ https://www.dpmms.cam.ac.uk/~tf/ [3] T. E. Forster, Set Theory with a Universal Set. http://ukcatalogue.oup.com/product/9780198514770.do http://ukcatalogue.oup.com/product/9780198514770.do
  - dvt 11y ago
    True, I was mostly referring to ZF-style set theories (which is what the thread is mainly about). Your point could even be extended by saying that there are proofs for a paraconsistent ZF with a universal set. Your [3] link doesn't work by the way, I'm interested in reading Forster!
    - mafribe 11y ago
      [3] works on my browser. Anyway, the link was to the publisher's page for the book. Here is another one: http://www.amazon.co.uk/Set-Theory-Universal-Exploring-Universe/dp/0198514778 http://www.amazon.co.uk/Set-Theory-Universal-Exploring-Unive... .

Sirenos 11y ago

Isn't Russell's paradox more like a problem with naive set theory? By analogy to a software framework, the paradox would be considered a bug in the framework and say nothing about how useful it is.

tikhonj 11y ago
In a sense. But it's interesting because naive set theory appears so simple and natural: it's a concrete example of how human ideas that seem platonic and inviolate can actually be inconsistent. So it's less like finding a bug in a software framework and more like finding a bug in your understanding of how computers can work.

valera_rozuvan 11y ago

Best article I read on the history of development of set theory is by José Ferreirós: "The Early Development of Set Theory". It can be found at http://plato.stanford.edu/entries/settheory-early/ http://plato.stanford.edu/entries/settheory-early/ .

sbilstein 11y ago

I just finished reading Godel's Proof (a non-textbook account of the proof recommended by Hofstader in GEB) and it was mind-blowing. I really recommend that and David Foster Wallace's Beyond Infinity. Beyond Infinity is great history of set theory and written in an exciting and fun style. I came across the ideas the opposite way...I loved math as child and as engineer but I always felt like systems of rationalization had to be limited in some way. I think I started feeling this way when I'd get into debates with other students in school about arguments and we'd have equally rational but contradictory viewpoints. Fast forward a few years later and I learn some genius had actually proved that we can't answer everything with these systems...or that there isn't a system that can say it all.

valera_rozuvan 11y ago
> Fast forward a few years later and I learn some genius had actually proved that we can't answer everything with these systems...or that there isn't a system that can say it all. So true...
EvaK_de 11y ago
The book by DFW sounds interesting, but all I could find is "Everything and More: A Compact History of Infinity". Is that it?
- sbilstein 11y ago
  Sorry yea, I misremembered the title when I was commenting.

pjungwir 11y ago

I felt similar amazement at Gödel's proof, and even suspect that Penrose must be on to something when he says the mind must therefore not be computable. . . . But the book Gödel's Theorem: An Incomplete Guide to its Use and Abuse by Törkel Franzén is very good at explaining that the conclusions we should draw are fairly limited, e.g. that the proof doesn't apply to anything other than arithmetic. I'm not sure I'm totally convinced, but it's a great perspective to dispel some of the more mystical interpretations.

GeneTT 11y ago
Dennet also has a pretty good take down of Penrose in chapter 15 of Darwins Dangerous Idea.

OJFord 11y ago

> I grew up starry eyed, thinking that our minds have virtually limitless capabilities ... and for the first time (late high school) got confronted by the limits of our 'tools' ... was just depressing and I took to computer science. Alas, not even safe there. Thanks a lot, Turing.