8
$\begingroup$

Let $T_1$ and $T_2$ be two theories having the same set of symbols. Assume that any interpretation of $T_1$ is a model of $T_1$ if and only if it is not a model of $T_2$. Then:

$T_1$ and $T_2$ are finitely axiomatizable.

(i.e. there are finite sets of sentences $A_1$ and $A_2$ such that, for any sentence $S$: $T_1$ proves $S$ if and only if $A_1$ proves $S$, and $T_2$ proves $S$ if and only if $A_2$ proves $S$).

/The proof will be by contradiction; assume $T_1$ or $T_2$ are not finitely axiomatizable, then .....?/

Any one have any idea of how to prove this argument?

  • 0
    @Sara: By symmetry, we may assume $T_2$ is not finitely axiomatizable; then every for every finite set $S$ of sentences of $T_2$, there is a model of $T_1$ in which $S$ is true (because there is some model of $S$ that is not a model for all of $T_2$, and hence is a model for $T_1$). Seems like this might lead somewhere...2010-12-04
  • 0
    @Taroccoesbrocco - it is not necessary to edit very old posts to fix minor formatting issues - it pops them to the front page needlessly.2018-02-24

2 Answers 2

9

The union $T_1\cup T_2$ has no models, and so by the Compactness theorem there is a finite subtheory with no models. This amounts to finite $A_1\subset T_1$ and $A_2\subset T_2$ such that $A_1\cup A_2$ has no models. Any model $M$ of $A_1$ is therefore not a model of $A_2$ and so $M$ is not a model of $T_2$ and hence by your assumption it is a model of $T_1$. So $A_1\vdash T_1$ and similarly $A_2\vdash T_2$, so both theories are finitely axiomatizable.

5

There's a result using compactness that says that if two sets of sentences, $T_1,T_2$ have no common model then there exists a sentence $\phi$ such that $T_1\models\phi$ and $T_2\models\lnot\phi$. To see this use the contrapositive: If for every sentence $\phi$ we have $T_1\models\phi$ has as a consequence that $T_2\cup\{\phi\}$ is satisfiable, then for every sentence $\phi$ that is a conjunction of sentences of $T_1$ we have $T_2\cup\{\phi\}$ is satisfiable and through compactness $T_1$ and $T_2$ share a model.

Now let $\phi$ be such that $T_1\models\phi$ and $T_2\models\lnot\phi$. Then $\phi$ is an axiomatization of $T_1$ and $\lnot\phi$ is an axiomatization of $T_2$. This is because, if a model satisfies $\phi$ then it can't satisfy $T_2$ and therefore satisfies $T_1$ and vice versa.

That's the answer I came up with, but maybe there's a more direct way to it.

  • 2
    The critical point is that every model satisfies either $T_1$ or $T_2$ and not both. So if there are two independent sentences, A and B that are both part of $T_1$ and their negations are part of $T_2$, a model of A and not B will not satisfy either one. This is the justification that $\phi$ is an axiomization of $T_1$.2010-12-05