4
$\begingroup$

Say we would like to prove that the class of all infinite groups $(G, \circ, e)$ is not finitely axiomatizable by making use of the compactness theorem. We normally prove this by contradiction since we know the axiomatic system is defined by the union of $\Phi_{group}$ (the standard FO axiomatic system for groups) and $\Phi_{\infty}$ (in FO logic, there exist $x_1$ to $x_n$ and they are all pairwise non-identical and that for all $n \in \mathbb{N}$).

Assuming there exist a $\Phi_{infGrp} \subseteq FO(\tau)$ that finitely axiomatizes this class. Therefore, we can find a $\psi \in FO(\tau)$ that axiomatizes this class too, since the axiomatic system is finite.

This implies that $\Phi_{infGrp} \cup \{\neg\psi\}$ is not satisfiable. We then go on to find a arbitrary, finite subset $\Phi_0 \subseteq \Phi_{infGrp} \cup \{\neg\psi\}$, and show that we can find a structure that is a model of this subset by making the said structure to have more elements than the formula with a largest $m \in \mathbb{N}$ in $\Phi_0$. We then finally say that since structure $\mathbb{A} \models \Phi_0$, by virtue of compactness theory, $\Phi_{infGrp} \cup \{\neg\psi\}$ is satsifiable.

The question is... how can $\Phi_{infGrp} \cup \{\neg\psi\}$ be satisfiable when $\neg\psi$ contains statements that negate the properties of a group. Wouldn't every structure (that is a group) not be a model for $\Phi_{infGrp} \cup \{\neg\psi\}$?

$\endgroup$
4
$\begingroup$

There is nothing in $\lnot\psi$ that needs to negate the properties of a group. Assume finite axiomatizability. So we can take the axioms to be $\alpha_1,\dots,\alpha_m$, the usual axioms of group theory, plus additional special axioms $\beta_1,\dots,\beta_n$, which in conjunction with the group axioms force the group to be infinite. Then $\psi$ is the sentence $$\alpha_1\land\cdots\land \alpha_m \land \beta_1\land\dots\land \beta_n.$$ The sentence $\lnot \psi$ is then the sentence $$\lnot\alpha_1\lor\cdots\lor \lnot\alpha_m \lor \lnot\beta_1\lor\dots\lor \lnot\beta_n.$$ This is a disjunction. No group property needs to fail.

$\endgroup$
  • $\begingroup$ Ah yea true that didn't occur to me! Thanks! $\endgroup$ – mercurial Aug 12 '14 at 12:25
  • $\begingroup$ You are welcome. It is natural to think that a group-theoretic axiom is being negated. $\endgroup$ – André Nicolas Aug 12 '14 at 13:13
3
$\begingroup$

The following may be a more intuitive proof:

Let $\mathcal{L}$ be the first order language of groups. Let $K$ denote the class of infinite groups.

If $K$ was finitely axiomatizable, then by taking conjunctions, one may assume that there is a single formula $\psi$ such that $K$ is the set of the all $\mathcal{L}$-structures $M$ such that $M \models \psi$. Since the group axioms are finite, let $\Phi$ be the conjunction of all the group axioms. Then $ \Phi \wedge \neg \psi$ axiomatizes the class of all finite groups. Let $\mathcal{L}' = \mathcal{L} \cup \{c_i : i < \omega\}$. $\mathcal{L}'$ is the expanded language with infinitely many new constant symbols. Let $T = \{\Phi \wedge \neg \psi\} \cup \{c_i \neq c_j : i \neq j\}$. If $\Delta \subseteq T$ is a finite set, then only finitely many new constant symbols $c_{i_0}, ..., c_{i_n}$ were mentioned in any sentence of $\Delta$. Take any group $G$ of size $n$. Make $G$ into a $\mathcal{L}'$-structure by interpreting $c_{i_0}, ..., c_{i_n}$ as $n$ distinct elements of $G$. (You can interpret the other constants to be whatever you want.) Then $G$ as a $\mathcal{L}'$-structure satisfies $\Delta$. So $\Delta$ is satisfiable. By the compactness theorem, there exists a $G$ such that $G \models T$. Clearly $G$ must be an infinite $\mathcal{L}'$-structure which satisfies $\Phi \wedge \neg \psi$. The reduct of $G$ back to $\mathcal{L}$ is then an infinite group satisfying $\Phi \wedge \neg \psi$. This is a contradiction since $\Phi \wedge \neg \psi$ was suppose to be an axiomatization of finite groups.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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