1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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