Boolean terms and unique readablity

1. Introduction

This web page puts a little more detail on the syntactical nature of the definition of $BT (X)$ the set of boolean terms over letters from $X$ , given in Chapter 6 of The Mathematics of Logic. We also give the unique readability theorem for such terms and explain how definitions by induction can be made on terms. Much of the material here consists of very precise (almost pedantic) constructions concerning strings of symbols, and the theorems proved here about them are in some sense obvious. The material here is aimed at readers who really need or want to see the full story with all the gory details.

2. Boolean terms

In Definition 6.1 the set $BT (X)$ is defined. The essential ingredients of this definition are that

$X$ is an arbitrary set. An element of $X$ is called a propositional letter from $X$ . The set $X$ may be empty. Two distinct elements of $X$ will be considered as distinct propositional letters. It is helpful if the symbols $⊤$ , $⊥$ , $($ , $)$ , $\neg$ , $\land$ , $\lor$ are not elements of $X$ . (This can always be achieved by modifying the set $X$ if necessary, or by restricting the set $X$ to being a subset of some familiar set of letters such as $\{x_{n}: n \in ℕ\}$ .) In the sequel we will always assume that this is the case.
We have precise and unambiguous ways of building the expressions ¬ α , ( α ∧ β ) , and ( α ∨ β ) from subexpressions α , β . Several possibilities exist. For the book and this webpage we take:
- $\neg α$ is the contatenation of the symbol $\neg$ with the string of symbols for the expression $α$ ;
- $(α \land β)$ is the contatenation of the symbol $($ , the string of symbols for the expression $α$ , the symbol $\land$ , the string of symbols for the expression $α$ , and the symbol $)$ , in that order;
- $(α \lor β)$ is the contatenation of the symbol $($ , the string for $α$ , the symbol $\lor$ , the string for $α$ , and the symbol $)$ , in that order;
The symbols $⊤$ , $⊥$ , $($ , $)$ , $\neg$ , $\land$ , $\lor$ are all distinct.

Here then is the full definition of $BT (X)$ , making Definition 6.1 more precise.

Definition.

A string of symbols $σ$ is in $BT (X)$ if there is a finite sequence $σ_{0}, σ_{1}, \dots, σ_{n}$ of strings of symbols, such that $σ_{n}$ is the string $σ$ and for each $i ⩽ n$ we have one of the following holding.

$σ_{i}$ is the one-symbol string $⊤$ .
$σ_{i}$ is the one-symbol string $⊥$ .
$σ_{i}$ is the one-symbol string $x$ consisting of some $x \in X$ .
There is $j < i$ such that $σ_{i}$ is the string $\neg σ_{j}$ .
There are $j < i$ and $k < i$ such that $σ_{i}$ is the string $(σ_{j} \land σ_{k})$ .
There are $j < i$ and $k < i$ such that $σ_{i}$ is the string $(σ_{j} \lor σ_{k})$ .

Definition.

A finite sequence $σ_{0}, σ_{1}, \dots, σ_{n}$ of strings of symbols such that for each $i ⩽ n$ one of the six conditions above hold is called a construction sequence for the boolean term $σ_{n}$ .

Exercise.

Rewrite the above definitions so that it is given by a formal system (which you must specify), a boolean term over $X$ is a theorem of the system, and a construction sequence is essentially a proof in the formal system.

All syntactical definitions by induction in the book can be re-written more precisely in this sort of form, expressing the existence of a finite sequence of subexpressions, or by introducing other secondary formal systems.

We can use this formal definition now to prove statements that might have seemed obvious but nevertheless deserve a proof in a highly rigorous treatment.

Example.

Each construction sequence $σ_{0}$ of length $1$ consists of a single string of a single symbol. That symbol may be $⊤$ , $⊥$ , or an element of $X$ .

Proposition.

Each $σ \in BT (X)$ is a string of finitely many symbols.

Proof.

By induction.

Subproof.

Our induction hypothesis $H (n)$ is the statement that if $σ_{0}, σ_{1}, \dots, σ_{n}$ is a construction sequence then $σ_{n}$ is a string of finitely many symbols.

$H (1)$ is true by the preceding example. If we could prove $H (n)$ for all $n$ then we would have proved the proposition for if $σ \in BT (X)$ there is a construction sequence for it of some length $n$ si by $H (n)$ there are finitely many symbols in $σ$ .

The induction step, saying that if $H (k)$ holds for all $k < n$ then $H (n)$ holds, is proved by looking at the six individual clauses in the definition of construction sequence. Note that if $σ_{0}, σ_{1}, \dots, σ_{n}$ is a construction sequence then for each $i < n$ , $σ_{0}, σ_{1}, \dots, σ_{i}$ is also a construction sequence. So by $H (i)$ for $i < n$ we may assume that each $σ_{i}$ is finite. It follows by looking at the individual clauses that $σ_{n}$ must be finite too.

