Results 1 to 2 of 2

Math Help - Corollary of compactness theorem

  1. #1
    Junior Member
    Joined
    Aug 2010
    Posts
    32

    Corollary of compactness theorem

    Show that if a set of sentences S entails a sentence F, then some finite subset of S implies F.

    Here's what I have so far. Suppose S entails F, and for reductio, that no finite subset of S implies F. So, for every finite subset S*, there is an interpretation that makes every sentence in S* true and F false. A fortiori, this means that for every finite subset S* of S, there is an interpretation that makes every sentence in S* true. By the compactness theorem, this means that S has a model, call it M. Since S entails F, F will be true on M.

    I don't know where to go from here.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Corollary of compactness theorem

    I assume that the compactness theorem says that if every finite subset of S has a model, then the whole S has a model. Continuing your proof, for every finite subset S*, there is an interpretation that makes every sentence in S* true and F false, i.e., S* has a model and S* ∪ {F} has a model. But every finite subset of S ∪ {F} has the form S* or S* ∪ {F} where S* is a finite subset of S. Therefore, S ∪ {F} has a model, which contradicts the assumption that S entails F.

    It is also easy to show the converse: if for all S and F, S entailing F implies that some finite subset of S entails F, then the (contrapositive of the) compactness theorem holds. Indeed, suppose that S does not have a model. Then S entails falsehood, which by assumption means that some finite subset S* of S entails falsehood. This means that S* does not have a model.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Compactness Theorem and partial orderings
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 2nd 2011, 12:35 PM
  2. Corollary
    Posted in the Geometry Forum
    Replies: 0
    Last Post: October 25th 2010, 05:00 PM
  3. compactness theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 27th 2010, 09:46 AM
  4. Prove this Theorem and Corollary
    Posted in the Differential Equations Forum
    Replies: 3
    Last Post: March 12th 2010, 05:30 AM
  5. Topological Compactness and Compactness of a Set
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: September 22nd 2009, 12:16 AM

Search Tags


/mathhelpforum @mathhelpforum