Maximal independency vs. Independent axiomatization

Question

For any first order(ordinary) theory $\mathrm K$, $T_K$ denotes the set of all theorems of $\mathrm K$.

For any subset $\Gamma$ of $T_K$, $\Gamma$ is said 'independent' iff there is no wff $\mathscr C\in\Gamma$ such that $\Gamma-\{\mathscr C\}\vdash\mathscr C$.

So for any independent subset $\Gamma$ of $T_K$, $\Gamma$ is called 'independent axiomatization of $\mathrm K$' if every theorem of $\mathrm K$ is derivable from $\Gamma$.

And any independent subset $\Gamma$ of $T_K$ is called 'maximal independent' if there is no independent subset $\Delta$ of $T_K$ such that $\Gamma\subset\Delta$.

When i was trying to prove that any first order theory has 'independent axiomatization', i immediately thought about the fact that every maximal independent subset of a vector space is a basis. So i wondered whether a similar statement also holds for first order theories.

So, is the statement 'for any first order theory $\mathrm K$, every maximal independent subset of $T_K$ is independent axiomatization of $\mathrm K$' true?(or false?)

It is obvious that the converse is true, but it seems somewhat hard to prove or disprove the original statement.

Answer 1

After Henning reminded me of the orginal problem(exercise in Mendelson's book Introduction to Mathematical Logic : prove that every theory has an independent axiomatization), I realized that my question should be distinguished from the case of finitely axiomatizable theories and the case of theories that are not finitely axiomatizable.

Because we can easily get an independent axiomatization from any finite axiomatization using inductive procedure, but it seems that there is no way to obtain independent axiomatizations in not finitely axiomatizable theories using the inductive procedure(I mean, procedure that building up a set of wffs maintaining independence, or discarding useless wffs from the set of all theorems.). So I think the case of not finitely axiomatizable theories is a real troublesome (And it really is in the exercise from Mendelson's book). And the statement 'Any maximal independent set of any not finitely axiomatizable theory is an independent axiomatzation of that theory' may holds!

So I thought getting an answer to the latter case is more fruitful. And I think it is false, too. My counterexample for not finitely axiomatizable case used same ideas as finitely axiomatizable case, which is already posted. The basic idea is getting an infinite set of wffs that is 'relatively very weak'(it may sounds little vague) and independent, and then enlarging it to maximal independent set.

Here's my proof.

Let $\mathrm H$ be a first order theory having denumerably many predicate letters $A_1^1 , A_2^1 ,....,A_n^1,...$, denumerably many individual constants $b_1, b_2,..., b_n,....$, and no function letters. $\mathrm H$ has denumerably many axioms, $(\forall x) A_1^1(x),(\forall x) A_2^1(x),...,(\forall x) A_n^1(x),...$

$\mathrm H$ is not finitely axiomatizable. If we assume it is finitely axiomatizable, then there exists one wff $\mathscr E$ such that all the axioms of $\mathrm H$ are derivable from $\mathscr E$. Then, we can easily notice that $\mathscr E$ must contains all predicate letters of $\mathrm H$, $A_1^1 , A_2^1 ,....,A_n^1,...$ But it is impossible since the length of $\mathscr E$ is finite.

Let $\Delta_0=\{ A_1^1(b_1),A_1^1(b_2),...,A_1^1(b_n),...,A_2^1(b_1),...,A_2^1(b_n),A_2^1(b_2),...,A_k^1(b_1),A_2^1(b_2),...,A_k^1(b_n),.... \}$

$\Delta_0$ is independent. It is more complicated to construct models to show that it is independent(it's like two-dimensional) then the theory $\mathrm C\mathrm E$'s $\Delta_0$(which is in my previous answer), but it is still easy to construct models.

And next, enlarge $\Delta_0$ to $\Delta$ which is maximal independent, using the same inductive method in my previous answer.

Finally, let's assume that $\Delta$ is an independent axiomatization of $\mathrm H$. Now $\Delta$ proves $(\forall x) A_1^1(x)$. But it can only use finitely many wffs among $A_1^1(b_1),A_1^1(b_2),...,A_1^1(b_n)$,..., so there exists $A_1^1(b_i)$ which does not appear in the proof of $\Delta \vdash (\forall x) A_1^1(x)$. Therefore $\Delta$-{$A_1^1(b_i)$} $\vdash (\forall x) A_1^1(x)$,

$\Delta$-{$A_1^1(b_i)$} $\vdash A_1^1(b_i)$. So $\Delta$ is not independent, and it is contradiction. $\Delta$ is a maximal independent set but not an independent axiomatizaion, so it is a counter example.

Answer 2

I think I solved it myself. It's false. Here's my proof.

lemma) For any finitely axiomatizable theory $\mathrm K$, any independent axiomatization of $\mathrm K$ is a finite axiomatization of $\mathrm K$.

-Since $\mathrm K$ is finitely axiomatizable, there exists a set $\Delta$={ $\mathscr C_1$, $\mathscr C_2$, ...$\mathscr C_n$ } such that $\Delta$ is an independent axiomatization of $\mathrm K$. Then, let $\Gamma$ be any independent axomatization of $\mathrm K$. Then any $\mathscr C_i$ is derivable from finitely many wffs of $\Gamma$, thus we only need finitely many wffs of $\Gamma$ to prove all wffs of $\Delta$. So if $\Gamma$ is infinite, then there must exists a wff $\mathscr C\in\Gamma$ such that $\Gamma-\{\mathscr C\}\vdash\mathscr C$, which leads to contradiction.

Let $\mathrm C$$\mathrm E$ be a first order theory having denumerabley many individual constants $b_1$,$b_2$,...,$b_n$,..., no function letters, and only one predicate letter $A_1^1$. $\mathrm C$$\mathrm E$ has only one axiom, $(\forall x)A_1^1(x)$. $\mathrm C$$\mathrm E$ is clearly finitely axiomatizable.

Let's consider the set $\Delta_0$={ $A_1^1(b_1)$,$A_1^1(b_2)$,...,$A_1^1(b_n)$,... }. $\Delta_0$ is infinite, and independent. To prove its independency, we may avoid to use model-theoretic notions, but it gets more easier with model-theoretic notions. let $\Delta_0^i$={ $A_1^1(b_1)$,$A_1^1(b_2)$,...,$\lnot A_1^1(b_i)$,$A_1^1(b_{i+1})$,... }. We can easily construct models for all $\Delta_0^i$s($i=1,2,3,....,n,..$). And $\Delta_0$ obviously has a model, thus it is independent.

Let $\mathscr B_1$, $\mathscr B_2$, ...$\mathscr B_n$,... be a enumeration of all theorems of $\mathrm C$$\mathrm E$. And let

$\Delta_0$=$\Delta_0$,

$\Delta_{n+1}$=$\begin{cases}\Delta_n \cup \{\mathscr B_{n+1}\}, & \text{if $\Delta_n \cup$ \{$\mathscr B_{n+1}$\} is independent}\\ \Delta_n, & \text{if $\Delta_n \cup$ \{$\mathscr B_{n+1}$\} is not independent} \end{cases}$

for $n=0,1,2,...,$ and

$\Delta=\bigcup_{i \in \omega} \Delta_{i}$

It is easy to see that $\Delta$ is a maximal independent subset of $T_{\mathrm C\mathrm E}$. But if we assume that $\Delta$ is an independent axiomatization of $\mathrm C\mathrm E$, since $\Delta$ is infinte, it leads to contradiction(by the lemma).

$\Delta$ is a counterexample!