Подскуп -{''-{S''}-'' скупа [[природан број|природних бројева]] се назива '''рекурзивним''' ако постоји [[тотална функција|тотална]] [[израчунљива функција]] <math>f\,</math> таква да је
<math>f(x) = 1\,</math> ако <math>x \in S</math> а <math>f(x) = 0\,</math> ако <math>x \notin S</math>. Другим речима, скуп -{''-{S''}-'' је рекурзиван [[ако и само ако]] је [[функција индикатор]] <math>1_{S}\,</math> [[израчунљива функција|израчунљива]].
== Примери ==
Ред 16:
== Својства ==
Ако је -{''-{A''}-'' рекурзиван скуп, онда је и његов [[комплемент (теорија скупова)|комплемент]] рекурзиван скуп. Ако су -{''-{A''}-'' и -{''-{B''}-'' рекурзивни скупови, онда су и ''-{''A}-''}- ∩ -{''-{B''}-'', -{''-{A'' ∪ ''B}-''}- и слика од -{''-{A'' × ''B''}-'' по [[Канторова функција упаривања|Канторовом упаривању]], рекурзивни скупови.
Скуп ''-{''A''}-'' је рекурзиван скуп [[ако и само ако]] су и -{''-{A''}-'' и његов [[комплемент (теорија скупова)|комплемент]] [[рекурзивно пребројив скуп|рекурзивно пребројиви скупови]]. Оригинал<!-- preimage --> рекурзивног скупа у односу на [[тотална функција|тоталну]] [[израчунљива функција|израчунљиву функцију]] је рекурзиван скуп. Слика израчунљивог скупа у односу на тоталну израчунљиву [[бијекцију]] је израчунљива.
Скуп је рекурзиван ако и само ако је на нивоу <math>\Delta^0_1</math> [[аритметичка хијерархија|аритметичке хијерархије]].
