Assessment exercises 2

Let $X$ be a set of letters such as $p, q, r, \dots$ ; suppose the symbols $⊥ () \to$ are not in $X$ . We define an alphabet $L$ consisting of letters in $X$ together with the symbols $⊥, (,), \to$ . 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 $σ, τ \in WFF$ then the string $(σ \to τ)$ formed by concatenation of $σ, τ$ with the symbols $(, \to,)$ 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 $α, β \in WFF$ and $α$ is an initial part of $β$ then $α = β$ . (Hint: use induction.)

Definition.

Suppose $f : X \to \{0, 1\}$ . We extend $f$ to a function $F_{f} : WFF \to \{0, 1\}$ as follows.

$F_{f} (⊥) = 0$
$F_{f} (a) = f (a)$ for each $a \in X$
$F_{f} (σ \to τ) = 0$ if $F_{f} (σ) > F_{f} (τ)$ and $F_{f} (σ \to τ) = 1$ if $F_{f} (σ) ⩽ F_{f} (τ)$ .

Definition.

Suppose $Σ \subseteq WFF$ and $σ \in WFF$ . We write $Σ ⊨ σ$ to mean: whenever $f : X \to \{0, 1\}$ there is some $v \in \{F_{f} (τ): τ \in Σ\} \cup \{1\}$ such that $F_{f} (σ) ⩾ v$ .

Exercise 2.2.

Prove that $Σ \cup \{τ\} ⊨ σ$ if and only if $Σ ⊨ (τ \to σ)$ .

Definition.

A formal system $⊢$ is devised such that $⊢$ is least such that

The Given rule: if $α \in Σ$ then $Σ ⊢ α$
$\to$ -Introduction: if $Σ \cup \{α\} ⊢ β$ then $Σ ⊢ (α \to β)$ .
$\to$ -Elimination: if $Σ ⊢ α$ and $Σ ⊢ (α \to β)$ then $Σ ⊢ β$ .
$⊥$ -Elimination: if $Σ ⊢ ((α \to ⊥) \to ⊥)$ then $Σ ⊢ α$ .

Exercise 2.3.

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

Exercise 2.4.

Show that if $Σ \subseteq WFF$ and $σ \in WFF$ then $Σ ⊬ ⊥$ implies either $Σ \cup \{σ\} ⊬ ⊥$ or $Σ \cup \{(σ \to ⊥)\} ⊬ ⊥$ .

Exercise 2.5.

Show that if $Σ \subseteq WFF$ and $σ \in WFF$ then $Σ \cup \{(σ \to ⊥)\} ⊢ ⊥$ if and only if $Σ ⊢ σ$ .

Exercise 2.6.

Assuming $Σ \subseteq WFF$ and $Σ ⊬ ⊥$ , show that there is $f : X \to \{0, 1\}$ such that $F_{f} (τ) = 1$ for all $τ \in Σ$ . (Hint: show there is a maximal $Σ^{+} \supseteq Σ$ such that $Σ^{+} ⊬ ⊥$ .)

Exercise 2.7.

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