Results 1 to 7 of 7

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

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2011
    Posts
    127

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Enderton 3.1 Problem 6 (p. 193)

    Quote Originally Posted by Annatala View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2011
    Posts
    127

    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).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.1 Problem 6 (p. 193)

    Quote Originally Posted by Annatala View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Enderton 3.1 Problem 6 (p. 193)

    Quote Originally Posted by Annatala View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Enderton 3.1 Problem 6 (p. 193)

    Quote Originally Posted by emakarov View Post
    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.

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Enderton 3.7 Problem 1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 14th 2012, 09:55 AM
  2. Enderton 3.4 Problem 1
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 24th 2011, 06:17 AM
  3. Enderton 3.3 Problem 5
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 19th 2011, 07:34 AM
  4. Enderton 3.3 Problem 8
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 05:46 AM
  5. Enderton 3.1 problem 1 (p.193)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 4th 2011, 10:30 AM

Search Tags


/mathhelpforum @mathhelpforum