\documentclass{article}

\begin{document}

{\bf Assignment 2, Problem 3}

{\em
What is the maximum number of nodes that can appear in an analytic tableau
(considered as a tree) for a formula of degree $n$?  Explain your answer.
}

\medskip

The most common solution was the following:

\medskip

{\em
While going from one level of the tableau to the next
the degree of the formula decreases.
Therefore the heights of the tableau tree is at most $n+1$.
Each node in the tableau tree can have one child ($\alpha$-type) or
two children ($\beta$-type).
In the worst case if all nodes are $\beta$-type we have a binary tree
with the heights at most $n+1$.
We know that this tree can have at most $2^{n+1}-1$ nodes.
Thus we have an upper bound for the number of the nodes in the tableau:  $2^{n+1}-1$.
This bound is reachable when we have a branch point at every node,
i.e. when each node has $\beta$-type.
}

\medskip

This solution gives us the correct upper bound, but the last sentence is wrong!
If all nodes have $\beta$-type then the tableau should have only linear number
of nodes: $2n+1$.

Indeed, suppose that {\em all} formulas in the tableau are $\beta$.
Then we always have to use the last formula in the path at each point.
Therefore we use each connectives exactly once. That is, there are exactly $n$
branching points in the tableau tree (forget about negation).
We know that a binary tree with $n$ branching point has $2n+1$ nodes.
(We can also prove it by induction on the construction of the formula).

Is $2n+1$ correct answer? No. If we alternate $\alpha$ and $\beta$ formulas we
can get exponential many nodes in the tree.

Consider formulas $Y_i=(p_i \wedge q_i)$
and $X_i=Y_1 \vee Y_2 \vee  \dots \vee Y_i$.
Take $k=[n/2]$ and construct the tableau for $F X_k$.
First, we get two formulas $F(p_k \wedge q_k)$ and $X_{k-1}$ (lines 2 and 3).
Then use the $\beta$-formula $F(p_k \wedge q_k)$.
This formula gives us two branches (lines 4 and 5).
Now unused line (3) lies on the both branches.
So we have to use the formula  $X_{k-1}$ twice on both branches.
Then we will use $X_{k-2}$ four times, and so on.

\newcommand{\tree}[3]{
  \begin{array}{c}
    #1 \\
    \begin{array}{c|c}
      #2 & #3
    \end{array}
  \end{array}}

$$
\hspace{-4cm}
\tree
{
 \begin{array}{lll}
     (1) & F X_k \\
     (2) & F p_k \wedge q_k & (1)  \\
     (3) & F X_{k-1} & (1)  \\
 \end{array}
 }
{\tree
  {
    \begin{array}{lll}
      (4) & F p_k & (2) \\
      (6) & F p_{k-1} \wedge q_{k-1} & (3)  \\
      (7) & F X_{k-2} & (3)  \\
    \end{array}
    }
    {
      \begin{array}{lll}
        (8) & F p_{k-1} & (6) \\
        (10) & F p_{k-2} \wedge q_{k-2} & (7)  \\
        (11) & F X_{k-3} & (7)  \\
     & \dots \\
      \end{array}
      }
    {
      \begin{array}{lll}
        (9) & F q_{k-1} & (6) \\
        (12) & F p_{k-2} \wedge q_{k-2} & (7)  \\
        (13) & F X_{k-3} & (7)  \\
     & \dots \\
      \end{array}
      }
}
{\tree
  {
    \begin{array}{lll}
      (5) & F q_k & (2) \\
      (14) & F p_{k-1} \wedge q_{k-1} & (3)  \\
      (15) & F X_{k-2} & (3)  \\
    \end{array}
    }
    {
      \begin{array}{lll}
        (16) & F p_{k-1} & (14) \\
        (18) & F p_{k-2} \wedge q_{k-2} & (15)  \\
        (19) & F X_{k-3} & (15)  \\
     & \dots \\
      \end{array}
      }
    {
      \begin{array}{lll}
        (17) & F q_{k-1} & (14) \\
        (20) & F p_{k-2} \wedge q_{k-2} & (15)  \\
        (21) & F X_{k-3} & (15)  \\
     & \dots \\
      \end{array}
      }
}
$$


Let $nodes(X_k)$ be the number of nodes in this tableau.
Then $nodes(X_k)=2nodes(X_{k-1})+3$. Therefore $nodes(X_k)=3*(2^k-1)$.
Remember that $k=[n/2]$.
The degree of $X_k$ is at most $n$, and the number of nodes in the tableau is
$3*(2^{[n/2]}-1)$.

Even if we use $\alpha$-formulas before $\beta$-formulas, we still get the
exponential number of nodes. In this case we get the tableau with
$2^{k+1}+2k-1$ nodes:


$$
\tree
{
 \begin{array}{lll}
     (1) & F X_k \\
     (2) & F p_k \wedge q_k & (1)  \\
     (3) & F X_{k-1} & (1)  \\
     (4) & F p_{k-1} \wedge q_{k-1} & (3)  \\
     (5) & F X_{k-2} & (3)  \\
     & \dots \\
     & \dots \\
 \end{array}
}
  {\tree
    {
    \begin{array}{lll}
      (6) & p_k & (2)
    \end{array}
    }
      {
        \begin{array}{lll}
          (8) & p_{k-1} & (4) \\
     & \dots \\
        \end{array}
        }
      {
        \begin{array}{lll}
          (9) & q_{k-1} & (4) \\
     & \dots \\
        \end{array}
        }
      }
  {\tree
    {
    \begin{array}{lll}
      (7) & q_k & (2)
    \end{array}
    }
      {
        \begin{array}{lll}
          (10) & p_{k-1} & (4) \\
     & \dots \\
        \end{array}
        }
      {
        \begin{array}{lll}
          (11) & q_{k-1} & (4) \\
     & \dots \\
        \end{array}
        }
      }
$$



\end{document}