News for hackers. Stuff that matters.
Re:AlphaProof's Greatest Hits: the coolest bits from the IMO... by Onavo on Sunday November 17, 2024 @04:20PM (#42167389)
> We know that any theorem that is provable at all (in the chosen foundation of mathematics) can be found by patiently enumerating all possible proofs.

Which computer science theorem is this from?

Re:AlphaProof's Greatest Hits: the coolest bits from the IMO... by kadoban on Sunday November 17, 2024 @04:32PM (#42167504)
It's a direct consequence of the format of a proof. They're finite-length sequences of a finite alphabet of symbols, so of course they're enumerable (the same algorithm you use to count works to enumerate them).

If you want a computer to be able to tell that it found a correct proof once it enumerates it, you need a bit more than that (really just the existence of automated proof checkers is enough for that).

Re:AlphaProof's Greatest Hits: the coolest bits from the IMO... by zeroonetwothree on Sunday November 17, 2024 @04:28PM (#42167461)
It’s just an obvious statement. If a proof exists, you will eventually get to it.
Re:AlphaProof's Greatest Hits: the coolest bits from the IMO... by j16sdiz on Monday November 18, 2024 @02:24AM (#42170467)
Only if we take AC, I guess?
Re:AlphaProof's Greatest Hits: the coolest bits from the IMO... by Tainnor on Monday November 18, 2024 @08:01AM (#42171957)
No, this has nothing to do with choice.
Re:AlphaProof's Greatest Hits: the coolest bits from the IMO... by E_Bfx on Sunday November 17, 2024 @05:07PM (#42167773)
I guess it is tautological from the definition of "provable". A theorem is provable by definition if there is a finite well-formulated formula that has the theorem as consequence (https://en.wikipedia.org/wiki/Theorem paragraph theorem in logic)
Re:AlphaProof's Greatest Hits: the coolest bits from the IMO... by Xcelerate on Sunday November 17, 2024 @05:49PM (#42168075)
Not sure it’s a tautology. It’s not obvious that a recursively enumerable procedure exists for arbitrary formal systems that will eventually reach all theorems derivable via the axioms and transformation rules. For example, if you perform depth-first traversal, you will not reach all theorems.

Hilbert’s program was a (failed) attempt to determine, loosely speaking, whether there was a process or procedure that could discover all mathematical truths. Any theorem depends on the formal system you start with, but the deeper implicit question is: where do the axioms come from and can we discover all of them (answer: “unknown” and “no”)?

Re:AlphaProof's Greatest Hits: the coolest bits from the IMO... by Tainnor on Monday November 18, 2024 @08:19AM (#42172070)
It's "obvious" in the sense that it's a trivial corollary of the completeness theorem (so it wouldn't be true for second order logic, for example).

Hilbert's program failed in no contradiction to what GP wrote because the language of FOL theorems is only recursively enumerable and not decidable. It's obvious that something is true if you've found a proof, but if you haven't found a proof yet, is the theorem wrong or do you simply have to wait a little longer?

Re:AlphaProof's Greatest Hits: the coolest bits from the IMO... by Turneyboy on Tuesday November 19, 2024 @05:15AM (#42181838)
Yeah but width-first immediately gives you the solution for any finite alphabet. So in that sense it is trivial.