10
$\begingroup$

Does the "propositions-as-type" paradigm matches mathematical practice? Or is logic in mathematical practice a layer beneath mathematics, and mathematics built on top? For example, should we distinguish between the meta-"or" (which we use when formulating theorems) and the function $\mathrm{Bool}\times\mathrm{Bool}\to\mathrm{Bool}$ on $\mathrm{Bool}:=\{0, 1\}$ that maps $(p, q)$ to $\mathrm{max}(p, q)$?

I think that in classical foundations such as FOL+ZFC, logic is a separated layer, but in modern foundations of mathematics such as type theory, the logical connectives which we are use when formulating theorems are themselves mathematical objects. Is that true?

$\endgroup$
7
  • 1
    $\begingroup$ I wonder how many mathematicians working outside logic concern themselves with this distinction in their work. $\endgroup$
    – Neal
    Commented Sep 17, 2016 at 13:06
  • $\begingroup$ If you mean ML type theory, connectives are not "in the theory", just meaningful propositions and judgements. But it's correct that ML type unifies the two layer metatheory and theory but this can be problematic. First, let me clarify that the philosophical foundations of ML are problematic and do not present the theory properly (the action of constructing is not faithful with the one in the theory). ... $\endgroup$
    – user40276
    Commented Sep 17, 2016 at 15:58
  • $\begingroup$ ...A problem is that the notion of truth and knowledge turns out the be a little redundant and some ontology is lost (this is in the philosophical foundations). Now from the perspective of the practical context (that is from the ML theory), there's the problem (essentially appearing in all intuitionist theory) of identifying the knowledge about the object and the object itself. Furthermore, I don't know if any (homotopy) type corresponds to a meaningful proposition, in other words, if the proofs of propositions (say in Peano arithmetic) exhausts all (homotopy) types. $\endgroup$
    – user40276
    Commented Sep 17, 2016 at 16:00
  • $\begingroup$ Let me go back to the philosophical foundations. From andrew.cmu.edu/user/ulrikb/80-518-818/MartinLof83.pdf, one can conclude that to know something is same thing as knowing that someone knows something. So why would you want to know? This is one problem (discovered by a friend of mine), for instance. $\endgroup$
    – user40276
    Commented Sep 17, 2016 at 16:03
  • $\begingroup$ @Neal: is it really relevant? $\endgroup$
    – Qfwfq
    Commented Sep 17, 2016 at 18:45

1 Answer 1

24
$\begingroup$

There are many aspects to the question "does a logical formalism reflect mathematical practice?" I will focus just on a very simple but important detail that every mathematician is familiar with.

In mathematical practice we differentiate between

  1. $\phi$ or $\psi$, and we know which one, and
  2. $\phi$ or $\psi$, but we may not know which one.

We also differentiate between

  1. there is a given $x$ such that $\theta(x)$, and
  2. there is $x$ such that $\theta(x)$, but we may not be given one.

Let me call the first kind the concrete disjunction an existential, and the second kind the abstract disjunction and existential. (There is no established terminology.) Thus, "concretely $\exists x \,.\, \theta(x)$" is meant to convey that I have a particular $a$ such that $\theta(a)$, while "abstractly $\exists x \,.\, \theta(x)$" is meant to convey that we know there is an individual satisfying $\theta$, but we may not have a specific one.

First-order logic formalizes the abstract version, because the inference rule for existentials forgets the witness $a$: $$\frac{\phi(a)}{\exists x \,.\, \theta(x)},$$ Martin-Löf type theory formalizes the concrete version because the witness $a$ is recorded in the proof term: $$\frac{p : \theta(a)}{(a,p) : \sum_{x : A} \theta(x)}.$$

A formalism which captures both is Martin-Löf type theory with propositional truncation. This is an operation which hides witnesses of statements. If you are familiar with type theory then you can look it up in homotopy type theory. If you are an ordinary mathematician, then it can be described as a quotient: given a type $A$, its propositional truncation $|A|$ is the quotient $A/{\sim}$ by the trivial equivalence relation $\sim$ which relates every $x$ and $y$ in $A$. Thus, if $A$ has an element then $|A|$ has one element. If $A$ is empty, then $|A|$ is empty as well.

With propositional truncation we can get all four variants:

  1. concrete disjunction is $\phi + \psi$
  2. abstract disjunction is $|\phi + \psi|$
  3. concrete existential is $\sum_{x : A} \theta(x)$
  4. abstract existential is $|\sum_{x : A} \theta(x)|$

