5 ms·

A common misconception in the first paragraph: > However, Godel shattered these aspirations in 1931 by proving the existence of true but unprovable mathematica

by tybug 3y ago

A common misconception in the first paragraph: > However, Godel shattered these aspirations in 1931 by proving the existence of true but unprovable mathematical formulas. Godel sentences are unprovable, but they are not "true". They are independent, i.e. true in some models and false in others. The godel sentence happens to be true in the standard model - some people take liberties with this and extend to calling it true, but that's not accurate, or at the very least misleading.

zokier 3y ago
> true in some models and false in others Isn't that the case for pretty much everything that you can twist them in any direction by the choice of axioms? https://xkcd.com/704/ https://xkcd.com/704/
- mananaysiempre 3y ago
  >> true in some models and false in others > Isn't that the case for pretty much everything that you can twist them in any direction by the choice of axioms? By models in this context are usually meant models of this one particular set of axioms you’re talking about at the moment (considered in some sort of ambient metatheory that isn’t always spelled out explicitly but you can go in that direction too if you want). For example, you can construct a model of PA in ZF that is morally { {}, {{}}, {{{}}}, ... } for the elements (that was not a syntactically valid formula in ZF, but you can prove a critter that is intuitively described by it exists nevertheless) and x \mapsto {x} for the successor, even though PA says nothing about sets, functions, or anything of that sort. Basically, for “model” read “implementation” (an “interpretation” of a thing within another thing is a synonymous term that actual logicians occasionally use). (And yes, there are models of PA inside ZF that are substantially different from that one[1].) [1] https://golem.ph.utexas.edu/category/2019/06/nonstandard_models_of_arithmet.html https://golem.ph.utexas.edu/category/2019/06/nonstandard_mod...
isaacfrond 3y ago
It's exactly that point that I've never understood. Please elaborate. What is the 'standard model'?
- H8crilA 3y ago
  The model of natural numbers with addition and multiplication that we intuitively understand as the correct one. As Godel showed you can't actually describe this model in first order logic (Skolem-Lowenheim further shows how hopeless we are in describing the model). "Every child knows what natural numbers actually are".
  - lisper 3y ago
    More concretely: you can add an axiom to standard PA that says, "There exists a number that is the Godel number of a proof of G." The resulting system is consistent, and includes a new kind of number that is not a natural number (because you can prove that N is not a proof of G for any N that is a natural number). It's analogous to adding an axiom that says, "There exists a number whose successor is 0", which introduces a new kind of number that we call "negative numbers." Math is extended in familiar interesting directions like this all the time by adding axioms like "There exists a number whose square is 2" (which gives you irrational numbers) or "there exists a number such that the successor of its square is 0" (which gives you imaginary numbers).
    - Y_Y 3y ago
      You didn't say otherwise, but it's interesting to note that the irrationals is quite "big" in the sense that you can do a lot without them. Not only can you make a nice consistent extension of usual structures on N, Z, Q etc by just adding sqrt(2), you can even add all square roots, or all n-th roots, or the solutions to all polynomials without getting plenty of good irrationals. Sets between Q and R are often neglected, but there's a wealth of good maths in there.
denotational 3y ago
“True in the standard model” is generally what most working mathematicians who are not logicians mean by “true”.
- tybug 3y ago
  No disagreement here. But I hold that this is an especially confusing way of describing independent statements, especially in this paper, which certainly was written by a logician. I take particular issue with the phrasing because it confused me for years in highschool and throughout undergraduate. How could something be true and not provable? It took me until a model theory course to realize that it cannot, and most pop descriptions of the incompleteness theorem are - dare I say it - wrong. Though I'm sure you would argue it's not wrong, merely an informal description. I would, however, expect a bachelor's thesis not to stray into such confusing territory.
