Кіріспе

Гудман-Михилл теоремасы конструктивті жиындық теориясында.

Есептеу теориясында Джон Михиллдің есімімен аталатын Михилл изоморфизм теоремасы, жиын үстіндегі есептеу ұғымын бірдей қамтамасыз ететін екі нөмірлеудің сипаттамасын береді.

Анықтамалар

Табиғи сандар жиындары A және B рекурсивті изоморфты деп аталады, егер табиғи сандардағы толық есептелетін биективті функция f болса, онда кез келген үшін .
Табиғи сандар жиыны A, жиын B-ға бірінші рет келуге келтіріледі, егер табиғи сандардағы толық есептелетін инъективті функция f болса, онда және .

Айтылым

Myhill-дің изоморфизм теоремасы екі табиғи сандар жиыны A және B рекурсивті изоморфты екенін, егер және тек қана егер A жиыны B жиынына, ал B жиыны A жиынына бір редукцияланатын болса, айтады.

Қорытындылар

Екі толық нөмірлеу эквивалентті болып саналады, егер және тек қана олар рекурсивті изоморфты болса.

Талқылау

Теорема екі инъективті азайтудың қарама-қарсы бағытта берілген жағдайында, натуралдарда есептеуге болатын биекция бар, ол сұрақ тудырған жиындарды биективті сәйкестікке келтіреді. Бұл жалпы жиындар туралы Шрёдер-Бернштейн теоремасын еске түсіреді, ал Майхилл теоремасы оның конструктивті нұсқасы деп аталады. Дегенмен, олардың дәлелдері әртүрлі. Шрёдер-Бернштейн теоремасының дәлелі екі инъекцияның кері функцияларын пайдаланады, бұл Майхилл теоремасының жағдайында мүмкін емес, себебі бұл кері функциялар рекурсивті болмауы мүмкін. Ал Майхилл теоремасының дәлелі биекцияны индуктивті түрде анықтайды, бұл Шрёдер-Бернштейн теоремасының жағдайында таңдау аксиомасын қолданбаса мүмкін емес (бірақ Майхилл теоремасын дәлелдеу үшін таңдау аксиомасы қажет емес).