Take the 2-minute tour ×
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.

I'm trying to work on the following problems:

  1. Prove that if a set S of sentences axiomatizes a finitely axiomatizable class K of structures then K can be axiomatized by a finite subset of S.
    I have an idea for this: Suppose not, i.e. for all finite subset $S_0$ of S and all $M \in K, M \nvDash S_0$. Suppose K is finitely axiomatized by $\phi$ then $M \models (\sim S_0) \cup \phi$. By compactness, $M \models (\sim S) \cup \phi$ so $M \models \sim S$ which is a contradiction. Does this look right?

  2. Show that a class K is finitely axiomatizable iff K and its complement are axiomatizable.
    Clearly if it's finitely axiomatizable then it's axiomatizable. For the other direction, I've been playing with it but not sure how to frame K's complement.

  3. Show that the class K of all infinite sets is axiomatizable but not finitely axiomatizable.
    I think K is axiomatized by $S=\{c_i \neq c_j | i \neq j \}$, and I know the finitely axiomatizable part has to do with compactness but not sure what to apply it to.

Any hint greatly appreciated.

share|improve this question
    
Note that "$K$ is not axiomatized by any finite subset of $S$" means for every finite $F \subseteq S$ there is an $M$ with $M \models F$ and $M \not \in K$. Your idea for #1 has a quantifier problem. –  Carl Mummert Mar 18 '11 at 22:02

1 Answer 1

Some hints.

For #1, say $K$ is axiomatized by $A$ and also by a finite set $F$. Let $\phi$ be the conjunction of the formulas in $F$. Then $A \vdash \phi$; apply compactness.

For #2, say $K$ is axiomatized by $A$ and $K^c$ is axiomatized by $B$. Assuming that $K$ is not finitely axiomatizable, you can show that $A \cup B$ is consistent, which is a contradiction.

For #3, this is a relatively standard compactness exercise. You idea works, you just have to prove it. You can apply #1: if the class was finitely axiomatizable it would be axiomatizable by a subset of your given set of axioms.

share|improve this answer

Your Answer

 
discard

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.