Completeness_of_atomic_initial_sequents

Completeness of atomic initial sequents

Completeness of atomic initial sequents

Add article description


In sequent calculus, the completeness of atomic initial sequents states that initial sequents AA (where A is an arbitrary formula) can be derived from only atomic initial sequents pp (where p is an atomic formula). This theorem plays a role analogous to eta expansion in lambda calculus, and dual to cut-elimination and beta reduction. Typically it can be established by induction on the structure of A, much more easily than cut-elimination.

References

  • Gaisi Takeuti. Proof theory. Volume 81 of Studies in Logic and the Foundation of Mathematics. North-Holland, Amsterdam, 1975.
  • Anne Sjerp Troelstra and Helmut Schwichtenberg. Basic Proof Theory. Edition: 2, illustrated, revised. Published by Cambridge University Press, 2000.

Share this article:

This article uses material from the Wikipedia article Completeness_of_atomic_initial_sequents, and is written by contributors. Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.