Enderton 3.1 Problem 6 (p. 193)

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

Necessary definitions can be found here.

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

Any hint to start this problem?

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.

Re: Enderton 3.1 Problem 6 (p. 193)

Quote:

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 $\displaystyle A_S$ is not enough.

What facts do you have in Section 2.6?

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).

Re: Enderton 3.1 Problem 6 (p. 193)

Quote:

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 $\displaystyle \text{Th }N_S = \text{Cn }A_S$, your guess is quite reasonable.

How do you justify your guess?

Thanks

Re: Enderton 3.1 Problem 6 (p. 193)

Quote:

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 $\displaystyle T\subseteq \mathop{\mathrm{Th}}N_S$ is a finite axiomatization of $\displaystyle \mathop{\mathrm{Th}}N_S$. The formulas from $\displaystyle A_S$ don't literally have to be in $\displaystyle T$. For example, $\displaystyle T$ may have $\displaystyle S1\land S1$ instead of $\displaystyle S1$.

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

Re: Enderton 3.1 Problem 6 (p. 193)

Quote:

Originally Posted by

**emakarov** Suppose that $\displaystyle T\subseteq \mathop{\mathrm{Th}}N_S$ is a finite axiomatization of $\displaystyle \mathop{\mathrm{Th}}N_S$. The formulas from $\displaystyle A_S$ don't literally have to be in $\displaystyle T$. For example, $\displaystyle T$ may have $\displaystyle S1\land S1$ instead of $\displaystyle S1$.

Ah, yes. I hadn't considered that.

Quote:

Originally Posted by

**emakarov** Since $\displaystyle \mathop{\mathrm{Th}}N_S=\mathop{\mathrm{Cn}}A_S$, we have $\displaystyle A_S\models T$. By compactness theorem, $\displaystyle A\models T$ for some finite $\displaystyle A\subset A_S$. Therefore, $\displaystyle T$ is true in a finite model. But then $\displaystyle 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. :)