Կանտորի անկյունագծային փաստարկ

Անհաշվելի բազմությունների գոյության համար Կանտորի անկյունագծային փաստարկի պատկերազարդում (2-ական հիմքով)։ Ներքևում պատկերված $s$-ը ըստ կառուցման չի կարող թվարկման անդամ լինել։

Բազմությունների տեսության մեջ Կանտորի անկյունագծային փաստարկը, որը նաև անվանվում է անկյունագծային փաստարկ, անկյունագծային կտրվածքի փաստարկ, հակաանկյունագծային փաստարկ, անկյունագծային մեթոդ և Կանտորի անկյունագծման ապացույց, բնական թվերի բազմության հետ փոխմիարժեք համապատասխանություն չունեցող անսահման բազմությունների գոյության փաստը ցույց տվող մաթեմատիկական ապացույց է։ Այն հրատարակել է Գեորգ Կանտորը 1891 թվականին։ Նման բազմությունները հայտնի են որպես անհաշվելի բազմություններ, և Կանտորի հիմնադրած կարդինալ թվերի տեսությունը ուսումնասիրում է նման բազմությունների հզորությունը։

Անկյունածային փաստարկը իրական թվերի բազմության անհաշվելիության Կանտորի առաջին ապացույցը չէր, որը հայտնվել էր դեռ 1874 թվականին։ Սակայն այն ընդհանուր մեթոդ է նկարագրում, որը բազմաթիվ ապացույցներում է օգտագործվել, ներառյալ Գյոդելի ոչ-ամբողջականության թեորեմներից առաջինն ու Թյուրինգի պատասխանը գերմ.՝ Entscheidungsproblem` որոշման խնդրին։ Անկյունագծային փաստարկը հաճախ են օգտագործում նաև Ռասելի կամ Ռիշարի պարադոքսի նման հակասություններ ստանալու համար։

Անհաշվելի բազմություններ

Կանտորը դիտարկել է բիթերի անսահման բոլոր հաջորդականությունների $T$ բազմությունը։ Նա սկսում է հետևյալ լեմմայի կառուցողական ապացույցով․

Եթե $s_{1},s_{2},\dots s_{n}\dots$ հաջորդականությունը $T$ բազմության անդամների թվարկումն է, հնարավոր է մի այնպիսի $s$ կառուցել, որը թվարկման որևէ $s_{i}$-ին չի համապատասխանի։

Ապացույցը սկսվում է $T$-ի անդամների թվարկմամբ։ Օրինակ․

$s_{1}=({\mathbf {0}},0,0,0,0,0,0,\dots )$

$s_{2}=(1,{\mathbf {1}},1,1,1,1,1,\dots )$

$s_{3}=(0,1,{\mathbf {0}},1,0,1,0,\dots )$

$s_{4}=(1,0,1,{\mathbf {0}},1,0,1,\dots )$

$s_{5}=(1,1,0,1,{\mathbf {0}},1,1,\dots )$

$s_{6}=(0,0,1,1,0,{\mathbf {1}},1,\dots )$

$s_{7}=(1,0,0,0,1,0,{\mathbf {0}},\dots )$

...

Հաջորդիվ, կառուցվում է նոր $s$ հաջորդականություն հետևյալ տրամաբանությամբ․ եթե $s_{i}$-ի $i$-երորդ նիշը $0$ է, ապա $s$-ի $i$-երորդ նիշը կլինի $1$, և հակառակը։ Այսպիսով, $s$-ի նիշերը կոմպլիմենտար են համապատասխան $s_{i}$-ի նիշերին։

Օրինակ, վերևում ներկայացված թվարկման համար $s$-ը կլինի $(1,0,1,1,1,0,1,\dots )$ : Ըստ կառուցման, $s$-ը $T$ բազմության անդամ է, բայց տարբերվում է յուրաքանչյուր $s_{i}\in T$, քանի որ $s$-ի $i$-երորդ նիշը երաշխավորված տարբերվում է $s_{i}$-ի $i$-երորդ նիշից։ Հետևաբար $s$-ը չի կարող թվարկման անդամ լինել։

Այս լեմմայի վրա հիմնվելով, Կանտորը, ըստ հակասության ապացույց օգտագործելով, ցույց է տալիս, որ

$T$ բազմությունը անհաշվելի է։

Ապացույցը սկսում է $T$ բազմության հաշվելի լինելու ենթադրությունից։ Եթե բազմությունը հաշվելի է, իր բոլոր անդամները կարելի է թվարկել ինչ-որ $s_{1},s_{2},\dots s_{n}\dots$ թվարկությամբ։ Լեմման կիրառելով կարող ենք կառուցել $s$ հաջորդականություն, որը $T$ բազմության անդամ է, բայց բացակայում է թվարկությունից։ Սակայն, եթե $T$-ն թվարկված հաշվելի բազմություն է, թվարկությունը պետք է ներառի իր յուրաքանչյուր անդամը, ներառյալ նոր կառուցած $s$-ը։ Այս հակասությունը նշանակում է, որ ելակետային ենթադրությունը սխալ էր, ու հետևաբար $T$-ն անհաշվելի է։

Իրական թվեր

Իրական թվերի անհաշվելիությունը արդեն հաստատված էր անհաշվելիության Կանտորի առաջին ապացույցով, բայց այն նաև հետևում է վերևում նկարագրված արդյունքից։ Սա ապացուցելու համար բավական է անվերջ երկուական շարանների $T$ բազմությունից իրական թվերի $\mathbb {R}$ բազմություն ինեկտիվ ֆունկցիա կառուցել։ Քանի որ ցույց ենք տվել, որ $T$-ն անհաշվելի է, իր պատկերի՝ $\mathbb {R}$֊ի ենթաբազմության, անհաշվելիությունը կհետևի։ Եթե $\mathbb {R}$-ն ունի անհաշվելի ենթաբազմության, ապա ինքնին $\mathbb {R}$-ը անհաշվելի է։

Ավելին, Կանտորի ստեղծած կառուցման մեթոդն օգտագործելով, կարող ենք $T\rightarrow \mathbb {R}$ բիեկցիա կառուցել, որից կհետևի, որ $T$ և $\mathbb {R}$ բազմությունները նույն հզորությունն ունեն։ Այս հզորությունը կոչվում է «կոնտինուումի հզորություն», և նշանակվում է որպես ${\mathfrak {c}}$ կամ $2^{\aleph _{0}}$։

$tan(x)$ շոշափողի ֆունկցիան $(-{\dfrac {\pi }{2}},{\dfrac {\pi }{2}})\rightarrow \mathbb {R}$ միջակայքերում

$h(x)$ ֆունկցիան $(0,1)\rightarrow (-{\dfrac {\pi }{2}},{\dfrac {\pi }{2}})$ միջակայքերում

$T\rightarrow \mathbb {R}$ ինեկցիա կարելի է սահմանել $T$-ի երկուական շարաններից տասնորդական թվերի քարտեզագրմամբ։ Օրինակ, $t=0111\dots \in T$ կհամընկնի $r=0.0111\dots \in \mathbb {R}$ տասնորդականին։ Այս ֆունկցիան՝ սահմանված $f(t)=0.t$ բանաձևով, ինեկցիա է, քանի որ այն երաշխավորում է, որ տարբեր շարաններ տարբեր թվերի կքարտեզագրվեն․ $\forall t_{i}\neq t_{j}\implies f(t_{i})\neq f(t_{j})$։

$T$ և $R$ բազմությունների միջև բիեկցիա կառուցելը մի քիչ ավեի բարդ է։ $0111\dots$ շարանը $0.0111\dots$ տասնորդական կոտորակի քարտեզագրելու փոխարեն, այն կարելի է քարտեզագրել $b$ հիմքով $0.0111\dots _{b}$ թվին։ Սա հանգեցնում է ֆունկցիաների ընտանիքի․ $f_{b}(t)=0.t_{b}$։ $f_{2}(t)$-ից բացի բոլոր $f_{b}(t)$ ֆունկցիաները ինեկցիաներ են։ Այս ֆունկցիան կփոփոխվի $T\rightarrow \mathbb {R}$ բիեկցիա դառնալու համար․

Այս կառույցն օգտագործում է 1878 թվականին Կանտորի ստեղծած մեթոդը։ Նա այն օգտագործել է $[0,1]$ փակ միջակայքի ու $(0,1)$ բաց միջակայքի իռացիոնալ թվերի միջև բիեկցիա կառուցելու համար։ Սկզբից Կանտորը հեռացրել է այդ բազմությունների հաշվելի անսահման ենթաբազմությունները, այնպես որ մնացած անհաշվելի բազմությունների մեջ բիեկցիա մնա։ Քանի որ հեռացված հաշվելի անսահման ենթաբազմությունների մեջ բիեկցիա գոյություն ունի, երկու փոխհամարժեք համապատասխանության ֆունկցիաների միավորումը տալիս է բիեկցիա նախնական բազմությունների մեջ։

Կանտորի մեթոդը կարելի է օգտագործել $f_{2}(t)=0.t_{2}$ ֆունկցիան վերափոխելու ու $T\rightarrow (0,1)$ բիեկցիա ստանալու համար։ Քանի որ որոշ թվեր երկու երկուական ընդլայնում ունեն, $f_{2}(t)$-ն նույնիսկ ինեկցիա չէ։ Օրինակ, $f_{2}(1000\dots )=0.1000\dots _{2}={\dfrac {1}{2}}$ և $f_{2}(0111\dots )=0.0111\dots _{2}={\dfrac {1}{4}}+{\dfrac {1}{8}}+{\dfrac {1}{16}}\dots ={\dfrac {1}{2}}$ (տե՛ս անսահման հաջորդականություններ)․ այդպիսով, $f(1000\dots )=f(0111\dots )={\dfrac {1}{2}}$։

$f_{2}(t)$ ֆունկցիան վերափոխելու համար դիտարկե՛նք, որ այն բիեկցիա է $(0,1)$-ի ու $T$-ի հաշվելի անսահման համապատասխան ենթաբազմություններից դուրս։ Մասնավորապես․ այն բիեկցիա չէ $(0,1)$ բազմության այն անդամների համար, որոնք մեկից ավել երկուական ընդլայնում ունեն։ Սրանք կոչվում են դիադիկ թվեր և ունեն ${\dfrac {m}{2^{n}}}$ ձևը, որտեղ $m$-ը կենտ ամբողջ թիվ է, և $n$-ը բնական թիվ է։ Կազմե՛նք այս թվերի հաջորդականությունը․ $r=({\dfrac {1}{2}},{\dfrac {1}{4}},{\dfrac {3}{4}},{\dfrac {1}{8}},{\dfrac {3}{8}},{\dfrac {5}{8}},{\dfrac {7}{8}},\dots )$։ Նաև $f_{2}(t)$ ֆունկցիան դեպի $(0,1)$ միջակայք բիեկցիա չէ $T$-ի այն շարանների բազմության համար, որոնք հայտնվում են $0$-ի, $1$-ի և $r$-ի հաջորդականության թվերի երկուական ընդլայնման երկուական տրոհիչից հետո։ Ներկայացնե՛նք այս ի վերջո հաստատուն շարանները հաջորդականության տեսքով․ $s=(000\dots ,111\dots ,1000\dots ,0111\dots ,01000\dots ,00111\dots ,11000\dots ,10111\dots ,\dots )$։ Սահմանե՛նք $g(t):T\rightarrow (0,1)$ բիեկցիան․ եթե $t$-ն $s$ հաջորդականության $n$-րդ շարանն է, $g(t)$-ն հավասար է $r$-րդ հաջորդականության $n$-րդ անդամն է, հակառակ դեպքում $g(t)=0.t_{2}$։

$T\rightarrow \mathbb {R}$ բիեկցիա կառուցելու համար, սկսե՛նք $tan(x)$ շոշափողի ֆունկցիայով, որը $(-{\dfrac {\pi }{2}},{\dfrac {\pi }{2}})$ միջակայքում բիեկցիա է դեպի $\mathbb {R}$։ Հաջորդիվ, դիտարկե՛նք, որ $h(x)=\pi (x-{\dfrac {1}{2}})$ ֆունկցիան $(0,1)\rightarrow (-{\dfrac {\pi }{2}},{\dfrac {\pi }{2}})$ միջակայքերում բիեկցիա է։ $tan(h(x)=tan(\pi (x-{\dfrac {1}{2}}))$ համադրույթ ֆունկցիան $(0,1)\rightarrow \mathbb {R}$ բիեկցիա է։ Այս ֆունկցիան $g(t)$-ի հետ համադրելը տալիս է $tan(h(g(t)))=tan(\pi (g(t)-{\dfrac {1}{2}}))$ ֆունկցիան, որը $T\rightarrow \mathbb {R}$ բիեկցիա է։

Ընդհանրացում

Ընդհանրացված անկյունագծային փաստարկի պատկերազարդում․ $T=\{n\in \mathbb {N} :n\notin f(n)\}$ բազմությունը չի կարող $f:\mathbb {N} \rightarrow P(\mathbb {N} )$ միջակայքին պատկանել։ $f$-ի քարտեզագրման օրինակը վերին նկարի $s$ թվարկմանն է համապատասխանում։

Կանտորն օգտագործել է անկյունագծային փաստարկի ընհանրացված ձևակերպումն իր Կանտորի թեորեմն ապացուցելու համար։ Թեորեմը հետևյալն է․ յուրաքանչյուր $S$ բազմության համար, $S$-ի հզոր բազմությունը չի կարող $S$-ի բիեկցիա լինել։

Ապացույց․ ենթադրենք $f$ ֆունկցիան $S\rightarrow P(S)$ ֆունկցիա է, որտեղ $P(S)$-ը $S$ բազմության հզոր բազմությունն է։ Բավական է ապացուցել, որ $f$-ը սուրյեկտիվ չէ։ Նշանակում է, որ գոյություն ունի $P(S)$-ի ինչ-որ $T$ անդամ (այսինքն՝ $S$-ի ինչ-որ ենթաբազմություն), որը $f$-ի պատկեր չէ։ Դիտարկենք հետևյալ բազմությունը․

$T=\{s\in S:s\notin f(s)\}$։

Յուրաքանչյուր $s\in S$ համար այն կա՛մ $T$ բազմության անդամ է, կա՛մ՝ ոչ։ Եթե $s$-ը $T$֊ի անդամ է, ապա $T$֊ի սահմանման համաձայն, $s$-ը $f(s)$-ին հավասար չէ։ Այդպիսով, $T$-ն հավասար չէ $f(s)$-ին։ Մյուս կողմից, եթե $s$-ը $T$֊ի անդամ չէ, ապա $T$֊ի սահմանման համաձայն, $s$-ը պատկանում է $f(s)$-ին։ Այդպիսով, $T$-ն կրկին հավասար չէ $f(s)$-ին։

Ապացույցի ավելի ամբողջական պատկերի համար տե՛ս Կանտորի թեորեմ հոդվածը։

Հետևանքներ

Կարդինալների կարգավորումը

Կանտորը սահմանում է կարդինալների ամբողջական կարգային հարաբերությունը․ այլ բառերով, $|S|$ և $|T|$ թվերը սահմանված են համապատասխան $S$ և $T$ բազմությունների միջև առկա ինեկցիայով։ Նախորդ պարբերության փաստարկն ապացուցում է, որ $\mathbb {N} \to \{0,1\}$-ի նման բազմություններն անհաշվելի են․ ասել է, թե $\neg (|\mathbb {N} \to \{0,1\}|\leq |\mathbb {N} |)$, և մենք կարող ենք ֆունկցիաների տարածության մեջ բնական թվերը ներդնել՝ $|\mathbb {N} |<|\mathbb {N} \to \{0,1\}|$ ստանալով։

Դասական մաթեմատիկայի համատեքստում սա սպառում է բոլոր հնարավորությունները, և անկյունագծային փաստարկը կարելի է օգտագործել հաստատելու համար օրինակ այն փաստը, որ, չնայած երկու բազմություններն էլ անսահման են, զրոների ու մեկերի անսահման հաջորդականություններն ավելի շատ են քան բնական թվերը։ Կանտորի արդյունքը ակնարկում է, որ բոլոր բազմությունների բազմության հասկացությունն ինքնահակասական է․ եթե $S$-ը բոլոր բազմությունների բազմությունը լիներ, ապա $P(S)$-ը միաժամանակ թե՛ $S$-ի ենթաբազմությունը կլիներ, թե՛ $S$-ից ավելի մեծ կլիներ։

Երրորդի բացառման օրենքը ենթադրելով` յուրաքանչյուր ենթա-հաշվելի բազմություն (ենթա-հաշվելիությունը սուռյեկտիվության ենթատեքստում սահմանված հատկություն է) արդեն հաշվելի է։

