Exercise 1, § 2

This solution was written by nemotron-3-ultra-free and judged by a machine. It is not Bourbaki's and it has not been checked by a person.

(a) Let $\mathscr{T}'$ be the theory with the same signs and schemes as $\mathscr{T}$ and with explicit axioms $A_1,\dots,A_{n-1}$. The explicit axioms of $\mathscr{T}'$ are among the explicit axioms of $\mathscr{T}$; an explicit axiom is a theorem in its theory because it forms a proof of length 1 (satisfying condition (a$_1$) of the definition of a proof). Hence $A_1,\dots,A_{n-1}$ are theorems in $\mathscr{T}$. Since $\mathscr{T}$ and $\mathscr{T}'$ have the same signs and the same schemes, $\mathscr{T}$ is stronger than $\mathscr{T}'$.

By definition, two theories are equivalent when each is stronger than the other. Because $\mathscr{T}$ is already stronger than $\mathscr{T}'$, the equivalence $\mathscr{T}'\equiv\mathscr{T}$ holds exactly when $\mathscr{T}'$ is stronger than $\mathscr{T}$. Now $\mathscr{T}'$ is stronger than $\mathscr{T}$ iff all explicit axioms of $\mathscr{T}$ are theorems in $\mathscr{T}'$. The axioms $A_1,\dots,A_{n-1}$ are explicit axioms of $\mathscr{T}'$, therefore they are theorems in $\mathscr{T}'$. Thus $\mathscr{T}'$ is stronger than $\mathscr{T}$ precisely when $A_n$ is a theorem in $\mathscr{T}'$. Consequently, $\mathscr{T}'$ is not equivalent to $\mathscr{T}$ — that is, $A_n$ is independent of the other axioms — if and only if $A_n$ is not a theorem of $\mathscr{T}'$.

(b) Let $\mathscr{T}'$ be the theory with the same signs and schemes as $\mathscr{T}$ and with explicit axioms $A_1,\dots,A_{n-1}$ (the theory considered in (a)). Denote by $\sigma$ the substitution $(T_1|a_1)\cdots(T_h|a_h)$. We are given that $\sigma A_i$ is a theorem in $\mathscr{T}''$ for $i=1,\dots,n-1$, and that not $\sigma A_n$ is a theorem in $\mathscr{T}''$.

We prove the contrapositive: if $A_n$ is not independent, then $\mathscr{T}''$ is contradictory. Assume $A_n$ is not independent. By part (a) this means $A_n$ is a theorem in $\mathscr{T}'$.

Form the theory $\sigma\mathscr{T}'$ by applying the substitution $\sigma$ to $\mathscr{T}'$. Its explicit axioms are $\sigma A_1,\dots,\sigma A_{n-1}$. By hypothesis these are theorems in $\mathscr{T}''$. The theories $\mathscr{T}''$, $\mathscr{T}$, $\mathscr{T}'$ and $\sigma\mathscr{T}'$ all have the same signs and the same schemes (the substitution does not change signs or schemes). Therefore $\mathscr{T}''$ is stronger than $\sigma\mathscr{T}'$. By Criterion C4, every theorem of $\sigma\mathscr{T}'$ is a theorem of $\mathscr{T}''$.

Since $A_n$ is a theorem in $\mathscr{T}'$, we apply Criterion C2 successively: $(T_1|a_1)A_n$ is a theorem in $(T_1|a_1)\mathscr{T}'$; then $(T_2|a_2)(T_1|a_1)A_n$ is a theorem in $(T_2|a_2)(T_1|a_1)\mathscr{T}'$; continuing in this way, after $h$ steps we obtain that $\sigma A_n$ is a theorem in $\sigma\mathscr{T}'$. Hence, by C4, $\sigma A_n$ is a theorem in $\mathscr{T}''$. But we are given that not $\sigma A_n$ is also a theorem in $\mathscr{T}''$. A theory containing both a relation and its negation as theorems is contradictory. Thus $\mathscr{T}''$ is contradictory.

We have shown that if $A_n$ is not independent then $\mathscr{T}''$ is contradictory; therefore either $A_n$ is independent or $\mathscr{T}''$ is contradictory.