Кіріспе

Сансыз жиынтықтардың ой эксперименті

Гилберттың Ұлы қонақ үй парадоксы (көбінесе: Сансыз қонақ үй парадоксы немесе Гилберт қонақ үйі) – сансыз жиынтықтардың күтпеген қасиетін көрсететін ой эксперименті. Толық толып тұрған, шексіз көп бөлмесі бар қонақ үйге қосымша қонақтарды, тіпті шексіз көп қонақтарды да орналастыруға болатыны көрсетіледі, және бұл процесті шексіз рет қайталауға болады. Бұл идеяны Дэвид Гилберт 1925 жылы "Über das Unendliche" атты лекциясында ұсынды, ол кейіннен 1947 жылы Джордж Гамовтың "Бір, екі, үш, шексіз" кітабы арқылы кеңінен танымал болды.

Парадокс

Гильберт 1, 2, 3 және т.б. нөмірленген, жоғарғы шегі жоқ болжамдық қонақ үйді көзге елестетеді. Бұл санаулы шексіз бөлмелер саны деп аталады. Бастапқыда барлық бөлмелер толған, бірақ соған қарамастан, жаңа қонақтар келіп, әрқайсысы жеке бөлме күтеді. Әдеттегі, шектеулі қонақ үй барлық бөлмесі толғанда жаңа қонақтарды қабылдай алмайды. Дегенмен, қазіргі тұрғындар мен жаңа келгендер – тіпті олардың саны шексіз болса да – бәрінің шексіз қонақ үйде жеке бөлмесі болатынын көрсетуге болады.

Жаңа қонақтар санының шегі

Бір қосымша қонақпен, қонақ үй оларды және қазіргі қонақтарды орналастыра алады, егер шексіз көп қонақ бір уақытта бөлмелерді ауыстырса. Қазіргі уақытта 1-бөлмедегі қонақ 2-бөлмеге, 2-бөлмедегі қонақ 3-бөлмеге, және т.с.с. әрбір қонақ өзінің қазіргі бөлмесінен n, n+1-бөлмеге көшеді. Шексіз қонақ үйде соңғы бөлме болмайды, сондықтан әрбір қонақтың баратын бөлмесі табылады. Осыдан кейін 1-бөлме бос болады, және жаңа қонақты сол бөлмеге орналастыруға болады. Осы процедураны қайталау арқылы, кез келген шекті сандағы жаңа қонақтарға орын табу мүмкін. Жалпы алғанда, егер k қонақ бөлме іздесе, қонақ үй сол процедураны қолданып, әрбір қонақты n бөлмеден n+k бөлмеге көшіре алады.

Жаңа қонақтар саны шексіз

Сондай-ақ, санауға болатын шексіз көп жаңа қонақтарды орналастыру мүмкін: жай ғана 1-ші бөлмедегі адамды 2-ші бөлмеге, 2-ші бөлмедегі қонақты 4-ші бөлмеге, ал жалпы, n-ші бөлмедегі қонақты 2n-ші бөлмеге (2-ге көбейтілген n) көшіріңіз, сонда барлық тақ нөмірлі бөлмелер (санауға болатын шексіз) жаңа қонақтарға бос болады.

Әрқайсысында шексіз көп қонақтары бар шексіз көп вагондар

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

Басты қуаттар әдісі

Қонақтарды бір бөлмеден екінші бөлмеге жіберіп, бөлмелерге бірінші вагонның жолаушыларын, бөлмелерге екінші вагонның жолаушыларын орналастырыңыз; жалпы, вагон нөмірі үшін бөлмелерді пайдаланамыз, онда -інші тақ жай сан болады. Бұл шешім кейбір бөлмелерді бос қалдырады (бұл қонақ үй үшін пайдалы болуы мүмкін немесе болмауы мүмкін); атап айтқанда, 15 немесе 847 сияқты жай санның дәрежесі емес барлық сандар енді толықтырылмайды. (Осылайша, нақты айтқанда, бұл келушілер саны бос орындар санынан кем немесе тең екенін көрсетеді. Келушілер саны бос орындар санынан артық немесе тең екенін тәуелсіз түрде көрсету, және осылайша олар тең екенін көрсету, алгоритмді дәл сәйкес келу үшін өзгертуден әлдеқайда оңай.) (Алгоритм егер біріншісін екіншісімен ауыстырсаңыз да, бірдей жұмыс істейді, бірақ қандай таңдау жасалса да, оны тұрақты түрде қолдану қажет.)

Басты факторлау әдісі

