Exercise 6, Appendix 0

A relation in a theory $\mathscr{T}$ is said to be logically irreducible if it begins with a relational sign. Let $R_1$, $R_2$, ..., $R_n$ be distinct logically irreducible relations in $\mathscr{T}$. A logical construction with base $R_1$, $R_2$, ..., $R_n$ is any sequence $A_1$, $A_2$, ..., $A_p$ of assemblies in $\mathscr{T}$ such that each $A_i$ satisfies one of the following conditions : (1) $A_i$ is one of the relations $R_1$, $R_2$, ..., $R_n$; (2) there exists an assembly $A_j$ preceding $A_i$ such that $A_i$ is $\neg A_j$; (3) there exist two assemblies $A_j$ and $A_k$ preceding $A_i$ such that $\vee A_i$ is $A_j A_k$.

(a) Show that the assemblies in a logical construction with base

are relations in $\mathscr{T}$. A relation which appears in such a logical construction is said to be logically constructed from $R_1$, $R_2$, ..., $R_n$.

(b) If $R$ and $S$ are logically constructed from $R_1$, $R_2$, ..., $R_n$, then so are $\neg R$, $\vee RS$, $\Rightarrow RS$, "$R$ and $S$", $R \Leftrightarrow S$.

(c) Let $R$ be a relation in $\mathscr{T}$. Consider the sequence of relations defined as follows. First of all, write $R$. If $R$ is logically irreducible, stop there. If not, write next the assembly or assemblies antecedent to $R$ (which are well determined relations). Then write the assembly or assemblies antecedent to those of the preceding assemblies which are not logically irreducible; and so on. Let $R_1$, $R_2$, ..., $R_n$ be the distinct logically irreducible relations which arise from this construction; they are called the logical components of $R$. Show that $R$ is logically constructed from its logical components, but that if one of the relations of the sequence

$R_1, R_2, \ldots, R_n$ is omitted, then $R$ is not logically constructed from the remaining $(n-1)$ relations.

(d) Let $R$ be a relation and let $R_1, R_2, \ldots, R_n$ be distinct logically irreducible relations such that (1) $R$ is logically constructed from $R_1, R_2, \ldots, R_n$, (2) if we omit one relation from the sequence $R_1, R_2, \ldots, R_n$, then $R$ is not logically constructed from the remaining relations. Show that $R_1, R_2, \ldots, R_n$ are the logical components of $R$.