11 ms·

Set Theory and Foundations of Mathematics

121 points by valera_rozuvan 11y ago

dmead 11y ago
i blew a google interview question because i failed to recognize a powerset. keeping up with this stuff is pretty important.
- gooseus 11y ago
  I tried to find it in the OP, it sounded way over my head... this link explained it real fast. https://www.mathsisfun.com/sets/power-set.html https://www.mathsisfun.com/sets/power-set.html I still wish I could find the time to study all this foundational math... super interesting and I have a sneaky suspicion the answer to a great many philosophical questions are hidden in there.
  - vowelless 11y ago
    > 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.
    - 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.
  - SchemeLisp 11y ago
    Back when I just started learning all this stuff, I used to confuse elements of a set and its subsets. For example, I'd be easily stumped when asked what the elements and subsets of {a} were. Also, it's good to know why the empty set is a subset of any set and the proof/s that there are 2^n elements in a power set.
  - tel 11y ago
    > I have a sneaky suspicion... You have no idea. The more I study this stuff the more I feel that all philosophical questions might be somehow encoded in there.
    - AnimalMuppet 11y ago
      Sartre said that the great philosophical question is, why is there something instead of nothing? (This does not mean, why is there something in philosophy. Why is there something in the real world? Why does anything physically exist?) If your philosophy doesn't explain the real world, it isn't much of a philosophy. But I don't think set theory can explain that. Two other great philosophical questions are: Where do we humans find meaning? And, what is the basis for morals and ethics? How do we determine what actions are right and wrong? Set theory isn't going to answer those questions at all.
      - mindcrime 11y ago
        Two other great philosophical questions are: Where do we humans find meaning? And, what is the basis for morals and ethics? How do we determine what actions are right and wrong? And Camus said that the one truly interesting philosophical problem is suicide. http://www.camus-society.com/myth-of-sisyphus.html http://www.camus-society.com/myth-of-sisyphus.html Set theory isn't going to answer those questions at all. Indeed.
      - anthony_d 11y ago
        Sorry, but "Where do we humans find meaning?" isn't even a mediocre philosophical question. It's navel gazing by angst ridden teenagers.
      - valera_rozuvan 11y ago
        > Two other great philosophical questions are: Where do we humans find meaning? And, what is the basis for morals and ethics? I think the best question is "What will humans do, when we find meaning to everything?". I hope that never happens.
      - tel 11y ago
- rectang 11y ago
  It's not really your fault, but defeating Google-gotcha interview questions is a very distorting motivation. I'd like to think that this material is worth studying because it will help you to achieve things you otherwise could not, whether at Google or elsewhere. But that leads to a different kind of study: deep dives into specialized subjects relevant for the task at hand, rather than attempting to maintain shallow coverage over a broad field.
  - acrefoot 11y ago
    If they specifically asked for "powerset" that might be considered a gotcha question, but a powerset is another way of thinking of binary enumeration[0], which isn't that rare. [0] by that I mean both the case of counting in binary, as well as enumerating all the ways you can have or not have some things--you might care about that when considering all the interactions of config flags you might have to deal with.
    - dmead 11y ago
      this is exactly the case. had i just remember what a power set was instead of say something dumb like "all the n-k combination of these children something someting" it would have gone much better. and yes, it was a hard tree question.
- rwallace 11y ago
  Well, that's like saying you blew a Google interview question because you failed to recognize a black vine weevil, therefore keeping up with entomology is pretty important. One company having a buggy interview process that asks questions irrelevant to the job, at the very most means if you are applying for a job at that company you should spend a couple days cramming for the interview. It does not mean you should spend the precious hours of your life studying a field that's irrelevant to your job on an ongoing basis. To be clear, if you want to study set theory or entomology because you find them interesting for their own sake then far be it from me to criticize that decision. I'm just disagreeing with the argument that you should do so because of one company's buggy interview process.
