Proving Set is Complete

Use Proof by Structural Induction

Structure

We want to show that set $C$ is complete

1. Define set $\mathcal{G}$ that uoc $\{\neg ,\wedge \}$ or $\{\neg ,\vee \}$
2. Use Proof by Structural Induction to prove that for every forumla $F\in \mathcal{G},\exists F^{\prime }$ s.t $F^{\prime }$ uoc $C$

Example

Prove that Zero Identity and implication forma complete set. $\{0,\to \}$

Step 1

Define set $\mathcal{G}$ of formulas that uoc $\{\neg ,\vee \}$

• Let $\mathcal{G}$ be the smallest set such that:
  • Basis: $x$ is a propositional variable, then $x\in \mathcal{G}$
  • Induction step: If $F_1,F_2\in \mathcal{G}$, then $\neg F_1,(F_1\vee F_2)\in \mathcal{G}$

Step 2

Now we prove that for all formula $F\in \mathcal{G}$, $\exists$ formula $F^{\prime }$ s.t $F^{\prime }$ uoc $\{0,\to \}$ and $F^{\prime }\equiv F$

Basis

Let $F=x$ where $x$ is a propositional variable Then $F^{\prime }$ uoc $\{0,\to \}$ (F’ uses no connectives at all) And $F^{\prime }\equiv F$ ($F^{\prime }=F$) As wanted

Induction Step

Suppose that are formulas $F_1^{\prime }$ and $F_2^{\prime }$ s.t $F_1^{\prime },F_2^{\prime }$ uoc $\{0,\to \}$ and $F_1^{\prime }\equiv F_1$ and $F_2^{\prime }\equiv F_2$ (IH) Then, there are two cases:

• $F=\neg F_1$
• $F=(F_1\vee F_2)$ Case 1:
• For $F=\neg F_1$, let $F^{\prime }=(F_1^{\prime }\to 0F_1^{\prime })$
  • Then, $F^{\prime }$ uoc $\{0,\to \}$ by IH as $F_1^{\prime }$ uoc $\{0,\to \}$
  • and, $F^{\prime }=\{0,\to \}\equiv (F_1\to 0F_1)$ by IH as $F_1^{\prime }\equiv F_1$
  • $\equiv \neg F_1$ as $0F_1$ is always falsified so $F_1\to 0F_1$ is satisfied when $F_1$ is false
  • $=F$’ Case 2:
• For $F=(F_1\vee F_2),$ let $F^{\prime }=((F_1^{\prime }\to 0F_1^{\prime })\to F_2^{\prime })$
• Then, $F^{\prime }$ uoc $\{0,\to \}$
• and $F^{\prime }=((F_1^{\prime }\to 0F_1^{\prime })\to F_2^{\prime })$
• $\equiv ((F_1\to 0F_1)\to F_2)$
• $\equiv (\neg F_1\to F_2)$
• $\equiv (\neg \neg F_1\vee F_2)$
• $\equiv (F_1\vee F_2)$
• $=F$
• As wanted $\square$

Step 3

Since $\{\neg ,\vee \}$ is complete, therefore $\{0,\to \}$ is also complete $\square$