Initial Part of WFF of Predicate Logic is not WFF

From ProofWiki
Jump to navigation Jump to search

Theorem

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

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


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


Proof

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

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

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


The proof proceeds by induction on $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$.

This is the basis for the induction.


Induction Hypothesis

Fix $n \in \N$ with $n \ge n_0$.

Assume the result holds for all WFFs of length $k$ or less.

This is our induction hypothesis.


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{DT}$ where $\mathbf T$ is non-null.


We need to investigate the following cases:

$(1): \quad \mathbf A = \neg \mathbf B$, where $\mathbf B$ is a WFF of length $k$.
$(2): \quad \mathbf A = \left({\mathbf B \circ \mathbf C}\right)$ where $\circ$ is one of the binary connectives.
$(3): \quad \mathbf A = p \left({t_1, t_2, \ldots, t_n}\right)$, where $t_1, t_2, \ldots, t_n$ are terms, and $p \in \mathcal{P}_n$.
$(4): \quad \mathbf A = ( Q x: \mathbf B )$, where $\mathbf B$ is a WFF of length $k-5$, $Q$ is a quantifier ($\forall$ or $\exists$) and $x$ is a variable.

We deal with these one by one.


Cases $(1)$ and $(2)$ are covered by the argument in Initial Part of WFF of PropLog is not WFF.


$(3): \quad$ The atomic WFF $\mathbf A = p \left({u_1, u_2, \ldots, u_n}\right)$:

Here we have that $\mathbf D$ would be a string of the form:

  • $p$ where $p$ is an $n$-ary predicate symbol. This can not be a WFF.
  • $p ($ which is also not a WFF.
  • $p (u_1, u_2, \ldots, u_k$ which can not be a WFF.
  • $p (u_1, u_2, \ldots, u_k,$ which can not be a WFF.


$(4): \quad \mathbf A = ( Q x: \mathbf B )$:

$\mathbf D$ can not be $($, $( Q$, $( Q x$ or $( Q x:$ as none of these are WFFs.

Thus $\mathbf D$ is a WFF, starting with $( Q x: $; hence $\mathbf D = ( Q x: \mathbf E )$, where $\mathbf E$ is also a WFF.

We remove the initial $( Q x: $ and the last closing parenthesis $)$ from $\mathbf A = \mathbf{DT}$ to get $\mathbf B = \mathbf{ET}'$ (where $\mathbf T'$ results from $\mathbf T$ by removing the last closing parenthesis).

Recall that $\mathbf B$ is a WFF of length $k-5$.

It has $\mathbf E$ as an initial part, which is itself a WFF.

This contradicts the induction hypothesis.

Therefore no initial part of $\mathbf A = ( Q x: \mathbf{B} )$ can be a WFF.


Thus all four cases have been investigated, and we have found that no initial part of any WFF of length $k+1$ can be a WFF.

The result follows by the Second Principle of Mathematical Induction.

$\blacksquare$


Sources