loicd 3y ago
Exactly. A statement is true by definition if and only if it is satisfied in every model. Also, Gödel also proved the completeness theorem that states that a statement is true if and only if it is provable. So, another way to look at undecidability is this: a statement is undecidable if and only if it can be neither proved nor disproved.
- Y_Y 3y ago
  Can you give an example of a nontrivial statement that's true in every model?
  - loicd 3y ago
    If you don't have any axioms, the statements that are true in every model are exactly the tautologies (by definition). Usually though, one is interested in a particular set of axioms, typically ZFC. Then "every model" implicitely means "every model of ZFC", so "true" statements are the statements that are true in every model of ZFC, or equivalently by Gödel's completeness theorem, the statements that are provable from the axioms ZFC (and only ZFC). As for examples of such statements, well, that's virtually all mathematics. (The use of exotic axioms is quite specialized within mathematics.)
    - Y_Y 3y ago
      Now you're moving the goalposts! You can't claim that's it's even "widely accepted" that the axiom of choice is "true". I can see this as a fine way of distinguishing DeMorgan's laws from the continuum hypothesis, but the meaning of "true" is a stickier subject.
      - loicd 3y ago
        > You can't claim that's it's even "widely accepted" that the axiom of choice is "true". I have never claimed anything like that. The original comment was a reaction to the notion of "true but unprovable" which is wrong because what is true is precisely what is provable. You may have an intuitive notion of "true", but with logic, the devil is in the details. In my experience, it is better to stick to the mathematical definitions, especially when talking about things like the incompleteness theorem. Now, the mathematical notions are as follows. First, you agree on some deduction rules, then some axioms (aka a theory), and by definition, what is true is what is satisfied by every model of the theory. A completeness theorem is then a theorem that states that what is true is precisely what is provable. (Proved by Gödel for classical logic.) Of course, you may disagree with the choice of axioms. However, when introducing a new axiom, mathematicians don't argue whether it is "true" or not, they have to justify in one way or another that it is relatively consistent. The same thing is true for the deduction rules. In other words, consistency, not truth, is the right metric for axioms and deduction rules. Finally, observe that mathematicians who argue against the axiom of choice or the law of excluded middle do not claim that these are false, they claim that these are not constructive. Yet another notion not to be confused with truth.
ttctciyf 3y ago
Isn't the claimed "truth" based on an appeal to a more intuitive notion of truth than a formal model-relative one? The Godel sentence for some Formal Axiomatic System asserts, by way of numerical encoding, its own unprovability in that FAS, and since it in fact cannot be proven in the FAS it is "true" in the sense that it asserts (via its numerical encoding) something which is in fact the case, i.e. just the ordinary sense of "true".

by tybug 3y ago

zokier 3y ago

> true in some models and false in others Isn't that the case for pretty much everything that you can twist them in any direction by the choice of axioms? https://xkcd.com/704/ https://xkcd.com/704/

mananaysiempre 3y ago
>> true in some models and false in others > Isn't that the case for pretty much everything that you can twist them in any direction by the choice of axioms? By models in this context are usually meant models of this one particular set of axioms you’re talking about at the moment (considered in some sort of ambient metatheory that isn’t always spelled out explicitly but you can go in that direction too if you want). For example, you can construct a model of PA in ZF that is morally { {}, {{}}, {{{}}}, ... } for the elements (that was not a syntactically valid formula in ZF, but you can prove a critter that is intuitively described by it exists nevertheless) and x \mapsto {x} for the successor, even though PA says nothing about sets, functions, or anything of that sort. Basically, for “model” read “implementation” (an “interpretation” of a thing within another thing is a synonymous term that actual logicians occasionally use). (And yes, there are models of PA inside ZF that are substantially different from that one[1].) [1] https://golem.ph.utexas.edu/category/2019/06/nonstandard_models_of_arithmet.html https://golem.ph.utexas.edu/category/2019/06/nonstandard_mod...

isaacfrond 3y ago

It's exactly that point that I've never understood. Please elaborate. What is the 'standard model'?