Propositional truncation can be defined in homotopy type theory as a higher inductive type. Thus, homotopy type theory reflects mathematical practice (in one respect) better than logic and Martin-Löf's propositions-as-types.

You are asking about "layers" of logic and mathematics, so let me address this as well. In mathematical practice we prove statements and perform constructions (an early reference of such activity would be Euclid's Elements). Moreover, deduction and construction steps are intertwined. During a proof we often consturct auxiliary objects, and a complicated construction may require justification of certain steps. (For example, while constructing a solution of a differential equation, we may have to argue that a certain sequence converges.)

Traditional foundations layer a term language at the bottom and first-order logic on top. This only captures the case of a logical deduction during which we perform axuliary constructions (expressed as terms of the first-order language) that require no further justifications. However, in practice we need more than that. For example, in the theory of fields it is natural to think of inverse as an operation. Every time we write $x^{-1}$ we need to argue that $x \neq 0$, so inverse is a construction which requires justification. If you look at how the theory of fields is formalized, you will see that it is unsatisfactory: either inverses are treated abstractly as existentials (instead of having the operation $x \mapsto x^{-1}$ we only state $\forall x \,.\, x \neq 0 \Rightarrow \exists y \,.\, x y = 1$), or the justification of $x \neq 0$ is ignored and the operation $x \mapsto x^{-1}$ is made everywhere defined by fiat by stipulating that $0^{-1} = 0$ or some such non-sense.

There are real-world consequences of the failure of logic to correctly capture the multi-layered nature of constructions and deductions: mathematicians often formulate constructions inappropriately as abstract existential statements (as there is no other kind in first-order logic). They say

Theorem 4.2: There exists $x$ such that $\theta(x)$.

Proof. (Construction of $x$ is given here.) QED

and later refer to Theorem 4.2 as if it were a construction. It is as if they were ashamed of saying

Problem 4.2: Give $x$ such that $\theta(x)$.

Construction. (Construction of $x$ is given here.) DEFINED

We should all go back to reading Euclid.

In contrast, Martin-Löf type theory is a theory of constructions, so there the problem arises when we want to state something without giving a specific construction. Once again, homotopy type theory comes to the rescue with the idea of propositional truncation. And we can precisely explain which bits of a statement are to be read as constructions and which ones as abstract existence. An example may help here:

  • $\prod_{n : \mathbb{N}} \sum_{b : \{0,1\}} \sum_{k : \mathbb{N}} n = 2 k + b$ means "a construction which decomposes a number into its least significant bit and the rest of the number".
  • $\prod_{n : \mathbb{N}} \sum_{b : \{0,1\}} \big|\sum_{k : \mathbb{N}} n = 2 k + b\big|$ means "a construction which calculates the least significant bit of a number".
  • $\prod_{n : \mathbb{N}} \big|\sum_{b : \{0,1\}} \sum_{k : \mathbb{N}} n = 2 k + b\big|$ means "every number is (abstractly) even or odd".
$\endgroup$
8
  • $\begingroup$ If I try interpreting truncation as double negation, will that correctly predict the inferences among truncated and untruncated propositions? $\endgroup$
    – user44143
    Commented Sep 20, 2016 at 15:20
  • 1
    $\begingroup$ By the way, we can use double negation in place of propositional truncation, in which case we get a known translation of classical logic into type theory. $\endgroup$ Commented Sep 22, 2016 at 9:36
  • 3
    $\begingroup$ At the next good opportunity, I will use "Problem 4.2: Give x such that θ(x) Construction. (Construction of x is given here.) DEFINED" in a paper of mine. Who should I credit for this? (this MO post?) Is this your idea, Andrej, to phrase things like that? Has this been used somewhere? (Euclid?) $\endgroup$ Commented Sep 22, 2016 at 21:57
  • 3
    $\begingroup$ I think you should credit Euclid for the original invention, as well as the recent efforts of Vladimir Voevodsky to bring this point to the attention of mathematical community. I'll try to find a good reference, but if you look at his recent arXiv papers, they're written in this style. $\endgroup$ Commented Sep 23, 2016 at 7:35
  • 1
    $\begingroup$ Even in reading ZF texts I find myself thinking something similar regarding class existence assertions. "There exists a (definable) class such that ..." is not even an honest paraphrase, where as "Here is a such a class" is. $\endgroup$ Commented Sep 25, 2016 at 16:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .