Ensemble extentionnel - Définition

Pour une énumération des fonctions partielles récursives

Soit une énumération des fonctions partielles récursives. Un ensemble E est dit extentionnel si, à partir du moment que E contient un indice d'une fonction f, il contient tous les indices de f.

Pour un langage de programmation

Un ensemble E est dit extentionnel si, à partir du moment que E contient un programme il contient tous les programmes fonctionnellement égaux à (qui calculent la même fonction que ).

Propriété logique

Un ensemble E est dit extentionnel s'il valide .