Thread: Enderton 3.1 Problem 6 (p. 193)

Show that is not finitely axiomatizable. Suggestion. Show that no finite subset of suffices, and then apply Section 2.6.

Necessary definitions can be found here.

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

Any hint to start this problem?

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.

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 is not enough.

What facts do you have in Section 2.6?

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

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 , your guess is quite reasonable.

How do you justify your guess?

Thanks

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 is a finite axiomatization of . The formulas from don't literally have to be in . For example, may have instead of .

Since , we have . By compactness theorem, for some finite . Therefore, is true in a finite model. But then is impossible.

Originally Posted by emakarov

Suppose that is a finite axiomatization of . The formulas from don't literally have to be in . For example, may have instead of .

Ah, yes. I hadn't considered that.

Originally Posted by emakarov

Since , we have . By compactness theorem, for some finite . Therefore, is true in a finite model. But then is impossible.

I don't follow the last part yet, but no need to explain--I'm currently working on it on my own.