# Hierarquia de Grzegorczyk

A hierarquia de Grzegorczyk (pronúncia:), denominação em referência ao lógico polaco Andrzej Grzegorczyk, é uma hierarquia de funções usadas em teoria da computação (Wagner and Wechsung 1986:43). Toda função na hierarquia de Grzegorczyk é uma função recursiva primitiva, e toda função recursiva primitiva aparece na hierarquia em algum nível. A hierarquia lida com taxas de funções crescentes. Intuitivamente, funções em níveis baixos da hierarquia crescem mais devagar que funções em níveis mais altos.

## Definição

Primeiro introduzimos um conjunto infinito de funções, denotadas E$_i$ para algum número natural i. Definimos $E_{0}(x,y)=x+y$ e $E_{1}(x)=x^{2}+2$, i.e, E$_0$ é a função adicional, e E$_1$ é uma função unária que eleva seus argumentos ao quadrado e soma dois. Depois, para cada n maior que 1, definimos $E_{n}(x)=E_{n-1}^{x}(2)$.
Dessas funções definimos a hierarquia de Grzegorczy. ${\mathcal {E}}^{n}$, o n-ésimo conjunto de hierarquias, contém as seguintes funções:
* E$_k$ para k < n
* A função zero (Z(x) = 0);
* A função sucessor (S(x) = x + 1);
* A função de projeção ($p_{i}^{m}(t_{1},t_{2},\dots ,t_{m})=t_{i}$);
* A composição de funções (generalizada) no conjunto (se h, g$_1$, g$_2$, ... e g$_m$ estão em ${\mathcal {E}}^{n}$, então $f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),\dots ,g_{m}({\bar {u}}))$ também estão); e
* O resultado da recursão limitada (primitiva) aplicada a funções no conjunto, (se g, h e j estão em ${\mathcal {E}}^{n}$ e $f(t,{\bar {u}})\leq j(t,{\bar {u}})$ para todo t e ${\bar {u}}$, e mais $f(0,{\bar {u}})=g({\bar {u}})$ e $f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))$, então f está em ${\mathcal {E}}^{n}$ também)
Em outras palavras, ${\mathcal {E}}^{n}$ é o fechamento do conjunto $B_{n}=\{Z,S,(p_{i}^{m})_{i\leq m},E_{k}:k<n\}$ com respeito a composição de funções e recursão limitada (como definido acima).

## Propriedades

Esses conjuntos claramente são da hierarquia
    ${\mathcal {E}}^{0}\subseteq {\mathcal {E}}^{1}\subseteq {\mathcal {E}}^{2}\subseteq \cdots$
porque eles são fechados sob a $B_{n}$'s e $B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \cdots$.
Eles são subconjuntos próprios (Rose 1984; Gakwaya 1997). Em outras palavras
    ${\mathcal {E}}^{0}\subsetneq {\mathcal {E}}^{1}\subsetneq {\mathcal {E}}^{2}\subsetneq \cdots$
porque a hiperoperação $H_{n}$ está em ${\mathcal {E}}^{n}$ mas não em ${\mathcal {E}}^{n-1}$.
* ${\mathcal {E}}^{0}$ inclui funções como x+1, x+2, ...
* ${\mathcal {E}}^{1}$ provê todas as funções adicionais, tais como x+y, 4x, ...
* ${\mathcal {E}}^{2}$ provê todas as funções de multiplicação, tais como xy, x$^4$
* ${\mathcal {E}}^{3}$ provê todas as funções exponenciais, tais como x$^y$, 2$^{22x}$, e é exatamente função recursiva elementar.
* ${\mathcal {E}}^{4}$ provê todas as funções de tetração, e assim por diante.

## Relação com as funções recursivas primitivas

A definição de ${\mathcal {E}}^{n}$ é a mesma de função recursiva primitiva, RP, exceto que recursão é limitada ($f(t,{\bar {u}})\leq j(t,{\bar {u}})$ para algum j em ${\mathcal {E}}^{n}$) e as funções $(E_{k})_{k<n}$ são explicitamente incluidas em ${\mathcal {E}}^{n}$. Assim, a hierarquia de Grzegorczyk pode ser vista como um caminho para o limite do poder de recursões primitivas de diferentes níveis.
Está claro deste fato que todas as funções em qualquer nível da hierarquia de Grzegorczyk são funções recursivas primitivas (i.e. ${\mathcal {E}}^{n}\subseteq RP$) e assim:
    $\bigcup _{n}{{\mathcal {E}}^{n}}\subseteq RP$
Também pode ser demonstrado que todas as funções recursivas primitivas estão em algum nível da hierarquia (Rose 1984; Gakwaya 1997), assim
    $\bigcup _{n}{{\mathcal {E}}^{n}}=RP$
e conjuntos ${\mathcal {E}}^{0},{\mathcal {E}}^{1}-{\mathcal {E}}^{0},{\mathcal {E}}^{2}-{\mathcal {E}}^{1},\dots ,{\mathcal {E}}^{n}-{\mathcal {E}}^{n-1},\dots$ [[partição de conjunto|particiona]] o conjunto de funções recursivas primitivas, PR.

## Extensões

A hierarquia de Grzegorczyk pode ser estendida para ordinal transfinito. Tal extensão define uma hierarquia de crescimento rápido. Para fazer isso, as funções geradoras $E_{\alpha }$ tem que ser recursivamente definida por ordinais limitados (observe que eles já eram recursivamente definidos para ordinais sucessores pela relação $E_{\alpha +1}(n)=E_{\alpha }^{n}(2)$). Se existe uma forma padrão de definir a sequencia fundamental $\lambda _{m}$, cujo ordinal limitado é $\lambda$, então a função geradora pode ser definida como $E_{\lambda }(n)=E_{\lambda _{n}}(n)$. Contudo, esta definição depende de um padrão de se definir a sequencia fundamental. Rose (1984) sugere uma forma padrão para todo ordinal α < ε$_0$.
A extensão original foi devido a Martin Löb e Stan S. Wainer (1970) e as vezes é chamada de Löb–Wainer hierarchy.