Exercise 7, Appendix 0

Let $R_1, R_2, \ldots, R_n$ be distinct logically irreducible relations (Exercise 6) in a theory $\mathscr{T}_0$. Let $A_1, A_2, \ldots, A_m$ be a logical construction with base $R_1, R_2, \ldots, R_n$. Suppose that each $R_j$ is endowed with one of the signs 0, 1. Then we give each $A_i$ one of the signs 0, 1 according to the following rules: (1) if $A_i$ is identical with $R_j$, give $A_i$ the same sign as $R_j$; (2) if $A_i$ is identical with $\neg A_j$, where $A_j$ precedes $A_i$, then give $A_i$ the sign 1 (resp. 0) if $A_j$ has the sign 0 (resp. 1); (3) if $A_i$ is identical with $\vee A_jA_k$, give $A_i$ the sign 1 if $A_j$ and $A_k$ both have the sign 1; otherwise give $A_i$ the sign 0. (We are applying the following “symbolical rule”:

(a) Show that there is only one way of attributing a sign to each $A_i$ in accordance with these rules.

(b) If $R$ is logically constructed from $R_1, R_2, \ldots, R_n$, then the sign carried by $R$ is independent of the logical construction, with base

in which $R$ appears.

(c) If $R$ and $S$ are logically constructed from $R_1, R_2, \ldots, R_n$, and if the signs carried by $R$ and $\Rightarrow RS$ are 0, then the sign carried by $S$ is 0.

(d) Suppose from now on that the only axioms of $\mathscr{T}_0$ are those provided from the schemes S1 through S4. Let $R$ be a theorem in $\mathscr{T}_0$, and let $R_1, R_2, \ldots, R_n$ be its logical components. Show, however, that the signs 0 and 1 are given to $R_1, R_2, \ldots, R_n$, and the sign carried by $R$ is 0. (Prove this first for the case when $R$ is an axiom of $\mathscr{T}_0$; in the general case, consider a proof of $R$, and apply (c)) $\mathscr{T}_0$.

(e) Let $R$ be a logically irreducible relation in $\mathscr{T}_0$. Show that neither $R$ nor “not $R$” is a theorem in $\mathscr{T}_0$. In particular, $\mathscr{T}_0$ is non-contradictory (use (d)).

(f) Let $R_1, R_2, \ldots, R_n$ be distinct, logically irreducible relations in $\mathscr{T}_0$. Consider all relations of the form “$R'_1$ or $R'_2$ or $\ldots$ or $R'_n$” where, for each $i$, $R'_i$ is one of the two relations $R_i$, “not $R_i$”. Let $S_1, S_2, \ldots, S_p$ be these relations. Let $T_1, T_2, \ldots, T_q$ be the relations of the form

"$S_{i_1}$ and $S_{i_2}$ and ... and $S_{i_r}$", where $i_1$, $i_2$, ..., $i_r$ is any strictly increasing sequence of indices. Finally, let $T_0$ be the relation "$R_1$ or (not $R_1$)", which is a theorem in $\mathscr{T}$. Show that every relation logically constructed from $R_1$, $R_2$, ..., $R_n$ is equivalent in $\mathscr{T}$ to exactly one of the relations $T_0$, $T_1$, ..., $T_q$. (Show first that every relation $R_i$ is equivalent in $\mathscr{T}$ to one of the relations $T_0$, $T_1$, ..., $T_q$. If $R$ is logically constructed from $R_1$, $R_2$, ..., $R_n$, argue step by step on a logical construction with base $R_1$, $R_2$, ..., $R_n$ which contains $R$. Finally, use (d) to prove uniqueness.)

(g) Let $R$ be a relation in $\mathscr{T}$, and let $R_1$, $R_2$, ..., $R_n$ be its logical components. Then $R$ is a theorem in $\mathscr{T}$ if and only if, however the signs 0 and 1 are assigned to $R_1$, $R_2$, ..., $R_n$, the corresponding sign carried by $R$ is 0.