robobro 11y ago
Honestly, Wittgenstein's philosophical critiques of set theory in relation to the foundations of mathematics still hold true today. Shame he doesn't get more recognition for his great work in logic.
- shadytrees 11y ago
  I'm intrigued but, upon Googling, pretty at sea with all the vocabulary. Is there an explain-like-I'm-slightly-above-five for Wittgenstein's critique of set theory? It seems like he doesn't like infinity very much?
  - valera_rozuvan 11y ago
    Have you seen Victor Rodych's entry at the plato.stanford.edu site entitled "Wittgenstein's Philosophy of Mathematics"? Direct link: http://plato.stanford.edu/entries/wittgenstein-mathematics/ http://plato.stanford.edu/entries/wittgenstein-mathematics/ .
  - valera_rozuvan 11y ago
    2.6 Wittgenstein's Intermediate Critique of Set Theory http://plato.stanford.edu/entries/wittgenstein-mathematics/#WitIntCriSetThe http://plato.stanford.edu/entries/wittgenstein-mathematics/#...
- dvt 11y ago
  Wittgenstein was primarily interested in the linguistic applications of logic. IMO, he wasn't on the same level as Whitehead, Russell, or Curry; let alone Hilbert, Gödel, and Zermelo. And maybe it's just my experience, but Wittgenstein was always shoved down our throats in my undergraduate and graduate classes, whereas people may have never even heard of Jan Łukasiewicz or Stephen Kleene.
  - tikhonj 11y ago
    Ah, different communities with different goals. In CS, I've run into Kleene a lot and Wittgenstein never. (Although I'm sure people have heard of him!)
gver 11y ago
If you follow the link to his page "I'm upset...Here is why", you can see that this person has a significant degree of "crankiness". These people through their perhaps not deliberate obfuscation, often manage to trick the mathematically naive into thinking there is substance there - "it is so hard and confusing, it must be real math." It is a disservice to have links like this on Hacker News.
- spacehome 11y ago
  I tried, but I don't think I have it in me to read that wall of text. What specifically made you think he was cranky?
  - deleted 11y ago
    [deleted]
- mathattack 11y ago
  That's two links away. Do we really need to hold HN to such a high standard?
  - deleted 11y ago
    [deleted]
- SerpentJoe 11y ago
  The parent isn't saying the author is cranky, like ornery, he's saying he's a crank. The link being referred to [0] seems to be a classic piece of crankery meandering from the solution to global warming to perceived slights against the author on Internet forums and who knows what else. The question then, knowing this, is whether the OP link is quality content? [0] http://settheory.net/life http://settheory.net/life
burritofanatic 11y ago
I studied set theory was I young as a student, but seeing something like this reminds me there's so much to learn, and re-learn.

121 points by valera_rozuvan 11y ago

dmead 11y ago

i blew a google interview question because i failed to recognize a powerset. keeping up with this stuff is pretty important.

gooseus 11y ago
I tried to find it in the OP, it sounded way over my head... this link explained it real fast. https://www.mathsisfun.com/sets/power-set.html https://www.mathsisfun.com/sets/power-set.html I still wish I could find the time to study all this foundational math... super interesting and I have a sneaky suspicion the answer to a great many philosophical questions are hidden in there.
- vowelless 11y ago
  > 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.
  - 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.
- SchemeLisp 11y ago
  Back when I just started learning all this stuff, I used to confuse elements of a set and its subsets. For example, I'd be easily stumped when asked what the elements and subsets of {a} were. Also, it's good to know why the empty set is a subset of any set and the proof/s that there are 2^n elements in a power set.
- tel 11y ago
  > I have a sneaky suspicion... You have no idea. The more I study this stuff the more I feel that all philosophical questions might be somehow encoded in there.
  - AnimalMuppet 11y ago
    Sartre said that the great philosophical question is, why is there something instead of nothing? (This does not mean, why is there something in philosophy. Why is there something in the real world? Why does anything physically exist?) If your philosophy doesn't explain the real world, it isn't much of a philosophy. But I don't think set theory can explain that. Two other great philosophical questions are: Where do we humans find meaning? And, what is the basis for morals and ethics? How do we determine what actions are right and wrong? Set theory isn't going to answer those questions at all.
    - mindcrime 11y ago
      Two other great philosophical questions are: Where do we humans find meaning? And, what is the basis for morals and ethics? How do we determine what actions are right and wrong? And Camus said that the one truly interesting philosophical problem is suicide. http://www.camus-society.com/myth-of-sisyphus.html http://www.camus-society.com/myth-of-sisyphus.html Set theory isn't going to answer those questions at all. Indeed.
    - anthony_d 11y ago
      Sorry, but "Where do we humans find meaning?" isn't even a mediocre philosophical question. It's navel gazing by angst ridden teenagers.
    - valera_rozuvan 11y ago
      > Two other great philosophical questions are: Where do we humans find meaning? And, what is the basis for morals and ethics? I think the best question is "What will humans do, when we find meaning to everything?". I hope that never happens.
    - tel 11y ago
