Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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}$.


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:


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.


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?

share|cite|improve this question

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.

share|cite|improve this answer
+1 Thank you for the answer to this old question. Give me some time to digest before I hand out the check mark. – Code-Guru Nov 5 '13 at 23:28
up vote 0 down vote accepted

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}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.