4 ms·

There is a scientific paper with a proof based on its own existence

22 points by msuvakov 9y ago

alehul 9y ago
This may be a very broad question, but has anyone else thought about whether our basic fundamentals of logic are flawed, and if so, how? Wouldn't a logically sound system be devoid of any paradox?
- GEB93933 9y ago
  That exact notion is covered here: https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach
- tensor_rank_0 9y ago
  there was a guy once who proved that any system is either capable of paradox or reliant on external support. look up Kurt Godel.
  - mikejb 9y ago
    Gödel's incompleteness theorems are really something. Ultimately (iirc) it boils down to this: If an axiomatic system is complex enough, it cannot be both consistent and complete. I.e. either you have statements that you can't prove despite them being true, or your system is inconsistent (i.e. you can prove false statements). That is a simple description of the first incompleteness theorem. The 2nd incompleteness theorem goes along similar lines: If an axiomatic system is complex enough and consistent, it can't prove it's own consistency. I.e.: If a system can prove it's own consistency, it isn't consistent. Regarding how complex an axiomatic system has to be: Simple arithmetic is enough. (FYI: it has been a while since I've spent time with the incompleteness theorems. No guarantees on accuracy, and correcting comments are welcome :) )
    - tensor_rank_0 9y ago
      thanks for the breakdown. the example of a Godel statement is usually given in terms of set theory. ("S is the set of all sets that do not contain themselves. Does S contain itself?") or binary logic. ("this statement is false"). Do you know of an example in arithmetic?
      - cgmg 9y ago
        The examples you mentioned are not Gödel sentences, but rather Russell’s paradox and the liar paradox, respectively. A Gödel sentence for a theory T says “This sentence is not provable by T.” Truth is very different from provability and, unlike provability, cannot be represented as an arithmetic formula. See the section titled “Relationship with the liar paradox” in the Wikipedia article on the incompleteness theorems.
rspeer 9y ago
"Hey, why do YOU get to be the president of Tautology Club-- wait, I can guess." -xkcd

22 points by msuvakov 9y ago

This may be a very broad question, but has anyone else thought about whether our basic fundamentals of logic are flawed, and if so, how? Wouldn't a logically sound system be devoid of any paradox?

GEB93933 9y ago
That exact notion is covered here: https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach
tensor_rank_0 9y ago
there was a guy once who proved that any system is either capable of paradox or reliant on external support. look up Kurt Godel.
- mikejb 9y ago
  Gödel's incompleteness theorems are really something. Ultimately (iirc) it boils down to this: If an axiomatic system is complex enough, it cannot be both consistent and complete. I.e. either you have statements that you can't prove despite them being true, or your system is inconsistent (i.e. you can prove false statements). That is a simple description of the first incompleteness theorem. The 2nd incompleteness theorem goes along similar lines: If an axiomatic system is complex enough and consistent, it can't prove it's own consistency. I.e.: If a system can prove it's own consistency, it isn't consistent. Regarding how complex an axiomatic system has to be: Simple arithmetic is enough. (FYI: it has been a while since I've spent time with the incompleteness theorems. No guarantees on accuracy, and correcting comments are welcome :) )
  - tensor_rank_0 9y ago
    thanks for the breakdown. the example of a Godel statement is usually given in terms of set theory. ("S is the set of all sets that do not contain themselves. Does S contain itself?") or binary logic. ("this statement is false"). Do you know of an example in arithmetic?
    - cgmg 9y ago
      The examples you mentioned are not Gödel sentences, but rather Russell’s paradox and the liar paradox, respectively. A Gödel sentence for a theory T says “This sentence is not provable by T.” Truth is very different from provability and, unlike provability, cannot be represented as an arithmetic formula. See the section titled “Relationship with the liar paradox” in the Wikipedia article on the incompleteness theorems.

rspeer 9y ago

"Hey, why do YOU get to be the president of Tautology Club-- wait, I can guess." -xkcd