Formalising Gödel's incompleteness theorems, I
lawrencecpaulson.github.io
lawrencecpaulson.github.io
Like, I understand that it's fundamentally still code, and so there are potential bugs in the kernel, but shear versatility and level of automation you get within Isabelle/HOL makes the development and understanding of proof feel like outright magic sometimes. Proof is really hard, and having a powerful tool to mechanically check it has nearly limitless potential.
Completely agree!
> having a powerful tool to mechanically check it has nearly limitless potential
As someone working in the industry and playing with theorem provers in my spare time, I've never been able to bridge the gap between industry and theory enough to be able to use these formal methods on projects that I'm on.
My PhD is in regards to proving properties about robotics, so maybe in 5-6 years I'll have fully bridged industry and theory, but I wouldn't hold my breath :)
As someone who doesn't code for a living, I am certain that this is a naïve question, but, if you want to use theorem-proving software for verification of existing code, does that require employer permission? Is the issue something like, e.g., you need the theorem-proving software and the code to be verified on the same machine, and you're not allowed to install the theorem-proving software on a work machine or to move the code to a non-work machine?
I had root access to my laptop so I could install anything I wanted, but it's hard to do anything if you don't have budget allocated to do so.
EDIT: I also should point out that I wanted to export the code from FStar to F# and use the exported and verified code.
Now in my company we are worried about bugs and reliability. If I can show via example that theorem proving catches bugs they will train all developers on it and demand all code be proved. However proving quality needs to be something that is worth the effort, if it slightly increases quality but at the expense of making projects take 10 times as long it is probably not worth it except for specific areas of concern.
The automation in Isabelle is quite good; good enough to where I don't feel that writing pure new code with proofs takes me a prohibitively long amount of time (about 2-3x writing the equivalent Haskell) (sledgehammer ftw), but I can't imagine trying to retroactively go and prove any of my old projects that are considerably smaller than 20 million lines.
One big perk for using Isabelle (or other proof systems), outside of the obvious correctness proofs, is being able to prove equivalence. If you can inductively show that two functions have the same inputs and outputs (say one was quick to write or easy to prove things about, the other is efficient), then you can tell the code exporter to replace any instances of the inefficient version with the efficient version. This means that your optimization is proven safe, and is done for free, which is worth its weight in gold when used correctly.
Of course, this really only applies to pure and mathey functions. It's substantially harder to prove properties about business logic.
This is one of the big problems in CS. We have code that has been in production for 20 years and as such has very few bugs left. We know from experience replacing that code with new proven correct code results in something more buggy (for a few years while we fix the incorrect requirements) than the original. We still are replacing a lot of old code with proven correct code, but only as the CPU it is tied to goes out of production (code that is portable thus is low on the to replace list). If we could prove existing code correct easily it would potentially save a lot of money as we can keep old code around and add correct features.
That seems optimistic!
Do you have any recommendations for getting started? Something like a "Proofs for Hackers"?
Not exactly the same, but if you want something a bit more approachable than Isabelle or Coq or Agda, it might be worth looking into TLA+. That can introduce you to predicate logic and state machines and set theory if you're not already familiar with them, and TLA+ is a lot more programmer-centric and less pure-mathey than Isabelle. TLA+ offers model checking for "brute force" verification, and also offers a formal proof system called TLAPS. Lamport's talks on TLA+ are quite good [2], and I found that learning Isabelle was a lot easier once I had a lot of practice with TLA+.
[1] http://concrete-semantics.org/ [2] https://lamport.azurewebsites.net/video/videos.html
nominal_datatype fm =
Mem tm tm (infixr "IN" 150)
| Eq tm tm (infixr "EQ" 150)
| Disj fm fm (infixr "OR" 130)
| Neg fm
| Ex x::name f::fm binds x in f
The programming world converged on full word variables, but it also converged on {} instead of BEGIN END etc.
Alex
Well, since we don't use multi-letter variable names, no such distinction is necessary! But if, for some reason, we did do so, then these two cases would be typeset in LaTeX as \(varname\) and \(var\,name\) (or, rather, \(\mathit{var}\) and \(\mathit{var}\,\mathit{name}\), since TeX correctly interprets \(var\) as semantically `var` anyway).
You remember the story about the Fox and the Grapes, right?
https://github.com/golang/go/wiki/CodeReviewComments#variabl...
HF seems 'hereditarily finite'.
I wish someone presents the proof that's 'inlines' the explanation of the terminology used and defines them before using. For something as fundamental as Godel's theorems, this should be worth doing.
I must say, be careful with "reasoning". For example, once a philosophy PhD minimized mathematics eloquently by saying all mathematical results are "tautological", hence uninteresting. Hence, why bother studying it, and in your case, why bother thinking Gödel did anything special.
Why bother about anything at all... there's the rub.
This seems quite circular, where the (claims mine) contrived statements enabling godel 2 incompletude theorem, make it unable to prove a non-contrived statement?
Thanks for the reference though, I'll admit that is a topic I'm not familiar enough with to fully challenge it.
> I must say, be careful with "reasoning". For example, once a philosophy PhD minimized mathematics eloquently by saying all mathematical results are "tautological", hence uninteresting. Hence, why bother studying it, and in your case, why bother thinking Gödel did anything special.
Yeah that's a classic, it's a good thought experiment but that only prove that one must not be careful with the pruning that can enable high level reasoning but more with being careful of fallacious or misleading reasonings. Yes in theory, mathematical chain proofs are only tautologies derived from ZFC/higher order logic, so yes mathematics doesn't say anything new. However in practice, the task of unfolding reasoning chains and being able to refer to past lemnas as abtractions/objects, enable the reader to optimize for cognition, and hence the more proofs advances, the more we can discover, retain, understand and refer, useful tautological yet transitive knowledge.
Also, I am aware there are non-contrived statements that are can't be proven in ZFC such as https://en.wikipedia.org/wiki/List_of_statements_independent.... I'm only claiming that the incompleteness theorems only find contrived ones, and that for the non-contrived ones humanity has found, it is NOT that they are mathematically unproveable, it is that ZFC is not enough.
Your second paragraph is confused. Given an axiom system like ZFC, there are (a) statements that can be proved true or false using it, (b) statements that can't be proved that are true in a particular model, (c) statements that can't be proved that are false in that model. It's set (b) that the incompleteness theorem tells us must exist. The theorem doesn't "find" statements, it proves that (b) exists by constructing a particular one, which is necessarily meta because it applies to every formal system.
However, we do not have access to a model which tells us the answers for things like the CH. So all you can do is decide on the axiom scheme you like, and then some things are provable. You can always add more axioms, like CH, but you can add their negation instead, if you want. So there's no sense in which there's really a right answer for CH but we haven't found it yet.
There are plenty of people who find ZFC + ¬CH a reasonable axiomatic system.
EDIT: I misread samth's statement (https://news.ycombinator.com/item?id=31424581), which I think is proveable in ZFC; I thought their statement was ¬CH.
Nothing especially contrived there. Less so for a professional logician.
So the calculus that formalises the theorem is either inconsistent or there are other true statements about it that can't be proven? Which is it? Can someone with a bigger brain elaborate on how the theorem applies to itself in a language for tiny brained people? No big words please.
And even an incomplete formal system can prove Gödel's Incompleteness Theorem.
A formal system can be thought of as an algorithm that takes a purported formal proof of some arithmetical statement (e.g. there is no largest twin prime) and returns true/false depending on whether the proof is correct. Call the algorithm a “proof checker” and say it “accepts” a statement if it returns true for some purported proof of the statement.
Godel’s first incompleteness theorem says that at least one of the following is true:
(1) There is some statement such that the checker accepts both the statement and the statement’s negation (e.g. the checker accepts both “2 + 2 = 4” and “2 + 2 ≠ 4”). This is called inconsistency.
(2) There is some true statement which the checker will not accept. This is called incompleteness.
Since Godel’s first incompleteness theorem is not a formal system, it does not apply to itself.
(3) The system's axioms are not finitely enumerable (i.e. not finite, and cannot be generated by a generator of finite length; e.g. a system where every true statement is an axiom and there are infinitely many axioms)
(4) The system is not complex enough to express arithmetic (e.g. propositional calculus)
I think I already excluded cases like (4) by stating that the checker operates on "arithmetical statement[s]".
It's at least a bit vague, I think you need something that is at least as strong as Robinson arithmetic. In particular, I believe that if you throw out multiplication (or addition, and keep multiplication), you get a complete theory.
Except the author is formalizing the theorem. Meaning the theorem is based off a formal system. That means the system itself that was created to derive this theorem is either incomplete or inconsistent.
So Yes it does apply to itself.
Its missing the qualifier: can't be proven in that system. They can be examined from outside the system, or say, with a different system.