# Math Help - Enderton 3.1 Problem 6 (p. 193)

1. ## Enderton 3.1 Problem 6 (p. 193)

Show that $\text{Th }N_S$ is not finitely axiomatizable. Suggestion. Show that no finite subset of $A_S$ suffices, and then apply Section 2.6.

Necessary definitions can be found here.

==============================

Any hint to start this problem?

2. ## Re: Enderton 3.1 Problem 6 (p. 193)

This is pretty straightforward. If you have a finite subset of the axioms, then you only have a finite number of versions of S4. Think of what might model that subset of axioms and what that implies.

3. ## Re: Enderton 3.1 Problem 6 (p. 193)

Originally Posted by Annatala
If you have a finite subset of the axioms, then you only have a finite number of versions of S4. Think of what might model that subset of axioms and what that implies.
This is how to show that a finite subset of $A_S$ is not enough.

What facts do you have in Section 2.6?

4. ## Re: Enderton 3.1 Problem 6 (p. 193)

Section 2.6 covers the basics of model theory and the cardinality of basic models (Lowenheim-Skolem, Los(Wash)-Vaught, etc.).

The result you want follows from Th 26H, I believe: If the consequences of some set are finitely axiomatizable, then there is a finite subset with the same consequences. So you need only to show that no finite subset of the consequences of As gives you the same consequences as As. I guess I would show it by showing that each of the single axioms must be in it in order to give you the same consequences, and any finite subset of the schema S4 gives you different consequences from all of S4.

Take this with a grain of salt though since I'm currently studying model theory myself (not for a class).

5. ## Re: Enderton 3.1 Problem 6 (p. 193)

Originally Posted by Annatala
Section 2.6 covers the basics of model theory and the cardinality of basic models (Lowenheim-Skolem, Los(Wash)-Vaught, etc.).

The result you want follows from Th 26H, I believe: If the consequences of some set are finitely axiomatizable, then there is a finite subset with the same consequences. So you need only to show that no finite subset of the consequences of As gives you the same consequences as As. I guess I would show it by showing that each of the single axioms must be in it in order to give you the same consequences, and any finite subset of the schema S4 gives you different consequences from all of S4.

Take this with a grain of salt though since I'm currently studying model theory myself (not for a class).
OK, since $\text{Th }N_S = \text{Cn }A_S$, your guess is quite reasonable.

How do you justify your guess?

Thanks

6. ## Re: Enderton 3.1 Problem 6 (p. 193)

Originally Posted by Annatala
So you need only to show that no finite subset of the consequences of As gives you the same consequences as As. I guess I would show it by showing that each of the single axioms must be in it in order to give you the same consequences, and any finite subset of the schema S4 gives you different consequences from all of S4.
Suppose that $T\subseteq \mathop{\mathrm{Th}}N_S$ is a finite axiomatization of $\mathop{\mathrm{Th}}N_S$. The formulas from $A_S$ don't literally have to be in $T$. For example, $T$ may have $S1\land S1$ instead of $S1$.

Since $\mathop{\mathrm{Th}}N_S=\mathop{\mathrm{Cn}}A_S$, we have $A_S\models T$. By compactness theorem, $A\models T$ for some finite $A\subset A_S$. Therefore, $T$ is true in a finite model. But then $T\models A_S$ is impossible.

7. ## Re: Enderton 3.1 Problem 6 (p. 193)

Originally Posted by emakarov
Suppose that $T\subseteq \mathop{\mathrm{Th}}N_S$ is a finite axiomatization of $\mathop{\mathrm{Th}}N_S$. The formulas from $A_S$ don't literally have to be in $T$. For example, $T$ may have $S1\land S1$ instead of $S1$.
Ah, yes. I hadn't considered that.

Originally Posted by emakarov
Since $\mathop{\mathrm{Th}}N_S=\mathop{\mathrm{Cn}}A_S$, we have $A_S\models T$. By compactness theorem, $A\models T$ for some finite $A\subset A_S$. Therefore, $T$ is true in a finite model. But then $T\models A_S$ is impossible.
I don't follow the last part yet, but no need to explain--I'm currently working on it on my own.