Белгілі бір орындық пен вагондағы әрбір адамды бөлмеге орналастыруға болады (қонақүйге келген адамдар үшін c = 0, бірінші вагондағы адамдар үшін 1 және т.б.). Кез келген санның бірегей жай көбейткіштері болғандықтан, барлық адамдардың бөлмесі болады және екі адам бір бөлмеде болмайды. Мысалы, 2592-бөлмедегі адам 4-ші вагондағы 5-ші орындықта отырды. Жай санның дәрежелері әдісі сияқты, бұл шешім кейбір бөлмелерді бос қалдырады. Бұл әдісті шексіз түндерге, шексіз кіреберістерге және т.б. оңай кеңейтуге болады. ()

Жапырақтасу әдісі

Әрбір жолаушы үшін, ондық санау жүйесі сияқты кез келген позициялық санау жүйесінде жазылғандай, вагон мен орын нөмірінің ұзындығын салыстырыңыз. (Қонақ үйдің әр тұрғынын 0-шы вагонның жолаушысы деп есептеңіз.) Егер екі санның біреуі қысқарақ болса, екеуінің де саны бірдей болатынша, оған басында нөлдер қосыңыз. Бөлме нөмірін құру үшін цифрларды кезегімен біріктіріңіз: оның цифрлары [вагон нөмірінің бірінші цифры] [орын нөмірінің бірінші цифры] [вагон нөмірінің екінші цифры] [орын нөмірінің екінші цифры] және т.б. болады. 1729-шы бөлмедегі қонақ 01070209-шы бөлмеге (яғни, 1 070 209-шы бөлмеге) көшеді. 789-шы вагонның 1234-ші орындығындағы жолаушы 01728394-ші бөлмеге (яғни, 1 728 394-ші бөлмеге) барады. Бұл әдіс қонақ үйді толығымен толтырады, және қонақтың бастапқы вагоны мен орын нөмірін кері біріктіру арқылы анықтауға болады. Егер бөлме нөмірінде тақ сан цифр болса, алдымен басына нөл қосыңыз. Содан кейін нөмірді екі санға бөліңіз: вагон нөмірі тақ орындағы цифрлардан, ал орын нөмірі жұп орындағы цифрлардан тұрады. Әрине, бастапқы кодтау шартты, және екі санның рөлі ауыстырылуы мүмкін (орын тақ, вагон жұп), бірақ бұл үнемі сақталуы керек.

Үшбұрышты сан әдісі

Отельде болғандар бөлмеге немесе үшбұрышты санға көшеді. Көліктің ішіндегілер бөлмеге немесе үшбұрышты санға плюс көшеді. Осылайша, барлық бөлмелер бір және бір ғана қонақпен толады. Бұл жұптастыру функциясын қонақ үйді бір бөлмелік тереңдігі бар, шексіз биік пирамида ретінде құру арқылы визуализациялауға болады. Пирамиданың ең жоғарғы қатары бір бөлмеден тұрады: 1-ші бөлме; екінші қатары 2-ші және 3-ші бөлмелерден; және т.с.с. Оң жақтанғы бөлмелер қатары үшбұрышты сандарға сәйкес келеді. Олар толтырылғаннан кейін (қонақ үйдің қайта орналастырылған тұрғындарымен), қалған бос бөлмелер бастапқы пішінге дәл ұқсас пирамида пішінін құрайды. Осылайша, процесті әр шексіз жиын үшін қайталауға болады. Әр көлік үшін бір-бірлеп жасау шексіз көп қадамдарды қажет етеді, бірақ бұрынғы формулаларды қолдану арқылы қонақ өзінің бөлмесінің қандай болатынын анықтап, көлік процесте жеткеннен кейін дереу бара алады.

Өз бетінше санау әдісі

Let есептеуге болатын болса, онда оның элементтерін тізбектеуге болады. Енді, егер , онда -шы автобустың -шы жолаушысын -шы бөлмеге орналастырыңыз (құнақ үйдегі жолаушыларды -шы автобустың жолаушылары деп есептейміз). Осылайша, әрбір адамды бөлмеге тағайындайтын функция бар; сонымен қатар, бұл тағайындама ешқандай бөлмені өткіріп кетпейді.

шексіздің қосымша қабаттары

