#mathematic #computing #computation # [[Epistemic status]] #schroedinger-uncertain # Related - [[Noether theorem]] - [[Kurt Gödel - On Formally Undecidable Propositions of Principia Mathematica and Related Systems|Kurt Gödel]] # Godel Theorem ![[DALL·E 2022-08-24 21.34.30 - The Church-Turing discovery of uncomputable functions is closely related to the discovery by the logician __Kurt Gödel__ that some theorems of arithme.png]] #todo history [[Hilbert]] [[Entscheidungsproblem]] -> [[Godel Theorem|Godel]] -> [[Turing]] >The Church-Turing discovery of uncomputable functions is closely related to the discovery by the logician **Kurt Gödel** that some theorems of arithmetic are undecidable, meaning that they **can neither be proved nor disproved in a finite number of steps.** >~ [[Max Tegmark]] ![[DALL·E 2022-06-18 19.40.27 - The ever incomplete information game played by men, surrealist, by Escher.png]] A [[Turing machine]] can solve a theorem using an [[Algorithm]] in a finite or infinite number of steps, the problem of whether it will be infinite is called the [[Halting problem]]. ![[IMG_20210904_120557.jpg]] From [[lesswrong.com]] Impossibility to find complete and consistent set of axioms for all mathematics. [[Truth]] and provability is not the same thing. There will always be true statement about [[Mathematic]] that cannot be proven. [[Mathematic]] is undecidable. ![[DALL·E 2022-08-24 21.34.52 - The Church-Turing discovery of uncomputable functions is closely related to the discovery by the logician __Kurt Gödel__ that some theorems of arithme.png]] [Theorem v2 white paper](https://monoskop.org/images/9/93/Kurt_G%C3%B6del_On_Formally_Undecidable_Propositions_of_Principia_Mathematica_and_Related_Systems_1992.pdf) [[Douglas R. Hofstadter - Godel, Escher, Bach_ an Eternal Golden Braid-Basic Books]] [Interesting paper on Godel](https://arxiv.org/pdf/1502.04135.pdf) >A scientific theory is just a mathematical model we make to describe our observations: it exists only in our minds. So it is meaningless to ask: which is real, “real” or “imaginary” time? It is simply a matter of **which is the more useful description**. ~ [[Hawking]] # More mathematical interpretation Some [[Mathematic]] branches have limited proof recursion There is decidable theories There is undecidable theories (Boolean algebra?) #work-in-progress <iframe width="560" height="315" src="https://www.youtube.com/embed/w11mI67R95I" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> # [[GPT3]] A set of formulas is consistent if for every sentence of this set, it is possible to prove it or disprove it. Therefore, a set of formulas is consistent if and only if it contains a sentence which is false but cannot be disproved. Gödel proved that no system can be complete: no matter how many statements are added, you can always find a statement that cannot be proved from the axioms by which we have defined our proofs. This is known as Godel's incompleteness theorem. In particular, the sentence "Pythagoras was wrong" cannot be proven from our axioms (because the axioms don't include "Pythagoras") so it can't be said to be true or false either (because neither of these would disprove the theorem). If we tried to prove it true or false, we would have to add axioms like Pythagoras' theorem or its negation; but then the system would already be complete and therefore there would not have been any incompleteness at all! It is therefore clear that no system can ever be complete for this reason; one may claim that this situation is an artefact of Gödel's formalisation and that he was mistaken, but there is nothing in mathematics per se to suggest that this should not be the case either. There is no formal system which contains all of mathematics (or even all of physics), so there must be some sentences which can't be proven from all the axioms and therefore can't be proved or disproved. In other words, there are sentences in the mathematical universe that are true and false at the same time. These are known as Contradictions. Some of them are well known, such as "0 equals 1", or "2 is greater than 1". Others are not so well known, such as "The square root of 2 is equal to (1/sqrt(2))+sqrt(2)". None of these are provable from any set of axioms we can think of. And yet, if you tried to prove any of them false, you could be forced to add more and more axioms and eventually your proof might well become as long as the complete system! If this seems far-fetched - consider that the sentence "If we build a bomb it will explode" is true but unprovable. This particular situation is an example of a mathematical metaphor being applied to a physical phenomenon. The field of quantum mechanics centres around the idea that there is no absolute truth about the state of a physical system - for example it is impossible to be certain that I am asleep or awake. This was considered a massive break with the idea that physics must obey certain axioms which were held to be true for all time - this has now been replaced by the more subtle worldview of quantum mechanics in which all one can say about the state of a system at a given time is probability. This may seem like an odd thing to say when there is no way to prove it true or false, but it turns out to be very useful because it means one can prove things about systems that are not currently known. It has been proven that no consistent set of axioms (of the sort we have defined) can ever include two contradictory sentences. So there are always some sentences which are true and false at the same time; but this does not mean they cannot be proven from our axioms - they can only be proven false by including new axioms (which might make our system inconsistent). This leads us to the following definition: A set of formulas S is consistent if, and only if, there exists an interpretation I where all S are true and some other S are false. Now we can define truth relative to an interpretation: P is true relative I if, and only if, I includes P. In other words, P is true relative I if P is included in I, or hasn't been excluded from I. This definition allows us to deal with our metaphorical metaphor by assuming that in some context C every sentence about C is always true relative C. For example, we might say that in some context C "The square root of 2 equals 1 + (1/sqrt(2))" always holds regardless of what values we give for sqrt(2). In fact this particular sentence was chosen precisely because it never changes whether it is true relative C or not: its meaning doesn't change depending on what assumptions we make about C! It's therefore called a Tautology: A formula S is a tautology relative I iff S holds relative I for every interpretation I which contains all the relevant sentences contained in S. In mathematics this means that S must hold relative I for every possible assignment of values for each symbol contained in S. Equivalently it means that no matter how each symbol gets interpreted - because different interpretations correspond to different worlds - it will always be true relative I. In other words, any world which contains all the symbols in S contains S as well. Consider again the statement "If we build a bomb then it will explode" - although it seems unprovable and therefore may seem paradoxical even after many generations of people working on it - it doesn't mean anything different given any possible world C different than our own! It's still true relative C in every possible way, so once again we can't disprove it without adding new axioms or making contrary statements! We've now seen how Gödel's incompleteness theorem applies in mathematics: sentences can be true/false under different interpretations; but if we follow Gödel's rules correctly then all contradictory sentences must also be proved true relative to some interpretation; furthermore, if we have found contradictory sentences then our system must have become inconsistent (it must have proved one thing and then proved something else which was already proved) and therefore must contain a contradiction somewhere which our proof has failed to find! Gödel's theorem tells us that no consistent mathematical system can ever prove both "every square root is irrational" and "every square root has an integer square root". From these two propositions one cannot prove anything else because they contradict each other! Indeed, any such proof would itself entail both propositions since they both hold relative such a proof (and therefore they would both hold relative everything else too). But this means that one cannot prove anything without adding axioms! Therefore there are statements which cannot be proven or disproved using any consistent mathematical system; meaning there must be statements which are simultaneously true and false - contradictions! Thus mathematical truths are subject to revision: after contradiction proofs may be added; but new proofs may turn out not to work when applied further down the line leading back to earlier proved truths... And so on: like ripples spreading out through water from an initial splash! The mathematical world behaves like a finite automaton where new states keep arising but at some point every ripple hits an edge and spreads out infinitely forming a fractal pattern until everything eventually collapses in on itself (if indeed anything does...) But now consider another type of contradiction: suppose someone says "I believe in God". You might want to ask them what they mean! They might reply "I believe that a god exists, and I believe that a god doesn't exist; and I believe that if a god exists then my name is Brian, and if a god doesn't exist then my name is Alice". All of these statements may be true relative to different interpretations, but how can they all be true at the same time? The first two are contradictory! This is a very different situation than our mathematical one: if someone says "I believe in God" it doesn't follow that they think "There is a God" or "There isn't a God", or that "My name is Brian" or "My name is Alice". Instead it means precisely one thing: that it's possible for a god to exist (or not exist) and for my name to be Brian (or Alice). In other words, the first sentence only makes sense relative to an interpretation which assumes both possibilities: the second sentence only makes sense relative to an interpretation which assumes the opposite. Hence they cannot both be true relative to the same interpretation: their truth depends on which other sentences you interpret them relative to! So how do we deal with this situation? Clearly it's impossible to prove anything about these statements just by adding more axioms; so somehow we have to find some way of choosing the right interpretation - otherwise we could never prove anything about these statements! But since the statements are contradictory there must be some set of interpretations which make one false and another true - this would mean there must be some set of interpretations where both can be true! Somehow we have to find this set of interpretations. We do this by defining truth as follows. A statement S is true relative I iff, relative I, all S are true. Here's an example: suppose someone says "I'm happy". This might mean they're happy today; or maybe they're happy in general; or maybe it means they're always happy. When someone says "I'm happy" they don't want to tell you whether they're happy today or in general - what they want to say is simply "it's possible for me to be happy" - i.e. if I interpret their statement relative to any possible world C then C must contain at least one possible world where I am happy. Saying "I'm happy" has no meaning unless it can be interpreted in such a way. So here's how we interpret it: "If you interpret my statement relative to any world C then at least one world contained in C must contain me being happy". In other words, the statement "I'm happy" is true relative any world C iff, relative every world C, I am happy. That makes sense, so we accept it as an axiom. What happens next? Well since we've defined truth as above it follows that every sentence P is false relative I iff all P are false relative I (because then all P will be false relative any interpretation). Now suppose S is false relative I. Then there must exist some world C contained in I where S is false (because otherwise S would have been true). This means that we've shown that S must have been true at least once during our proof! But this means that S cannot have been false throughout our proof and therefore it must have been true from the start! Which means we've proven our theorem! So let's sum up what's happened: firstly we've proved that no consistent mathematical system can prove both "every square root is irrational" and "every square root has an integer square root"; secondly we've defined truth so that whenever two statements are contradictory then there must exist some set of interpretations where one statement is true and the other statement is false (and therefore both are false); finally we've proven that no consistent mathematical system can prove both "every square root is irrational" and "every square root has an integer square root"! Now consider another type of contradiction: suppose you're standing next to me on a railway platform and you think "I wonder what time the train leaves?" Since you know nothing about trains you can only ask questions like "do you know when the next train leaves?" or "what time does the train leave?" Since I know nothing about trains either I might respond with either a yes or no answer via some probability distribution over all the possible train times; i.e. I might say 2pm tomorrow or 8pm today with some probability but not both simultaneously because this would be a logical paradox (since clearly 2pm tomorrow and 8pm today cannot both be correct). If however I did reply with both at once then you would conclude that either 1) I was lying (in which case everything you thought you knew about trains was wrong) or 2) something had gone horribly wrong with your assumptions about trains (in which case you would conclude your question had led you on a wild goose chase). Either way there would definitely *not* be logical paradoxes involving trains... Now let us consider another type of contradiction: suppose there exists an infinite number of worlds exactly like our own except that different people live in them (different names etc.). We call this collection of worlds Population P. Since each person in Population P can only observe things which happen within their own population (as far as they know), hence everyone thinks everyone else has exactly the same name as themselves and exactly the same age as themselves regardless of what actually happens within Population P - after all, when they look around at everyone else their feelings towards those others will be unchanged regardless of what moves within Population P because they only see themselves through others' eyes. We call this population Population P'. If we assume that each person in Population P' can only observe things which happen within their own population (as far as they know) then we can also assume that Population P' is a world just like our own except that different people live in it. And therefore there must be one world exactly like our own except that it contains a person called Alice who is - say - 5 years older than the Alice in Population P. Since the age difference is only 5 years it doesn't matter what name we give to this person (e.g. "Fred") since we know that no-one else in Population P' knows of this person so they will still be able to see Alice just as they remember her and hence they will still think she's the same age as they remember her being (old age has not affected their memory of young Alice). So if we were to ask someone in Population P' whether "Alice is older than 5" they would say "yes" and if asked if "Alice is younger than 5" they would say "no". So for all intents and purposes the two worlds are identical! This means that although from a logical point of view everything is fine, from an intuitive point of view the two worlds are not the same and so any contradiction between them *must* be wrong! Indeed, from an intuitive point of view there *can't* be a contradiction between them since you can't have two different but identical worlds. So all contradictions are false! In other words, one might say "All contradictions are false" and by saying this, one has shown that logic cannot be replaced by intuition - or rather that logic can only be replaced by logic, not intuition. In fact, one might even go further and claim that any system which contains contradictions cannot be complete: no complete system can contain contradictions! The reader may object: "But what if you're given contradictory information?" They may for example say "I know I'm standing next to you but I can't see you; I know I'm on my own but I hear other people talking." In such a case I would just tell them "That's because your assumption was wrong!" and then change my assumptions to suit their new observations: assuming now that I'm talking to someone else won't work because you can't see me; assuming now that I'm alone won't work either because you can hear me; so now suppose I tell you that "There's someone else here too" which means you now know there's someone else here who isn't me; which means I must therefore be talking to someone else and so now I'm talking to them instead; since I know you're next to me it must mean they're on my other side - i.e. I must be talking to you; therefore I mustn't be alone; therefore there must be two people here!" It's worth pointing out at this point that although this argument sounds like a contradiction it is actually not a paradox: it doesn't involve both true and false statements being said at the same time, so it doesn't contradict itself! It does however seem very strange indeed: if the left hand statement is true then it should make all of the right hand arguments false! But this is where intuition fails again: according to intuition if something looks like a paradox then it has to be wrong somewhere - for example, if a train has ten wheels then it can't go fast; but according to intuition no train could ever have 10 wheels (or any number of wheels) since trains are always moving at speeds slower than 10 miles per hour... Here is another example: suppose B says "I believe in God". Suppose A says B believes in God with certainty and C says B believes in God with uncertainty (the uncertainty being indicated using the symbol $\varepsilon$). Now suppose D says "God exists". What does A conclude? Should she conclude that B believes with certainty in God or should she conclude that B believes with uncertainty in God? The truth is quite straightforward: since A knows nothing about B she knows nothing about what he believes - so she should conclude what B believes with certainty, i.e. he believes with certainty in God! But her statement implies otherwise: if A knew B believed with certainty in God then she would have known this from the start so her statement wouldn't have needed making... This leads us to another contradiction: A cannot know B believes with certainty in God while simultaneously knowing nothing about him - unless B believes with certainty in God, but A knows nothing about him yet has concluded he believes with certainty in God! Which means A's statement implies both knowledge and non-knowledge simultaneously! Which leads us back to our first contradiction: A's statement cannot be true relative to any possible interpretation where all interpretations contain exactly the same information about B! So far we have been defining truth as follows: S is true relative I iff all S are true relative I. We've seen how this leads us into lots of trouble when interpreting statements relative to different interpretations where some sentences may appear contradictory relative some interpretations but not relative others. But what if we defined truth differently? Let's define truth as follows: S is true relative I iff S could never have been false relative any world containing all relevant information about all sentences relevant for interpreting S relative I (i.e. C contains all relevant information for interpreting S relative C). ![[daf26196-2d20-4fd3-93cb-3b31f1f46afd-0-3625184233.png]] Similar topics Wikipedia URLs: - en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems - https://en.wikipedia.org/wiki/Logical_truth - https://en.wikipedia.org/wiki/Truth_value - https://en.wikipedia.org/wiki/Semantic_paradox