2
$\begingroup$

I'm reading Russ's proof of the compactness theorem, wherein we suppose $\Gamma = \{\phi_1, \phi_2,...\}$ is a set of propositional sentences with all of the propositional variables chosen from $V = \{p_1,p_2,...\}$. We identify $2^V$ as the set of all truth-assignments--I take it this means that although $2^V$ is the power-set of $V$, an element like $\{p_1,p_3,p_5,...\}$ would be identified with the truth-assignment $\tau$ in which $\tau(p_1)=T$ and $\tau(p_2)=F$ and so on. I believe he also says to identify these with $X\times X\times ...$ where $X=\{T,F\}$ so that in my example this truth-assignment is identified with the tuple $(T,F,T,F,T,...)$, and to give this the product topology. He notes that, by the Tychonoff theorem $2^V$ is compact. From here he defines $D_\phi = \{\tau | \tau \vDash \phi\}$ and notes that this is always both open and closed.

Getting to the proof of compactness, we want to show that if every finite subset of $\Gamma$ has a model then so does $\Gamma$. He points out that $\Gamma$ has a model if and only if $\cap_{\phi\in\Gamma}D_\phi\ne\emptyset$. So far I'm good with all this.

Next he says that, due to the compactness of $2^V$, this is equivalent to $\cap_{\phi\in\Gamma_0}D_\phi\ne\emptyset$ for every finite $\Gamma_0\subset\Gamma$. Here's where I get lost. How does compactness get us this, where are we using open covers?

I have a suspicion about what the open covers are but I'm not seeing exactly the move, still. I suspect that the open sets in the cover are, for any given $\Gamma_0$ and $\phi\in\Gamma_0$, the set of all associated $D_\phi$ and $2^V-D_\phi$, hence why he remarked that $D_\phi$ is both open and closed. How does the fact that every open cover has a finite subcover connect to these particular finite subcovers?

$\endgroup$
  • 3
    $\begingroup$ Google for the Finite Intersection Property, a well´known and extremely useful characterization of compactness. It should be explained in every textbook on general topology. $\endgroup$ – Mariano Suárez-Álvarez Jan 13 '17 at 6:10
1
$\begingroup$

One of the key theorems that characterize compactness says that a topological space $X$ is compact if and only if every collection $\mathcal{C}$ of closed subsets of $X$ such that the intersection of every finite subset of $\mathcal{C}$ is nonempty, has nonempty intersection.

This theorem provides the link between the definition of compactness in terms of finite subcovers and the view of compactness that we use when we claim that propositional logic enjoys compactness.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.