Шешілмейтін математикалық теоремалар

Кіріспе

Математикалық дәлелдеу санаты

Математикада мүмкін емес теорема – мәселені немесе мәселелердің жалпы жиынтығын шешуге болмайтын теорема. Бұлар мүмкін еместікті дәлелдеу, теріс дәлелдеу немесе теріс нәтиже деп те аталады. Мүмкінсіздік теоремалары шешімнің жоқтығын дәлелдеу арқылы, шешім іздеуге жұмсалған ондаған немесе ғасырлар бойығы жұмысты жиі аяқтайды. Бір нәрсенің мүмкін еместігін дәлелдеу, әдетте, кері тапсырмаға қарағанда әлдеқайда қиын, себебі тек нақты бір мысалды көрсетуден гөрі, жалпы жағдайда жұмыс істейтін дәлелді жасау қажет. Мүмкінсіздік теоремалары логикада теріс экзистенциалдық немесе әмбебап тұжырымдар түрінде көрініс береді. 2-нің квадрат түбірінің иррационалдығы – мүмкін еместіктің ең ерте дәлелдерінің бірі. Ол 2-нің квадрат түбірін екі бүтін санның қатынасы ретінде көрсету мүмкін емес екенін көрсетеді. Мүмкін еместіктің тағы бір маңызды дәлелі – 1882 жылы Фердинанд фон Линдеман жасаған дәлел, ол шеңберді шаршылау мәселесін шеше алмайтынын көрсетті, себебі π саны трансценденттік (яғни, алгебралық емес), және компас пен сызғыш арқылы алгебралық сандардың ғана бір бөлігін құруға болады. 19 ғасырда басқа екі классикалық мәселе – жалпы бұрышты үш бөлікке бөлу және кубты екі еселеу де мүмкін емес екені дәлелденді, және осы мәселелердің барлығы күрделі математикалық құрылымдарды зерттеуге түрткіс болды. 20 ғасырда табылган мүмкін еместіктің ең маңызды дәлелдерінің бірі – шешілмейтін мәселелерге қатысты болды, ол кез келген алгоритммен жалпы шешілмейтін мәселелердің бар екенін көрсетті, олардың ең танымалдарының бірі – тоқтату мәселесі. Гёдельдің толық емес теоремалары формальды жүйелердің дәлелдеу мүмкіндігінің негізгі шектеулерін ашқан тағы бір мысал болды. Есептеу күрделілігі теориясында релятивизация (оракул қосу) сияқты әдістер мүмкін еместіктің «әлсіз» дәлелдемелерін жасауға мүмкіндік береді, себебі релятивизацияға тәуелсіз дәлелдеу әдістері P және NP мәселесін шеше алмайды. Тағы бір әдіс – күрделілік класы үшін толықтығын дәлелдеу, ол кластағы кез келген басқа мәселені шешумен салыстырылатын қиындық деңгейін көрсетеді, соның арқасында мәселелердің қиындығын дәлелдеуге болады. Атап айтқанда, егер кластағы мәселелердің бірі шешілмейтін болса, толық мәселе де шешілмейтін болады.

