Results 1 to 5 of 5

Math Help - Question about second-order quantification

  1. #1
    Member
    Joined
    Aug 2010
    Posts
    130

    Question about second-order quantification

    In second-order logic, when you quantify over all models of a given first-order theory, isn't a statement for a given first-order sentence P in that theory of the form
    "for all M (M models P)"
    merely saying that P is a tautology?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Question about second-order quantification

    Quote Originally Posted by nomadreid View Post
    In second-order logic, when you quantify over all models of a given first-order theory, isn't a statement for a given first-order sentence P in that theory of the form
    "for all M (M models P)"
    merely saying that P is a tautology?
    I don't know why you're referring to second order logic in this regard, but

    for all M, if M is a model (i.e. structure) for the language, then M is a model of P

    can be taken as saying that P is logically valid.

    Some people use 'tautology' to mean 'logically valid'. But other people reserve 'tautology' for those formulas that are logically valid in particular on account of their form regarding the connectives in the formula.
    Follow Math Help Forum on Facebook and Google+

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

    Re: Question about second-order quantification

    Quote Originally Posted by nomadreid View Post
    In second-order logic, when you quantify over all models of a given first-order theory
    How do you do it? Second-order logic quantifies over all sets.

    isn't a statement for a given first-order sentence P in that theory of the form
    "for all M (M models P)"
    merely saying that P is a tautology?
    How do you write "M models P" as a logical formula? Are you talking about truth definition as in Tarski's undefinability theorem?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2010
    Posts
    130

    Re: Question about second-order quantification

    Thanks for both replies.

    Thank you, Moe Blee.
    I don't know why you're referring to second order logic.
    Oops. Mistake. I meant "third-order logic", which would be necessary to quantify over models. Or perhaps I should have been more cautious and write "higher-order logics."
    Some people use 'tautology' to meanů
    I am thinking of the definition of tautology as a sentence which is true in all models in which the sentence is meaningful. (A formal definition would restrict it to a class of models in order to tiptoe around paradoxes from the use of the word "all" here, and undoubtedly theorems on absoluteness could help. My question here is the first step in my working this out.)

    Thanks, emakarov.
    Second-order logic quantifies over all sets.
    You are right; mea culpa. As I just mentioned, I meant third-order.
    How do you write "M models P" as a logical formula?
    The full formal definition would be rather long; whereas the central idea is essentially due to Tarski, the full definition of model would start from the inductive definitions given in standard works such as Chang & Keisler's "Model Theory" (pages 20-21 in the 1973 edition), or Drake's "Set Theory" (p 4-5 in the 1976 edition); in both of these works they essentially leave it to the reader to perform the tedium of writing these all out in first-order sentences, but assure the reader that it is possible. However, since in first-order logic they would be schemata, one would need second-order logic to express them as a single sentence, which would then express "M is a model of P" for a given M and a given P. Then, to quantify over all M which satisfy this definition, one would apparently need third-order logic. Alternatively, one could start from something like Kripke semantics.

    Further criticisms are welcome. I go out on a branch to see who will saw it off.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Question about second-order quantification

    Quote Originally Posted by nomadreid View Post
    I meant "third-order logic", which would be necessary to quantify over models. Or perhaps I should have been more cautious and write "higher-order logics."
    I don't think you need to write about any second, third, or higher order logic. I think it would be easier for you to think of using (first order) set theory to discuss models. At least that's the approach usually taken. If you want to formalize discussions about languages, models, theories, etc., then usually the convenient way to do that is to formalize in set theory. Of course, you could formalize in other ways, including, say, second order arithmetic (which is, in a certain sense, the same as first order set theory), but perhaps the easiest, and certainly the most common approach is to use set theory.

    Quote Originally Posted by nomadreid View Post
    I am thinking of the definition of tautology as a sentence which is true in all models in which the sentence is meaningful.
    I would say: a sentence that is true in all models for the language in which the sentence is written (also, though, there are formulas that are satisfied by any assignment for the variables for all models in which the formula is written). That's all okay, but I'm just pointing out that certain authors prefer a more narrow definition of tautology, to distinguish logically valid formulas in general from the tautologies that are logically valid but logically valid on account of the structure of the sentential connectives.

    Quote Originally Posted by nomadreid View Post
    Chang & Keisler's "Model Theory"
    Notice that in that book they mention that all the work in that book could be carried out in set theory.

    Quote Originally Posted by nomadreid View Post
    in first-order logic they would be schemata, one would need second-order logic to express them as a single sentence, which would then express "M is a model of P" for a given M and a given P.
    In set theory, you can write such things as a single sentence. It seems to me that you're getting yourself unnecessarily confused by trying to use higher order logic when the more ordinary and easier approach is to use set theory.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Universal Quantification proof
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: August 14th 2010, 11:29 AM
  2. logical quantification
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: November 25th 2009, 10:47 AM
  3. First Order Question
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: October 22nd 2009, 08:20 AM
  4. Logic: quantification
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 1st 2009, 06:18 AM
  5. universal quantification over null set
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 18th 2007, 03:07 PM

Search Tags


/mathhelpforum @mathhelpforum