# Tychonoff's Theorem via the Compactness Theorem for propositional logic

I am trying to prove Thychonoff's Theorem using the Compactness Theorem for propositional logic.

A space $$X$$ is compact if and only if every collection $$C$$ of closed subsets of $$X$$ having the finite intersection property has nonempty intersection.

Hence, I am trying to show that given a family of compact spaces $$\{X_{i}\}_{i\in I}$$ then their product $$X=\prod_{i\in I}X_{i}$$ is compact by showing that an arbitrary family $$C$$ of closed subsets of $$X$$ having the f.i.p. has non-empty intersection.

I run into trouble defining the appropriate set $$S$$ of propositional formulas. And, in fact it seems we may need the $$X_{i}$$ to be also Hausdorff, since once $$S$$ is shown to be satisfiable it seems reasonable to use any assignment satisfying $$S$$ in order to define a non-empty set (perhaps a single point) which will be contained in $$\cap C$$ and thus show that the intersection is non-empty.

May someone point me in the right direction? Or perhaps there is a more direct argument not relying on the f.i.p. formulation of compactness?

Disclaimer: I have not learned first order logic yet. Hence, this related question does not really answer mine, as far as I can tell.

Let $$\{X_i\}_{i\in I}$$ be a family of compact spaces, and let $$X = \prod_{i\in I} X_i$$. Let $$C$$ be a family of closed subsets of $$X$$ with the f.i.p.

Notation: For $$Y_i\subseteq X_i$$, let's write $$\tilde{Y_i}$$ for the set $$Y_i\times \prod_{j\neq i} X_i\subseteq X$$. The sets $$\tilde{U_i}$$ with $$U_i$$ open in $$X_i$$ form a subbasis for the topology on $$X$$, so a basic open set has the form $$\tilde{U}_{i_1}\cap \dots \cap \tilde{U}_{i_n}$$, where each $$U_{i_j}$$ is open in $$X_{i_j}$$. Then a basic closed set has the form $$\tilde{V}_{i_1}\cup \dots \cup \tilde{V}_{i_n}$$, where each $$V_{i_j}$$ is closed in $$X_{i_j}$$.