In mathematics, an impossibility theorem is a theorem that demonstrates a problem or general set of problems cannot be solved. These are also known as proofs of impossibility, negative proofs, or negative results. Impossibility theorems often resolve decades or centuries of work spent looking for a solution by proving there is no solution. Proving that something is impossible is usually much harder than the opposite task, as it is often necessary to develop a proof that works in general, rather than to just show a particular example. Impossibility theorems are usually expressible as negative existential propositions or universal propositions in logic. The irrationality of the square root of 2 is one of the oldest proofs of impossibility. It shows that it is impossible to express the square root of 2 as a ratio of two integers. Another consequential proof of impossibility was Ferdinand von Lindemann's proof in 1882, which showed that the problem of squaring the circle cannot be solved because the number [[Pi is transcendental (i. e., non algebraic), and that only a subset of the algebraic numbers can be constructed by compass and straightedge. Two other classical problems—trisecting the general angle and doubling the cube—were also proved impossible in the 19th century, and all of these problems gave rise to research into more complicated mathematical structures. Some of the most important proofs of impossibility found in the 20th century were those related to undecidability, which showed that there are problems that cannot be solved in general by any algorithm, with one of the more prominent ones being the halting problem. Gödel's incompleteness theorems were other examples that uncovered fundamental limitations in the provability of formal systems. In computational complexity theory, techniques like relativization (the addition of an oracle) allow for "weak" proofs of impossibility, in that proofs techniques that are not affected by relativization cannot resolve the P versus NP problem. Another technique is the proof of completeness for a complexity class, which provides evidence for the difficulty of problems by showing them to be just as hard to solve as any other problem in the class. In particular, a complete problem is intractable if one of the problems in its class is.

Қайшылық

Қарсылықпен дәлелдеу – мүмкінсіздікті дәлелдеудің кеңінен қолданылатын түрлерінің бірі. Осы дәлелдеу түрінде, егер белгілі бір теңдеулер тобының шешімі сияқты бір ұсыныс дұрыс деп есептелсе, логикалық қорытынды арқылы екі бір-біріне қайшы нәрсе дұрыс екені көрсетіледі, мысалы, бір санның жұп тақ болуы немесе теріс, оң болуы. Қарсылық бастапқы болжамнан туындағандықтан, ондағы бастапқы ұсыныс дұрыс болмайды дегенді білдіреді. Ал, мүмкін емес екенін конструктивсіз дәлелдеу үшін барлық мүмкін қарсы мысалдардың бұрыс екендігі логикалық тұрғыдан дәлелденеді: мүмкін қарсы мысалдар тізіміндегі кем дегенде біреуі, сол мүмкін емес екенін айтуға қарсы мысал болуы керек. Мысалы, иррационал санның иррационал санға көтерілген дәрежесінің рационал сан болуы мүмкін емес деген пікір, екі мүмкін қарсы мысалдың бірінің дұрыс екенін көрсету арқылы жоққа шығарылды, бірақ олардың қайсысы екені көрсетілген жоқ.

Ұрпағы бойынша

Қарама-қайшылық арқылы дәлелдеудің тағы бір түрі – түсіру арқылы дәлелдеу, ол алдымен бірдеңе мүмкін деп есептейді, мысалы, теңдеулер тобының оң бүтін сан шешімі, демек, ең кішкентай шешім болуы тиіс (Жақсы реттелу принципі бойынша). Содан кейін, осы деп есептелген ең кішкентай шешімнен, одан да кішкентай шешім табуға болатыны көрсетіледі, бұл бастапқы болжамға – бұл шешімнің ең кішкентай екендігіне қайшы келеді, соның салдарынан шешімнің бар екендігі туралы бастапқы есептеудің жалған екендігі дәлелденеді.

Қарсы мысал

Мүмкін емес болжамның жалған екендігін дәлелдеудің ең оңай жолы – бір ғана қарсы мысал келтіру. Мысалы, Эйлер бір n-ші дәрежелі санды алу үшін кем дегенде n түрлі n-ші дәрежелі сандардың қосылуы қажет деп ұсынған. Алайда, бұл болжам 1966 жылы бір қарсы мысалмен жоққа шығарылды: төрт түрлі бесінші дәрежелі санның қосындысы тағы бір бесінші дәрежелі санға тең болды: 275 + 845 + 1105 + 1335 = 1445. Қарсы мысалмен дәлелдеу – бұл конструктивті дәлелдеудің бір түрі, себебі дәлелдемеге қайшы келетін нақты мысал көрсетіледі.

Жебе теоремасы: Рационалды реттік таңдау дауыс беруі

Әлеуметтік таңдау теориясында Ароудың мүмкін еместік теоремасы диктаторлық емес және рационалды мінез-құлықтың «байланыссыз баламалардың тәуелсіздігі» деп аталатын негізгі қағидасын қанағаттандыратын реттік дауыс беру жүйесін құрудың мүмкін емес екенін көрсетеді.

