# For every axiomatic system in first order logic there exists an equivalent independent system

The question is how to prove the assertion in the title. With "axiomatic system" I just mean any (consistent) set of sentences (over any given language). "independent" means that no axiom can be derived from the others. "equivalent" is supposed to mean that both systems have the same class of models.

This is just something I came across while trying to teach myself some logic (an exercise in a book I was reading).

• If you have in mind systems with finitely many axioms, you can always find an equivalent system one with just one axiom (just and them all into one big lump) and then independence is automatic! – Mariano Suárez-Álvarez Oct 12 '12 at 2:20
• Yeah, or you can remove axioms which follow from the (remaining) others one by one until arriving at an independent system. But the case of infinitely many axioms seems to be more difficult. – user35359 Oct 12 '12 at 2:24
• I see that you are new to this site. The best questions here include context of where you encountered your question, why you think it is true, what you have tried, and so forth. Your question wold be improved if you edited it to add this information. – Carl Mummert Oct 12 '12 at 12:11

This is a standard piece of knowledge in logic: first that you can find an independent axiomatization for any given countable theory, and second that if you start with a set of axioms you cannot in general find an independent subset of that particular set. It's often mentioned in logic textbooks, either in the text or in the exercises. The second point was already demonstrated by Qiaochu Yuan in his answer.

Here is how to make an independent axiomatization of a countable theory $T$. In other words, we will pick a set $S$ of axioms in the same language as $T$ that have the same set of logical consequences as $T$, but no axiom in $S$ is provable from the rest of $S$. If $T$ is finitely axiomatizable this is trivial (we can make $|S|\leq 1$), so we assume no finite set of axioms in the language of $T$ has the same set of logical consequences as $T$.

First, let $\{A_i : i \in \omega\}$ be the set of logical consequences of $T$. Now inductively choose a sequence $n_k$ such that

• $n_0$ is minimal such that $A(n_0)$ is not a logical validity.

• $n_{k+1}$ is minimal so that $$A(n_0)\land A(n_1) \land \cdots \land A(n_k) \not\vdash A(n_{k+1})$$

This can be done because $T$ is not finitely axiomatizable.

For each $k$ let $B_k = A(n_0) \land \cdots \land A(n_k)$. Then, for all $i < j$, we have $B_i \not \vdash B_j$ and $B_j \vdash B_i$.

Let $$S = \{ B_0, B_0 \to B_1, B_1 \to B_2, \ldots\}$$ Then $S$ has the same set of logical consequences as $T$, because the consequences of $S$ include at least the entire set $\{A(n_k) : k \in \omega\}$ and this set in turn generates $S$ by construction.

Moreover, $S$ is independent. First, we show that $B_0$ is not provable from the remainder of $S$. This is because the other axioms are all true in a model where $B_0$ is false, and such a model exists because $A(n_0)$ is not a logical validity.

Next, we show that an implication $B_j \to B_{j+1}$ is never provable from the other axioms in $S$. To see this, we construct a model in which $B_j$ is true and $B_{k}$ is false for all $k > j$, which we can do by the construction of the sequence $A(n_k)$. In particular, we can directly form a model in which $B_j$ is true and $B_{j+1}$ is false, by construction. But then $B_{j+2}$ must be false in this model, because $B_{j+2}$ implies $B_{j+1}$, and similarly $B_k$ is false in this model for all $k > j$.

So this model satisfies both all "previous" implications compared to $B_j \to B_{j+1}$, because $B_j \vdash B_i$ for $i < j$, and it satisfies all "later" implications because their hypotheses are false. Thus it satisfies all of $S$ except for $B_j \to B_{j+1}$; hence the rest of $S$ cannot prove this sentence.

(I take no credit for the ideas in this proof; as I said I consider it standard knowledge.)

• By the way, people who know how to visualize $A \to B$ as an operation on a Boolean algebra can visualize this proof in terms of constructing an independent set of generators for an ideal on the Lindenbaum algebra for the language of $T$. This is not something I've seen mentioned, so I learned something from writing this answer. – Carl Mummert Oct 12 '12 at 12:30
• What if $T$ is uncountable? – Chris Eagle Oct 12 '12 at 13:32
• @Chris Eagle: apparently there is a positive answer in general, proved by Iégor Reznikoff, "Tout ensemble de formules de la logique classique est équivalent à un ensemble indépendant". (French) C. R. Acad. Sci. Paris 260 1965 2385–2388, ams.org/mathscinet-getitem?mr=177873 . But I am not familiar with that argument. – Carl Mummert Oct 12 '12 at 13:39
• There is a topological analogue (probably stronger than an analogue) here; what you're doing is turning an open cover of some space into an irredundant open cover by first taking increasing unions and then taking complements. – Qiaochu Yuan Oct 12 '12 at 18:13
• @user35359: I found a "translation" of Reznikoff's argumetn at arxiv.org/pdf/1108.5171v1.pdf – Carl Mummert Oct 14 '12 at 1:19

The other two answers have both attempted to prove the stronger statement that if $S$ is a set of axioms, then there is an independent subset $S' \subset S$ which is equivalent to $S$. This statement is false.

For a counterexample, work in the language of sets with countably many constants and consider the axioms $s_i$ which state that there exist at least $i$ distinct elements of the set. The implication structure among these axioms is that $s_{i+1}$ strictly implies $s_i$, and consequently no subset of $S = \{ s_i : i \in \mathbb{N} \}$ equivalent to it (precisely the infinite ones) is independent.

(Actually this might also be a counterexample to the desired statement. I don't think you can write down an independent set of axioms equivalent to $S$ at all.)

• Of course. I'm deleting my answer which is completely obvious, and also completely incorrect. – user642796 Oct 12 '12 at 7:27
• And I'm also in the corner wearing the dunce's cap! – Peter Smith Oct 12 '12 at 8:21
• I don't think this is a counterexample of the desired statement. Take the sentences (for all $n\in\omega$): 'If there are at most $n+2$ elements then there are at most $n+1$' and the sentence `There are two distinct element'. It's easy to check that they are all independent (at least I think so; I haven't rigorously checked) and they give the same theory. – Apostolos Oct 12 '12 at 10:32
• The equivalent independent set is "there is one element", "if there is one element there are two elements", "if there are two elements there are three elements", etc. – Carl Mummert Oct 12 '12 at 12:24