[Math] some problems about axiomatizable classes resulting from compactness

logicmodel-theory

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.

Best Answer

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.