1
$\begingroup$

I currently have an idea and I'm wondering whether it could be implemented:

There is this system called Dedukti, which is essentially a kernel for various proof assistants. Can it be described that way?

I wonder if it could be done the other way around: a program with many kernels. In particular, could one create some kind of database program that stores various proofs, each of them made for different proof assistants, and then use this database program to verify the proofs by accessing the kernels of the respective proof assistants?

Would that be possible in principle, or is there something that fundamentally speaks against it?

$\endgroup$
3
  • 1
    $\begingroup$ Isn’t this database called GitHub? $\endgroup$ Commented May 11 at 23:29
  • 2
    $\begingroup$ But in seriousness, I don’t really understand what you are looking for or what this database would add? Is this about interoperability? About storing all known formal knowledge? The challenge is that proof assistants use computer code and it is usually important to keep that code working in a maintainable and composable manner. Putting stuff in a static and unchanging database often leads to bit rot. (This is in contrast to math papers which are still relevant 100 years later.) $\endgroup$ Commented May 11 at 23:34
  • $\begingroup$ @JasonRute math papers also bit rot. I am filled with dread trying to follow papers from the 1930s, the notation is all alien. $\endgroup$ Commented May 12 at 9:07

3 Answers 3

2
$\begingroup$

There are two things at play here. The first is about having different kernels for basically the same proof assistant. That is, having different programs that are all able to type-check essentially the same proofs. This is something the Lean community is quite keen on, for instance, with various external kernels implemented in various languages. But it seems this is not what you are after.

Instead, as far as I understand, you would like to be able to somehow communicate proofs between different proof assistants/kernels. The difficulty, here, is that basically all proof assistants have different logics. Some are relatively close (Rocq and Lean, for instance, are so close that at some point there was an exporter from the latter to the former), some are much further apart (for instance, Isabelle's HOL foundation is quite different from the dependent type systems used in Agda, Rocq, Lean…). The issue with this is twofold.

The first issue is called concept alignment. The issue is that, to be able to transfer a theorem between systems, you need to be able to translate its statement from one logical formalism into the other. This can seem like a trivial task, and indeed if the statement is e.g. about natural numbers, the translation can be relatively direct. However, for more complex/interesting statements about more complex/interesting objects, this would not be as easy at all! Think, for instance, about a statement about algebraic closures, or vector fields, or… And this is compounded by the fact that even in relatively close logical formalisms, choice can differ wildly in the way you set up definitions. Yet, you'd really like to make sure that you did not make a wrong statement about a subtly different object.

Second, while translating one single theorem might be vaguely useful, more often than not you would like to transfer an entire library, say a series of result about algebraic closures, rather than a single one. This makes concept alignment even harder, and especially so since different systems have different approaches to organising libraries. And typically libraries do not consist only of definitions/theorems, there are also all other sorts of objects, for instance including tactics/tactic scripts. Being able to make these communicate is even harder!

I do not wish to mean that translating between proof assistants is unfeasible, and multiple projects, in particular Dedukti which you mentioned, are trying hard to see what is feasible in this space. But at the moment at least it remains a long-term research question to achieve this sort of communication.

$\endgroup$
3
  • $\begingroup$ Thanks for the reply. It is definitely very interesting. However, let me clarify my question: Some theorems are implemented in many different proof assistants. To present them didactically, one could compare these implementations side by side. What I am interested in is bassically an editor that can display such proofs from different systems in parallel and send them to the respective kernels for verification. In essence, an editor that can work with multiple proof assistants simultaneously. $\endgroup$ Commented May 12 at 11:49
  • $\begingroup$ @FranziskusWiesnet So all you're looking for is an interface, some kind of IDE? Emacs and VSCode both have support for all major proof assistants. $\endgroup$ Commented May 12 at 12:36
  • $\begingroup$ You could say that, but I would still have to load each proof assistant individually, right? I would not be able to use multiple ones within a single document? The real question is whether something like that is fundamentally possible, or if there’s something that fundamentally prevents it. $\endgroup$ Commented May 12 at 12:43
2
$\begingroup$

There is this system called Dedukti, which is essentially a kernel for various proof assistants. Can it be described that way?

It can, I believe.

But this is a property that all "logical frameworks" share. For an introduction to logical frameworks, see Frank Pfenning's Logical Frameworks chapter in Handbook on Automated Reasoning (vol. II).

For example, Isabelle also acts as a "kernel" for various proof assistants and foundations of Mathematics. Hence you find Isabelle/X which is foundations X built atop Isabelle.

However, if you want to compare results from two separate foundations, a logical framework cannot do that. You need something more: a metalogical framework.

HOL is a metalogical framework, Feferman's $FS_{0}$ is another (see Feferman's paper for more details).

I wonder if it could be done the other way around: a program with many kernels. In particular, could one create some kind of database program that stores various proofs, each of them made for different proof assistants, and then use this database program to verify the proofs by accessing the kernels of the respective proof assistants?

This idea has been kicked around before. There were several different proposals for something like a hybrid combination of "proof wiki" and "rosetta code" using proof assistants to verify the results back around 2004 or 2007, as I recall. vdash.org was one which stood out, in my mind.

They went nowhere, really.

$\endgroup$
0
$\begingroup$

Why not?

Database of proofs --> [proof, proofID, kernelProofWasMadeWith]

for all proofs with ID = 5 for example, validate those proofs with the relevant kernel and display

As long as each kernel can act independent of eachother and all your solution aims to do is bring together the functionality of different "engines" I see nothing fundamentally impossible.

I have no knowledge of "proof engines" or how they work.

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.