Кіріспе

Жинақтағы элементтердің реттелген тізімі

Тізімдеу – бұл жиындағы барлық элементтердің толық, реттелген тізімі. Бұл термин математика мен компьютерлік ғылымда жиынның барлық элементтерін тізімдеу үшін қолданылады. Тізімдеудің нақты талаптары (мысалы, жиын шекті болуы керек пе, немесе тізімде қайталаулар болуы мүмкін бе) зерттеу саласы мен нақты мәселенің контекстіне байланысты. Кейбір жиындарды табиғи рет бойынша тізімдеуге болады (мысалы, оң бүтін сандар жиыны үшін 1, 2, 3, 4), бірақ басқа жағдайларда реттілік белгілеу қажет болуы мүмкін (бәлкім, кездейсоқ). Кейбір контекстерде, мысалы, санау комбинаторикасында, тізімдеу термині көбінесе санау мағынасында қолданылады – жиынның қанша элементтен тұратынын анықтауға, одан гөрі олардың нақты тізімін жасауға көбірек назар аударылады.

Комбинаторлық

Комбинаторикада санау – бұл санау, яғни шекті жиындардың элементтерінің нақты санын анықтау, көбінесе шексіз отбасыларға біріктіріледі, мысалы, әрқайсысы белгілі бір шекті жиынның барлық мүмкін орналасуларынан (пермутацияларынан) тұратын жиындар отбасы. Математиканың көптеген салаларында нақты түрдегі объектілерді осы мағынада санаумен айналысатын қарқынды дамып жатқан салалар бар. Мысалы, бөлулерді санау және графтарды санауда мақсат – белгілі бір шарттарға сай келетін бөлулерді немесе графтарды есептеу болып табылады.

Жинақ теориясы

Жинақтар теориясында, тізімдеу ұғымы кеңірек мағынаға ие, және тізімделетін жиынның шекті болуын қажет етпейді.

Тізімге енгізу

Тізбелі тізімде санау қолданылғанда, біз индекс жиынтығына белгілі бір реттелу құрылымын қоямыз. Реттелу талаптарын өте бос етіп, жоғары деңгейде жалпыламалыққа мүмкіндік беруге болады, бірақ ең табиғи және жиі кездесетін алғышарт – индекс жиынтығының жақсы реттелген болуы. Осы сипаттама бойынша, реттелген санау – жақсы реттелген домені бар сюръекция (үстінен қатынас) ретінде анықталады. Бұл анықтаманың табиғи болуының себебі, индекс жиынтығындағы жақсы реттелу, ішінара санау берілген жағдайда келесі элементті тізімдеудің бірегей жолын қамтамасыз етеді.

Санауға болатын және санауға болмайтын

Егер басқаша көрсетілмесе, санау табиғи сандар арқылы жасалады. Яғни, S жиынының санауы – табиғи сандардан немесе табиғи сандардың бастапқы кесіндісінен S жиынына біржақты сәйкестік. Егер жиынды санауға болатын болса, яғни оның санауы болса, онда ол санаулы болады. Әйтпесе, ол санауға келмейтін болады. Мысалы, нақты сандар жиыны санауға келмейтін жиын. Жиын шекті болады, егер оны табиғи сандардың дұрыс бастапқы кесіндісі арқылы санауға болатын болса, онда оның кардиналдығы n-ге тең болады. Бос жиын шекті, себебі оны табиғи сандардың бос бастапқы кесіндісі арқылы санауға болады. "Жиын" термині кейде санаулы жиындар үшін қолданылады. Дегенмен, ол көбінесе есептеуге болатын жиындар үшін де қолданылады, яғни санау функциясы алгоритм арқылы есептелетін санаулы жиындар. Шекті және санаулы шексіз жиындарды ажырату үшін, көбінесе басқа, эквивалентті анықтама қолдану пайдалы: S жиыны санаулы болады, егер және тек қана одан табиғи сандарға инъекциялық функция болса.

Қасиеттері

Жинақтың (осы мағынада) санамасы бар, егер және тек егер жиын санаулы болса. Егер жиын санаулы болса, бос жиынның немесе (нақты анықтамасына байланысты) бір элементі бар жиынның дегенеративті жағдайларын қоспағанда, әртүрлі санамалардың санаусыз шексіз саны болады. Дегенмен, егер санамалар инъективті болуын қажет етсек және егер f(n) анықталған болса, онда f(m) барлық m < n үшін анықталған болуы керек, онда N элементтен тұратын шекті жиынның дәл N! санамасы болады. Жиынның S санамасы e, домені жинақтың өзінде жақсы рет ≤ құрады, егер және тек егер s ≤ t болса. Бұл рет жиынның өзімен байланысы аз болғанымен, жиынның белгілі бір реті қажет болғанда пайдалы болады.

Ординалдар