3. Unique readability

Unique readability is the proposition that we chose a good method for encoding terms as strings. For example if we had omitted the brackets, writing $(α \land β)$ instead as $α \land β$ , and also writing $(α \lor β)$ instead as $α \lor β$ the encoding we would have would not satisfy unique readability as $\neg α \land β \lor γ$ could be variously read as $(\neg α) \land (β \lor γ)$ , $\neg (α \land (β \lor γ))$ , $(\neg (α \land β)) \lor γ$ , $\neg ((α \land β) \lor γ)$ , etc.

Thus unique readability is a theorem about correctness of encodings of a natural mathematical idea (terms and expressions) into the realm of strings of symbols. Most of the work is done by the following technical proposition.

Proposition.

Suppose $α$ and $β$ are boolean terms over a set $X$ and that $α$ is an initial part of $β$ , that is $β$ is the concatenation $α γ$ for some string $γ$ . Then in fact $α$ and $β$ have the same length and are equal as strings.

Proof.

By induction on the length of construction sequences. We assume we are given $n \in ℕ$ with the property that whenever $α$ and $β$ are boolean terms over a set $X$ both with construction sequences of length at most $n$ and $α$ is an initial part of $β$ then $α = β$ . Observe that this is true when $n = 1$ since in this case both $α$ and $β$ are $⊤$ , $⊥$ , or an element of $X$ , and so if $α$ is an initial part of $β$ and both have length $1$ then $α = β$ .

For the induction step we suppose we have that $α$ is an initial part of $β$ both having construction sequences of length at most $n + 1$ . We look at the first symbol in $α$ , which is also, necessarily the first symbol in $β$ .

If this symbol is $⊤$ , $⊥$ or $x \in X$ then both $α$ and $β$ are one-symbol strings, as the only clauses in the construction allowing these as the first symbol are the first three, and these construct single symbol strings. Thus $α = β$ in this case.

If the first symbol in $α$ is $\neg$ then $α = \neg γ$ for some $γ$ with construction sequence of length at most $n$ as this is the only possible construction clause. Similarly $β = \neg δ$ for some $δ$ with construction sequence of length at most $n$ . Also as $α$ is an initial part of $β$ , $γ$ is also an initial part of $δ$ , so $γ = δ$ by our induction hypothesis and hence $α = β$ .

If the first symbol in $α$ is an open parenthesis then there are two possibilities: either $α$ is $(γ_{1} \land γ_{2})$ or $α$ is $(γ_{1} \lor γ_{2})$ . Similarly $β$ is $(δ_{1} * δ_{2})$ where $*$ is $\land$ or $\lor$ . This means that $γ_{1}$ is an initial part of the string $δ_{1} * δ_{2}$ and hence either $γ_{1}$ is an initial part of the string $δ_{1}$ or $δ_{1}$ is an initial part of the string $γ_{1}$ . Therefore by our induction hypothesis $γ_{1} = δ_{1}$ . Now by looking at the rest of $α$ and how it is an initial part of $β$ we see that the operator $*$ is the same as the operator of alpha, i.e. $α$ is $(γ_{1} * γ_{2})$ which is an initial part of $β = (δ_{1} * δ_{2})$ . So $γ_{2}$ is an initial part of $δ_{2}$ and hence by the induction hypothesis they are equal. This shows $α = β$ .

Proposition.

Suppose $σ \in BT (X)$ . Then exactly one of the following holds.

$σ$ is the one-symbol string $⊤$ .
$σ$ is the one-symbol string $⊥$ .
$σ$ is the one-symbol string $x$ consisting of some $x \in X$ .
There is a string $α$ such that $σ$ is the string $\neg α$ .
There are strings $α, β$ such that $σ$ is the string $(α \land β)$ .
There are strings $α, β$ such that $σ$ is the string $(α \lor β)$ .

Moreover, in the last three cases, the strings $α, β$ are uniquely determined from $σ$ .

Proof.

Case-by-case, using the previous proposition.

The importance of unique readability is that it enables new definitions by induction on the way a boolean term $σ$ is built up. One hugely important example of such a definition is given in chapter 7, page 80 where a valuation, a function $f : X \to B$ is extended to a function $BT (X) \to B$ . If a boolean term could be ambiguously read in two or more different ways, the definition given would not be sound and the whole theory collapse.

Exercise.

Let $L$ be a first order language. Assume that the symbols of $L$ , especially the variables, constant symbols, function symbols and relation symbols are all distinct. State and prove a unique readability theorem for terms of $L$ .

Exercise.

With $L$ as in the previous exercise, state and prove a unique readability theorem for formulas of $L$ .