1
$\begingroup$

Alexander's Subbasis Theorem (AST) is the following statement:

A topological space $X$ is compact if and only if there is a subbasis $\mathcal{S}$ for the topology such that every cover of $X$ by elements of $\mathcal{S}$ has a finite subcover.

I can prove the following (over $\mathsf{ZF}$):

  • AST $\Rightarrow$ Tychonoff's Theorem for compact Hausdorff spaces $\Rightarrow$ Propositional compactness (PC).

  • PC $\Rightarrow$ Boolean Prime Ideal Theorem (eq. Ultrafilter Theorem) $\Rightarrow$ AST.

I know how to show AST $\Rightarrow$ PC more directly, by appropriately topologizing the set $X$ of all valuations of propositional formulas ($X$ will be homeomorphic to $\{0,1\}^{|L|}$), showing that $X$ is compact iff PC holds, and then applying AST to show that $X$ is a compact space.

However, is there a direct proof of PC $\Rightarrow$ AST? That is, by directly defining an appropriate set of propositional formulas encoding the conclusion of AST.

$\endgroup$

1 Answer 1

1
$\begingroup$

Yes, you can use exactly the same strategy I showed you in my answer to your previous question on Tychonoff's Theorem. Since it seems you had some lingering questions about that answer, I'll write out the details again for you.

One direction of AST is trivial. Suppose $X$ is compact. Taking $\mathcal{S}$ to be the subbasis consisting of all open sets, every cover of $X$ by elements of $\mathcal{S}$ has a finite subcover.

For the non-trivial direction, suppose $\mathcal{S}$ is a subbasis for the topology on $X$ such that every cover of $X$ by elements of $\mathcal{S}$ has a finite subcover. Let $\mathcal{B}$ be the basis generated by $\mathcal{S}$ (so $\mathcal{B}$ is the set of all finite intersections of sets from $\mathcal{S}$). To show $X$ is compact, it suffices to show that every cover of $X$ by elements of $\mathcal{B}$ has a finite subcover. Equivalently, it suffices to show that if $(U_i)_{i\in I}$ is a family of basic open sets from $\mathcal{B}$ such that no finite subfamily covers $X$, then $(U_i)_{i\in I}$ does not cover $X$.

So fix $(U_i)_{i\in I}$ such that no finite subfamily covers $X$. For each $i\in I$, write $U_i = S_i^1\cap\dots\cap S_i^{k_i}$ with each $S_i^j\in \mathcal{S}$. Consider the propositional language consisting of one proposition symbol $P_S$ for each set $S\in \mathcal{S}$, and the propositional theory $T$ consisting of the following two axiom schemes:

  1. Whenever $S_1,\dots,S_n\in \mathcal{S}$ and cover $X$, include the axiom $\varphi_{S_1,\dots,S_n}\colon \bigvee_{j=1}^n \lnot P_{S_j}$.
  2. For each $i\in I$, include the axiom $\psi_{U_i}\colon \bigvee_{j=1}^{k_i} P_{S_i^j}$.

Claim 1: For any point $x\in X$, define a valuation $v_x$ by $$v_x(P_S) = \begin{cases} \top& \text{if }x\notin S\\ \bot&\text{if }x\in S.\end{cases}$$ Then $v_x$ satisfies all axioms from scheme 1, and if $x\notin U_i$, then $v_x$ satisfies axiom $\psi_{U_i}$ from scheme 2.

Proof of Claim 1: For scheme 1, suppose $S_1,\dots,S_n\in S$ and cover $X$. Then $x\in S_j$ for some $1\leq j \leq n$, so $v_x(P_{S_j}) = \bot$, and $v_X$ satisfies $\varphi_{S_1,\dots,S_n}$. For scheme 2, suppose $x\notin U_i = S_i^1\cap\dots\cap S_i^{k_i}$. Then there exists $1\leq j\leq k_i$ such that $x\notin S_i^j$, so $v_x(P_{S_i^j}) = \top$, and $v_X$ satisfies $\psi_{U_i}$. $\square$

Claim 2: Let $v$ be a valuation which satisfies all axioms from scheme 1. Then there is a point $x\in X$ such that for all $S\in \mathcal{S}$, if $v(P_S) = \top$, then $x\notin S$. Further, if $v$ satisfies axiom $\psi_{U_i}$ from scheme 2, then $x\notin U_i$.

Proof of Claim 2: Let $\mathcal{F} = \{S\in \mathcal{S}\mid v(P_S) = \top\}$. Let $S_1,\dots,S_n\in \mathcal{F}$. If $S_1,\dots,S_n$ cover $X$, then $v$ satisfies $\varphi_{S_1,\dots,S_n}$, so there is some $1\leq j\leq n$ such that $v(P_{S_j}) = \bot$. This contradicts the fact that each $S_j\in \mathcal{F}$. So no finite subfamily of $\mathcal{F}$ covers $X$. By our hypothesis on $\mathcal{S}$, $\mathcal{F}$ fails to cover $X$, so there is some $x\in X\setminus \bigcup_{S\in \mathcal{F}} S$. Thus, for all $S\in \mathcal{S}$ such that $v(P_S) = \top$, $x\notin S$. Now suppose $v$ satisfies the axiom $\psi_{U_i}$. Then for some $1\leq j\leq k_i$, $v(P_{S_i^j}) = \top$, so $x\notin S_i^j$, and hence $x\notin U_i$. $\square$

To finish the proof of AST, I claim that the theory $T$ is consistent. A finite subset $\Delta\subseteq T$ includes only finitely many axioms $\psi_{U_{i_1}},\dots,\psi_{U_{i_m}}$ from scheme $2$. By our assumption, $U_{i_1},\dots,U_{i_m}$ does not cover $X$, so there is some point $x$ which is not in any $U_{i_j}$. By Claim 1, the valuation $v_x$ satisfies $\Delta$.

By compactness, $T$ is consistent. Let $v$ be a valuation satisfying $T$. By Claim 2, there is a point $x\in X$ such that $x\notin U_i$ for all $i\in I$. Thus $(U_i)_{i\in I}$ does not cover $X$, as was to be shown.

$\endgroup$
1
  • $\begingroup$ Thank you very much for your very detailed answer. Also, last week I carefully read your past answer to the Tychonoff Theorem question, and I thought I had resolved my lingering issues. However, in reading your answer to the Alexander Subbase Theorem I see that the way you think about these types of problems is a bit different than mine, so I decided to post my answer (re-worked via open covers) to the Tychonoff Theorem question. If my "how to" approach to define what's needed is flawed, I would certainly welcome a correction, if you have the time to read it. $\endgroup$
    – John
    May 25 at 13:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .