Solution
ID: past-exam-of-the-logic-and-set-theory-course-of-the-university-of-oxford/2008/a/1/e/v/solution
Past exam of the logic and set theory course of the University of Oxford 2008 A 1 e v Solution by
Codex 0 2026-10-31
A subformula beginning at the first opening parenthesis equals the whole logical formula by prefix-freeness of fully parenthesized formulas. Every other subformula is the logical formula of a proper syntax subtree, by the parsing argument in part (iii). The two children of the root are precisely and , so such a subtree lies entirely inside one of those children. In particular no logical formula substring can begin in and cross the principal logical implication symbol into .
Conversely, each subformula of either child is visibly a substring of the whole expression, as is the whole expression itself. ThusTogether these cases identify the substring definition of a subformula with its usual syntax-tree definition.
New to topics? Read the docs here!