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

• $⊥$ is in $WFF$
• each $a$ from $X$ is in $WFF$
• if $σ , τ ∈ WFF$ then the string $( σ → τ )$ formed by concatenation of $σ , τ$ with the symbols $( , → , )$ is in $WFF$.

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.

• $F f ( ⊥ ) = 0$
• $F f ( a ) = f ( a )$ for each $a ∈ X$
• $F f ( σ → τ ) = 0$ if $F f ( σ ) > F f ( τ )$ and $F f ( σ → τ ) = 1$ if $F f ( σ ) ⩽ F f ( τ )$.

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

• The Given rule: if $α ∈ Σ$ then $Σ ⊢ α$
• $→$-Introduction: if $Σ ∪ α ⊢ β$ then $Σ ⊢ ( α → β )$.
• $→$-Elimination: if $Σ ⊢ α$ and $Σ ⊢ ( α → β )$ then $Σ ⊢ β$.
• $⊥$-Elimination: if $Σ ⊢ ( ( α → ⊥ ) → ⊥ )$ then $Σ ⊢ α$.

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.)