29
$\begingroup$

Most proof assistants (with some exceptions like Isabelle/ZF or the B method) rely on type theory.

See also the MathOverflow question What makes dependent type theory more suitable than set theory for proof assistants?

Next, formalizing mathematics is one of the main use cases of an interactive proof assistant.
But many pen-and-paper mathematical proofs are written in a set-theoretic fashion (e.g., in ZFC).

Finally, there are many different type theories (first-order, higher-order, dependently-typed or not, intuitionistic or not, etc.)

So, formalizing existing set-theoretic results typically involves some formal hindrances.

Keeping the constructiveness issue apart, and focusing on the definability of mathematical objects:

  1. what mathematical concepts can't typically be "formalized as is", within the main proof-assistants / type-theories?
    (e.g., we can think about matrices in a non-dependently-typed theory…)
  2. is a "workaround" possible, to still be able to formally deal with this mathematical concept in the considered theory? (if yes, feel free to cite a formalization example)
$\endgroup$
4
  • 3
    $\begingroup$ You might be interested in this: An initial algebra of a complete sup-lattice equipped with an endofunction is exactly a model of IZF... This can be formalized in type theories with HITs. $\endgroup$ Commented Feb 9, 2022 at 5:16
  • $\begingroup$ Thanks @Trebor (I guess we could say your answer refer to some "deep embedding"; while "shallow embedding"-like answers could be interesting as well) $\endgroup$ Commented Feb 9, 2022 at 12:25
  • $\begingroup$ I wasn't the close voter, but I presume the close vote was because this question seems to ask two questions instead of one, and most sites have a one-question-per-post policy. $\endgroup$ Commented Feb 9, 2022 at 22:52
  • 1
    $\begingroup$ Notably, even Isabelle/ZF shares with Isabelle/HOL a common root Pure that is a very weak type theory. $\endgroup$ Commented Feb 12, 2022 at 14:12

3 Answers 3

34
$\begingroup$

Almost no pen-and-paper mathematics is written in ZFC. The vast majority of mathematical texts is actually written in something that resembles structural set theory and is closer to type theory than to ZFC.

Most mathematics can be formulated in type theory in a fairly straightforward manner. However, not every brand of type theory is equally good for formalization of mathematics. Some type theories are more like programming languages, and others are geared towards formalization of mathematics.

Here are some features that make it easier to formalize mathematics in type theory:

  1. Quotients: it is annoying to not be able to form quotients by equivalence relations. In type theories without quotients people use setoids (types equipped with equivalence relations) – and those who worked with setoids sometimes refer to the activity as "setoid hell".

  2. Impredicativity: often a type theory does not have a type of truth values, but instead has a whole hierarchy of them (one in each universe). This leads to various complications because one has to keep track of universes.

  3. Extensional equality: In type theory equality is represented by identity types. These may behave in unusual ways, unless we adopt some principles (such as Uniqueness of identity proofs or equality reflection).

  4. Function extensionality: this principle states that $f, g : A \to B$ are equal if $f(x) = g(x)$ for all $x : A$. It seems quite hard to do mathematics without this principle.

  5. Other extensionality principles: these are principles like "equivalent propositions are equal" and "pairs are equal if their first and second components are equal".

  6. Excluded middle and the axiom of choice are needed to a much lesser degree than one might expect.

Some type theories have all of the above constructions and principles, for instance the type theory of Lean. By doing so they sacrifice some good computational properties that "pure" type theories have (by this I mean that the type theory can be used a programming language as well as a foundation of mathematics). And there are alternatives which keep the good computational properties but require one to rethink how mathematics is done (such as cubical type theories).

