What's Gödel's incompleteness theorem? And what importance does it have?
>>8185041
Basically says for a system of axioms sufficiently powerful enough to express arithmetic there are true statements that cannot be proven in the system. It's a mathematical result on the limitation of foundational issues.
>>8185060
>there are true statements that cannot be proven in the system
should be
>there are statements in the language of that system which cannot be proven/disproven
>>8185060
Can you provide an example?
>>8185072
There are statements about the natural numbers that are true, which cannot be proven within the language. That is not incorrect.
>>8185090
The continuum hypothesis if i remember correctly
>>8185090
Godel formalized the notation of the liar's paradox. Look into:
https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814758371
https://www.amazon.com/G%C3%B6dels-Theorem-Incomplete-Guide-Abuse/dp/1568812388
https://www.amazon.com/G%C3%B6delian-Puzzle-Book-Puzzles-Paradoxes/dp/0486497054/ref=pd_sim_14_6?ie=UTF8&dpID=51Vw3HENQxL&dpSrc=sims&preST=_AC_UL480_SR303%2C480_&psc=1&refRID=HQFWRDJ55KGRQCRZYP2M
To learn more
>>8185098
This statement is false.
What does his theorem even mean in real life?
>>8185118
It would be difficult to build a bridge from this kind of mathematics to areas one thinks of as "real life."
It's not at all clear to me what such a bridge is made out of, but some have attempted to apply it to philosophy of mind by giving formal descriptions to consciousness (ex: the mind is unable to prove or disprove certain statements about reality because it is, in some sense, like one of the systems Godel considers)
>>8185118
I'll add that I'm skeptical of this theorem's relevance to results or inquiries outside of mathematics.
>>8185118
Basically it means certain formal systems can't prove everything we wished/hope they could. It goes into undecidability.
>>8185118
Take this problem for example
>https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable_generalizations
It's a generalization of the Collatz conjecture. If we could solve it, it would probably have application in computer science, but it has been proven to be undecidable.
Since we know that now, the problem has been somewhat "solved".
Remember children: there are two incompleteness theorems: (1) any formal system powerful enough to do arithmetic will contain statements that cannot be proved or disproved within the system; (2) any formal system power enough to do arithmetic cannot prove that it does not contain contradictions.
>>8185096
No. You're a fucking idiot. CH is independent of ZFC but we don't know that if it's true or not.
>>8185152
Let me attempt to persuade you otherwise. Gödel's incompleteness theorems have very important implications for an area of philosphy which is called epistomology, or the theory of knowledge. Roughly speaking, if there's any type of philosophical question which involves knowledge, questions knowledge, "how do you really know what you think you know" " u can't know nuffin :^3 ", etc, then it can reasonably be claimed to be an epistomological problem.
Since humans have some ambition for knowledge, modern philosophy especially has often entertained the projected notion (notice that a notion is not "knowledge") that perhaps it is possible to "know everything (worth knowing)" in this-or-that discipline (we would often like to, in principle). And any assertions to the contrary have historically been sorts of cultural, normative, or emotional statements to that effect: atheists can't prove that god exists, etc. Notice that this whole paragraph has not contained any /knowledge about the limits of knowledge/, just wishes, culture, suggestions, supposition, etc.
So the language about what it is possible to know has historically been fuzzy and vague. What if it were possible for someone to actually, scientifically make a /very general statement/ to the effect that "um, pardon me desu lads, but you actually can't know everyfin. And here is the proof." In other words, we've moved beyond culture, emotion, suspicion, etc, back into the category of /knowledge/, ironically (but not paradoxically), to produce a /scientific statement/ or two: "There are true things that U can't prove (and if by proving you mean knowledge, so that scuttles an area of knowledge), and U can't prove that U don't have contradictions either :^) )
That Gödel ushered definite statements and proofs to these effects are, to my understanding , a Very Big Deal. It wasn't some political program, or a theory of aesthetics, or any subjective enterprise. No, it was knowledge.
>>8185060
What the fuck does "powerful enough to express arithmetic" mean?
Jesus, it's a math thread, be rigorous, please!
>>8186706
literally that. you're able to express arithmetic in your system.
>>8186706
It's one of those things where if you don't already know what it means, you're not ready for a formal definition.
>>8186124
True or false only have meaning within a system of axioms. CH may be true in some and false in others. In ZFC, it is impossible to prove like you said.
But my point is that thr CH can't just "be true" on its own. (Unless you make it an axiom.) It can only be true within some system.
>>8186768
In ZFC, it is impossible to prove **one way or the other**
>>8186640
Fucking A dude this sucked.
>>8185098
>>8185114
Tldr:
It is impossible to analyze the truth of the statement.
Mathematicians attempted to create a hierarchical system to prevent paradoxes like that from happening.
Godel proved that any system able to evaluate systems will contain these kinds of paradoxes, making previous attempts at eliminating them useless.
>>8186768
CH is false, truth and provability are different things. You should know this, you're posting in a Gödel thread.
>>8185092
how can you know they're true if they can't be proven/disproven?
>>8186848>>8186908
truth does not exist in formal systems for deduction. at best you have truth values
>>8186927
I believe what you're saying is meaningless
>>8186908
from wikipedia
> Gödel essentially constructed a formula that claims that it is unprovable in a given formal system. If it were provable, it would be false, which contradicts the idea that in a consistent system, provable statements are always true. Thus there will always be at least one true but unprovable statement. That is, for any computably enumerable set of axioms for arithmetic (that is, a set that can in principle be printed out by an idealized computer with unlimited resources), there is a formula that is true of arithmetic, but which is not provable in that system.
>>8186951
>claim to be rigorous
>is not rigorous
>>8186927
Truth doesn't have to exist in formal systems for it to exist. Even Gödel was a Platonist.
I only believe in empricism.
How can something be unprovable yet true?
>>8187761
>How can something be unprovable yet true?
If it's not provable and not disprovable, that doesn't mean it's neither true nor false. The existence of God can't be proven or disproven, and yet it is either a true or (obviously more likely) false concept.
>>8185118
Again, see:
>>8185096
>The continuum hypothesis if i remember correctly
For example, in conventional ZFC, it's an unanswerable question whether there exists a level of infinity between Naturals and Reals. In fact, someone mathematically proved this statement in ZFC.
Some mathematicians do work in ZFC plus CH.
In practice, it has some relevance for my field of computing. One consequence of this fact is that a decompiler is impossible in the general case. The Incompleteness Theorems and the Halting Problem are very closely related.
>>8185090
.999... = 1
>>8187761
> How can something be unprovable yet true?
Very easily. Why would you assume that any given formal system is complete (capable of proving any true statement)?
It's not hard to create a formal system which is provably incomplete. But not being provably incomplete isn't the same thing as being complete.
http://lesswrong.com/lw/93q/completeness_incompleteness_and_what_it_all_means/
>>8185041
That any formal system powerful enough will always be able to express theorems which are undecidable within the formal system. Thus the need to express new axioms will never run dry and the theory can therefore never be "completed".
>>8185090
Collatz' conjecture
>>8185041
Basically it says there are no program that can tell for all programs and all inputs if they will stop, hence for some program p and input i , the question "does p(i) stop ?" can not be answered.
>>8189086
what is CH?
there is an infinity between #N and #R
there is no infinity between #N and #R
>>8185041
>you can't know everyfin mah boi
>>8189272
>what is CH?
https://en.wikipedia.org/wiki/Continuum_hypothesis
