Welcome to our blog! Check back on this page every now and then to find new posts, including articles from Notes from the Margin.

Blog Entries

Topologie et apprentissage machine

November 14, 2017

Notes from the Margin, the twice-yearly CMS Studc publication featuring student writing for a general mathematical audience, has for several years provided a platform for topics from higher-order Fourier analysis to tenure-track job interviews. We are excited to present this first post on the Notes from the Margin blog, which will complement but not replace the semi-annual print publication. We invite submissions year-round at student-editor@cms.math.ca.

The article for “October” is in French, it is available here.

“Why Compactness?”

September 29, 2017

Notes from the Margin, the twice-yearly CMS Studc publication featuring student writing for a general mathematical audience, has for several years provided a platform for topics from higher-order Fourier analysis to tenure-track job interviews. We are excited to present this first post on the Notes from the Margin blog, which will complement but not replace the semi-annual print publication. We invite submissions year-round at student-editor@cms.math.ca.

“Why Compactness?”

Todd Schmid

With consequences such as the Upward Löwenheim-Skolem Theorem, the Compactness Theorem is one of the most foundational results in the study of first-order logic. It is common to see only a Henkin-style syntactic proof or a lay-it-on-the-anvil ultraproduct proof of first-order compactness. However illuminating these proofs are, neither of them illustrate a topological picture of what the theorem represents. As one might guess, this picture is where the theorem gained its name.

A few clarifications before we begin: We define an $\mathcal{L}$ –theory to be a set of first-order logic sentences written in the language $\mathcal{L}$ which is closed under logical consequence. For example, the uniqueness of the group-theoretic inverse

$\forall x \exists y \forall z(z \cdot x = x \cdot z = 1 \rightarrow z = y)$

is a sentence in the $\{\cdot, 1\}$ -theory of groups, because it follows from the group axioms. An $\mathcal{L}$ -theory $T$ is called consistent if $\neg \varphi$ does not belong to $T$ when $\varphi$ belongs to $T$ . Note that I have chosen to draw no distinction between two sentences which are logically equivalent, and that “iff” should read “if and only if.”

Compactness Theorem. Fix a language of symbols $\mathcal{L}$ , and let $T$ be an $\mathcal{L}$ -theory. Then $T$ is consistent iff every finite subset $T_0$ of $T$ is consistent.

Considering the compactness theorem is a statement about consistent $\mathcal{L}$ -theories, it should seem sensible to topologize this collection. There turns out to be a natural way of doing this, but the fact of the matter is this: The set of all consistent $\mathcal{L}$ -theories is unnecessarily complicated for our purposes! All we need to encode in our open sets are which finite subsets belong to an $\mathcal{L}$ -theory. It is sufficient to focus our attention on a much better behaved collection of $\mathcal{L}$ -theories.

Definition. An $\mathcal{L}$ -theory $T$ is complete if for any $\mathcal{L}$ -sentence $\varphi$ , either $\varphi \in T$ or $\neg \varphi \in T$ .

In other words, complete theories decide on the truth-value of every sentence. To motivate the attention we give this special class of theories, one should verify for themselves the following properties of complete theories, omitting the parenthetical content either altogether or not at all:

(1) Each (consistent) $\mathcal{L}$ -theory is contained in some complete (and consistent) $\mathcal{L}$ -theory,

(2) any intersection of (consistent) $\mathcal{L}$ -theories is also a (consistent) $\mathcal{L}$ -theory, and

(3) an $\mathcal{L}$ -theory is determined precisely by the set of complete $\mathcal{L}$ -theories which contain it.

In particular, (3) holds for single sentences.

I will denote the collection of complete and consistent $\mathcal{L}$ -theories with $S$ . We define a topology on $S$ as follows: For each $\mathcal{L}$ -sentence $\varphi$ , let $[\varphi]$ denote the collection of $\mathcal{L}$ -theories containing $\varphi$ . Then

$\mathcal B = \{[\varphi] \mid \varphi \text{ is an } \mathcal{L}\text{-sentence}\}$

is a basis for a topology called the Stone topology on $S$ (named after the mathematician M. H. Stone). To see that this is true, notice that $[\varphi]\cap[\psi] = [\varphi\wedge\psi]$ , that $\emptyset = [\varphi \wedge \neg \varphi]$ , and that $[\varphi \vee \neg \varphi] = S$ . The theorem which follows is exactly the connection between topological and logical compactness.

Lemma. A subset $\mathcal O \subseteq \mathcal B$ covers $S$ iff $\{\neg \varphi : [\varphi] \in \mathcal O\}$ is inconsistent.

Proof.

$\begin{array}{rl} \mathcal O \subseteq \mathcal B \text{ covers S } & \\ \text{iff} & \text{for every }T \in S\text{ there is a }[\varphi]\in \mathcal O\text{ such that }\\ &\varphi \in T \\ \text{iff}&\text{ for no }T \in S\text{ is }\varphi \not\in T\text{ for every }[\varphi] \in \mathcal O \\ \text{iff}&\text{ for no }T \in S\text{ is }\neg\varphi\in T\text{ for every }[\varphi] \in \mathcal O \\ \text{iff}& \{\neg \varphi\mid [\phi]\in\mathcal O\}\text{ is inconsistent (see (1) above).} \end{array}$

$\square$

Theorem. $S$ is compact iff the Compactness Theorem holds.

Proof. $(\Leftarrow)$ Suppose that the Compactness Theorem holds, and let $\mathcal O$ be a collection from $\mathcal B$ which covers $S$ . Every element of $\mathcal O$ is of the form $[\varphi]$ , so we can form a set $B$ out of the $\L$ -sentences $\{\neg\varphi \mid [\varphi] \in \mathcal O\}$ . By the lemma, $B$ is an inconsistent set of sentences, so the Compactness Theorem tells us there is a finite subset $B_0$ of $B$ which is inconsistent. We are left with a finite subset $\{[\neg\varphi] \mid \varphi \in B_0\}$ of $\mathcal O$ which covers $S$ . $\mathcal O$ was chosen arbitrarily, so $S$ must be compact.

$(\Rightarrow)$ Suppose that $S$ is compact, and let $T$ be an $\L$ -theory. If $T$ is inconsistent, then the lemma tells us $\mathcal O = \{[\neg\varphi] \mid \varphi \in T\}$ is an open cover of $S$ . $S$ is compact, so a finite subset $\mathcal O_0\subseteq \mathcal O$ covers $S$ . The collection $B_0 = \{\neg \varphi \mid [\varphi] \in \mathcal O_0\}$ is a finite subset of $T$ which is inconsistent. On the other hand, if $T$ has a finite inconsistent subset $T_0$ , then $T$ is inconsistent and there is nothing to show. $\square$

What amazes me about the illustration above is that it approaches consistency in first-order logic from a purely topological perspective. Further inquiries in this direction can be found in [2] and [3], and a proof that $S$ is compact can be found somewhere in [1].

Bibliography.

[1] A Topological Viewpoint of Logic and the Compactness Theorem (2016). T Schmid. Link.

[2] Ultrafilters, ultraproducts, and the Compactness Theorem (2009). A Caicedo. Link.

[3] Notes On Ultrafilters. A Kruckman. Link.

Todd Schmid is an undergraduate at the University of Victoria. He likes long beach walks, the overlap of geometry and logic, and strange Scandinavian films. Among his favourite quotations is this one by César Vallejo: “Beloved be the ones who sit down.”