4
$\begingroup$

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).

  • 1
    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.2012-10-12

2 Answers 2

8

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.)

  • 1
    @user35359: I found a "translation" of Reznikoff's argumetn at http://arxiv.org/pdf/1108.5171v1.pdf2012-10-14
8

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.)

  • 2
    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.2012-10-12