15
$\begingroup$

The compactness theorem has a lot of applications to logic and model theory. I'm looking for applications. I'm looking for theorems in other areas of mathematics which seem at first sight to have nothing to do with logic but which allow a fairly simple proof with Compactness. For example, the existence of the algebraic closure can easily be proved in that manner (see JDH's answer in this MO question), and Marker shows in his book on model theory that every injective polynomial map $\Bbb C^n \rightarrow \Bbb C^n$ is surjective.

Do you know any other examples? I would be especially grateful for an application outside of algebra, if there is any.

$\endgroup$
  • 1
    $\begingroup$ @user14111 The "compactness theorem" is from logic, not topology. en.wikipedia.org/wiki/Compactness_theorem . It's related, but it is more genera than Tychonoff's. $\endgroup$ – Thomas Andrews Jun 7 '13 at 13:12
  • 3
    $\begingroup$ The compactness theorem for first-order logic is equivalent to the statement "every filter can be extended to an ultrafilter". From this many many things follow. $\endgroup$ – Asaf Karagila Jun 7 '13 at 18:11
  • 5
    $\begingroup$ @user: in fact the compactness theorem is equivalent to Tychonoff's theorem for compact Hausdorff spaces. (In that sense it is known to be strictly weaker than Tychonoff's theorem, which is equivalent to the axiom of choice, so I don't understand Thomas' comment.) $\endgroup$ – Qiaochu Yuan Jun 7 '13 at 18:37
  • 1
    $\begingroup$ @user14111: That's because there is a deep connection between model theory and topology. $\endgroup$ – Asaf Karagila Jun 8 '13 at 0:26
  • $\begingroup$ @AsafKaragila: What king of connection? That sounds perplexing. $\endgroup$ – Trismegistos Jun 10 '13 at 9:12
5
$\begingroup$

Yet another version of these 'extension' examples: if a set of figures (polyominos, Wang tiles, etc.) tiles arbitrarily large regions of the plane (or, for instance, if it tiles a quarter-infinite plane) then it tiles the whole plane. This is a straightforward application of Konig's theorem, and compactness is another way of framing the argument; see https://math.stackexchange.com/a/38751/785 for the basic details of this approach.

$\endgroup$
8
$\begingroup$

There is a very nice proof from compactness that every set can be linearly ordered.

For a set $A$ define the language $\mathcal L_A$ to have the binary relation symbol $<$, and a constant symbol $c_a$, for every $a\in A$.

Let $T$ be the theory stating that $<$ is a linear order, and for every distinct $a,b\in A$ add an axiom $c_a\neq c_b$. It is not hard to show that every finite $T_0\subseteq T$ has a model. By compactness $T$ has a model $M$, which $<^M$ linearly orders. The function $a\mapsto c_a^M$ is an injection, therefore $A$ can be linearly ordered.

$\endgroup$
  • $\begingroup$ Can you give an outline of it? $\endgroup$ – Steven Stadnicki Jun 7 '13 at 18:50
  • $\begingroup$ @Steven: Done and done. $\endgroup$ – Asaf Karagila Jun 7 '13 at 18:52
  • 1
    $\begingroup$ Fantastic; thank you! For a moment I thought this implied that compactness was equivalent to full AC, but there's a nicely subtle flaw in that logic. $\endgroup$ – Steven Stadnicki Jun 7 '13 at 18:59
  • $\begingroup$ @Steven: Yes. I gave my students this question (with a generous hint) recently. After that I sat to understand exactly where it fails to well-order $A$, and it's a very subtle point indeed! $\endgroup$ – Asaf Karagila Jun 7 '13 at 19:00
5
$\begingroup$

The compactness theorem is equivalent to various other results in mathematics, including

$\endgroup$
  • 1
    $\begingroup$ See form 14 from the Consequences of the Axiom of Choice. The reference page at consequences.emich.edu/conseq.htm lists the Compactness Theorem as form 14H. Tychonoff's theorem is 14J, Ultrafilter theorem is 14A, Stone's representation theorem is 14B, the Banach-Alaoglu theorem is 14Q. $\endgroup$ – András Salamon Jun 7 '13 at 18:54
  • $\begingroup$ @András: To be more accurate, Tychonoff's theorem for Hausdorff spaces is 14J. Tychonoff as a whole is equivalent to the axiom of choice. $\endgroup$ – Asaf Karagila Jun 7 '13 at 22:19
  • $\begingroup$ @Asaf: you are right, though I was specifically aiming to tie Qiaochu's list to the "official" numbers. $\endgroup$ – András Salamon Jun 8 '13 at 7:13
4
$\begingroup$

The compactness theorem is routinely used in Ramsey theory and combinatorial graph theory to give a link between finitary versions and infinitary versions of theorems. For example, if we know that every infinite graph has either an infinite complete subgraph or an infinite antichain, we can deduce that for each $k$ there is an $n$ such that every graph of $n$ vertices has either a complete subgraph of size $k$ or an antichain of size $k$. I believe that people in the field view these implications as somewhat routine.

$\endgroup$
4
$\begingroup$

Similar to Carl Mummert's example, if the Four Color Theorem holds for all finite maps in the plane, then it holds for all infinite maps in the plane.

$\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.