Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 1 / 16G (Logic and Set Theory)

A set $S$ is a deductively closed set of formulae when every consequence of $S$ already belongs to it:It is a consistent set of formulae when it does not prove a contradiction,

If $S$ is inconsistent, there is a formal derivation of $\perp$ from assumptions in $S$. By the finite character of formal proofs, that derivation mentions only finitely many assumptions $s_1,\dots ,s_m\in S$. Henceso this finite subset of $S$ is already inconsistent.

Suppose the finitary set of formulae $S$ is equivalent to the finite setFor each $f_j$, the relation $S⊢f_j$ has a finite proof, so it uses a finite set $R_j\subseteq S$ of assumptions. PutThis is a finite subset of $S$, and $R⊢f_j$ for every $j$, hence $R⊢F$. Since equivalence also gives $F⊢S$, transitivity of deduction yields

If some $T_i$ were inconsistent, it would prove every formula by the classical principle of explosion. Because $T_i$ is a deductively closed set of formulae, it would then contain every formula and could have no proper extension. This contradicts $T_i⊊T_{i+1}$. Thus every $T_i$ is consistent.

LetIf $T$ were inconsistent, the finite character of formal proofs would give a finite inconsistent subset $R\subseteq T$. The chain is increasing, so all finitely many members of $R$ lie in some common $T_N$. Then $T_N$ would be inconsistent, a contradiction. Hence $T$ is consistent.

If $T⊢\phi$, a proof again uses only finitely many assumptions from $T$, all lying in some $T_N$. ThusSince $T_N$ is deductively closed, $\phi \in T_N\subseteq T$. Therefore $T$ is deductively closed.

Finally, suppose that $T$ were finitary. Part (b) would provide a finite $R\subseteq T$ such that $R⊢T$. Choose $N$ with $R\subseteq T_N$. Then $T_N⊢T$; since $T_N$ is deductively closed, this implies $T\subseteq T_N$. Buta contradiction. Consequently $T$ is not finitary, proving the increasing union of deductively closed sets.