What are $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$?

1,295

A similar notation appears in

So it depends on context. Often (but not always) these symbols indicate that the hierarchy of object has the following diagram:

Hierarchial diagram

The meaning of the arrows depends on the context. For example, in the Borel hierarchy, $\bf\Sigma$ are families of sets closed under $\sigma$-union, $\bf \Pi$ are families closed under $\sigma$-intersection, $\bf\Delta$ are closed under both, and the arrows in the diagram indicate inclusion.

Share:
1,295

Related videos on Youtube

MphLee
Author by

MphLee

Updated on August 01, 2022

Comments

  • MphLee
    MphLee over 1 year

    Sometimes reading on wikipedia or in this site (and in very different context like topology, arithmetic and logic) I have found these symbols $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$. They are probably classes of something, but i don't know their name and i wasn't able to find something i can understand (I read about hierachies, but hierachies of what and, in which field of mathematics?)

    I hope someone can give me an easy explaination of these things (classes?), how they are related, in which field(s) of mathematics these concepts appear and a formal definition (or a link).

    Thanks in advance. and I apologize for errors (I'm using a translator).

    Update

    What is the meaning of the upper index $0$? In the logic use of this notation $\Sigma_n^1$ is the hieracy of the formulas in the language of second-order arithmetic. Intuitively I could think that the hierchies $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$ are the hierachies of the formulas in the language of $(i−1)$-order arithmetic..probably I'm wrong but how this index is linked with other fields?

    • Nate Eldredge
      Nate Eldredge over 10 years
      Perhaps you're thinking of the projective hierarchy?
    • Asaf Karagila
      Asaf Karagila over 10 years
      $i+1$-order formulas, not $i-1$. $\Sigma^0_n$ is first-order, and $\Sigma^1_n$ is second-order. And so on.
    • MphLee
      MphLee over 10 years
      Ah yes, thanks, i meant that even if I typed it wrong.@AsafKaragila
  • MphLee
    MphLee over 10 years
    Thanks, that makes all more clear to me. At least brings order in my mind. Anyways, I still don't understand what is the meaning of the upper index $0$, in the logic use of this notation $\Sigma^1_n$ is the hieracy of the formulas in the language of 2nd order arithmetic.Intuitively I could think that the hierchies $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$ are the hierachies of the formulas in the language of $(i-1)$-order arithmetic..probably I'm wrong but how this index is linked with other fields?
  • Yoni Rozenshein
    Yoni Rozenshein over 10 years
    I don't know the answer, but this book looks promising: Kechris, A. S., Classical Descriptive Set Theory
  • MphLee
    MphLee over 10 years
    Thanks. Well I'll search an online version of this book, meanwhile i'll update my question.