‹ BackHN Continuity

Thread

Anatomy of a Lean proof for software engineers

128 points · 76 comments · abiro

  1. fooker · · focus · HN ↗
    Please do not try to understand Lean or proof assistants without first getting a rudimentary understanding of the logic involved. This article sort of skips over it, which is reasonable because it is pretty involved.

    Even if you have written a large number of math proofs, you'd usually not have learnt the language or logic of proofs themselves. And even if you are an accomplished computer scientist, logic is not just AND, OR, NOT.

    Here is some necessary reading, feel free to find better sources but wikipedia is good too.

    * Proof trees - <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Method_of_analytic_tableaux" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Method_of_analytic_tableaux

    * Constructive&#x2F;Intuitionistic logic - <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Intuitionistic_logic" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Intuitionistic_logic

    * Proofs and Types - <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Curry%E2%80%93Howard_correspondence" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Curry%E2%80%93Howard_correspon...

    * (In)completeness - <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;G%C3%B6del%27s_incompleteness_theorems" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;G%C3%B6del%27s_incompleteness_...

    * Compactness - <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Compactness_theorem" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Compactness_theorem

    1. 6gvONxR4sf7o · · focus · HN ↗
      Honestly, I&#x27;d say just play some of the lean games instead (<a href="https:&#x2F;&#x2F;adam.math.hhu.de&#x2F;" rel="nofollow">https:&#x2F;&#x2F;adam.math.hhu.de&#x2F;). I went through the dependent type theory and proof stuff first, and in hindsight it would have been much faster to just get the intuition first from learning to use a language like lean.
      1. fooker · · focus · HN ↗
        Sure, use whatever method of learning that works well for you.

        All I&#x27;m saying is that you&#x27;re unlikely to be making effective use of a tool like this without understanding it&#x27;s theoretical foundations.

        1. watt · · focus · HN ↗
          Or, you could invest time in making a tool that can be used effectively without having to understand all the theoretical foundations. What&#x27;s stopping you?
          1. fooker · · focus · HN ↗
            I don&#x27;t know how to do it.

            If someone would figure this out, the theoretical advancements they would discover on the way would likely earn them a Turing award.

Open on Hacker News to reply ↗

Unofficial Hacker News client; not affiliated with Y Combinator.