$\endgroup$
19
  • 3
    $\begingroup$ @M.Lonardi They can be added to a proof assistant. It might not be clear from the way it was written but lean has all of 1-6. HoTT also has quotient types, but without proof irrelevance I would argue that they don't act in the way one would normally expect, and I'm not sure if they are actually strong enough to escape "setoid hell". $\endgroup$ Commented Feb 10, 2022 at 8:54
  • 7
    $\begingroup$ @MarioCarneiro: setoid hell arises because one has to verify that a map respects equivalences all the time, even when no quotients are really involved. The HoTT quotients are like any other quotients: you only need to check that something is being preserved when you map out of a quotient type. So I'd say it's not really setoid hell. $\endgroup$ Commented Feb 10, 2022 at 14:36
  • 1
    $\begingroup$ Maybe worth noting that there are different kinds of impredicativity. The propositional-resizing sort of impredicativity is indeed very helpful for formalizing mathematics (which sounds like what you were referring to), but impredicative quantification for a non-propositional universe is not really very relevant for mathematics. $\endgroup$ Commented Feb 10, 2022 at 18:35
  • 3
    $\begingroup$ @MarioCarneiro HoTT quotients do act the way you would expect when you talk only about types that are sets, because in that case you do have "local" proof-irrelevance. It's best to think about HoTT not as saying that "the types you're used to act in weird ways" but rather that "in addition to the types you're familiar with that act in the usual way, there are also higher types that act in different ways". $\endgroup$ Commented Feb 10, 2022 at 18:36
  • 1
    $\begingroup$ Paragraph number 2, about Basic Law V. Be careful: sometimes the proofs are hidden by a link, you have to click on it. $\endgroup$ Commented Feb 11, 2022 at 13:25
13
$\begingroup$

Andrej's answer that "Almost no pen-and-paper mathematics is written in ZFC" is correct. But it's perhaps also worth noting that some pen-and-paper mathematics is written in ZFC (or, at least, something closer to ZFC than to type theory), such as much of the mathematics done by set theorists (in which phrase, of course, "set" refers traditionally to a ZFC-set).

A good deal of set theory can be rephrased more structurally to make sense in type theory, but this would be a rephrasing, and the amount of work that would be required is, I think, variable. For instance, set theorists work with ordinals defined in the von Neumann way, with $\in$ as the well-founded relation. This in particular implies that ordinals are literally unique representatives of isomorphism classes of well-ordered sets. In type theory it is more natural to work "structurally" with arbitrary well-ordered sets rather than with von Neumann ordinals. This makes some things more cumbersome because of isomorphisms that get carried around (although under univalence, these isomorphisms become equalities), but probably doesn't change things a whole lot.

On the other hand, as far as I know, no one has ever come up with a convincing structural presentation of Godel's constructible universe $L$. The only structural approaches to $L$ that I know of essentially involve building a model of ZF(C) in some way and then constructing $L$ inside that model. Note that $L$ is, as far as I know, still the only way to prove the relative consistency of the Axiom of Choice, so it is of interest even to mathematicians who don't care about ZF for its own sake. (In contrast, the symmetric/permutation methods used to prove relative consistency of not-AC, and the forcing methods that can be used to prove consistency of other properties such as GCH and not-GCH, seem much more amenable to structuralization.) [Note: this paragraph was edited to remove a false claim that GCH is not forceable; see comments.]

As another example, Scott's trick is a method used in pen-and-paper mathematics that is of interest beyond set theory, but relies on the axiom of foundation from ZFC, and so is not obviously formalizable in type theory.

$\endgroup$
20
  • $\begingroup$ You can force GCH using Easton (class) forcing. That’s essentially the same as good old forcing, but the poset used is a definable class instead of an element of the ground model. $\endgroup$ Commented Mar 5, 2022 at 2:05
  • 2
    $\begingroup$ I had the same thought as PMP but I gave up on it because the construction of L is throwing in rather specific sets (the definable ones, in a suitable sense), whereas an inductive-recursive definition of U throws in functions A → U from the ambient type theory. I am afraid this won't give enough control over what lands in U. $\endgroup$ Commented Mar 6, 2022 at 7:43
  • 1
    $\begingroup$ @PedroSánchezTerraf Thanks. I would actually be interested already in a reference for how to force ordinary CH. Why is this not better known? Everyone always cites L as the reason why (G)CH is consistent but forcing as the reason why not-(G)CH is consistent. $\endgroup$ Commented Mar 6, 2022 at 17:38
  • 1
    $\begingroup$ @PedroSánchezTerraf Most uses of ordinals can be easily rephrased structurally in terms of arbitrary well-founded relations. $\endgroup$ Commented Mar 15, 2022 at 16:05
  • 1
    $\begingroup$ Sorry for commenting on a years-old answer, but doesn't forcing GCH imply you can force AC, because GCH implies AC? (A citation for "GCH implies AC" appears in the MO question "Does $2^X=2^Y\Rightarrow |X|=|Y|$ imply the axiom of choice?" and it is also proven in Metamath.) $\endgroup$ Commented Aug 8 at 21:35