Կառուցողական մաթեմատիկայում ավելի դժվար և կամ անհնարին է թե՛ օրդինալ, թե՛ կարդինալ թվերը կարգավորելը։ Օրինակ Շրոդեր-Բերնշտեյն թեորեմը երրորդի բացառման օրենքն է պահանջում․ այդպիսով ինտուիցիոնիստները կարդինալների կարգավորման մասին թեորեմը չեն ընդունում։ Իրական թվերի կարգավորումը (ռացիոնալ թվերի ստանդարտ կարգավորման ընդլայնումը) նույնպես անպայմանորեն որոշելի չէ։ Ըստ Րայսի թեորեմի ֆունկցիաների հետաքրքրություն ներկայացնող դասերի հատկությունների մեծ մասը նմանապես որոշելի չեն։ Ասել է թե․ ենթա-հաշվելի բազմություների հաշվող թվերի ճիշտ բազմությունը կարող է ռեկուրսիվ չլինել։

Բազմությունների տեսության մեջ մաթեմատիկայի տեսությունները մոդելավորված են։ Օրինակ, բազմությունների տեսության մեջ, իրական թվերի «իսկական» բազմությունը նույնականցվում է որպես այն բազմությունը, որը հիմնվում է իրական թվերի ինչ-որ աքսիոմների վրա։ Տարբեր մոդելներ են ուսումնասիրվել, ներառյալ Դեդեկինդ իրական թվերն ու Կոշիի իրական թվերը։ Ավելի թույլ աքսիոմներից ավելի քիչ սահմանափակումներ են բխում` մոդելների ավելի հարուստ կարգ թույլատրելով։ Որպես հետևանք, այնպիսի համատեքստում, որը հակառակ դեպքում կառուցողական կլիներ (այսինքն․ կառուցողական կիներ եթե կիրառեր երրորդի բացառման օրենքը), հետևողական է ընդունել երրորդի բացառման օրենքին հակասող ոչ դասական աքսիոմներ։ Օրինակ․ կարող ենք պնդել, որ $\mathbb {N} \to \{0,1\}$ ֆունկցիաների անհաշվելի տարածությունը ենթա-հաշվելի է․ $|\mathbb {N} |<|\mathbb {N} \to \{0,1\}|$ պնդմանը ուղղահայաց չափի հասկացություն կիառելով։ Նման համատեքստում բոլոր բազմությունների ենթա֊հաշվելիությունը կամ անհաշվելի $\mathbb {N} ^{\mathbb {N} }$ բազմությունից $\mathbb {N}$ ինեկցիան հնարավոր է։

Բաց հարցեր

Իրական թվերի բազմության բնական թվերի բազմությունից «ավելի մեծ» լինելու փաստի արձանագրումը ստիպում է մտածել երկու բազմությունների հզորությունների «միջև» թվերի գոյության մասին․ կա՞ բազմություն, որի հզորությունը փոքր է իրական թվերի բազմության հզորությունից, բայց՝ մեծ բնական թվերի բազմության հզորությունից։ Այս հարցը հանգեցնում է կոնտինուումի վարկածին։

Նույն կերպ, «գոյություն ունի՞ այնպիսի բազմություն, որի հզորությունը փոքր է $P(S)$ բազմության հզորությունից, բայց՝ մեծ $S$ բազմության հզորությունից (որտեղ $S$-ն ինչ-որ անսահման բազմություն է)» հարցը հանգեցնում է ընդհանրացված կոնտինուումի վարկածին։

Ակնյունագծումը ավելի լայն համատեքստում

Ռասելի պարադոքսը ցույց է տվել, որ անսահմանափակ ըմբռնման սխեմայի վրա հիմնաված բազմությունների միամիտ տեսությունը հակասական է։ Նկատե՛նք, որ $T$ բազմության ու Ռասելի պարադոքսի բազմության կառուցման մեջ նմանություններ կան։ Հետևաբար․ բոլոր բազմությունների հավաքածուի բացակայության նման փաստարկները կարող են ուժի մեջ մնալ կամ չմնալ՝ կախված թե պարադոքսից խուսափելու համար ինչպես ենք փոփոխում ըմբռնման աքսիոմայի սխեման։

Տարատեսակ օբյեկտների մաթեմատիկայում գոյություն չունենալու փաստը ցուցադրելու համար անկյունագծային փաստարկի տարատեսակ անալոգներ լայն կիրառում ունեն։ Օրինակ․ կանգառի խնդրի անլուծելիության ամենատարածված ապացույցն ըստ էության անկյունագծային փաստարկ է։ Ի սկզբանե անկյունագծումն օգտագործվել է պայմանական բարդության դասերի գոյությունը ցույց տալու համար, և առանցքային դեր է խաղացել P և NP դասերի անհավասարության ապացույցի նախնական փորձերում։