Zbiór rekurencyjny

Zbiór rekurencyjny – podzbiór $X\subseteq \mathbb {N}$ (zbioru liczb naturalnych) dla którego można skonstruować algorytm, który w skończonym czasie rozstrzyga czy dana liczba należy do zbioru czy też nie. Inne nazwy tego pojęcia to zbiór obliczalny oraz zbiór rozstrzygalny.

Własność ogólniejsza (słabsza) to bycie zbiorem rekurencyjnie przeliczalnym.

Definicje

• Zbiór $X\subseteq \mathbb {N}$ jest zbiorem rekurencyjnym, jeśli istnieje funkcja rekurencyjna $f\colon \mathbb {N} \longrightarrow \mathbb {N}$ taka, że dla każdego $n\in \mathbb {N}$

$f(n)=0$ wtedy i tylko wtedy, gdy $n\in X$

• Zbiór $X\subseteq \mathbb {N}$ jest zbiorem rekurencyjnie przeliczalnym, jeśli istnieje funkcja rekurencyjna $f\colon \mathbb {N} \longrightarrow \mathbb {N}$ taka, że $X=\{f(n)\colon n\in \mathbb {N} \}.$

Przykłady

Następujące zbiory są rekurencyjne:

• zbiór pusty
• zbiór liczb naturalnych $\mathbb {N}$
• każdy skończony podzbiór $\mathbb {N}$
• zbiór liczb pierwszych

Podstawowe własności

• Każdy zbiór rekurencyjny jest też zbiorem rekurencyjnie przeliczalnym.
• Nieskończony zbiór rekurencyjnie przeliczalny musi zawierać nieskończony podzbiór rekurencyjny.
• Istnieją zbiory rekurencyjnie przeliczalne które nie są rekurencyjne.
• Zbiór $X\subseteq {\mathbb {N} }$ jest rekurencyjny wtedy i tylko wtedy, gdy zarówno $X,$ jak i $\mathbb {N} \setminus X$ są rekurencyjnie przeliczalne.
• Jeśli zbiory $X,Y\subseteq \mathbb {N}$ są rekurencyjne, to także zbiory $X\cap Y,X\cup Y$ oraz $\mathbb {N} \setminus X$ są rekurencyjne.