OpenLogicProject / OpenLogicProject/OpenLogic

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

Open
#160 9 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
TeX
Stars
1.4k
Forks
288
PR merge metrics
No merged PRs in 30d

Description

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?

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reviewing the book's beta function lemma and its use of the factorial function. Compare the proposed lcm(1,...,j) replacement and ensure the added remark explains, without circularity, that primitive-recursive functions are provably total in PA; done means the argument is complete and consistent with the existing proof.

Written by the indexing model from the issue text.

Assessment

Tech stack
tex
Domain
content, documentation
Issue type
Documentation
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.