8
$\begingroup$

This thread has it compactness theorem can be derived from Tychonoff theorem. I'm interested in how this can be done, but got stuck.

Here's how far I understand:

Following the version of campactness theorem in A Mathematical Introduction to Logic, Herbert B. Enderton(2ed):

A set of wffs (well-formed formula) is satisfiable iff every finite subset is satisfiable.

Let $\Sigma$ be a set of wffs, each of which is generated by a set of sentence $A$ whose elements can be indexed by $I$. Then the truth value of each finite subset $\Sigma_{\alpha}$ is determined by the truth assignment of $A$, which can be expressed as a function in the space $\{T, F\}^I$. For each finite subset $\Sigma_{\alpha}$, there is a non-empty subset $J_{\alpha}$ of $\{T, F\}^I$ which makes $\Sigma_{\alpha}$ true. Suppose all finite subsets of $\Sigma$ can be indexed by $B$, then the compactness theorem says $\bigcap_{\alpha \in B}J_{\alpha} \neq \varnothing$

I got stuck on how to define the topology of $\{T, F\}^I$. It seems to me, since $\Sigma_{\alpha}$ is a finite set of wffs, its truth value should only depend on the truth values of a finite number of sentences in $A$.

Supposedly, Tychonoff Theorem could serve as a hint, but I don't know how to proceed.

$\endgroup$
5
  • $\begingroup$ You can piece together a proof from the material in qchu.wordpress.com/2010/11/22/… ; the relevant paragraph is the second-to-last one although it may not make a lot of sense until you read the rest of the post. $\endgroup$ Dec 29, 2012 at 7:33
  • $\begingroup$ Also, hint: the statement of the compactness theorem should remind you of the finite intersection property, so try to rephrase it in those terms (using the product topology on $\{ T, F \}^I$). $\endgroup$ Dec 29, 2012 at 7:57
  • $\begingroup$ @QiaochuYuan: Thank you very much for your hints, but I can't quite follo it.If I want to use finite intersection property, then $J_\alpha$ is supposed to be closed. But in product topology, they seem to be open. $\endgroup$ Dec 29, 2012 at 8:05
  • $\begingroup$ Also related: math.stackexchange.com/questions/842/… $\endgroup$
    – Asaf Karagila
    Dec 29, 2012 at 9:11
  • $\begingroup$ @Metta: the $J_{\alpha}$ are both open and closed. $\endgroup$ Dec 29, 2012 at 9:18

1 Answer 1

5
$\begingroup$

Working according to your setup above, you should give $\{T,F\}$ the discrete topology, and $\{T,F\}^I$ the product topology of $|I|$ copies of the discrete topology.

In the product topology on $\{T,F\}^I$, a basis for the open sets is given by $$\{B_{i_1,\dots,i_k,v_1,\dots,v_k}\mid i_1,\dots,i_k\in I, \ v_1,\dots, v_k\in\{T,F\},\ k \in {\Bbb Z}_{>0}\}, $$ where $$ B_{i_1,\dots,i_k,v_1,\dots,v_k}=\{s=(s_i)_{i\in I}\in \{T,F\}^I\mid s_{i_1}=v_1,\dots, s_{i_k}=v_k.\} $$ In other words, the basic open sets are simply those which constrain the values of finitely many coordinates of an element in $\{T,F\}^I$ to be fixed values in $\{T,F\}$.

Suppose that you can determine whether or not an element $s=(s_i)_{i\in I}$ of $\{T,F\}^I$ is a member of a set $Y$ by looking at only finitely many coordinates $s_{i_1}$, $\dots$, $s_{i_k}$ of $s$. Then, $Y$ is open, because it is a union of basic open sets. The complement of $Y$ is also open, for the same reason. Therefore $Y$ is clopen (both closed and open.) Given any wff $f\in\Sigma$, whether an assignment satisfies $f$ or not can be determined by looking at only a finite subset of the basic sentences. So, the set $J_f$ of satisfying assignments to $f$ is clopen.

$\{T,F\}$ is finite, so it's compact. Then, by Tychonoff's Theorem, $\{T,F\}^I$ is compact. If every finite set of wffs is satisfiable, the $J_f$s have the finite intersection property (every finite subset of the $J_f$s has a nonempty intersection.) Each $J_f$ is closed, so by compactness, $\bigcap_{f\in\Sigma} J_f\ne\emptyset$. Therefore, $\Sigma$ is satisfiable. This is the Compactness Theorem.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer, which is as good as Jon Barwise's second proof(page 27) in Handbook of Mathematical Logic :-) $\endgroup$ Feb 15, 2013 at 8:04

You must log in to answer this question.

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