Initial Part of WFF of PropLog is not WFF

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathbf A$ be a WFF of propositional logic.

Let $\mathbf S$ be an initial part of $\mathbf A$.


Then $\mathbf S$ is not a WFF of propositional logic.


Proof

The proof proceeds by strong induction on the length of a WFF of propositional logic.


Let $l \left({\mathbf Q}\right)$ denote the length of a string $\mathbf Q$.


For all $n \in \N_{> 0}$, let $P \left({n}\right)$ be the proposition:

The initial part of $\mathbf A$ such that $l \left({\mathbf A}\right) = n$ is not a WFF of propositional logic.


By definition, $\mathbf S$ is an initial part of $\mathbf A$ if and only if $\mathbf A = \mathbf {S T}$ for some non-null string $\mathbf T$.

Thus we note that $l \left({\mathbf S}\right) < l \left({\mathbf A}\right)$.


Basis for the Induction

Let $\mathbf A$ be a WFF such that $l \left({\mathbf A}\right) = 1$.

Then for an initial part $\mathbf S$:

$l \left({\mathbf S}\right) < 1 = 0$

That is, $\mathbf S$ must be the null string, which is not a WFF.

So the result holds for WFFs of length $1$.

That is, $P \left({1}\right)$ is true.


This is our basis for the induction.


Induction Hypothesis

Now we need to show that for $k \ge 1$, if $P \left({j}\right)$ is true for all $j \le k$, then it logically follows that $P \left({k + 1}\right)$ is true.


So this is our induction hypothesis:

The initial part of $\mathbf A$ such that $l \left({\mathbf A}\right) = k$ is not a WFF of propositional logic.


Then we need to show:

The initial part of $\mathbf A$ such that $l \left({\mathbf A}\right) = k + 1$ is not a WFF of propositional logic.


Induction Step

This is our induction step:


Let $\mathbf A$ be a WFF such that $l \left({\mathbf A}\right) = k + 1$.

Suppose $\mathbf D$ is an initial part of $\mathbf A$ which happens to be a WFF.

That is, $\mathbf A = \mathbf{D T}$ where:

$\mathbf D$ is a WFF
$\mathbf T$ is non-null.


There are two cases:


$(1): \quad \mathbf A = \neg \mathbf B$

where $\mathbf B$ is a WFF of length $k$.

Thus $\mathbf D$ is a WFF starting with $\neg$.

So:

$\mathbf D = \neg \mathbf E$

where $\mathbf E$ is also a WFF.

We remove the initial $\neg$ from $\mathbf A = \mathbf{D T}$ to get:

$\mathbf B = \mathbf{E T}$

But then $\mathbf B$ is a WFF of length $k$ which has $\mathbf E$ as an initial part which is itself a WFF.

This contradicts the induction hypothesis.

Therefore no initial part of $\mathbf A = \neg \mathbf B$ can be a WFF.

$\Box$


$(2): \quad \mathbf A = \left({\mathbf B \circ \mathbf C}\right)$

where $\circ$ is one of the binary connectives.

In this case, $\mathbf D$ is a WFF starting with $($, so:

$\mathbf D = \left({\mathbf E * \mathbf F}\right)$

for some binary connectives $*$ and some WFFs $\mathbf E$ and $\mathbf F$.

Thus:

$\mathbf B \circ \mathbf C) = \mathbf E * \mathbf F) \mathbf T$.

Both $\mathbf B$ and $\mathbf E$ are WFFs of length less than $k + 1$.

Therefore, by the induction hypothesis, neither $\mathbf B$ nor $\mathbf E$ can be an initial part of the other.

But since both $\mathbf B$ and $\mathbf E$ start at the same place in $\mathbf A$, they must be the same:

$\mathbf B = \mathbf E$

Therefore:

$\mathbf B \circ \mathbf C) = \mathbf B * \mathbf F) \mathbf T$

So $\circ = *$ and:

$\mathbf C) = \mathbf F) \mathbf T$

But then the WFF $\mathbf F$ is an initial part of the WFF $\mathbf C$ of length less than $k + 1$.

This contradicts our induction hypothesis.

Therefore no initial part of $\mathbf A = \left({\mathbf B \circ \mathbf C}\right)$ can be a WFF.

$\Box$


As $\mathbf A$ is arbitrary, it follows that no initial part of any WFF of length $k + 1$ can be a WFF.

So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by strong induction.


Therefore, for all $n \in \N_{> 0}$, the initial part of $\mathbf A$ such that $l \left({\mathbf A}\right) = n$ is not a WFF of propositional logic.

Hence the result.

$\blacksquare$


Sources