rectang 11y ago
It's not really your fault, but defeating Google-gotcha interview questions is a very distorting motivation. I'd like to think that this material is worth studying because it will help you to achieve things you otherwise could not, whether at Google or elsewhere. But that leads to a different kind of study: deep dives into specialized subjects relevant for the task at hand, rather than attempting to maintain shallow coverage over a broad field.
- acrefoot 11y ago
  If they specifically asked for "powerset" that might be considered a gotcha question, but a powerset is another way of thinking of binary enumeration[0], which isn't that rare. [0] by that I mean both the case of counting in binary, as well as enumerating all the ways you can have or not have some things--you might care about that when considering all the interactions of config flags you might have to deal with.
  - dmead 11y ago
    this is exactly the case. had i just remember what a power set was instead of say something dumb like "all the n-k combination of these children something someting" it would have gone much better. and yes, it was a hard tree question.
rwallace 11y ago
Well, that's like saying you blew a Google interview question because you failed to recognize a black vine weevil, therefore keeping up with entomology is pretty important. One company having a buggy interview process that asks questions irrelevant to the job, at the very most means if you are applying for a job at that company you should spend a couple days cramming for the interview. It does not mean you should spend the precious hours of your life studying a field that's irrelevant to your job on an ongoing basis. To be clear, if you want to study set theory or entomology because you find them interesting for their own sake then far be it from me to criticize that decision. I'm just disagreeing with the argument that you should do so because of one company's buggy interview process.

robobro 11y ago

Honestly, Wittgenstein's philosophical critiques of set theory in relation to the foundations of mathematics still hold true today. Shame he doesn't get more recognition for his great work in logic.

shadytrees 11y ago
I'm intrigued but, upon Googling, pretty at sea with all the vocabulary. Is there an explain-like-I'm-slightly-above-five for Wittgenstein's critique of set theory? It seems like he doesn't like infinity very much?
- valera_rozuvan 11y ago
  Have you seen Victor Rodych's entry at the plato.stanford.edu site entitled "Wittgenstein's Philosophy of Mathematics"? Direct link: http://plato.stanford.edu/entries/wittgenstein-mathematics/ http://plato.stanford.edu/entries/wittgenstein-mathematics/ .
- valera_rozuvan 11y ago
  2.6 Wittgenstein's Intermediate Critique of Set Theory http://plato.stanford.edu/entries/wittgenstein-mathematics/#WitIntCriSetThe http://plato.stanford.edu/entries/wittgenstein-mathematics/#...
dvt 11y ago
Wittgenstein was primarily interested in the linguistic applications of logic. IMO, he wasn't on the same level as Whitehead, Russell, or Curry; let alone Hilbert, Gödel, and Zermelo. And maybe it's just my experience, but Wittgenstein was always shoved down our throats in my undergraduate and graduate classes, whereas people may have never even heard of Jan Łukasiewicz or Stephen Kleene.
- tikhonj 11y ago
  Ah, different communities with different goals. In CS, I've run into Kleene a lot and Wittgenstein never. (Although I'm sure people have heard of him!)

gver 11y ago

If you follow the link to his page "I'm upset...Here is why", you can see that this person has a significant degree of "crankiness". These people through their perhaps not deliberate obfuscation, often manage to trick the mathematically naive into thinking there is substance there - "it is so hard and confusing, it must be real math." It is a disservice to have links like this on Hacker News.

spacehome 11y ago
I tried, but I don't think I have it in me to read that wall of text. What specifically made you think he was cranky?
- deleted 11y ago
  [deleted]
mathattack 11y ago
That's two links away. Do we really need to hold HN to such a high standard?
- deleted 11y ago
  [deleted]
SerpentJoe 11y ago
The parent isn't saying the author is cranky, like ornery, he's saying he's a crank. The link being referred to [0] seems to be a classic piece of crankery meandering from the solution to global warming to perceived slights against the author on Internet forums and who knows what else. The question then, knowing this, is whether the OP link is quality content? [0] http://settheory.net/life http://settheory.net/life

burritofanatic 11y ago

I studied set theory was I young as a student, but seeing something like this reminds me there's so much to learn, and re-learn.