Мейрамхана мұхит жанына орналасқан делік, онда шексіз көп паромдар келеді, әрқайсысында шексіз көп вагондар, әрқайсысында шексіз көп жолаушы. Бұл шексіздіктің үш "деңгейін" қамтитын жағдай және оны бұрынғы шешімдердің кез келгенінің кеңейтуі арқылы шешуге болады. Басты бөлшектерді бөлу әдісін шексіздіктің әрбір қосымша қабатына ( , пароммен) жаңа жай сан қосу арқылы қолдануға болады. Бастапқы сандарды одан әрі экспоненциалдастыру арқылы, тіпті кішігірім мәндерді ескере отырып, өте үлкен бөлме нөмірлерін алу үшін, бастапқы сандар көбеюімен негізгі қуат шешімін қолдануға болады. Мысалы, екінші паромдағы үшінші автобустың екінші орындығында отырған жолаушы (2 3 2 мекенжайы) екінші тақ жай санны (5) 49-ға көтереді, бұл үшінші тақ жай санны (7) оның орындық нөмірінің (2) дәрежесіне көтерудің нәтижесі. Бұл бөлме нөмірінің ондық саны отыздан асады. Бір-бірімен тоқу әдісін екі емес, үш тоқылған "жіптермен" қолдануға болады. 2 3 2 мекенжайы бар жолаушы 232-ге, ал 4935 198 82217 мекенжайы бар жолаушы #008,402,912,391,587 номеріне барады (алдыңғы нөлдерді алып тастауға болады). Мейманхана шексіз қонақтардың кез келген санды қабаттарын күтіп, қонақтардың ешқайсысына жылжудың қажеті болмайтындай, кейін қанша қонақ келсе де бөлмелерді бөлуді қалауы мүмкін. Бір шешім - әр келушінің мекенжайын екілік санға айналдыру, онда әр қабаттың басында біліктерді ажыратқыштар ретінде қолданады, ал берілген қабаттағы сан (мысалы, қонақтың автобус нөмірі) сол көптеген нөлдермен бейнеленеді. Осылайша, 2 5 1 3 1 (бес шексіз қабат) бұрынғы мекенжайы бар қонақ 10010000010100010 бөлмесіне (ондық 295458) барады. Бұл процесте қосымша қадам ретінде әр бөлімнен бір нөлді алып тастауға болады; Бұл мысалда қонақтың жаңа бөлмесі 101000011001 (ондық 2585). Бұл әрбір бөлмені гипотетикалық қонақпен толтыруға мүмкіндік береді. Егер қонақтардың саны шексіз болмаса, онда тек екінің дәрежесіндегі бөлмелер ғана толтырылады.

Ұя салудың шексіз қабаттары

Кез келген шекті сандағы ішкі шексіздіктерге адамдарды орналастыруға бөлме табу мүмкін болса да, шексіз қабаттар саны үшін мұндай мүмкіндік әрқашан бола бермейді. Тіпті әрбір қабатта шекті санда ғана элемент болған жағдайда да.

Талдау

Гильберттің парадоксы – бұл шындыққа сай келетін парадокс: ол дәлелденген, шындыққа сәйкес келетін интуитивті емес нәтижеге әкеледі. "Әр бөлмеде қонақ бар" және "басқа қонақтарды орналастыру мүмкін емес" деген мәлімдемелер, бөлмелердің саны шексіз болғанда тең емес. Бастапқыда мұндай жағдай интуитивті емес сияқты көрінуі мүмкін. Шексіз жиындардың қасиеттері, шекті жиындардың қасиеттерінен мүлдем өзгеше. Гильберттің "Гранд-отель" парадоксын Кантордың трансфинит сандар теориясын қолдану арқылы түсінуге болады. Демек, бір бөлмеден астам бөлмесі бар кез келген (шекті) қонақ үйде, тақ нөмірлі бөлмелердің саны жалпы бөлмелер санынан әлдеқайда аз болады. Алайда, Гильберттің "Гранд-отеле" тақ нөмірлі бөлмелердің саны жалпы бөлмелердің "санынан" кем емес. Математикалық тұрғыдан алғанда, тақ нөмірлі бөлмелерді қамтитын ішкі жиынның кардиналдығы, барлық бөлмелер жиынының кардиналдығымен бірдей. Шындығында, шексіз жиындар өзінің кардиналдығымен бірдей болатын дұрыс ішкі жиындарға ие ретінде сипатталады. Саналатын жиындар үшін (табиғи сандармен бірдей кардиналдылығы бар жиындар) бұл кардиналдылық мынадайша қайта айтылады: кез келген саналатын шексіз жиын үшін, осы саналатын шексіз жиынды табиғи сандар жиынына бейнелейтін биективті функция бар, тіпті егер саналатын шексіз жиынға табиғи сандар кірсе де. Мысалы, рационал сандар жиыны – бүтін сандардың бөлігі ретінде жазыла алатын сандар – табиғи сандарды ішкі жиын ретінде қамтиды, бірақ рационал сандар саналатындықтан табиғи сандар жиынынан үлкен емес: табиғи сандардан рационал сандарға биекция бар.