4 ms·
I’ve only ever seen examples like the one you give here, which seem like trite, trivial, and uninteresting middle-school level logical gotchas. Are there actual
by adastra22 4y ago
I’ve only ever seen examples like the one you give here, which seem like trite, trivial, and uninteresting middle-school level logical gotchas. Are there actually interesting properties which are true but can’t be proven? Or is it just a statement about self-referential recursive logic being unprovable?
- voldacar 4y ago>Are there actually interesting properties which are true but can’t be proven? Goodstein's theorem and the Paris-Harrington theorem are some examples of this for ZFC. There are several more, maybe a logician could chime in
- flebron 4y agoWell, most interesting properties about computer programs are, in general for all programs, undecidable (https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem). Undecidability is a closely related notion to unprovability (https://en.wikipedia.org/wiki/Undecidable_problem#Relationship_with_G%C3%B6del's_incompleteness_theorem) https://en.wikipedia.org/wiki/Undecidable_problem#Relationsh....
- thayne 4y agoI don't know if it is quite what you are looking for, but with the normal mathematical axioms, it isn't possible to prove whether or not the there are any sets with a cardinality between the cardinality of the natural numbers and the cardinality of the real numbers. But one of those two must be true, you just can't prove it. Of course you can add a new axiom that allows you to prove one or the other (or accept one of those statements as an axiom), but you will still have other statements that you can't prove.
- DontchaKnowit 4y agoThis is super interesting. Was not aware of this. Is there a proof that this is not provable?
- thayne 4y agoYes, Paul Cohen proved that the continuum hypothesis (that there is no set with cardinality between that of natural numbers and real numbers) was independent of the ZFC formulation of set theory (the most standard set of axioms used in today's set theory) in 1963.
- schoen 4y agoMore about this on Wikipedia: https://en.wikipedia.org/wiki/Continuum_hypothesis#Independence_from_ZFC https://en.wikipedia.org/wiki/Continuum_hypothesis#Independe... Also: https://en.wikipedia.org/wiki/Axiom_of_choice#Independence https://en.wikipedia.org/wiki/Axiom_of_choice#Independence And thanks to Wikipedia for this elaborate list: https://en.wikipedia.org/wiki/List_of_statements_independent_of_ZFC https://en.wikipedia.org/wiki/List_of_statements_independent...
- schoen 4y ago> But one of those two must be true, you just can't prove it. Three alternative accounts: * Both the CH and ¬CH mathematical universes really exist, so we just have to choose which one we're more interested in at a given time. Like one might say there are the "reall numbers" and the "realle numbers", both valid and interesting constructions which humanity was just slow to recognize the distinctions between (because they were initially less relevant to our interests and our day-to-day lives). * We are actually ultimately thinking about one or the other of them, or are in some sense in one or the other mathematical universe, but we don't know enough about our intuition about the reals to be able to specify or explain which one. (Maybe we need other properties whose obviousness or relevance humanity is not smart enough to notice?) * Some finitist or ultrafinitist approach is actually right: the real numbers are a formalism that, while reasonably motivated by historical attempts to "complete" mathematics in various ways, doesn't correspond to anything Platonically real or to anything intellectually relevant to humanity. (In this account, there is potentially no answer to the question because the real numbers don't exist at all. Neither CH nor ¬CH refers to a mathematical reality, just to games about formalisms.)
- thayne 4y agosure, but if you ignore any connection to the real world or platonic truth and are just talking about within the ZFC formalism, then `CH ∨ ¬CH` is a true statement, even though it is impossible to prove either `CH` or `¬CH`.
- chriswarbo 4y ago> within the ZFC formalism, then `CH ∨ ¬CH` is a true statement It's also a provable statement (via excluded middle)
- memetomancer 4y agoInteresting take. You have casually dismissed the Goldbach Conjecture (perhaps the deepest centuries old problem in number theory) as 'trite, trivial and uninteresting'... Suggesting that you are only minimally familiar with the issue... then toss about an inapplicable phrase 'self-referential recursive logic' as if you are deeply immersed in such matters, perhaps even _much_ smarter than the thousands of mathematicians (including the likes of Euler) that have applied themselves to this problem. An odd contradiction! I do believe this opinion places you very high on the 'confidence' axis, but not especially far along the 'competence' axis.
- adastra22 4y agoI was talking about Gödel, not Goldbach: > The proof of Gödel's result's involves very carefully formalizing what statements and proofs mean so that they can be encoded as statements about arithmetic. He then shows there is a statement with encoding G that says "The statement with encoding G cannot be proved" – if it is true, then it cannot be proved. Sorry I meant to quote this bit at the beginning of my comment. Parent comment which I was replying to talks about both.
- ColinWright 4y agoI'm late to the party, so I'm not sure you'll see this. Hope you do. Different people will each have their own contexts and their own concepts of "useful" or "interesting". I'm making assumptions about yours ... apologies if I misrepresent you. The proof of Gödel's result uses the paradoxical statement "This statement is false", but that's being used to prove this very general result about all systems. So the hunt is then on to find "natural" statements that are True but Unprovable. But the "unprovable" bit should more completely be stated as "unprovable in a specific axiomatic proof system". If we want to prove that statement S is "True but Unprovable" then we must actually prove that it's true. So if we've proved it's true, what does it mean to say it's unprovable? We just proved it! What's going on? So let's take a specific example. Peano Arithmetic (PA)[0] is an axiomatic proof system intended to capture Natural Numbers and their behaviour. The "Goodstein Sequence" G(m) of a number m is a sequence of natural numbers ... you can find the definition here[1]. It's not hard, but it's longer than I want to reproduce here. Goodstein's Theorem (GT) says that for every integer m greater than 0, G(m) is eventually zero. It has been proven that GT cannot be proved in PA, but it can be proved in stronger systems, such as second-order arithmetic. So the statement of GT is not self-referential, along the lines of "This Statement Is False" sort of thing. It's an actual statement about the behaviour of integers, so it's not a self-referential trick. Your question now is: What's the point? How is this useful or relevant? Much of modern (pure) mathematics is chasing things because the mathematicians find them interesting. The vast, vast majority will never, of themselves, be useful by (what I expect are) your standards. But it was once thought that factoring integers was of no practical use, and only pursued or investigated by cranks. Imaginary Numbers were thought to be bizarre, useless, and dangerous. Non-Euclidean Geometry was thought to be utter nonsense, and held up as part of the "proof" that the fifth postulate was unnecessary and was deducible from the other four. All three of these now form critical components in modern technology. Even more, to the average person on the street, anything to do with algebra is completely pointless. For you, Gödel's theorem is completely pointless and useless and probably of no interest at all, but it helps us understand the limitations of formal systems. The techniques that have been developed in the time since it was proved have helped us understand more about what computer verification systems might or might not be able to accomplish. Of itself, Gödel's theorem might not be of direct, immediate, and practical use, but the work it has inspired has tangentially been useful, and may yet be moreso. But not for everyone. After all, some people don't care about the Mona Lisa, or Beethoven's Fifth Symphony, or Michaelangelo's David, or the fact that people have walked on the Moon, so why should people care about results in Pure Mathematics? That's the thing about Pure Mathematics. Sometimes it ends up being useful in ways we never expected. [0] https://en.wikipedia.org/wiki/Peano_axioms https://en.wikipedia.org/wiki/Peano_axioms [1] https://en.wikipedia.org/wiki/Goodstein's_theorem#Goodstein_sequences https://en.wikipedia.org/wiki/Goodstein's_theorem#Goodstein_...
- Tainnor 4y agoThere are examples of "natural" sentences which are unprovable in Peano Arithmetic (which is one of the simpler systems for which Gödel's theorems apply): https://en.m.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem https://en.m.wikipedia.org/wiki/Paris%E2%80%93Harrington_the... But in general, Gödel applies to all formal systems that satisfy certain properties, it's just that the exact unprovable sentences will be different (since you may just add that sentence as an axiom) that's why the general example is very abstract. It shows that sufficiently rich theories are not only incomplete, but also incompletable.
- machina_ex_deus 4y agoThe Continuum hypothesis is independent of ZFC. It is the first of Hilbert's 23 problems.
- wikfwikf 4y agoThis is the best example - before it was shown that the Continuum Hypothesis was unprovable, many people believed, like the GP, that only uninteresting and artificial statements could be shown to be unprovable. The CH is undoubtedly meaningful, natural, and of huge interest to (a subset of) mathematicians.
- adastra22 4y agoWhat are the practical applications of CH?
- SamBam 4y agoAt this point I feel like you're going from a reasonable question about Godel's theorem to cranky person unwilling to see how any math that doesn't explain how to fly a 747 is relevant to the world. There are huge branches of mathematics that don't find immediate practicality in physics. Often these end up being practical in cryptography or quantum mechanics, but sometimes they don't. But to dismiss the entire field that relates to the cardinality of real numbers as uninteresting if someone can't give you a practical application of it shows a simple disregard for other fields of study.
- wikfwikf 4y agolol
- adastra22 4y agoWhat was funny?
- red_trumpet 4y agoWikipedia has a list[1] of statements which are not provable in (or rather independent of) ZFC. IMO the most weird thing is the following, intertwining consistency of ZFC with Diophantine equations[2]: > One can write down a concrete polynomial p ∈ Z[x1, ..., x9] such that the statement "there are integers m1, ..., m9 with p(m1, ..., m9) = 0" can neither be proven nor disproven in ZFC (assuming ZFC is consistent). [...] the polynomial is constructed so that it has an integer root if and only if ZFC is inconsistent. [1] https://en.wikipedia.org/wiki/List_of_statements_independent_of_ZFC https://en.wikipedia.org/wiki/List_of_statements_independent... [2] https://en.wikipedia.org/wiki/List_of_statements_independent_of_ZFC#Number_theory https://en.wikipedia.org/wiki/List_of_statements_independent...
- gsinclair 4y agoMy understanding is this: Gödel proved his earth shattering result in the 1930s. Then the dust settled and mathematicians thought it might be “academic” and that mathematics might not come tumbling down after all. Then in the 1960s Paul Cohen proves that the continuum hypothesis is undecidable. That is, we will never know whether an infinite set can have a cardinality between the natural numbers and the real numbers. My understanding comes from Keith Devlin’s wonderful book “Mathematics: A new golden age”.
- butokai 4y agoHarvey Friedman, one of the most renowned contemporary logicians, has a research program devoted to finding such examples as those you seem to be looking for. This article presents his views: https://nautil.us/this-man-is-about-to-blow-up-mathematics-236446/ https://nautil.us/this-man-is-about-to-blow-up-mathematics-2...