Completeness of atomic initial sequents
Encyclopedia
In sequent calculus
, the completeness of atomic initial sequents states that initial sequents (where is an arbitrary formula) can be derived from only atomic initial sequents (where 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 , much more easily than cut-elimination.
Sequent calculus
In proof theory and mathematical logic, sequent calculus is a family of formal systems sharing a certain style of inference and certain formal properties. The first sequent calculi, systems LK and LJ, were introduced by Gerhard Gentzen in 1934 as a tool for studying natural deduction in...
, the completeness of atomic initial sequents states that initial sequents (where is an arbitrary formula) can be derived from only atomic initial sequents (where is an atomic formula
Atomic formula
In mathematical logic, an atomic formula is a formula with no deeper propositional structure, that is, a formula that contains no logical connectives or equivalently a formula that has no strict subformulas. Atoms are thus the simplest well-formed formulas of the logic...
). This theorem plays a role analogous to eta expansion in lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
, and dual to cut-elimination and beta reduction. Typically it can be established by induction on the structure of , much more easily than cut-elimination.