Let be the set of propositional variables. may be finite, countable, or of any cardinality. Let us denote by the space of all truth assignments. is given the product topology. is compact by Tychonoff’s theorem.
Let us examine the equivalence between compactness of propositional logic and compactness of .
Compactness of Propositional Logic. Let be a collection of formulas. If is unsatisfiable, then there exists a finite unsatisfiable subset of .
For every formula , denote the collection of unsatisfying assignments by . forms a clopen set in . On the other hand, for every clopen set , there exists a formula such that . Moreover, is unsatisfiable if and only if . Look at the following proposition and observe the equivalence.
Compactness of . Let be a collection of clopen sets in . If covers , then there exists a finite subset of that covers .
Observation. Let be a subset of Cantor space. is clopen if and only if can be expressed as a finite union of basis elements if and only if 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 be a subset of Cantor space or Baire space. is open if and only if is semidecidable with an oracle.
Proof. If is open, then is a countable union of basis elements. Encode those information into an oracle and then we can semidecide . On the other hand, if is semidecidable by an oracle Turing machine , then
with each being open.
Then, there exists a uniformly Cauchy subsequence of .
For every , the covering has a subcovering for a finite set . Let
and be an enumeration of countable set .
Let us define a two-dimensional sequence inductively on , so that be a subsquence of .
Inductive Case) Let us define from . Since is compact, there exists a convergent subsequence of , for a strinctly increasing . Define
Consider the diagonal sequence given by
By construction, converges for every . Now it is left to show that is uniformly Cauchy.
Fix . Pick satisfying . Choose so that
This is possible since is finite. Note that depends on , but not on any particular .
Fix . There exists such that . Let . Observer that