Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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} = \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.

share|cite|improve this answer
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
@Alexis: I consider it fairly standard (enough to use it in my answer without explicit comment!) -- I cannot point to an authoritative source for it as an abbreviation, but certainly anyone familiar with logic ought to understand it that way in an informal argument. If you're talking to a mechanical proof checker, you might want to be more explicit. – Henning Makholm Jan 27 '12 at 15:02
Thanks for the explanation. – Alexis Jan 27 '12 at 17:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.