Compactness of Propositional Logic

Let $V$ be the set of propositional variables. $V$ may be finite, countable, or of any cardinality. Let us denote by $2^V = \{0,1\}^V$ the space of all truth assignments. $2^V$ is given the product topology. $2^V$ is compact by Tychonoff’s theorem.

Let us examine the equivalence between compactness of propositional logic and compactness of $2^V$.

Compactness of Propositional Logic. Let $\mathcal{F}$ be a collection of formulas. If $\mathcal{F}$ is unsatisfiable, then there exists a finite unsatisfiable subset of $\mathcal{F}$.

For every formula $F$, denote the collection of unsatisfying assignments by $U(F)$. $U(F)$ forms a clopen set in $2^V$. On the other hand, for every clopen set $V \in 2^V$, there exists a formula $F$ such that $U(F) = V$. Moreover, $\mathcal{F}$ is unsatisfiable if and only if $\bigcup_{F \in \mathcal{F}} U(F) = 2^V$. Look at the following proposition and observe the equivalence.

Compactness of $2^V$. Let $\mathcal{U}$ be a collection of clopen sets in $2^V$. If $\mathcal{U}$ covers $2^V$, then there exists a finite subset of $\mathcal{U}$ that covers $2^V$.

Topological Aspects of Cantor space and Baire space

Observation. Let $U$ be a subset of Cantor space. $U$ is clopen if and only if $U$ can be expressed as a finite union of basis elements if and only if $U$ is decidable.

The observation above is proved using compactness. Baire space is not compact, which is why the same property does not hold for Baire space.

Observation. Let $U$ be a subset of Cantor space or Baire space. $U$ is open if and only if $U$ is semidecidable with an oracle.

Proof. If $U$ is open, then $U$ is a countable union of basis elements. Encode those information into an oracle and then we can semidecide $U$. On the other hand, if $U$ is semidecidable by an oracle Turing machine $M$, then

$U = \bigcup_i U_i$

where

$U_i = \{ p \mid M(p) \text{ halts in $i$ or less steps }\}$

with each $U_i$ being open.

Arzela-Ascoli Theorem

Arzela-Ascoli Theorem.

• Let $X$ be a compact space.
• Let $Y$ be a compact metric space.
• Let $(f_n: X \rightarrow Y)$ be an equicontinuous sequence of maps, that is, for every $x \in X$ and $\epsilon > 0$, there exists an open neighborhood $U(x, \epsilon) \subseteq X$ such that $f_n[U(x, \epsilon)] \subseteq B(f_n(x), \epsilon)$ for all $n \in \mathbb{N}$. ($U$ depends on $x$ and $\epsilon$, but not $n$)

Then, there exists a uniformly Cauchy subsequence of $(f_n)$.

Proof.
For every $\epsilon > 0$, the covering $\{ U(x,\epsilon) \mid x \in X\}$ has a subcovering $\{ U(x, \epsilon) \mid x \in S_{\epsilon}\}$ for a finite set $S_{\epsilon} \subseteq X$. Let

$S = \bigcup_{n \in \mathbb{N}} S_{1/n}$

and $(s_n)$ be an enumeration of countable set $S \subseteq X$.

Let us define a two-dimensional sequence $(g_{i,n}:X \rightarrow Y)_{i,n}$ inductively on $i$, so that $(g_{i+1,n})_n$ be a subsquence of $(g_{i,n})_n$.

Base Case) $g_{0,n} = f_n$

Inductive Case) Let us define $(g_{i+1,n})_n$ from $(g_{i,n})_n$. Since $Y$ is compact, there exists a convergent subsequence $(g_{i,\alpha(n)}(s_i))_n$ of $(g_{i,n}(s_i))_n$, for a strinctly increasing $\alpha : \mathbb{N} \rightarrow \mathbb{N}$. Define

$g_{i+1, n} = g_{i, \alpha(n)} .$

Consider the diagonal sequence $(h_n : X \rightarrow Y)$ given by

$h_n = g_{n, n} .$

By construction, $(h_n(s))_n$ converges for every $s \in S$. Now it is left to show that $(h_n)$ is uniformly Cauchy.

Fix $\epsilon > 0$. Pick $m \in \mathbb{N}$ satisfying $1/m \leq \epsilon$. Choose $N$ so that

$\forall s \in S_{1/m} \quad \forall n, m \ge N \quad d(h_n(s),h_m(s)) \le \epsilon.$

This is possible since $S_{1/m}$ is finite. Note that $N$ depends on $\epsilon$, but not on any particular $x \in X$.

Fix $x \in X$. There exists $s \in S_{1/m}$ such that $x \in U(s, 1/m)$. Let $n, m \ge N$. Observer that

$d(h_n(x), h_n(s)) \le 1/m \le \epsilon$

$d(h_n(s), h_m(s)) \le \epsilon$

$d(h_m(s), h_m(x)) \le 1/m \le \epsilon$

together yielding

$d(h_n(x), h_m(x)) \le 3\epsilon .$