Htykuut

Let $L =${ $E$ } where $E$ is a symbol for a binary relation. If $K$ is a class of $L$ structures and $T$ an $L$ theory, we say $T$ auxiomatize $K$ if for every $L$ structure $M$, $M$ in $K$ if and only if $Mmodels T$ we say $K$ is axiomatizable if exists $T$ such T axiomatize $T$

I don't know how to find if a given class is axiomatisable or not, my professor say that I need to use compactness to find when it is not. But I think I don't understand the concepts. I need examples of how you axiomatize a class and when this is not possible.

For example in some exercise he give us the follow is in it:

$K_1$ is the class of all $L$-structures $M$ such $E^M$ is an equivalent relation.

To show a class is axiomatizable, you can find a set of axioms for it. For instance, $E$ being an equivalence relation is axiomatizable by the usual three axioms: $$ forall x xEx\forall x,y(xEyleftrightarrow yEz)\forall x,y,z(xEyland yEzto xEz).$$ Another property that is axiomatizable is $E$ being an equivalence relation with infinitely many equivalence classes. You can write down the property $phi_3$ that there are three or more equivalence classes as $$ exists x,y,z(lnot x Eyland lnot x E zland lnot y Ez)$$ (this says $x,$ $y$, and $z$ are in different equivalence classes). You can similarly write down an axiom $phi_4$ that says $E$ has greater than $4$ equivelence classes, and similarly a $phi_n$ for any $n.$ Then the class of equivalence relations with infinitely many equivalence classes is axiomatized by the three equivalence axioms, plus the axioms ${phi_n:ninmathbb N}.$

As your professor says, a good way to show something isn't axiomatizable is to use compactness. For instance, the class of equivalence relations with finitely many equivalence classes is not axiomatizable. To show this, we assume $Sigma$ axiomatizes it and derive a contradiction. We add a countably infinite set of new constant symbols ${c_1, c_2,ldots}$ to the language. Then we consider the set of axioms $Sigma' = {lnot c_i E c_j: ine j}$ that say the $c_i$ are all in different equivalence classes.

Let $T=Sigmacup Sigma'.$ We can see that any finite subset of $T$ has a model, since any finite subset of $Sigma'_0subseteq Sigma'$ can be satisfied by an equivalence relation with finitely many equivalence relations provided we make the number of classes large enough to assign all the $c_i$ that appear in $Sigma_0'$ to different equivalence classes. Thus compactness says $T$ is satisfiable. Yet $T$ cannot be satisfiable since it is contradictory: $Sigma$ says there are finitely many equivalence classes, but $Sigma'$ implies there are infinitely many.

For another example that follows a similar pattern, we can show "$<$ is a well-ordering" is not axiomatizable. Assume for contradiction that $Sigma$ axiomatizes it, and as before add ${c_n:ninmathbb N}$. Let $Sigma'$ contain the sentences "the ordering has a greatest element and every element that isn't least has an immediate predecessor" (write these out!) as well as $c_ine c_j$ for all $ine j.$

Again, any finite subset of $T=Sigmacup Sigma'$ is satisfiable. Simply find a finite ordered set that is large enough to assign the $c_i$ that appear in our finite number of sentences to different elements. Any finite set is well-ordered (so satisfies $Sigma$) and has a greatest element and an immediate predecessor for every element except the least (so satisfies the rest of $Sigma'$). So by compactness $Sigmacup Sigma'$ has a model. But $SigmacupSigma'$ says the model is an infinite well-ordered set that has a greatest element, and such that every element except the least has an immediate predecessor, and no such well-ordered set exists.

A good pattern we can abstract from this last example is that if we can find some axioms that have arbitrarily large finite models in the class but no infinite models in the class, then the class is not axiomatizable. (This also explains how we came up with the ordering properties in $Sigma’,$ which probably seemed like they were pulled out of a hat at first glance.)