Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Compactness in Topology and in Logic

  1. Sep 15, 2011 #1
    Hi, All:

    I am trying to understand better the similarity between the compactness theorem

    in logic--every first-order sentence is satisfiable (has a model) iff every finite subset

    of sentences is satisfiable, and the property of compactness : a topological space X is

    said to be compact iff (def.) every cover C of X by open sets has a finite subcover, i.e.,

    a subcollection C' of the cover C that also covers X , i.e., the union of the elements of

    the cover contains X. But, by De Morgan, compactness is equivalent to the finite

    intersection property, i.e., every finite subcollection (of the elements of a cover) has a

    non-empty intersection (the subcollections will be sentences, and the intersection

    has to see with the finite subcollection having a model ).

    Anyway, so the topological space we consider is that of the infinite product

    of {0,1} (discrete topology ) -- 0 and 1 will be the values we will be giving to the free

    variables in a sentence--with the product indexed by I:=[0,1] in the Reals. We then

    get the Cantor Space . Then any

    string of 0's , 1's is a valuation, is a clopen subset of the Cantor Space. By compactness,

    of the Cantor space (and some hand-waving) we get satisfiability.

    I think this is "spiritually correct", but I think there are some gaps. Any Ideas?

  2. jcsd
  3. Sep 16, 2011 #2
    Well, the only gap is that you appear to be talking about propositional logic, not first-order logic. The completeness therem for classical first-order logic is more complicated to prove.

    For propositional logic, to each set of sentences, assign the set of valuations which make all of the sentences true. Then the finite intersection property of the (Cantor) space of valuations is simply another way of stating the compactness of the logic.
  4. Sep 16, 2011 #3
    Thanks, Preno; can you think of an argument along these lines to prove compactness
    in FOL? I know (please critique/suggest) that in FOL, a valuation making all sentences true (if this is possible; I guess if the sentences are not contradictory) is a model/interpretation for the collection of sentences, and not just an assignment in a truth table. So, given a collection of sentences, we need to "interpret" the bound sentences by using Tarski's definition of truth . Any comments?
  5. Sep 23, 2011 #4
    Never mind, Preno, I saw an argument that has to see with Stone's theorem on representability of Boolean algebras. I will read it and post it here soon.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook