2

This is an exercise in Mendelson's Mathematical Logic.

If $\mathscr{B} \implies \mathscr{D}$ is a tautology, and $\mathscr{B}$ and $\mathscr{D}$ have the statement letters $B_1, \dots, B_n$ in common, then there is a statement form $\mathscr{C}$ having only $B_1, \dots, B_n$ such that $\mathscr{B} \implies \mathscr{C}$ and $\mathscr{C} \implies \mathscr{D}$ are tautologies.

Is $B_1, \dots, B_n$ supposed to be precisely all the statements letters $\mathscr{B}$ and $\mathscr{D}$ have in common or just some of the ones they have in common (but perhaps not all of them)?

user197498
  • 41
  • 1
    Every statement letter ${\mathscr B}$ and ${\mathscr D}$ have in common should occurr among the $B_i$. For assume you pick no $B_i$ at all, i.e. $n=0$. Then, up to equivalence you can only choose between ${\mathscr C}=0$ or ${\mathscr C}=1$, which both do not fulfill the requirement that ${\mathscr B}\Rightarrow{\mathscr C}$ and ${\mathscr C}\Rightarrow{\mathscr D}$ are tautologies if neither $\neg\ {\mathscr B}$ nor ${\mathscr C}$ are such. – Hanno Dec 04 '14 at 08:03
  • Mendelson definitely means that the $B_1, \ldots, B_n$ lists all the statement letters that $\cal B$ and $\cal D$ have in common. $\cal C$ need not contain all the $B_i$, but you could arrange that if you wanted by adding trivial conjuncts $B_i \Leftrightarrow B_i$ to $\cal C$ – Rob Arthan Dec 04 '14 at 23:14

1 Answers1

0

Mendelson means that $B_1, \ldots, B_n$ are all the shared letters.

An interpolant, $\mathscr C$, may have all the shared letters in it, or just some of them.

For example, consider $$(A \land (B \lor \lnot B)\land D) \Rightarrow (A \lor (B \land C))$$

One interpolant here is $\mathscr C \equiv A$. Another is $A \land (B \lor \lnot B)$.

The interpolant you are likely to construct in the proof, however, will probably include all the shared letters.

Carl Mummert
  • 81,604