Let be a set of letters such as ; suppose the symbols are not in . We define an alphabet consisting of letters in together with the symbols . We will define a formal system on this alphabet and investigate its properties.
The set of well-formed formulas of is the least set of strings of such that
A string is an initial part of if there is a string of symbols of nonnegative length (possibly zero) from such that is the concatenation .
Prove the Unique Readability Lemma that says that if and is an initial part of then . (Hint: use induction.)
Suppose . We extend to a function as follows.
Suppose and . We write to mean: whenever there is some such that .
Prove that if and only if .
A formal system is devised such that is least such that
Prove the Soundness Theorem, implies . (Use induction on length of proofs.)
Show that if and then implies either or .
Show that if and then if and only if .
Assuming and , show that there is such that for all . (Hint: show there is a maximal such that .)
Prove the Completeness Theorem, implies . (Use previous results.)