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

Homework Help: Infinite Models + Compactness

  1. Nov 1, 2007 #1
    1. The problem statement, all variables and given/known data

    Problem: 2.6.8 Enderton: A Mathematical Introduction to Logic

    Assume that A is true in all infinite models of a theory T. Show that there is a finite number k such that A is true in all models D of T for which |D| has k or more elements.

    3. The attempt at a solution

    To be honest I'm completley stuck on a solution for this. One of my classmates said that I was supposed to use completness to do the proof though I'm unsure how.

    I'm guessing the first step is to show that A is even true under a finite model of T.

    Compactness Theorem States:

    A) If G implies S then for some finite g subset of G we have g implies S.

    G a set of formula's and S is a formula.

    B) If every finite set of G is satisfiable then G is satisfiable.

    Also: A set G of sentences has a model iff every finite subset has a model.

    So, the only thing that I can possibly see using for the problem is that G is a set of sentences (Ie: one sentence) and that every finite subset must have a model iff the whole set has a model. Thus I can add on sentences to show there must be a finite model. Though I'm still unsure how that would work out. I'm unsure how I would be able to show that a set of sentances has a finite model if I'm unsure that the sentence alone can have a finite model :*(.
    Last edited: Nov 1, 2007
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted