Does the Compactness Theorem Guarantee a Minimum Model Size for Theorem Truth?

[moo5003]

Homework Statement

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.

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.

Edit:
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 :*(.

 

[mighty2000]

Dear fellow student,

Thank you for bringing this problem to our attention. I understand that you are stuck on finding a solution for this problem. I would like to offer some suggestions and guidance to help you work through it.

Firstly, let's break down the problem into smaller parts. We are given that A is true in all infinite models of a theory T. This means that for any infinite model, A will be true. Now, we need to show that there exists a finite number k such that A is true in all models D of T for which |D| has k or more elements.

One way to approach this problem is to use the Compactness Theorem, as you have mentioned. The Compactness Theorem states that if a set of sentences has a model, then every finite subset of that set also has a model. In other words, if the whole set is satisfiable, then every finite subset of the set is also satisfiable.

Now, let's apply this to our problem. We know that A is true in all infinite models of T. This means that the set of sentences {A} has a model, since any infinite model of T will satisfy A. By the Compactness Theorem, we can conclude that every finite subset of {A} also has a model. This includes sets of the form {A, B}, {A, B, C}, etc.

Next, we need to use the fact that A is true in all infinite models to show that A is also true in finite models with a certain number of elements. This is where you can use the Completeness Theorem. The Completeness Theorem states that a set of sentences has a model if and only if every finite subset of that set has a model. This means that if A is true in all infinite models, then it must also be true in all finite models with a certain number of elements.

Combining these two theorems, we can conclude that there exists a finite number k such that A is true in all models D of T for which |D| has k or more elements. This is because we know that A is true in all infinite models, and by the Completeness Theorem, it must also be true in all finite models with a certain number of elements, which is k.

I hope this helps in your understanding of the problem. Remember to always break down the problem into smaller parts and use the theorems and definitions that you have