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

1. ## 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

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

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

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

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

6. 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?

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