Assessment exercises 2

Let X be a set of letters such as p , q , r , ; suppose the symbols   (   )   are not in X . We define an alphabet L consisting of letters in X together with the symbols , ( , ) , . We will define a formal system Imp on this alphabet and investigate its properties.

Definition.

The set of well-formed formulas of Imp is the least set WFF of strings of L such that

Definition.

A string α is an initial part of β if there is a string of symbols γ of nonnegative length (possibly zero) from L such that β is the concatenation α γ .

Exercise 2.1.

Prove the Unique Readability Lemma that says that if α , β WFF and α is an initial part of β then α = β . (Hint: use induction.)

Definition.

Suppose f : X 0 1 . We extend f to a function F f : WFF 0 1 as follows.

Definition.

Suppose Σ WFF and σ WFF . We write Σ σ to mean: whenever f : X 0 1 there is some v { F f ( τ ) : τ Σ } 1 such that F f ( σ ) v .

Exercise 2.2.

Prove that Σ τ σ if and only if Σ ( τ σ ) .

Definition.

A formal system is devised such that is least such that

Exercise 2.3.

Prove the Soundness Theorem, Σ σ implies Σ σ . (Use induction on length of proofs.)

Exercise 2.4.

Show that if Σ WFF and σ WFF then Σ implies either Σ σ or Σ ( σ ) .

Exercise 2.5.

Show that if Σ WFF and σ WFF then Σ ( σ ) if and only if Σ σ .

Exercise 2.6.

Assuming Σ WFF and Σ , show that there is f : X 0 1 such that F f ( τ ) = 1 for all τ Σ . (Hint: show there is a maximal Σ + Σ such that Σ + .)

Exercise 2.7.

Prove the Completeness Theorem, Σ σ implies Σ σ . (Use previous results.)