On verifying that primitive-recursive functions are provably total in PA

[iblech]

As far as I see, the book doesn't state or prove that primitive-recursive functions are provably total in PA; but most of the ingredients are there! The only thing missing is an explanation that Peano arithmetic proves that one can append elements to lists (coded via the beta function as numbers). I'd like to write a remark sketching that argument. Is there interest in that?

There is, however, a slight problem. The construction given in the proof of the beta function lemma uses the factorial function. I don't know how to verify in a non-circular fashion that the factorial function is total. I'd therefore change j! to lcm(1,...,j). Unlike the factorial function, the function j \mapsto lcm(1,...,j) can be represented and verified to be total without recourse to the beta function. The rest of the proof can be adapted to this change with extremely minimal effort. Am I missing something? Should I go ahead with the change?

[rzach]

I'll think about the change to the beta function lemma. One fundamental principle I like to follow is that proofs remain as simple as possible. I would definitely welcome an explanation of provably total functions -- could be its own chapter! If the change from factorial to lcm makes the beta function lemma harder to understand on a first read, my instinct would be to re-prove it with the change (and perhaps an explanation why the original proof isn't enough). That said, for the typical non-math student the beta function lemma may be a black box anyway. I'll see @avigad on Monday and ask him what he thinks.

[iblech]

Any updates on this? My current (research and teaching) focus is not on these foundational matters, hence there is no need to hurry from my side, but I still believe this issue to be relevant.

In my personal opinion, I don't think that the change to the lcm function will make the proof substantially harder.

[rzach]

Sorry that I spaced on this. I did talk to Jeremy at the time and IIRC he was intrigued. Before making the change in https://github.com/OpenLogicProject/OpenLogic/blob/master/content/incompleteness/representability-in-q/beta-function.tex via pull request, maybe let's see how it'd look with the change. What's there right now is just a sketch and doesn't have enough detail anyway. Eg I never go through the proof, just use the fact. So in other words: go ahead! But let's put the new material (including a changed beta function lemma discussion) into a new chapter -- or just do it offline for now, by email. When it's done I'll either revise the old section.

[beastaugh]

Do I take it that this didn't result in any concrete changes? I've been teaching the beta function lemma from the current version and didn't find it so lacking in detail (but my students are mathematicians, so I just spelled out a couple of points in slightly more detail—it didn't seem to need a complete overhaul). In any case, if the two of you think this is potentially worth doing, I'd be happy to have a look whether we could cleanly replace the factorial function with the lcm function without many changes or much difference in explanatory difficulty.

[rzach]

Go for it!

[avigad]

In case it's helpful, an interpretation of PRA in ISigma_1 is described in Section 10.4 of my book, Mathematical Logic and Computation. Hajek and Pudlak's book has sharper versions of some theorems, but I tried to keep the proofs reasonably easy.

[beastaugh]

Thanks Jeremy, I'll have a look at the proofs in your book.

[beastaugh]

I've added some commits making the minimal change of swapping out the factorial function for the lcm function on this branch:

https://github.com/beastaugh/OpenLogic/commits/beta/

[beastaugh]

I fixed the issues noted in this commit:

beastaugh@199a7f2

Once this is included we can also close this pull request of @iblech which is basically the same as mine.