# Independent system of axioms for $\Delta$-elementary class of S-structures

I try to solve the following exercise from a textbook and need some help:

A set $\Phi$ of S-sentences is called independent if no $\phi \in \Phi$ is a consequence of $\Phi - \{\phi\}$.

a) Every finite set $\Phi$ of S-sentences has an independent subset $\Phi_0$ such that $Mod_S\Phi = Mod_S\Phi_0$.

b) If S is at most countable then every $\Delta$-elementary class of S-structures has an independent system of axioms. (Hint: Start by defining an axiom system $\phi_0, \phi_1, \dots$ such that $\models \phi_{i+1}\rightarrow\phi_i$ for all $i\in \mathbb{N}$.)

I solved a) but don't have a good idea for b). Any ideas?

-
Could you remind us what $\Delta$-elementary means here? – Henning Makholm Jan 24 '12 at 17:43
A class $K$ of S-structures is called $\Delta$-elementary iff there is a set $\Phi$ such that $K = Mod_S\Phi$. – Alexis Jan 24 '12 at 17:47
What is the textbook? – magma Jan 24 '12 at 19:37

Since $S$ is at most countable, so is $\Phi$ from the definition of $\Delta$-elementary. Enumerate $\Phi$ as $\phi_1, \phi_2, \phi_3$ and so forth. Now inductively define a series of finite sets of sentences $(\Psi_i)_{i\in \mathbb N}$ by $$\Psi_0=\varnothing, \quad \Psi_{i+1} = \cases{\Psi_i &\text{if }\phi_1,\ldots,\phi_i\vDash \phi_{i+1}\\ \Psi_i \cup \{ (\phi_1 \land \cdots \land \phi_i) \rightarrow \phi_{i+1} \} &\text{otherwise}}$$ Now, $\bigcup_i \Psi_i$ is clearly equivalent to $\Phi$, and it is also independent -- because otherwise there would be some finite subset of it that was not independent, and each of the $\Psi_i$s are independent.
Thank you! I think this construction works. Just a minor question: Is it custom to define $\emptyset \rightarrow \phi$ to mean $\phi$? If not, I don't see how the first $\phi_1$ gets included in $\Psi$. – Alexis Jan 27 '12 at 14:58