Compactness of Propositional Logic

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

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

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

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

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

Topological Aspects of Cantor space and Baire space

Observation. Let UU be a subset of Cantor space. UU is clopen if and only if UU can be expressed as a finite union of basis elements if and only if UU 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 UU be a subset of Cantor space or Baire space. UU is open if and only if UU is semidecidable with an oracle.

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

U=iUiU = \bigcup_i U_i


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

with each UiU_i being open.

Arzela-Ascoli Theorem

Arzela-Ascoli Theorem.

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

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

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

and (sn)(s_n) be an enumeration of countable set SXS \subseteq X.

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

Base Case) g0,n=fng_{0,n} = f_n

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

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

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

hn=gn,n.h_n = g_{n, n} .

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

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

sS1/mn,mNd(hn(s),hm(s))ϵ.\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 S1/mS_{1/m} is finite. Note that NN depends on ϵ\epsilon, but not on any particular xXx \in X.

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

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

d(hn(s),hm(s))ϵd(h_n(s), h_m(s)) \le \epsilon

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

together yielding

d(hn(x),hm(x))3ϵ.d(h_n(x), h_m(x)) \le 3\epsilon .