Tableau Extension Lemma/General Statement
Theorem
Let $T$ be a finite propositional tableau.
Let its hypothesis set $\mathbf H$ be finite.
Let $\mathbf H'$ be another finite set of WFFs.
Then there exists a finished finite propositional tableau $T'$ such that:
$(1):\quad$ the root of $T'$ is $\mathbf H \cup \mathbf H'$;
$(2):\quad$ $T$ is a rooted subtree of $T'$.
Proof 1
Let $T_{\mathbf H'}$ be the finite propositional tableau obtained by replacing the hypothesis set $\mathbf H$ of $T$ with $\mathbf H \cup \mathbf H'$.
By the Tableau Extension Lemma, $T_{\mathbf H'}$ has a finished extension $T'$.
By definition of extension, $T_{\mathbf H'}$ is a rooted subtree of $T'$.
But $T_{\mathbf H'}$ and $T$ are equal when considered as rooted trees.
The result follows.
$\blacksquare$
Proof 2
The proof uses induction on the number $n$ of elements of $\mathbf H$.
Suppose we are given the result for the case $n = 1$, that is, when $\mathbf H$ is a singleton.
Suppose also that we are given the result for all sets $\mathbf H'$ with $n$ elements.
Now, given a set $\mathbf H' = \set {\mathbf A_1, \ldots, \mathbf A_{n+1} }$ with $n + 1$ elements.
Let $T$ be a finite propositional tableau.
By induction hypothesis, there is a finished finite propositional tableau $T'$ containing $T$ as a subgraph, and with root $\mathbf H \cup \set {\mathbf A_1, \ldots, \mathbf A_n}$.
Now apply the case $n = 1$ to this resulting propositional tableau $T'$ and the set $set {\mathbf A_{n + 1} }$.
This yields a finished finite propositional tableau $T$ which:
$(1):\quad$ has root $\mathbf H \cup \set {\mathbf A_1, \ldots, \mathbf A_n} \cup \set {\mathbf A_{n + 1} } = \mathbf H \cup \mathbf H'$;
$(2):\quad$ contains $T'$ as a subgraph.
But then $T$ also contains $T$ as a subgraph, proving the result for $\mathbf H'$.
It thus only remains to take care of the base cases $n = 0$ and $n = 1$.
First, the case $n = 0$.
Let $T$ be a finite propositional tableau.
To find the finite propositional tableau $T'$ with the desired properties, we use some of the tableau construction rules, starting with $T$.
Let $t$ be any leaf node of $T$, and let $\Gamma_t$ be the branch from Leaf of Rooted Tree is on One Branch.
Let $\map n {\Gamma_t}$ be the number of non-basic WFFs that were not used to add any of the nodes of $\Gamma_t$ to $T$.
It is seen that for any application of the tableau construction rules on $t$:
- If $s$ is added by the rule, then $\map n {\Gamma_s} \le \map n {\Gamma_t}$.
Moreover, it is seen that any rule reduces the total count $\map m {\Gamma_t}$ of logical connectives occurring in these non-basic, unused WFFs along $\Gamma_t$.
In conclusion:
- If $s$ is added by a rule, then $\map m {\Gamma_s} < \map m {\Gamma_t}$
By the Method of Infinite Descent applied to $\map m {\Gamma_t}$, only finitely many rules can be applied, starting from $t$.
Since $T$ has only finitely many leaves and corresponding branches, only finitely many rules can be applied to $T$ in total.
Let $T'$ be the finite propositional tableau resulting from applying all these possible rules.
By construction of $T'$, it follows that every branch of $\Gamma$ is either contradictory or finished.
That is, $T'$ is finished.
Finally, the last case, $n = 1$.
Let $\mathbf A$ be a WFF of propositional logic.
Let $T$ be a finite propositional tableau.
First, using the case $n = 0$, extend $T$ to a finished finite propositional tableau $T'$.
Again using the case $n = 0$, let $T_{\mathbf A}$ be a finished finite propositional tableau with root $\set {\mathbf A}$.
Now add $\mathbf A$ to the root of $T'$.
Then at every leaf $t$ of $T'$, $\mathbf A$ is the only WFF that is not used yet.
As far as the rules for propositional tableaus are concerned, there is no difference between:
- $t$ as a leaf of $T'$, and
- the tableau consisting only of a root and with hypothesis set $\mathbf A$.
Therefore, the rules allow to "paste", as it were, the finished tableau $T_{\mathbf A}$ under every leaf $t$ of $T'$.
Denote the resulting tableau with $T'_{\mathbf A}$.
Then for any branch $\Gamma$ of $T'_{\mathbf A}$ and every non-basic WFF $\mathbf B$ along it:
- $\mathbf B$ is on $T'$, or:
- $\mathbf B$ is on a copy of $T_{\mathbf A}$.
In either case, the finished nature of these tableaus implies that:
Hence $\Gamma$ is contradictory or finished.
In conclusion, $T'_{\mathbf A}$ is finished, and contains $T$ as a subgraph.
The result follows from the Principle of Mathematical Induction.
$\blacksquare$