Let's begin with the standard observation that we can replace $$C$$ with a family of basic closed sets. Indeed, every closed set is the intersection of all the basic closed sets containing it, so letting $$C' = \{V'\mid V'\text{ basic closed, and }V\subseteq V'\text{ for some }V\in C\}$$ we have $$\bigcap_{V\in C} V = \bigcap_{V'\in C'} V'$$ and $$C'$$ also has the f.i.p. So we can assume every closed set in $$C$$ is a basic closed set.

For every closed set $$F\subseteq X_i$$, introduce a proposition symbol $$P_F^i$$. A point of $$X$$ can be written as $$(x_i)_{i\in I}$$, and we think of $$P_F^i$$ as meaning "$$x_i\in F$$".

Now consider the following propositional theory $$T$$:

1. For all $$V\in C$$, with $$V = \tilde{V}_{i_1}\cup \dots \cup \tilde{V}_{i_n}$$, $$T$$ contains the axiom $$P^{i_1}_{V_{i_1}}\lor \dots \lor P^{i_n}_{V_{i_n}}.$$
2. For all $$i\in I$$ and all closed sets $$F_1,\dots,F_n$$ in $$X_i$$, if $$\bigcap_{j=1}^{n}F_j = \varnothing$$, then $$T$$ contains the axiom $$\lnot \bigwedge_{j=1}^{n} P^i_{F_j}.$$
3. For all $$i\in I$$ and all closed sets $$F,F'$$ in $$X_i$$, if $$F\cup F'= X_i$$, then $$T$$ contains the axiom $$P^i_{F}\lor P^i_{F'}.$$

I claim that $$T$$ is satisfiable. By compactness, it suffices to show that we can find an assignment satisfying all axioms from schemas 2 and 3, together with finitely many axioms from schema 1, corresponding to finitely many $$V_1,\dots,V_m\in C$$. By the hypothesis that $$C$$ has f.i.p., we can pick some $$x = (x_i)_{i\in I}\in V_1\cap\dots\cap V_m$$. For each proposition symbol $$P^i_F$$, set $$P^i_F$$ to be true if $$x_i\in F$$ and false otherwise. It is straightforward to check that this assignment works.

Since $$T$$ is satisfiable, there is some assignment $$t$$ from our proposition symbols to $$\{\top,\bot\}$$ satisfying $$T$$.

Fix $$i\in I$$. I claim that $$C_i = \{F\subseteq X_i\mid F\text{ closed, and }t(P^i_F) = \top\}$$ has non-empty intersection. Since $$X_i$$ is compact, it suffices to show that $$C_i$$ has the f.i.p. Let $$F_1,\dots,F_n\in C_i$$. If $$\bigcap_{j=1}^n F_j = \varnothing$$, then the axiom $$\lnot\bigwedge_{j=1}^n P^i_{F_j}$$ is in $$T$$, so we cannot have $$t(P^i_{F_j}) = \top$$ for all $$1\leq j\leq n$$, contradiction.

Thus we can pick $$x_i\in \bigcap_{F\in C_i}F$$ for all $$i\in I$$. I claim that $$x = (x_i)_{i\in I}\in\bigcap_{V\in C} V$$. For each $$V\in C$$ with $$V = \tilde{V}_{i_1}\cup \dots \cup \tilde{V}_{i_n}$$, $$T$$ contains the axiom $$P^{i_1}_{V_{i_1}}\lor \dots \lor P^{i_n}_{V_{i_n}}$$. So for some $$1\leq j\leq n$$, $$t(P^{i_j}_{V_{i_j}}) = \top$$. Then $$V_{i_j}\in C_{i_j}$$, so $$x_{i_j}\in V_{i_j}$$, so $$x\in V$$.

Great! But note that above, we have to use the axiom of choice to pick $$x_i\in \bigcap_{F\in C_i}F$$ for all $$i\in I$$. If you want to prove Tychonoff's Theorem from compactness for propositional logic relative to ZF, then you need to additionally assume that each $$X_i$$ is Hausdorff.

The fix is that when $$X_i$$ is compact Hausdorff, the set $$\bigcap_{F\in C_i}F$$ is a singleton $$\{x_i\}$$, so there is no choice to be made. Suppose $$x,y\in \bigcap_{F\in C_i}F$$ with $$x\neq y$$. Since $$X_i$$ is Hausdorff, we can find disjoint open neighborhoods $$U_x$$ and $$U_y$$ of $$x$$ and $$y$$, respectively. Let $$F_x = X_i\setminus U_x$$, and let $$F_y = X_i\setminus U_y$$. Since $$x\notin F_x$$, we must have $$t(P^i_{F_x}) = \bot$$. And since $$y\notin F_y$$, we must have $$t(P^i_{F_y}) = \bot$$. But since $$U_x\cap U_y = \varnothing$$, $$F_x\cup F_y = X_i$$, so the axiom $$P^i_{F_x}\lor P^i_{F_y}$$ is in $$T$$. This is a contradiction.

Note that we only used axiom schema 3 in the choiceless proof for compact Hausdorff spaces. But it didn't hurt to throw these axioms into $$T$$ in the proof for compact spaces as well.

• Your proof uses notions (such as consistency of a theory) which I have not learned yet. However, from your axiom schema I will try to work out an answer for compact Hausdorff spaces via the Compactness theorem for propositional logic (that is, defining the set S and then proving it is finitely satisfiable, etc). Certainly I will be coming back to your proof as I progress in my learning the concepts. Thanks again!
– John
Commented May 3, 2022 at 21:28
• @John oh, sorry. You can take "consistent" to be a synonym for "satisfiable" in what I wrote (in fact they are equivalent by the completeness theorem for propositional logic). And a theory is just a set of sentences. What I did was prove that the set $T$ is finitely satisfiable. You don't need to know anything beyond the statement of the compactness theorem to understand what I wrote. Commented May 3, 2022 at 21:31
• Thank you for the clarification.
– John
Commented May 4, 2022 at 3:14
• I returned to this exercise, and I see that my understanding was flawed. How do the propositional symbols $P_{F}^{i}$ relate to the elements $x\in X$, or the $x_{i}\in X_{i}$ for each $i$? When you say $P_{F}^{i}$ means $x_{i}\in F$, to what $x_{i}$ are you referring to? Do you mean that we have a propositional symbol $P_{F}^{x_{i},i}$ for each $i$, $F\in X_{i}$ closed and $x_{i}\in X_{i}$?
– John
Commented May 14, 2023 at 16:16
• @John No, I meant what I wrote. The point is this: to show that $C$ has non-empty intersection, we need to produce a point $x$ in the intersection. To produce $x=(x_i)_{i\in I}$, we need to specify $x_i\in X_i$ for each $i$. Somehow this specification should come from a valuation assigned to some propositional variables. Now the key idea is that we can specify a point in a compact Hausdorff space by specifying which closed sets it is an element of. So if the valuation given to us by the compactness theorems says $P_F^i$ is true, then we make sure to pick $x_i$ such that $x_i\in F$. Commented May 14, 2023 at 17:23

I had some lingering issues, and after carefully reading the well-written answer posted by Alex Kruckman I wanted to rework the solution using the open cover definition of compactness in order to display my reasoning in detail, hoping it can be corrected if appropriate. I want to make sure I get this right.

A brief set-up:

A collection of subsets of a topological space $$X$$ is inadequate if and only if it fails to cover $$X$$, and finitely inadequate if and only if no finite subcollection covers $$X$$. Then, it is straightforward to check that a topological space $$X$$ is compact if and only if every finitely inadequate collection of open sets of $$X$$ is inadequate.

If $$\mathcal{C}$$ is a finitely inadequate collection of open sets of $$X$$, then there is a finitely inadequate collection $$\mathcal{O}$$ of basic open sets of $$X$$ such that $$\bigcup_{V\in\mathcal{C}}V = \bigcup_{U\in\mathcal{O}}U$$

Indeed, simply consider $$\mathcal{O} = \{U:\text{U is basic open and U\subseteq V for some V\in\mathcal{C}}\}$$.

Let $$\{(X_{\alpha},\tau_{\alpha}),\alpha\in I\}$$ be a collection of compact topological spaces. Based on the set-up above we only need to consider a finitely inadequate collection $$\mathcal{O}$$ of basic open sets of $$X=\prod_{\alpha\in I}X_{\alpha}$$. We will use propositional compactness to show that $$\mathcal{O}$$ is inadequate by describing a point of $$X$$ which is not covered by $$\mathcal{O}$$ using a valuation appropriately definied on the right propositional symbols (the language $$L$$ below) and satisfying the right set of $$L$$-sentences (the set $$S$$ below).

How do we define the right $$L$$ and $$S$$? Well, let us say $$a=(a_{\alpha})_{\alpha\in I}$$ is not covered by $$\mathcal{O}$$. That is, $$a\in X-\bigcup_{U\in \mathcal{O}}U$$ This means that for each $$U\in \mathcal{O}$$ with $$U=\bigcap_{\alpha\in J}\tilde{U}_{\alpha}$$ for some finite $$J\subseteq I$$ and $$U_{\alpha}\in\tau_{\alpha}$$ for all $$\alpha\in J$$, there is some $$\alpha\in J$$ such that $$a_{\alpha}\not\in U_{\alpha}$$.

Therefore, a description of a point of $$X$$ not covered by $$\mathcal{O}$$ requires a description of its coordinates in the factor spaces $$X_{\alpha}$$, which can be accomplished by describing to which open subsets of $$X_{\alpha}$$ the coordinate does not belong to. Hence, it makes sense that

for each $$\alpha\in I$$, our propositional language $$L$$ has propositional atoms $$P_{V}^{\alpha}$$, for all $$V\in\tau_{\alpha}$$. We think of $$P_{V}^{\alpha}$$ expressing, when true (for a point of $$X$$), that the $$\alpha$$-th coordinate (of the point) does not belong to $$V$$. (e.g. for $$a$$, that $$a_{\alpha}\not\in V$$).

Now, let us go back to the particular $$a$$ not covered by $$\mathcal{O}$$ I am using to derive what we need. Describing to which open subsets of $$X_{\alpha}$$ the coordinate $$a_{\alpha}$$ does not belong to entails a description of the collection $$A_{\alpha}=\{V\in\tau_{\alpha}:a_{\alpha}\not\in V\}.$$ Indeed, we would like that
$$a_{\alpha}\in X_{\alpha}-\bigcup_{V\in A_{\alpha}}V.$$ Therefore, it is required we describe that $$A_{\alpha}$$ does not cover $$X_{\alpha}$$, which since $$X_{\alpha}$$ is compact, it is the same as saying that $$A_{\alpha}$$ is finitely inadequate. Indeed, if we want our truth valuation $$v:\{\text{L-atoms P_{V}^{\alpha}}\}\rightarrow\{\top\bot\}$$ to truly describes a point not covered by $$\mathcal{O}$$ by telling us to which open subsets $$V$$ in the factor space $$X_{\alpha}$$ the $$\alpha$$-th coordinate of the point does not live in, we must have $$v(P_{V}^{\alpha})=\top$$. Hence, it makes sense to consider for each $$\alpha\in I$$, the collection $$C_{\alpha} = \{V\in\tau_{\alpha}:v(P_{V}^{\alpha})=\top\},$$ which we would want to be finitely inadequate, just as $$A_{\alpha}$$ (i.e. $$v$$ will be defined in such a way that $$A_{\alpha}\subseteq C_{\alpha}$$)

Let us put this all together by considering the following set $$S$$ of $$L$$-sentences:

• (a) For each basic open set $$U\in\mathcal{O}$$ with $$U=\bigcap_{\alpha\in J}\tilde{U}_{\alpha}$$ for some finite $$J\subseteq I$$ and $$U_{\alpha}\in\tau_{\alpha}$$ for all $$\alpha\in J$$, we have the $$L$$-sentence $$\bigvee_{\alpha\in J}P_{U_{\alpha}}^{\alpha}$$ Collectively, these $$L$$-sentences describe that our truth valuation will express that $$\mathcal{O}$$ is inadequate by describing a point not covered by $$\mathcal{O}$$.
• (b) For each $$\alpha\in I$$ and each finite subset $$F\subseteq\tau_{\alpha}$$ with $$\bigcup_{V\in F}V=X_{\alpha}$$, we have the $$L$$-sentence $$\bigvee_{V\in F}\neg P^{\alpha}_{V}$$ These $$L$$-sentences express that for each $$\alpha\in I$$ our truth-valuation-defined collection $$C_{\alpha}$$ is finitely inadequate.
• (c) For each $$\alpha\in I$$ and each pair $$V,W\in\tau_{\alpha}$$ with $$U\cap W=\emptyset$$, we have the $$L$$-sentence $$P^{\alpha}_{V}\vee P_{W}^{\alpha}$$ For each $$\alpha\in I$$, these $$L$$-sentences express that our truth valuation respects that $$X_{\alpha}$$ is Hausdorff (these $$L$$-sentences will be crucial when each factor space $$X_{\alpha}$$ is also Hausdorff, but will be satisfied regardless)

If $$S$$ is finitely satisfiable, by propositional compactness it is satisfiable, and let $$v$$ be a truth valuation satisfying $$S$$. Then for each $$\alpha\in I$$ we can define $$C_{\alpha} = \{V\in\tau_{\alpha} : v(P_{V}^{\alpha}) = \top\},$$ which is wat we wanted.

If for each $$\alpha\in I$$ the collection $$C_{\alpha}$$ is finitely inadequate, it is also inadequate, and we can pick (notice the use of the full axiom of choice here!) for each $$\alpha\in I$$ a point $$a_{\alpha}\in X_{\alpha}-\bigcup_{V\in C_{\alpha}}V$$ We claim that the point $$a=(a_{\alpha})_{\alpha\in I}$$ so chosen is not covered by $$\mathcal{O}$$. Indeed, suppose it is. Then, there would be $$U\in\mathcal{O}$$ such that $$a\in U$$. But $$U=\bigcap_{\alpha\in J}\tilde{U}_{\alpha}$$ for some finite $$J\in I$$ and $$U_{\alpha}\in\tau_{\alpha}$$ for all $$\alpha\in J$$. Therefore, $$a_{\alpha}\in U_{\alpha}$$ for all $$\alpha\in J$$. Now, recall that $$v$$ satisfies the $$L$$-sentences in (a), so $$v(P^{\alpha}_{U_{\alpha}})=\top$$ for some $$\alpha\in J$$. Therefore, for some $$\alpha\in J$$ we have $$U_{\alpha}\in C_{\alpha}$$, i.e. $$a_{\alpha}\not\in U_{\alpha}$$, which is a contradiction.

Let us then prove that for each $$\alpha\in I$$, the collection $$C_{\alpha}$$ is finitely inadequate. Indeed, suppose there is a finite subset $$F\subseteq C_{\alpha}$$ such that $$\bigcup_{V\in F}V = X_{\alpha}$$. Clearly, $$v(P_{V}^{\alpha}) = \top$$ for all $$V\in F$$. On the other hand, since $$v$$ satisfies the $$L$$-sentences in (b) we must have $$v(P_{V}^{\alpha}) = \bot$$ for some $$V\in F$$, which is a contradiction.

Finally, we will prove that $$S$$ is finitely satisfiable. Indeed, let $$\Delta\subseteq S$$ be a finite subset of $$S$$. Then there are finitely many basic open sets $$U_{1},\ldots, U_{m}\in\mathcal{O}$$ occurring in the $$L$$-sentences of $$\Delta$$. Since $$\mathcal{O}$$ is finitely inadequate, we can pick $$b=(b_{\alpha})_{\alpha\in I}\in X-(U_{1}\cup\ldots\cup U_{m})$$. Define a truth valuation $$v_{\Delta}$$ by $$v_{\Delta}(P_{V}^{\alpha}) = \top\text{ if and only if b_{\alpha}\not\in V}.$$ It is straightforward to check that $$v_{\Delta}$$ satisfies all the $$L$$-sentences in (a)-(c) occurring in $$\Delta$$.

Regarding the use of the sentences in (c) when we make the additional assumption that each $$X_{\alpha}$$ is also Hausdorff: Recall that we needed the full axiom of choice to pick for each $$\alpha\in I$$ a point in $$Y_{\alpha} = X_{\alpha}-\bigcup_{V\in C_{\alpha}}V$$ This need dissapears when each $$X_{\alpha}$$ is compact Hausdorff because the previous set is a singleton for each $$\alpha\in I$$. Indeed, suppose $$x\neq y\in Y_{\alpha}$$. Since $$X_{\alpha}$$ is Hausdorff, we can find disjoint $$V,W\in\tau_{\alpha}$$ with $$x\in V$$ and $$y\in W$$. Let $$v$$ be the truth valuation satisfying $$S$$. Then, $$v(P_{V}^{\alpha}\vee P_{W}^{\alpha})=\top,$$ which means $$v(\neg P_{V}^{\alpha})=v(\neg P_{W}^{\alpha})=\top$$ cannot occur. But since $$x\in V$$ and $$y\in W$$, we have $$V,W\not\in C_{\alpha}$$, which means precisely that $$v(\neg P_{V}^{\alpha})=v(\neg P_{W}^{\alpha})=\top$$. This is a contradiction, and we must have $$x=y$$.

• I see no essential difference between your answer and mine. Commented May 25, 2023 at 15:22