1
$\begingroup$

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?

  • 0
    the question is from H.-D. Ebbinghaus's Mathematical Logic, 2nd Edition, Chapter VI, 3.11 Exercise.2016-12-28

1 Answers 1

2

I'm not sure what to do with the hint, but how about this:

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} = \begin{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} \end{cases} $ 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.

  • 0
    Thanks for the explanation.2012-01-27