# What is the outermost class 2^Σ* referring to on the Extended Chomsky Hierarchy?

After having searched a bit, it seems I can't find terminology or references for this outermost class, 2Σ* in blue -- see below. What is it describing?

• It's the power set of all sentences over $\Sigma$. In other words, it is all possible languages built from the alphabet $\Sigma$, since a language is just a subset of $\Sigma^*$, and the power set describes all possible subsets of a set.
– rici
Nov 18, 2021 at 18:11
• Several comments on the diagram. 1. A language is either "recognizable" or "not recognizable"; there should be no room outside of these two boxes. 2. Whether $\text{NP} \neq \text{P}$ is not known/proved. 3. Whether $\text{PSPACE}\neq\text{EXPTIME}$ is not known/proved. 4. Any given language can be included in a "Turing degree." Nov 18, 2021 at 18:58
• @JohnL. it seems to be missing caveats like "contained in" or <= or ?=, rather than a distinct = or . I don't have a caption for this figure. Nov 19, 2021 at 14:19
• Good point. However, had I drawn the diagram, I would have drawn the boundary of a box differently, such as dotted lines, if the box does not mean strict containment by the area outside of it. Nov 19, 2021 at 15:52

$$2^{\Sigma^{*}}$$ means the powerset of the full language $$\Sigma^{*}$$. It means the set of all subsets of $$\Sigma^{*}$$, including the empty set and $$\Sigma^{*}$$ itself, i.e., all possible languages with alphabet $$\Sigma$$.
Here is the simple understanding. When we want to describe a language $$X$$ with alphabet $$\Sigma$$, for each string $$w$$ in $$\Sigma^{*}$$, there are $$2$$ choices, including $$w$$ in $$X$$ or excluding $$w$$ from $$X$$. All these choices are independent.