3
$\begingroup$

Type theory seems to have a bit of difficulty with partial functions in practice. Since total functions are the primitive concept, you have to code partial functions somehow. I've seen the following approaches:

  • Use some specific junk value (e.g., 2 - 3 = 0 : ℕ and 1 / 0 = 0 : ℚ).
  • Use an undefined junk value (i.e., 1 / 0 is a term of the appropriate type, but you can't prove anything about its particular value). (This is the approach sometimes used in Isabelle/HOL with its undefined term.)
  • Use a maybe/option monad. In other words, rather than having subtraction on be a function of type ℕ → ℕ → ℕ, you have it be a function of type ℕ → ℕ → ℕ ⊕ Unit, using () : Unit as your undefined value.
  • Use something like Lean's PFun monad. So now subtraction on the naturals would be a function of type Σ a b : ℕ, Σ p : a ≥ b, ℕ, which takes two inputs a and b and a proof p that a is greater than or equal to b and then produces a - b : ℕ. (Or something like this. This isn't literally what Lean's PFun monad does, but it's essentially equivalent.)
  • Use side conditions or subtypes (which is what's used in PVS). These are formally quite similar to the PFun approach, but are a bit different from an end-user perspective.

The last three are obviously more 'conceptually correct' but they're enough of a hassle that the first approach is fairly common. (I think Rocq, Agda, Lean, and Isabelle/HOL all have 2 - 3 = 0 : ℕ, for instance.) This leads to its own issues though, as discussed by Loeffler and Stoll in Section 5 of Formalizing zeta and L-functions in Lean. They had to perform a (in their words) "lengthy and quite delicate computation" to establish that Lean's definition of the Riemann zeta function satisfies $\zeta(1) = \frac{1}{2}(\gamma - \log 4\pi)$ in order to show in particular that Lean's value of $\zeta(1)$ didn't make certain statements of the Riemann hypothesis trivially false (since in principle it might have been the case that $\zeta(1) = 0$). This result is now a named theorem in Mathlib, specifically riemannZeta_one. So, in other words, the difficulty with talking about partial functions directly eventually necessitated the inclusion of a mathematically non-trivial junk theorem in Mathlib.

New contributor
James E Hanson is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
7
  • $\begingroup$ Do you consider this to be a purely practical issue or you mean to imply that there is an underlying theoretical issue? I understood the question as being about concepts that we just don't know how to express in type theory at all (as in the $V=L$ example from Mike's answer, and one could add things like "there exists a Reinhardt cardinal"). The definition of a partial element of $X$ as a proposition with a map into $X$ is pretty much the same as one would write in $\mathsf{IZF}$, isn't it? $\endgroup$ Commented yesterday
  • $\begingroup$ On the other hand, in the spirit of "drawing inspiration from practical problems as a source of interesting theoretical problems" (which I very much like), it would be interesting to work out a type theory with partial terms and prove its conservativity. $\endgroup$ Commented yesterday
  • $\begingroup$ See also: proofassistants.stackexchange.com/questions/602/… $\endgroup$ Commented yesterday
  • $\begingroup$ It's only a practical issue but I think it's a meaningful one. $\endgroup$ Commented 21 hours ago
  • $\begingroup$ @JeanAbouSamra If I were formalizing partial functions in $\mathsf{IZF}$, I would do it in the same way I would in $\mathsf{ZF}$, as sets of ordered pairs. $\endgroup$ Commented 21 hours ago

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.