Structural Induction: Base case leads to a contradiction

Question

To make my question clear, I will start with some definitions and notation from the book I am studying:

Definition:

A function $\theta$ from the set of formulas into the set of formulas is a substitution iff

1. $\theta\mathbf{X}$ is the empty formula iff $\mathbf{X}$ is the empty formula.

2. for all formulas $\mathbf{X}$ and $\mathbf{Y}$, $\theta\mathbf{XY}=\theta\mathbf{X}\theta\mathbf{Y}$; i.e., $\theta$ applied to a formula $\mathbf{XY}$ which is the concatentation of $\mathbf{X}$ and $\mathbf{Y}$ is the result of concatenating $\theta\mathbf{X}$ and $\theta\mathbf{Y}$.

Notation:

Let $\mathbf{x}_1,\ldots,\mathbf{x}_n$ be distinct primitive symbols and let $\mathbf{Y}_1,\ldots,\mathbf{Y}_n$ be formulas. $\mathsf{S}^{\mathbf{x}_1,\ldots,\mathbf{x}_n}_{\mathbf{Y}_1,\ldots,\mathbf{Y}_n}$ is that (finite) substitution $\theta$ such that $\theta\mathbf{x}_i=\mathbf{Y}_i$ for $1 \leq i \leq n$ and $\theta\mathbf{y} = \mathbf{y}$ for any primitive symbol $\mathbf{y}$ distinct from $\mathbf{x}_1,\ldots,$ and $\mathbf{x}_n$. If $\mathbf{Z}$ is a formula, we say that $(\mathsf{S}^{\mathbf{x}_1,\ldots,\mathbf{x}_n}_{\mathbf{Y}_1,\ldots,\mathbf{Y}_n}\mathbf{Z})$ is the result of simultaneously substituting $\mathbf{Y}_1$ for $\mathbf{x}_1$, ..., and $\mathbf{Y}_n$ for $\mathbf{x}_n$ in $\mathbf{Z}$.

---

Now for the problem I am trying to solve:

Exercise:

If $\mathbf{C}$ and $\mathbf{C}$ are wffs of propositional calculus, we say that $\mathbf{D}$ is obtained from $\mathbf{C}$ by identifying certain propositional variables if $\mathbf{D}$ is of the form $\mathsf{S}^{\mathbf{p}_1,\ldots,\mathbf{p}_n}_{\mathbf{q}_1,\ldots,\mathbf{q}_n}\mathbf{C}$ where $\mathbf{p}_1,\ldots,\mathbf{p}_n$ are distinct propositional variables of $\mathbf{C}$ and $\mathbf{q}_1,\ldots,\mathbf{q}_n$ are propositional variables of $\mathbf{C}$ distince from $\mathbf{p}_1,\ldots,$ and $\mathbf{p}_n$. Prove that if $\mathbf{C}$ is a tautology, and $\mathbf{D}$ is obtained from $\mathbf{C}$ by identifying certain propositional variables, then $\mathbf{D}$ is a tautology.

---

Finally, my proof begins with the typical set-up:

Beginning of a proof:

Suppose that $\mathbf{C}$ is a tautology, and $\mathbf{D}$ is obtained from $\mathbf{C}$ by identifying certain propositional variables. Let $\varphi$ be any assignment. We need to show that $\mathscr{V}_\varphi\mathbf{D}=\mathsf{T}$.

First note that, there are distinct propositional variables $\mathbf{p}_1,\ldots,\mathbf{p}_n$ of $\mathbf{C}$ and propositional variables $\mathbf{q}_1,\ldots,\mathbf{q}_n$ of $\mathbf{C}$ distinct from $\mathbf{p}_1,\ldots,\mathbf{p}_n$ such that $\mathbf{D}$ is of the form $\mathsf{S}^{\mathbf{p}_1,\ldots,\mathbf{p}_n}_{\mathbf{q}_1,\ldots,\mathbf{q}_n}\mathbf{C}$. Now we proceed by induction on the construction of $\mathbf{D}$.

Case 1. $\mathbf{D}$ is a propositional variable $\mathbf{r}$.

Case 1a. $\mathbf{r}$ is some $\mathbf{p}_i$.
This leads to an immediate contradiction since none of $\mathbf{p}_1,\ldots,\mathbf{p}_n$ appears in $\mathbf{D}$.

Case 1b. $\mathbf{r}$ is some $\mathbf{q}_i$.
Then $\mathbf{C}$ is $\mathbf{p}_i$. Then $\mathsf{T}=\mathscr{V}_\varphi\mathbf{C}=\mathscr{V}_\varphi\mathbf{p}_i$ for all substitutions $\varphi$. This is also a contradiction.

Case 1c. $\mathbf{r}$ is none of $\mathbf{p}_1,\ldots,\mathbf{p}_n$ or $\mathbf{q}_1,\ldots,\mathbf{q}_n$.
A similar argument shows a contradiction here as well.

---

Question:

Now I'm just not entirely sure how to continue. Do I simply state that the result is vacuously true for the base case and then continue with my induction cases for negation and disjunction?

Answer 1

For 1a, you're correct. None of the $\mathbf p_i$ can occur in $\bf D$, so this case is impossible.

For 1b and 1c, you've cut corners. These do not give rise to contradictions.

But indeed:

• For 1b: Given $\phi$, define $\phi'$ by: $$\phi'(\mathbf p) = \begin{cases}\phi(\mathbf q_i) & \text{if $\mathbf p= \mathbf p_i$}\\\phi(\mathbf p)&\text{otherwise}\end{cases}$$ Now show $\mathscr V_\phi \mathbf D = \mathscr V_{\phi'} \mathbf C$. Conclude.

• For 1c: Convince yourself that $\mathbf D = \mathbf C$. The result is immediate.

The type of argument used for 1b is important in this context. I suggest you memorise it, preferably by going through it in detail.

Answer 2

I had an epiphany and found a three-sentence proof for this problem using some theorems and definitions from the book:

Proof. Since $\mathbf{C}$ is a tautology, it is also a theorem by 1204. So $\mathbf{C}$ has a proof $\mathbf{C}_1,\ldots,\mathbf{C}_m$. But then by the Rule of Substitution $\mathsf{S}^{\mathbf{p}_1,\ldots,\mathbf{p}_n}_{\mathbf{q}_1,\ldots,\mathbf{q}_n}\mathbf{C}_1,\ldots,\mathsf{S}^{\mathbf{p}_1,\ldots,\mathbf{p}_n}_{\mathbf{q}_1,\ldots,\mathbf{q}_n}\mathbf{C}_m$ is a proof for $\mathsf{S}^{\mathbf{p}_1,\ldots,\mathbf{p}_n}_{\mathbf{q}_1,\ldots,\mathbf{q}_n}\mathbf{C}$.

---

1101 Rule of Subtitution. If $\mathscr{H} \vdash \mathbf{A}$, and if $\mathbf{p}_1,\ldots,\mathbf{p}_n$ are distinct variables which do not occur in any wff in $\mathscr{H}$, then $\mathscr{H} \vdash \mathsf{S}^{\mathbf{p}_1,\ldots,\mathbf{p}_n}_{\mathbf{B}_1,\ldots,\mathbf{B}_n}\mathbf{A}$.

1204 Completeness Theorem. Every tautology is a theorem of $\mathscr{P}$.