Гиббард теоремасы: Диктаторлық емес стратегиялық ойындар

Гиббард теоремасы екіден астам нәтижеге ие кез келген стратегияға төзімді ойын формасының (яғни үстемдік стратегиясы бар) диктаторлық екенін көрсетеді. Гиббард-Саттертуэйт теоремасы – ешбір детерминистік дауыс беру жүйесінің, басқалардың қалай дауыс бергеніне қарамастан, барлық жағдайларда стратегиялық дауыс беруден толығымен қорғала алмайтынын көрсететін арнайы жағдай.

Ашылу принципі: Адал емес шешімдер

Аян принципін Гиббард теоремасының «керісін» көрсететін мүмкін еместік теоремасы деп қарастыруға болады: кез келген ойын немесе дауыс беру жүйесі стратегияны механизмге енгізу арқылы стратегияға қарсы тұруға бейімделуі мүмкін. Осылайша, ашық айту механизмінен жақсырақ шешімге қол жеткізе алмайтын механизмді құру мүмкін емес.

Мт түбірін рационалды түрде көрсету

500 ж.б. шамасында Пифагордың дәлелі математикаға терең әсер етті. Ол 2-нің квадрат түбірін екі бүтін санның қатынасы түрінде көрсетуге болмайтынын көрсетеді. Дәлел "сандарды" екі өзара жат жиынға – рационалды сандар мен иррационалды сандарға бөлді. Платонның «Теетет» атты еңбегінде Теодордың (Платонның ұстазы) 17 шаршы футтың квадрат түбіріне дейінгі барлық жеке жағдайларды иррационалды екенін дәлелдегені туралы белгілі бір мәтін бар. Көбірек жалпылама дәлел, егер N бүтін санның m-дәрежесі болмаса, N бүтін санының m-дәрежелі түбірі иррационалды екенін көрсетеді. Яғни, N бүтін санының m-дәрежелі түбірін екі бүтін санның a/b қатынасы ретінде көрсету мүмкін емес, егер a мен b ортақ жай көбейткішке ие болмаса, b=1 болған жағдайларды қоспағанда.

Тең жақты n-колонн құрастыру

Гаусс-Вантцель теоремасы 1837 жылы n-нің көптеген мәндері үшін теңқабырлы n-бұрыш салудың мүмкін еместігін дәлелдеді.

Евклидтің параллельдік постулатын анықтау

Евклидтің "Элементтер" еңбегіндегі параллельдік постулат – берілген түзу сызық пен осы сызықта жатпайтын нүкте үшін, осы нүкте арқылы сол түзуге параллель тек бір түзу жүргізуге болады деген тұжырымға тең. Басқа постулаттардан өзгеше, бұл постулатты өзінен-өзі түсінікті емес деп санады. Нагель мен Ньюман бұл постулаттың кеңістіктің "шексіз алыс" аймақтарына қатысты болуы мүмкін дейді; атап айтқанда, параллель түзулер асимптоталар сияқты емес, тіпті "шексіздікте" де қиылыспайды деп анықталады. Осылайша, өзінен-өзі дәлелдеудің жеткіліксіздігінен, бұл постулатты басқа Эвклид аксиомалары мен постулаттарынан шығаруға бола ма деген сұрақ туды. Тек XIX ғасырда Гаусс, Болай, Лобачевский және Риманның еңбектерінде ғана параллельдік постулатты басқалардан логикалық түрде шығару мүмкін емес екені көрсетілді. Бұл жұмыстар сонымен қатар параллельдік постулатты Евклидтік емес геометрияға алып келетін баламалармен алмастыруға болатынын көрсетті. Нагель мен Ньюман параллельдік постулаттың тудырған мәселені "кейінгі математикалық тарихқа оның ұзақ мерзімді әсері тұрғысынан алғанда, бәлкім ең маңызды жаңалық" деп есептейді.

