Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Qiaochu Yuan Dec 29 '12 at 7:33
    
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$). –  Qiaochu Yuan Dec 29 '12 at 7:57
    
@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. –  Metta World Peace Dec 29 '12 at 8:05
    
Also related: math.stackexchange.com/questions/842/… –  Asaf Karagila Dec 29 '12 at 9:11
    
@Metta: the $J_{\alpha}$ are both open and closed. –  Qiaochu Yuan Dec 29 '12 at 9:18

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Thank you for your answer, which is as good as Jon Barwise's second proof(page 27) in Handbook of Mathematical Logic :-) –  Metta World Peace Feb 15 '13 at 8:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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