Logic for People

Leading programming language theorist Robert Harper refers to so-called constructive or intuitionistic logic as “logic as if people mattered”. There is a fascinating convergence of ideas here. In the early 20th century, Dutch mathematician L. E. J. Brouwer developed a philosophy of mathematics called intuitionism. He emphasized that mathematics is a human activity, and held that every proof step should involve actual evidence discernible to a human. By contrast, mathematical Platonists hold that mathematical objects exist independent of any thought; formalists hold that mathematics is a meaningless game based on following rules; and logicists argue that mathematics is reducible to formal logic.

For Brouwer, a mathematical theorem is true if and only if we have a proof of it that we can exhibit, and each step of that proof can also be exhibited. In the later 19th century, many new results about infinity — and infinities of infinities — had been proved by what came to be called “classical” means, using proof by contradiction and the law of excluded middle. But from the time of Euclid, mathematicians have always regarded reproducible constructions as a better kind of proof. The law of excluded middle is a provable theorem in any finite context. When the law of excluded middle applies, you can conclude that if something is not false it must be true, and vice versa. But it is not possible to construct any infinite object.

The only infinity we actually experience is what Aristotle called “potential” infinity. We can, say, count a star and another and another, and continue as long as you like, but no actually infinite number or magnitude or thing is ever available for inspection. Aristotle famously defended the law of excluded middle, but in practice only applied it to finite cases.

In mathematics there are conjectures that are not known to be true or false. Brouwer would say, they are neither true nor false, until they are proved or disproved in a humanly verifiable way.

The fascinating convergence is that Brouwer’s humanly verifiable proofs turn out also to exactly characterize the part of mathematics that is computable, in the sense in which computer scientists use that term. Notwithstanding lingering 20th century prejudices, intuitionistic math actually turns out to be a perfect fit for computer science. I use this in my day job.

I am especially intrigued by what is called intuitionistic type theory, developed by Swedish mathematician-philosopher Per Martin-Löf. This is offered simultaneously as a foundation for mathematics, a higher-order intuitionistic logic, and a programming language. One might say it is concerned with explaining ultimate bases for abstraction and generalization, without any presuppositions. One of its distinctive features is that it uses no axioms, only inference rules. Truth is something emergent, rather than something presupposed. Type theory has deep connections with category theory, another truly marvelous area of abstract mathematics, concerned with how different kinds of things map to one another.

What especially fascinates me about this work are its implications for what logic actually is. On the one hand, it puts math before mathematical logic– rather than after it, as in the classic early 20th century program of Russell and Whitehead — and on the other, it provides opportunities to reconnect with logic in the different and broader, less formal senses of Aristotle and Kant, as still having something to say to us today.

Homotopy type theory (HoTT) is a leading-edge development that combines intuitionistic type theory with homotopy theory, which explores higher-order paths through topological spaces. Here my ignorance is vast, but it seems tantalizingly close to a grand unification of constructive principles with Cantor’s infinities of infinities. My interest is especially in what it says about the notion of identity, basically vindicating Leibniz’ thesis that what is identical is equivalent to what is practically indistinguishable. This is reflected in mathematician Vladimir Voevodsky’s emblematic axiom of univalence, “equivalence is equivalent to equality”, which legitimizes much actual mathematical practice.

So anyway, Robert Harper is working on a variant of this that actually works computationally, and uses some kind of more specific mapping through n-dimensional cubes to make univalence into a provable theorem. At the cost of some mathematical elegance, this avoids the need for the univalence axiom, saving Martin-Löf’s goal to avoid depending on any axioms. But again — finally getting to the point of this post — in a 2018 lecture, Harper says his current interest is in a type theory that is in the first instance computational rather than formal, and semantic rather than syntactic. Most people treat intuitionistic type theory as a theory that is both formal and syntactic. Harper recommends that we avoid strictly equating constructible types with formal propositions, arguing that types are more primitive than propositions, and semantics is more primitive than syntax.

Harper disavows any deep philosophy, but I find this idea of starting from a type theory and then treating it as first of all informal and semantic rather than formal and syntactic to be highly provocative. In real life, we experience types as accessibly evidenced semantic distinctions before they become posited syntactic ones. Types are first of all implicit specifications of real behavior, in terms of distinctions and entailments between things that are more primitive than identities of things.

Constructive

Brandom’s inferentialist alternative to representationalism stresses material, meaning-oriented over formal, syntactic inference. Prior to the development of mathematical logic, philosophers typically used a mixture of reasoning about meanings with natural language analogues of simple formal reasoning. People in ordinary life still do this.

Where Brandom’s approach is distinctive is in its unprecedentedly thorough commitment to the reciprocal determination of meaning and inference. We don’t just do inference based on meanings grasped ready-to-hand as well as syntactic cues to argument structure, but simultaneously question and explicitate those very meanings, by bracketing what is ready-to-hand, and instead working out recursive material-inferential expansions of what would really be meant by application of the inferential proprieties in question.

For Brandom, the question of which logic to use in this explicitation does not really arise, because the astounding multiplication of logics — each with different expressive resources — is all in the formal domain. It is nonetheless important to note that formal logics vary profoundly in the degrees of support they offer for broad representationalist or inferentialist commitments.

Michael Dummet in The Logical Basis of Metaphysics argued strongly for the importance of constructive varieties of formal logic for philosophy. Constructive logics are inherently inference-centered, because construction basically just is a form of inference. (Dummet is concerned to reject varieties of realism that I would call naive, but seems to believe the taxonomy of realisms is exhausted at this point. This leads him to advocate a form of anti-realism. His book is part of a rather polarized debate in recent decades about realism and anti-realism. I see significant overlap between non-naive realisms and nonsubjective idealisms, so I would want to weaken his strong anti-realist conclusions, and I think Brandom helps us to do that.)

Without endorsing Dummet’s anti-realism in its strong form, I appreciate his argument for the philosophical preferability of constructive over classical logic. It seems to me that one cannot use modern “classical” formal logic without substantial representationalist assumptions, and a lot of assumed truth as well. If and when we do move into a formal domain, this becomes important.

As used in today’s computer science, constructive logic looks in some ways extremely different in its philosophical implications from Brouwer’s original presentation. Brouwer clouded the matter by mixing good mathematics with philosophical positions on intuition and subjectivity that were both questionable and not nearly as intrinsic to the mathematics as he seemed to believe. The formal parts of his argument now have a much wider audience and much greater interest than his philosophizing.

Constructive logic puts proof or evidence before truth, and eschews appeals to self-evidence. Expressive genealogy puts the material-inferential explicitation of meaning before truth, and eschews appeals to self-evidence. Both strongly emphasize justification, but one is concerned with proof, the other with well-founded interpretation. Each has its place, and they fit well together.