191–200 of 252 posts
Intellectually poor man's attempt at a summary of the summary: Part 1 - math proof that a formal system when evaluated by an agent "breaking out of the system" can use that system to prove itself inconsistent. ("f* up" the internal logic of that system by feeding it into itself) Part 2 - ironically, to be conscious you have to have an awareness of your own system (a "strange loop") but you'll never be able to underst…
Earlier quoted context omitted.
I 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. Pa…
wait, so you are casually dismissing Gödel's work as a logical "gotcha"? don't premise opinions about complex proofs on other peoples woefully impoverished and misrepresented explanations of said proofs that is disrespectful and very very very short sighted. also, go read up (...on Gödel, Cantor, Turing, Tarski, etc...)
> Gödel's Incompleteness Theorem: any sufficiently rich formal system, together with an interpretation, has strings which are true but unprovable. This is only half of it! Gödel's Incompleteness Theorem states that any sufficiently rich formal system, together with an interpretation, either has strings which are true but unprovable or has strings which are provable but untrue. Either is possible! In practice people p…
Am I the only one who did not find this book that interesting? I studied CS so it just felt like reading my class textbooks again, except with random trippy stories in between that try to shoehorn theory into a poor metaphor. The fundamentals of CS (strings, automata, graphs) are elementary building blocks. This is by design. You can apply them to almost anything. Almost everything "is a graph", or "recursion" if you…
Earlier quoted context omitted.
It might be easiest to give a sense of what "unprovable but true" means by way of an imagined example. Goldbach's conjecture is that "every even number bigger than 2 is the sum of exactly two prime numbers", so 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, etc. For this statement to be *true* it just means that every even number there must exist two primes that add to that number. This is a statement about infinitely many integer…
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?
My understanding comes from Keith Devlin’s wonderful book “Mathematics: A new golden age”.
Earlier quoted context omitted.
That's a good intuition for first order PA, where the completeness theorem holds, but not the full story either. PA in second order logic only has a single model, but is still incomplete: there are statements that are true in the only model, but not provable.
Yeah but second order logic itself is incomplete. ZFC doesn't have a single model, too, btw. In the end unprovable sentences exist because there are multiple models satisfying your axioms.
Concerning multiple models of ZFC: I'm always confused by such statements about the foundations of set theory itself, they seem weirdly self-referential. ZFC certainly can't prove that it has multiple (or even any) models. Does such a statement need additional axioms, or is there a general theorem like "If a first order theory has any model, then it has multiple ones."?
Earlier quoted context omitted.
The central thesis of GEB is this: what is a self? From the preface of the 20th anniversary edition: "GEB is a very personal attempt to say how it is that animate beings can come out of inanimate matter. What is a self, and how can a self come out of stuff that is as selfless as a stone or a puddle?"
It is interesting to me that the author would start at the materialist assumption. Most people take it as a “given”, but I have softened to the idea that maybe it is not a correct or complete way of viewing things.
Earlier quoted context omitted.
It might be easiest to give a sense of what "unprovable but true" means by way of an imagined example. Goldbach's conjecture is that "every even number bigger than 2 is the sum of exactly two prime numbers", so 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, etc. For this statement to be *true* it just means that every even number there must exist two primes that add to that number. This is a statement about infinitely many integer…
What do we actually mean by saying "statement S is unprovable"? Do we mean "there is no prove for S" (which includes the case that S is provably false), or do we mean "there is no proof for S and there is no proof for its converse"? Because if you show that the converse of Goldbach's conjecture is not provable, you have actually proven Goldbach's conjecture (since you have shown that there is no counterexample!). >Th…
By “converse” I think you mean “negation”.
A statement being unprovable means we will never know whether it is this or false. > Because if you show that the converse of Goldbach's conjecture is not provable, you have actually proven Goldbach's conjecture (since you have shown that there is no counterexample!).
Nope: demonstrating that (the opposite of Goldbach’s conjecture) is unprovable is logically equivalent to demonstrating that (Goldbach’s conjecture) is unprovable. It means we’ll never know either way.
Earlier quoted context omitted.
It might be easiest to give a sense of what "unprovable but true" means by way of an imagined example. Goldbach's conjecture is that "every even number bigger than 2 is the sum of exactly two prime numbers", so 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, etc. For this statement to be *true* it just means that every even number there must exist two primes that add to that number. This is a statement about infinitely many integer…
What do we actually mean by saying "statement S is unprovable"? Do we mean "there is no prove for S" (which includes the case that S is provably false), or do we mean "there is no proof for S and there is no proof for its converse"? Because if you show that the converse of Goldbach's conjecture is not provable, you have actually proven Goldbach's conjecture (since you have shown that there is no counterexample!). >Th…
Lets hypothetize that Goldbach's conjecture is true and unprovable (let's call it S1). In that case, the following statments are both true: C1) It is impossible to prove S1. C2) It is impossible to prove the converse of S1. (since in this case S1 is true, the converse is actually false, so cannot be proven).
Now, if we go into meta-proofs, we may be able to prove C1 (whether or not S1 is true). But we will never be able to prove C2 (if S1 is true and unprovable, C2 will also be true and unprovable).
Now, if S1 is actually false, We may actually at some point find a proof of that. But that's not really so interesting.
The interesting part is that there DOES exist statements like this that ARE true AND unprovable (even if we don't know which statments), we just don't know WHAT statments those are.