Skip to main content
5 of 8
added 539 characters in body
Drike
  • 1.6k
  • 8
  • 19

I wonder whether 'deepness' is subjective or not. The Compactness Theorem of first-order logic has several proofs.

Theorem. (Gödel-Maltsev) Given a language $L$ and a set $S$ of first-order sentences in that language, if every finite subset of $S$ has a model, then $S$ has model.

(A language is just a set of relational, function and constant symbols, for example the language of ordered fields is $+,\times,=,\leqslant,0,1$; a first-order sentence in this language is a finite word using this language and $\exists,\forall,\land(and),\lor(or)$ and paranthesis for ease of reading only, for instance the sentence $\forall x\exists y(y^2=x)$; a model of a sentence is just a set where the sentence can be interpreted in a 'true' way. For instance $\bf R$ is not a natural model of the above sentence as $-1$ does not have a squareroot there, but $\bf C$ is a model of it.)

(For one immediate application, one can deduce in a straightforewared way that there is an ordered field containing $\bf R$ as well as infinitesimal/infinite elements while having the same first order properties as $\bf R$)

Some Proofs. (I believe there are many more)

(1) Gödel's original proof (for Gödel, in 1929, this Theorem was stated as a 'Remark') is from his Completeness Theorem, stated in the particular case where the language $L$ is countable. The proof does not use the axiom of choice. Hard for me to say the nature of the proof. Grammatical maybe.

(2) I don't know precisely the nature of Maltsev's proof, published in German in 1936, and extending G.'s result to the case of an arbitrary signature $L$, using the axiom of choice.

(3) Los' proof via the 'explicit' construction of the model as ultraproduct of finite structures, using the 'axiom of the ultrafilter', which is weaker that the axiom of choice. I would say this proof is of a topological nature.

In the same (?) vein, Gromov's 'bounded version' of his Theorem stating that a finitely generated group of polynomial growth as a nilpotent subgroup of finite index has several (at least 2) proofs, apparently.

Theorem. (Gromov) For any positive integers $k$, $d$, $n$, there exists a positive integer $m$ such that any $n$-generated group, in which for all $r= 1,\dots,m$ the size of the ball of radius $r$ centered at the identity is at most $kr^d$, has a subgroup of index and nilpotency class at most $m$.

I read that Gromov's original proof is a Compactness argument. Van den Dries and Wilkie gave an alternative proof using Gödel's Compactness Theorem. Belegradek recently provided a third proof using yet another kind of compactness argument, using very little model theory.

Edit: To match the OP's Edit, I'm just adding that the field concerning the first Theorem should be 'model theory' which currently classified as the latest of the 4 branches of 'mathematical logic'. It is central in the sense that it more or less gave birth to the 'field', and is used more or less tacitly in pretty much every Theorem of model theory. The second Theorem belongs to the field of 'geometric group theory', and I do not know about it's being central. I'd just say it is a Theorem of Gromov. Maybe this is enough!

Drike
  • 1.6k
  • 8
  • 19