Upgrade to Pro — share decks privately, control downloads, hide ads and more …

The Programming Language of Mathematics

The Programming Language of Mathematics

A motivation to study logic and type theory. First presented at PyCon Ukraine 2017 in Lviv.

Volodymyr Kyrylov

April 08, 2017
Tweet

More Decks by Volodymyr Kyrylov

Other Decks in Science

Transcript

  1. plan hacker one informal menace revenge of the incompleteness a

    constructive hope return of the synthetic univalence awakens closing the loop
  2. casual introduction to formal language language is the medium for

    communicating ideas human ↔ computer, human ↔ human hand-waving (sort of) works for humans, but not for computers!
  3. typed programming languages compiler needs to know which processor commands

    to emit depending on the type polymorphism is a good abstraction to let programmers use memory management: ARC, session types (rust) DSLs: CSS, SQL, AWK, Prolog, TensorFlow
  4. “please do not do that” we would like to be

    a lot more precise about the intention of our code than we are now
  5. often a different PL makes an abstraction look natural instead

    of forced Dijkstra: The purpose of abstraction is not to be vague, but to create a new semantic level in which one can be absolutely precise. Example virtual tables in C vs interfaces in Java manual parsing in Java vs pattern-directed scanning in Awk concurrency in Python vs message passing in Erlang memory layout in R vs Assembly
  6. two years ago i spoke about haskell: a language with

    an expressive type system there is a trend of using dependently-typed languages, which allow types to depend on values
  7. dependent types an extra approach to software quality adding to

    selective invariant checking (TDD and alike), property-based testing (QuickCheck) and model checking (SMT and Z3) — proofs of correctness DeepSpec — a research project producing a vertified RTL compiler, a verified OS kernel, a verified C compiler and development tools
  8. motivating example: interfaces class Monoid a where id :: a

    (*) :: a -> a -> a Documentation: Instances should satisfy the following laws: id * x = x x * id = x x * (y * z) = (x * y) * z
  9. motivating example: interfaces with invariant proofs Structure monoid A :=

    Monoid { id : A; op : A -> A -> A; opA : forall x y z : A, op x (op y z) = op (op x y) z; idL : forall x : A, op id x = x; idR : forall x : A, op x id = x }.
  10. just like programmers need to precisely communicate computation steps to

    the machine, mathematicians do it to each other just like PLs are syntax for computation, formal systems are syntax for doing inference (proving your point) we’re going to assert that proving your point and computing is the same
  11. logic studies valid forms of inference, it’s grammar of thought

    proof theory studies a syntax of proofs as mathematical objects domain theory studies meaning of logics as mathematical objects there’re a lot less concepts in math than names for them!
  12. classes of logic propositional logic predicate (first-order) logic higher-order logics

    / type theories a lot of variantions on all possible rules in every possible logic point to drive home: there’s no such thing as “The Logic”
  13. first-order logic: ∀ ∃ ∧ ∨ ⊃ ¬⊥ = allows

    to quantify (∀ ∃) over domains of discourse introducing variables1 domains of discourse are defined outside of the logic 1the name “variables” has nothing to do with mutation
  14. first-order logic: the workhorse of formal mathematics take ∀ ∃

    ∧ ∨ ⊃ ¬⊥ = add some axioms add rules of inference now you have a first-order theory!
  15. soundness and completeness metatheory stuff — you’d better have a

    proof of: you can’t prove both truth and falsehood for the same formula you can’t define an underivable formula
  16. first-order theories Presburger Arithmetic (N+) Peano Arithmetic (N + ×)

    Tarski Real Closed Fields Group Theory . . . a lot of abstract algebra . . .
  17. first-order theories: set theory Cantor Set Theory Zermelo Set Theory

    Fraenkel Pull Request to Zermelo Set Theory Zermelo-Fraenkel Set Theory with Choice (ZFC)
  18. vernacular alert “set theory” sometimes also means naive set theory

    which is a theory defined in a natural language to explain concepts. despite being successful, it’s not formal! we’re going to be arrogant and informally hand-wave about formal things instead
  19. Axiom (Extensionality) Sets are equal if their elements are equal.

    Axiom (Comprehension (Subsets)) Given a set and a predicate, there is a subset of your set containing only elements of the predicate. Axiom (Unordered Pair) For two sets there is always a set which has those sets as members. Axiom (Union) A union of sets is a thing. Axiom (Power Set) Power sets P(X) are a thing.
  20. Axiom (Infinity) At least one infinite set I (aka inductive

    set) is a thing. Axiom (Replacement) The image of the domain set A under the definable function f (i.e. the range of f) falls inside a set B. Axiom (Foundation) Every non-empty set x contains a member y such that x and y are disjoint sets. (E.g. Russell’s paradox can’t happen.) Axiom (Choice (AC)) For any set X of nonempty sets, there exists a choice function f defined on X. A choice function is a function f, defined on a collection X of nonempty sets, such that for every set A in X, f (A) is an element of A.
  21. set theory “macro expansion” example ∀x . ∀y . {x,

    y} = {y, x} ⇓ ∀x . ∀y . ∃z . (∀a . a ∈ z ⇔ a = x ∨ a = y)∧ (∃a . (∀b . b ∈ a ⇔ b = y ∨ b = x) ∧ z = a) https://gist.github.com/andrejbauer/09258d80842b37b6afa1c7ab6227029e
  22. Russell’s Hackathon “Pure Mathematics is the class of all propositions

    of the form p ⊃ q where p and q are propositions containing one or more variables, the same in the two propositions, and neither p nor q contains any constants except logical constants.” Let’s do all of the mathematics in Cantor Set Theory!
  23. Russell’s Paradox during Russell’s Hackathon added a hack before the

    demo: types, to prevent paradoxes gossip: I heard that Zermelo knew about this problem by that time
  24. (A tiny bit of) Hilbert’s Program is there an axiomatic

    formal system that lets us do all of the mathematics?
  25. G¨ odel’s Two Incompleteness Theorems 1. can’t be consistent if

    you have arithmetic (like, in PA) 2. if your system is “powerful” enough, you can’t prove its consistency in itself
  26. G¨ odel’s Numbering every formula gets a unique number —

    using primes and the fundamental theorem of arithmetic!
  27. Gentzen’s Habilitationsschrift numbers are not enough! you can “tie” the

    consistency of your theory to another theory (a system is consistent if it has a model) same formal system may do different things under different assumptions!
  28. Gentzen’s Kalk¨ ule nat¨ urlichen Schließens cut back on axioms

    — just represent natural deduction and add a notion of assumptions gives a framework for proof construction you can “run” the proof — through normalization of its parts (e.g. the Y combinator doesn’t let Church’s lambdas normalize)
  29. Gentzen ND and Trees scope: Γ ctx atomic: J judgment

    hypothetical ( means entailment, subject to structural rules): J0 judgment . . . Jn judgment J judgment J0 J1 . . . Jn J inference-rule
  30. Peek at Classical Propositional Logic in ND: ⊥ ∧ ∨

    ¬ ⊃ A prop B prop A ∧ B prop ∧F
  31. Propositional logic: ⊥ ∧ ∨ ¬ ⊃ remember truth tables?

    p q ∨ 0 0 0 0 1 1 1 0 1 1 1 1 propositions with a model in Boolean algebra is only one possible model for such logic which we can use to study provability in it. truth tables imply you assume Boolean algebra as the model (and reduce the solving propositional formulas to Boolean SAT)
  32. Boolean Algebra complemented lattice with distributivity of ∧ over ∨

    and exponential I found a complete definition of it in the Scottish Book written down by John von Neumann, while sitting in the Szkocka Cafe
  33. Enter Brouwer Brouwer had a philosophical issue with p ∨

    ¬p = . He claimed that the Law of Excluded Middle made no sense universally: how do you encode an open problem? LEM also concides with decidability: not every set membership is decidable! Core issue: in order to create a mathematical object, you have to give a way of explicitly constructing it. Classical mathematics allows weaker proofs that pull constructions out of thin air by applying LEM. This movement is known as Intuitionism, and a variant of it was known in USSR (and Imperial Russia?) as Constructivism.
  34. Definition LEM := forall P : Prop, P \/ (~

    P). Definition De_Morgan1 := forall P Q : Prop, ~(~P /\ ~Q) -> P \/ Q. Theorem LEM_implies_De_Morgan1 : LEM -> De_Morgan1. intros LEM P Q Nots. pose proof (LEM P) as Lp. pose proof (LEM Q) as Lq. destruct Lp. left. exact H. destruct Lq. right. exact H0. pose proof (Nots (conj H H0)) as HH. contradiction. Qed.
  35. Double-Negation Translation: Glivenko, G¨ odel, Gentzen If φ is a

    propositional formula, then φ is a classical tautology if and only if ¬¬φ is an intuitionistic tautology. Intuitionistic and Classical logics are related!
  36. Brouwer Heyting Kolmogorov Gentzen Curry Howard De Brujin Wadler intuitionism

    is also about proof relevance: a proof is also a mathematical object propositions as types, proofs as programs when a type is inhabited — we have a proof
  37. Bishop: Foundations of Constructive Analysis calculus (and another set theory)

    without LEM. less assumptions lead to stronger results!
  38. Martin-L¨ of Type Theory foundations for constructive mathematics starting with

    1972 does not have axioms, only inference rules! data types are a part of the theory A type a : A type a ≡ b : A
  39. Synthetic Mathematics analytic mathematics is hacking in assembly (which is

    often ZFC) synthetic mathematics is using DSLs example: Descartes geometry vs Euclidean geometry
  40. Homotopy Theory analytically: spaces are equivalence classes of topological spaces

    by homotopy equivalence synthetic: spaces are just (higher inductive) types in MLTT image from http://www.home.uni-osnabrueck.de/mfrankland/Math527/Math527.html
  41. Bonus: Topology that thing about donuts and coffee mugs analytically

    (aka point-set or general topology): a set with a family of subsets that are closed under unions, finite intersections and include the empty set and the set itself synthetic: abstract stone duality, axiomatisation of Sierpi´ nski space (big picture: keep the core structure intrinsic to the axiomatisation, kind of like “correct” by construction)
  42. Homotopy Type Theory unites higher category theory, logic (type theory)

    and algebraic topology (homotopy theory) homotopy-theoretic proofs gain elegance from type-theoretic interpretation
  43. Univalent Foundations Use MLTT, Univalence and Higher Inductive Types (a

    way of defining homotopical spaces) as The Foundations of Mathematics. Does not contradict Classical mathematics, but subsumes it. The book works through all of it and is free: https://homotopytypetheory.org/
  44. logic types homotopies proposition type space proof program point predicate

    dependent type fibration disjunction sum bundle product product product implication function type function space universal quantifier Π product space existential quantifier Σ total space equality identity type path space
  45. logic types homotopies proposition A space proof a : A

    point predicate A → Type fibration disjunction + bundle product × product implication A → B function space universal quantifier Π(x : A).B product space existential quantifier Σ(x : A).B total space equality IdA MN path space
  46. let’s go down the rabbit hole: you will find out

    i barely scratched the surface if you are a student — go talk to your professors! start proving theorems — you don’t need to buy a GPU
  47. A mathematician is a person who can find analogies between

    theorems; a better mathematician is one who can see analogies between proofs and the best mathematician can notice analogies between theories. One can imagine that the ultimate mathematician is one who can see analogies between analogies. — Stefan Banach