Results 1 to 7 of 7

Math Help - In the hierarchy of formulas according to quantifiers and variables....

  1. #1
    Member
    Joined
    Aug 2010
    Posts
    130

    In the hierarchy of formulas according to quantifiers and variables....

    When one characterises a formula by an uppercase pi or sigma, and the superscript is 2 or greater, is this the same thing as saying that the formula is a second-order formula, so that for example the L÷wenheim-Skolem or Compactness theorems don't apply to theories containing such formulas?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Actually, I don't think I've seen superscripts 2 and greater. Usually, the superscript is just a mark whose numerical value is not important. Superscript 0 is used to denote classes of first-order formulas, and superscript 1 is used for second-order formulas.

    In contrast, the subscript n refers to n alternating groups of similar quantifiers. So if P(x,y) and Q(X,Y) are quantifier-free formulas, then \forall x\exists y.\,P(x,y) is a \Pi^0_2-formula (lowercase variables range over numbers), while \forall X\exists Y.\,Q(X,Y) is a \Pi^1_2-formula (uppercase variables range over sets of numbers).

    See arithmetical hierarchy and analytical hierarchy.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2010
    Posts
    130
    Thanks, emakarov. So the correction of my superscript error brings up two related questions.

    (a) Since inaccessibles are Pi-1,1 indescribable, does that make the formula which describes them Pi-1,1 in the analytic hierarchy?

    (b) This question applies only if inaccessibles are Pi-m,n, m>0. (m superscript) I know there is a countable model of the sentence that an uncountable cardinal exists. But this is from the L÷wenheim-Skolem Downward Theorem. However, if the sentence that there exists an inaccessible cardinal is a Pi 1,1 formula, then since that theorem doesn't apply to second-order, the same proof would not apply. So, as to the sentence that there exists an inaccessible cardinal, is there
    (i) a countable model of the sentence?
    (b) if so, how would that be proven?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Sorry, I am a beginner in set theory and don't know what a \Pi^1_1-indescribable cardinal is. Wikipedia talks about formulas in second-order logic, but I studied set theory (ZF) as a first-order theory. I encountered second- and higher-order logics mostly in arithmetic and proof theory.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2010
    Posts
    130
    Thanks for the reply, emakarov. Indescribable cardinals are quite interesting as a way of classifying large cardinal strengths. A cardinal k is said to be Pi(m,n) indescribable iff for every set S in R(k) [which is also called V_k] and every Pi(m,n) sentence P, if <R(k), epsilon, S> |= P, then there exists a cardinal b < k such that <R(b), epsilon, S intersect R(b)> |= P. Similarly for Sigma(m,n) indescribable. In other words, they are cardinals for which no formula of that strength can fully describe, so my first reaction is that inaccessibles, as Pi(1,1) indescribables, are stronger than Pi(1,1), and hence not liable to the L-S downward theorem. But I am unsure.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    And what is a Pi(m,n) sentence? Are we working with ZF set theory, which is first-order, or some other theory and/or logic?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Aug 2010
    Posts
    130
    A Pi(m,n) formula (being lazy and letting the uppercase Pi, with a superscript m and subscript n) is the extension of the analytic hierarchy as explained in the link that you gave me from Wiki, and usually comes up for higher orders in discussions of the constructible universe. The language is an extension of the ZF-language, and the theories are extensions of ZF, (or Bernays-Morse) with new variables added for the higher-order variables. The formula is put into prenex form with various tricks. If the first order variables range over the domain A, then second-order variables range over P(A) or P(A X A) or…., where P(S) is the power set of S; third order variables over P(P(A)) or other ranges of this type: with a depth of at most wo in terms of the power set operator. Similarly for higher-order variables. Then, as you corrected me, terms of order n+1 are the variables X^n, etc. Then, the subscript refers to the number of alternating quantifiers of the highest order of the formula, beginning with a universal quantifier (and Sigma(m,n) with an existential one) as in the arithmetic case. The other definitions, such as satisfaction, deduction, validity, are then all defined similarly to those for first-order formulas, although the properties sometimes are different.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: December 3rd 2011, 10:27 PM
  2. Cumulative hierarchy
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 1st 2010, 04:27 AM
  3. Quantifiers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 10th 2009, 08:57 PM
  4. Replies: 1
    Last Post: August 26th 2009, 08:04 AM
  5. Quantifiers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 7th 2008, 06:31 PM

Search Tags


/mathhelpforum @mathhelpforum