Фермат үштігінің мүмкін еместігі

Ферманың соңғы теоремасы Пьер де Ферманың 1600 жылдардағы болжамы, оған сәйкес оң бүтін сандардағы xⁿ + yⁿ = zⁿ теңдеуіне шешім табу мүмкін емес. Ферма өзі шексіз түсу әдісін қолданып, n = 4 жағдайы үшін дәлел келтірді, ал кейін басқа арнайы жағдайлар да дәлелденді, бірақ жалпы жағдайды 1994 жылға дейін Эндрю Уайлс дәлелдемеді.

Диофантилік теңдеулердің бүтін сандық шешімдері: Хилберттің оныншы мәселесі

"Кез келген доғарылған Диофанти теңдеуінің бүтін сан шешімі бар ма?" деген сұрақ шешілмейді. Яғни, барлық жағдайлар үшін сұраққа жауап беру мүмкін емес. Францен Хилберттің оныншы мәселесін және МРДП теоремасын (Матиасевич, Робинсон, Дэвис, Путнам теоремасы) таныстырады, ол "Диофанти теңдеуінің шешімі бар ма, жоқ па, оны анықтай алатын алгоритм жоқ" деп мәлімдейді. МРДП Тьюрингтің шешілмейтіндігін дәлелдеуін пайдаланады: "шешілетін Диофанти теңдеулер жиыны – есептеу арқылы санауға болатын, бірақ шешілмейтін жиынға мысал, ал шешілмейтін Диофанти теңдеулер жиыны есептеу арқылы санауға болмайтын жиын".

Ричард парадоксы

Бұл терең парадокс 1905 жылы Жюль Ричард ұсынған болатын және Курт Гёдель мен Алан Тьюрингтің жұмысына әсер етті. "Математикалық принциптерде" оның қысқаша анықтамасы бар: Курт Гёдель өзінің дәлелін Ричардтың парадоксына ұқсас деп санады, оны ол "Ричардтың антиномиясы" деп атады. Алан Тьюринг осы парадоксты машина арқылы құрастырып, оның қарапайым сұраққа жауап бере алмайтынын дәлелдеді: бұл машина кез келген машинаның (өзінің ішінде) нәтижесіз, шексіз циклге түсіп қалуын анықтай ала ма (яғни, ол диагональдік санды есептеуді тоқтатып қоя ма?).

Табиғи ғылымдар

Табиғи ғылымда мүмкін емес теоремалар математикалық нәтижелер ретінде, жақсы орныққан ғылыми теориялар шеңберінде дәлелденеді. Осы мықты қабылдаудың негізі – бір нәрсе болмауына қатысты мол дәлелдердің жиынтығы, сонымен қатар, өте сәтті болжамдар жасайтын және оның негізгі қағидалары логикалық тұрғыдан бір нәрсенің мүмкін емес екеніне алып келетін теориямен байланысты. Физикада кеңінен қабылданған мүмкін емес жағдайлардың екі мысалы – энергияның сақталу заңына қайшы келетін мәңгілік қозғалыс машиналары және арнайы салыстырмалылық теориясының салдарларын бұзатын жарық жылдамдығынан асу. Тағы бірі – кванттық механиканың белгісіздік принципі, ол бір бөлшектің орнын және импульсін бір уақытта анықтау мүмкін емес екенін көрсетеді. Сондай-ақ, Белл теоремасы бар: жергілікті жасырын айнымалылардың ешбір физикалық теориясы кванттық механиканың барлық болжамдарын қайта жасай алмайды. Табиғи ғылымдағы мүмкін еместік туралы мәлімдеме ешқашан толыққанды дәлелденбесе де, оны бір қарсы мысалдың табылуымен жоққа шығаруға болады. Мұндай қарсы мысал, мүмкін еместік туралы теорияны негіздеген қағидаларды қайта қарастыруды қажет етеді.