Жинақтар теориясында, тізімдеу функциясының домені табиғи сандардың бастапқы сегменті болуын талап ететін сипаттамадан гөрі, санаудың көбірек жалпы түсінігі бар, мұнда тізімдеу функциясының домені кез келген ординалды қабылдауы мүмкін. Осы анықтама бойынша, S жиынының санауы – S-ке ординал α-дан кез келген сюръекцияны білдіреді. Бұрын айтылған санаудың шектеулі нұсқасы – α шекті ординал немесе бірінші шекті ординал ω болғандағы ерекше жағдай. Бұл жалпыланған нұсқа жоғарыда аталған анықтаманы трансфинитті тізімдерді қамтуға кеңейтеді. Осы анықтама бойынша, бірінші санауға келмейтін ординалды сәйкестік функциясы арқылы санауға болады, сондықтан бұл екі ұғым сәйкес келмейді. Жалпы алғанда, ZF теоремасы бойынша, кез келген жақсы реттелген жиын осы сипаттама бойынша санауға болады, сондықтан ол жалпыланған тізімдеу санауымен қайта белгіленгенде сәйкес келеді. Егер таңдау аксиомасын да қабылдасақ, онда барлық жиындарды қайта белгіленгенде санауға болады, бұл санаудың ең жалпы түрімен сәйкес келеді. Жинақтар теориясымен айналысатын математиктер кездейсоқ үлкен кардиналдықтардың шексіз жиындарымен жұмыс істейтіндіктен, олардың арасында жиынды санаудың әдепкі анықтамасы – оның барлық элементтерін дәл тізімдейтін кез келген α тізбегі болып табылады. Шындығында, жинақтар теориясының кең таралған анықтамалығы болып табылатын Jech кітабында санау осылай анықталған. Сондықтан, түсініксіздіктен сақтану үшін, санаудың сәйкес типтерін белгілеу үшін «шекті санауға болатын» немесе «санауға болатын» терминдерін қолдануға болады.

Кардинальдықтарды салыстыру

Формальды түрде, S жиынтығын санаудың ең толық анықтамасы – кез келген индекстік жиын I-ден S жиынтығына кез келген сюръекция. Бұл кең мағынада, кез келген S жиынтығын S-ден өзіне сәйкестік функциясы арқылы тривиальды түрде санауға болады. Егер таңдау аксиомасын немесе оның вариациясын қабылдамаса, S жиынтығының жақсы реттелуі міндетті емес. Таңдау аксиомасы қабылданған жағдайда да, S жиынтығының табиғи жақсы реттелуі міндетті емес. Осылайша, бұл жалпы анықтама санау ұғымына жарайды, онда біз "қанша" санына қызығамыз, "қандай ретпен" емес. Іс жүзінде, санаудың бұл кең мағынасы әртүрлі жиынтықтардың салыстырмалы өлшемдерін немесе кардиналдықтарын салыстыру үшін жиі қолданылады. Егер Зермело-Франкель жиындар теориясында таңдау аксиомасы қолданылмаса, санаудың инъективті болуы (қайталанбауы) қажеттігін қосымша талап етуге болады, себебі бұл теорияда I-ден S-ке сюръекцияның болуы S-тен I-ге инъекцияның болуын қамтамасыз етпейді.

Есептеуге қабілеттілік және күрделілік теориясы

Есептеу теориясында көбінесе саналатын санаулар, барлық табиғи сандар жиынынан саналған жиынға сәйкестендіру есептелуі керек деген қосымша талаппен қарастырылады. Саналатын жиын рекурсивті саналатын (немесе қазіргі заманғы тілмен есептелетін) деп аталады, бұл рекурсия теориясының картаның есептелуі дегенімізді формалдау үшін қолданылуын көрсетеді. Осы мағынада, табиғи сандардың ішкі жиыны егер ол есептелетін функцияның мәндер жиыны болса, есептелетін түрде саналады. Осы контексте, "саналатын" дегені "есептелетін түрде саналатын" дегенді білдіруі мүмкін. Алайда, бұл анықтамалар әртүрлі класстарды сипаттайды, себебі ω доменіндегі кез келген функциямен саналатын, бірақ тек саналатын көптеген есептелетін функциялар бар. Санауға ие, бірақ есептелетін санауға ие емес жиынның нақты мысалы – тоқтау жиынының толықтығы. Бұдан әрі, бұл сипаттама тізімнің реті маңызды екенін көрсетеді. Тоқтау жиынының есептелетін санауы бар, бірақ элементтерді өсу ретімен тізімдейтін санау жоқ. Егер мұндай санау болғанда, тоқтау жиыны шешілетін болар еді, бұл дәлелмен жалған. Жалпы, рекурсивті саналатын болу, шешілетін жиын болудан әлсіз шарт. Санау ұғымы санау алгоритмдері контекстінде әртүрлі міндеттер үшін есептеу күрделілігі теориясының тұрғысынан да зерттелді.