What are $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$?
A similar notation appears in
- (In logic) Arithmetical hierarchy or Analytical hierarchy
- (In descriptive set theory) Borel hierarchy or Projective hierarchy
- (In computer science) Polynomial hierarchy
So it depends on context. Often (but not always) these symbols indicate that the hierarchy of object has the following 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.
Related videos on Youtube
MphLee
Updated on August 01, 2022Comments
-
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 over 10 yearsPerhaps you're thinking of the projective hierarchy?
-
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 over 10 yearsAh yes, thanks, i meant that even if I typed it wrong.@AsafKaragila
-
-
MphLee over 10 yearsThanks, 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 over 10 yearsI don't know the answer, but this book looks promising: Kechris, A. S., Classical Descriptive Set Theory
-
MphLee over 10 yearsThanks. Well I'll search an online version of this book, meanwhile i'll update my question.