Suppose $A_1, A_2, \ldots$ are sentences such that no $A_i$ is deducible from earlier sentences. Demonstrate that this is not finitely axiomatizable.

logic

Suppose $A_1, A_2, \ldots$ are sentences such that no $A_n$ is deducible from the conjunction of the $A_m$ as long as $m < n$. Let $T = \{D : D \; \text{is deducible from} \; \{A_1, A_2, A_3, \ldots\} \}$. Show that $T$ is not finitely axiomatizable.

Hint: suppose there were some $B_1, \ldots, B_m$ such that $T$ was axiomatized by $\{B_1, \ldots, B_m\}$. Try showing that each $B_j$, $j \le m$ is deducible from a finite number of $A_i$.

Clearly, if each $B_j$ is deducible from a finite number of $A_i$ sentences then the rest is easy: then all $B_j$ sentences are deducible from some finite number of $A_i$ sentences, with some max $m$ such that $A_{m+1}$ is in $T$ and by hypothesis not deducible from the first $m$ $A_i$ sentences and therefore not deducible from the finite set $\{ B_1, \ldots, B_m \}$ and therefore $T$ is not finitely axiomatizable.

However, how do I show that each $B_j$ is deducible from a finite number of $A_i$? I'm not really sure how to do this or what theorems would be useful.

EDIT: I believe I have a counter-example showing that $T$ can be finitely axiomatizable:

Consider the counter-example with the language of arithmetic. Each $A_i$ is the sentence $c > 2i$, so $A_1$ is $c > 2$, $A_2$ is $c > 4$, etc. Clearly, any $A_n$ is not deducible from the conjunction of $A_1 \land \cdots \land A_{n-1}$. However, $T$ is finitely axiomatized by single the sentence $\forall x (c > x)$. And that sentence can't be deduced from a finite set of $A_i$ sentences.

Best Answer

If the theory were finitely axiomatisable, consider sentences $B_1, ..., B_n$ which axiomatise it. Since $B_1, ..., B_n$ are in $T$, each can be deduced from a the $A_i$s. In particular, let $B_i$ be deducible from $A_{m_{i, 1}}, A_{m_{i, 2}}, ..., A_{m_{i, n_i}}$. Now let $k = 1 + \max_{1 \leq i \leq n, 1 \leq j \leq n_i} m_{i, j}$. Then $A_k$ is deducible from $B_1, ..., B_n$ and hence is deducible from the $A_{m_{i, j}}$. But this is a contradiction, since $k > m_{i, j}$ for all $i, j$ such that $1 \leq i \leq n$ and $1 \leq j \leq n_i$ and no $A_k$ is deducible from the previous sentences.