While this submission is a draft, it cannot be used by other submissions.

Proof of `Completeness for simple rational terms`

groundedproofs/Lax149335Proofs/Results/SimpleCompleteness.lean · lax-149335

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

The completeness rule and the conjugacy rule are proved together by induction on the nesting depth of lists in the input type. The completeness rule follows the proof of Theorem 2.6. For the conjugacy rule with a nonempty value ww of length kk, Lemmas 6.4 and 6.5 reduce to co-pairings of kk-guarded nonempty terms. After grouping the list into bundles of size at least kk with the bundle lemma (Lemma 6.7), the bundled terms become syntactically ww-conjugate, by the induction hypothesis, and Lemma 6.2 applies. The bundle isomorphism is cancelled with Lemma 5.5.