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
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
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
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 }.
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
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!
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
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
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.
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.
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
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!
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!
— 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)
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)
¬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.
propositional formula, then φ is a classical tautology if and only if ¬¬φ is an intuitionistic tautology. Intuitionistic and Classical logics are related!
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
by homotopy equivalence synthetic: spaces are just (higher inductive) types in MLTT image from http://www.home.uni-osnabrueck.de/mfrankland/Math527/Math527.html
(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)
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/
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
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
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