H8crilA 3y ago
The model of natural numbers with addition and multiplication that we intuitively understand as the correct one. As Godel showed you can't actually describe this model in first order logic (Skolem-Lowenheim further shows how hopeless we are in describing the model). "Every child knows what natural numbers actually are".
- lisper 3y ago
  More concretely: you can add an axiom to standard PA that says, "There exists a number that is the Godel number of a proof of G." The resulting system is consistent, and includes a new kind of number that is not a natural number (because you can prove that N is not a proof of G for any N that is a natural number). It's analogous to adding an axiom that says, "There exists a number whose successor is 0", which introduces a new kind of number that we call "negative numbers." Math is extended in familiar interesting directions like this all the time by adding axioms like "There exists a number whose square is 2" (which gives you irrational numbers) or "there exists a number such that the successor of its square is 0" (which gives you imaginary numbers).
  - Y_Y 3y ago
    You didn't say otherwise, but it's interesting to note that the irrationals is quite "big" in the sense that you can do a lot without them. Not only can you make a nice consistent extension of usual structures on N, Z, Q etc by just adding sqrt(2), you can even add all square roots, or all n-th roots, or the solutions to all polynomials without getting plenty of good irrationals. Sets between Q and R are often neglected, but there's a wealth of good maths in there.

denotational 3y ago

“True in the standard model” is generally what most working mathematicians who are not logicians mean by “true”.

tybug 3y ago
No disagreement here. But I hold that this is an especially confusing way of describing independent statements, especially in this paper, which certainly was written by a logician. I take particular issue with the phrasing because it confused me for years in highschool and throughout undergraduate. How could something be true and not provable? It took me until a model theory course to realize that it cannot, and most pop descriptions of the incompleteness theorem are - dare I say it - wrong. Though I'm sure you would argue it's not wrong, merely an informal description. I would, however, expect a bachelor's thesis not to stray into such confusing territory.

loicd 3y ago

Exactly. A statement is true by definition if and only if it is satisfied in every model. Also, Gödel also proved the completeness theorem that states that a statement is true if and only if it is provable. So, another way to look at undecidability is this: a statement is undecidable if and only if it can be neither proved nor disproved.

Y_Y 3y ago
Can you give an example of a nontrivial statement that's true in every model?
- loicd 3y ago
  If you don't have any axioms, the statements that are true in every model are exactly the tautologies (by definition). Usually though, one is interested in a particular set of axioms, typically ZFC. Then "every model" implicitely means "every model of ZFC", so "true" statements are the statements that are true in every model of ZFC, or equivalently by Gödel's completeness theorem, the statements that are provable from the axioms ZFC (and only ZFC). As for examples of such statements, well, that's virtually all mathematics. (The use of exotic axioms is quite specialized within mathematics.)
  - Y_Y 3y ago
    Now you're moving the goalposts! You can't claim that's it's even "widely accepted" that the axiom of choice is "true". I can see this as a fine way of distinguishing DeMorgan's laws from the continuum hypothesis, but the meaning of "true" is a stickier subject.
    - loicd 3y ago
      > You can't claim that's it's even "widely accepted" that the axiom of choice is "true". I have never claimed anything like that. The original comment was a reaction to the notion of "true but unprovable" which is wrong because what is true is precisely what is provable. You may have an intuitive notion of "true", but with logic, the devil is in the details. In my experience, it is better to stick to the mathematical definitions, especially when talking about things like the incompleteness theorem. Now, the mathematical notions are as follows. First, you agree on some deduction rules, then some axioms (aka a theory), and by definition, what is true is what is satisfied by every model of the theory. A completeness theorem is then a theorem that states that what is true is precisely what is provable. (Proved by Gödel for classical logic.) Of course, you may disagree with the choice of axioms. However, when introducing a new axiom, mathematicians don't argue whether it is "true" or not, they have to justify in one way or another that it is relatively consistent. The same thing is true for the deduction rules. In other words, consistency, not truth, is the right metric for axioms and deduction rules. Finally, observe that mathematicians who argue against the axiom of choice or the law of excluded middle do not claim that these are false, they claim that these are not constructive. Yet another notion not to be confused with truth.

ttctciyf 3y ago

Isn't the claimed "truth" based on an appeal to a more intuitive notion of truth than a formal model-relative one? The Godel sentence for some Formal Axiomatic System asserts, by way of numerical encoding, its own unprovability in that FAS, and since it in fact cannot be proven in the FAS it is "true" in the sense that it asserts (via its numerical encoding) something which is in fact the case, i.e. just the ordinary sense of "true".