Cantorjev diagonalni dokaz: razlika med redakcijama

m
m/dp/slog
m (m+/dp/+ktgr)
m (m/dp/slog)
'''Cantorjev diagonalni dokaz''' je [[matematični dokaz]], s katerim je [[Georg Ferdinand Cantor]] leta [[1877 v znanosti|1877]] pokazal, da [[realno število|realnih števil]] ni [[števna množica|števno neskončno]]. To pomeni, da je realnih števil ''več'' kot [[naravno število|naravnih]], čeprav sta obe množici [[neskončnost|neskončni]].
 
Čeprav je najbolj znan, to ni bil ''prvi'' Cantorjev dokaz o neštevnosti realnih števil. Njegov tri leta starejši [[Cantorjev prvi dokaz o neštevnosti|prvi dokaz]] ni omenjal desetiškega zapisa niti drugih [[številski sistem|številskih sistemov]]. Cantorjev diagonalni dokaz uporablja isti koncept kot [[Cantorjeva diagonalizacija|diagonalizacija]] s katero je dokazal, da je [[racionalno število|racionalnih]] in naravnih števil enako mnogo.
 
Cantorjev izvirni dokaz pokaže, da [[interval]] [0,1] ni ''števno'' neskončen. Ta [[dokaz s protislovjem]] gre takole:
# PrivzemimoPrivzame se (kot predpostavko, za katero bomose bo pozneje dokazalidokazalo, da mora biti napačna), da bi interval [0,1] res bil števno neskončen.
# Potem se lahko oštevilčimooštevilči vsa (realna) števila na tem intervalu v [[zaporedje]], ( ''r''<sub>1</sub>, ''r''<sub>2</sub>, ''r''<sub>3</sub>, …)
# VemoVe se, da se lahko vsako od teh števil lahko predstavimopredstavi v [[desetiški zapis|desetiškem zapisu]].
# Vsa ta števila zberemose zbere v seznam (ni treba, da so v kakšnem posebnem vrstnem redu). V primeru števil, ki imajo po dva desetiška zapisa, kot npr. 0,499… = 0,500…, vzamemose vzame zapis, ki se končuje z deveticami. VzemimoVzame se, na primer, da so desetiški zapisi na začetku zaporedja takšni:
#: ''r''<sub>1</sub> = 0 , 5 1 0 5 1 1 0 …
#: ''r''<sub>2</sub> = 0 , 4 1 3 2 0 4 3 …
#: ''r''<sub>7</sub> = 0 , 0 1 0 5 1 3 5 …
#: …
# Zdaj bomose skonstruiralibo skonstruiralo realno število ''x'' z intervala [0,1] tako, da bomose pogledalibo pogledalo ''k''-to [[števka|števko]] za desetiško vejico v [[desetiški zapis|desetiškem zapisu]] števila ''k''-tega števila, ''r''<sub>k</sub>. Števke, ki se jih bomobo gledaligledalo, so krepke in podrčtane, da nakazujejo zakaj se temu reče '''diagonalni dokaz'''.
#: ''r''<sub>1</sub> = 0 , <u>'''5'''</u> 1 0 5 1 1 0 …
#: ''r''<sub>2</sub> = 0 , 4 <u>'''1'''</u> 3 2 0 4 3 …
#: ''r''<sub>7</sub> = 0 , 0 1 0 5 1 3 <u>'''5'''</u> …
#: …
# Iz teh števk definirajmonaj se definira števke števila ''x'' kot sledi.
#* če je ''k''-ta števka števila ''r''<sub>''k''</sub> enaka 5, potem naj bo ''k'-ta števka števila ''x'' enaka 4,
#* če ''k''-ta števka števila ''r''<sub>''k''</sub> ni enaka 5, potem naj bo ''k'-ta števka števila ''x'' enaka 5.
# Število ''x'' je očitno realno število (saj vsak desetiški zapis predstavlja neko realno število) na intervalu [0,1]. Za zgornje zaporedje {r<sub>n</sub>}, na primer, dobimose dobi naslednji desetiški zapis:
#: ''x'' = 0 , 4 5 5 5 5 5 4 …
# Torej mora za neki ''n'' veljati ''r''<sub>''n''</sub> = ''x'', saj smose predpostavilije predpostavilo, da zaporedje (''r''<sub>1</sub>, ''r''<sub>2</sub>, ''r''<sub>3</sub>, …) oštevilči ''vsa'' realna števila na intervalu [0,1].
# Toda, ker smoso se v 6. koraku 4-ke in 5-ke izbraliizbralo na posebno »zloben« način, se ''x'' od ''r''<sub>''n''</sub> razlikuje vsaj na ''n''-tem mestu, za vsak ''n''. To pomeni, da števila ''x'' v zaporedju (''r''<sub>1</sub>, ''r''<sub>2</sub>, ''r''<sub>3</sub>, …) ni!
# To zaporedje torej ni oštevilčenje množice vseh realnih števil z intervala [0,1]. '''To je [[protislovje]]'''.
# Sklep: privzetek (1), da je interval [0,1] [[števna neskončnost|števno neskončen]], mora biti napačen.
 
Neposredna posledica tega rezultata je, da tudi množica vseh realnih števil '''R''' ni števna. Če bi bila '''R''' števna, bi se lahko oštevilčilioštevilčilo vsa realna števila in bi se zaporedje, ki bi oštevilčilo [0,1], lahko dobilidobilo tako, da bi odstranilise odstranilo vsa realna števila zunaj tega intervala. Vendar smose je pravkar pokazalipokazalo, da tako zaporedje, ki bi oštevilčilo [0,1], ne more obstajati.
 
Lahko bi se tudi dokazalidokazalo, da sta množici [0,1] in '''R''' enako [[kardinalnost|močni]] tako, da bi se med njima konstruiralikonstruirala [[bijektivna preslikava|bijekcijobijekcija]]. Za zaprti interval [0,1] je to storiti rahlo nerodno, čeprav možno; za odprti interval (0,1) bi se lahko uporabiliuporabilo
<math>f\colon (0,1)\rightarrow\mathbb{R}</math>
definirano kot <math>f(x) = \,\mathrm{tg}\,\left(\pi\left(x-\frac{1}{2}\right)\right)</math>.
== Zakaj to ne deluje na celih številih ==
 
Ljudje včasih mislijo, da je moč zgornji dokaz prilagoditi na [[celo število|cela števila]] in s tem pokazati, da so tudi ona neštevna. To skušajo storiti tako, da iz zgornjih izrazov črtajo decimalne vejice. Težava pri tem je, da neskončno zaporedje neničelnih števil ne določa celega števila. To je razlog za 7. zgordnjizgornji korak. Množica celih števil je seveda števna, zato tak dokaz ni mogoč.
 
== Splošne množice ==
 
Cantor je uporabil posplošeno obliko diagonalnega dokaza, da je dokazal [[Cantorjev izrek]]: za vsako [[množica|množico]] ''S'', je [[potenčna množica]] množice ''S'' - se pravi, množica vseh [[podmnožica|podmnožic]] množice ''S'' (tu se jo bomobo pisalipisalo kot '''P'''(''S'')) - [[kardinalnost|večja]] kot sama množica ''S''. Ta dokaz s protislovjem gre takole:
 
Denimo, da sta ''S'' in '''P'''(''S'') enako močni in naj bo torej ''f'' katerakoli bijektivna preslikava med njima. Zadostuje dokazati, da ''f'' ne more biti [[surjektivna preslikava|surjekcija]]. To pomeni, da neki element množice '''P'''(''S'') - to se po zgornji definiciji v konkretnem primeru pravi: neka podmnožica množice ''S'' - ni v [[množica slik|sliki]] preslikave ''f''. Taka množica je množica ''T'', definirana kot
* Če ''t'' je v ''T'', potem je ''t'' v ''f''(''t''), vendar, po definiciji množice ''T'', odtod sledi, da ''t'' ni v ''T''.
* Po drugi plati, če ''t'' ni v ''T'', potem ''t'' ni v ''f''(''t''), in po definiciji ''T'' odtod sledi, da ''t'' je v ''T''.
V vsakem primeru imamoje [[protislovje]].
 
Bodite pozorni na podobnost pri konstrukciji ''T'' in množice v [[RusselovRussllov paradoks|RusselovemRussllovem paradoksu]]. Cantorjev rezultat pomeni, da je pojem »[[množica vseh množic|množice vseh množic]]« v običajni [[teorija množic|teoriji množic]] nekonsistenten; če bi bila '''''S''''' res množica vseh množic, bi bila njena potenčna množica '''P'''('''''S''''') hkrati večja od '''''S''''' in podmnožica množice '''''S'''''.
 
Zgornjega dokaza ni moč izvesti v [[Willard Van Orman Quine|Quineovi]] teoriji množici na »novih temeljih«, ki uporablja drugačno različico [[aksiom ločljivosti|aksioma ločljivosti]], v katerem ni moč izraziti <math>\{\,s\in S: s\not\in f(s)\,\}</math>.
Analogije diagonalnega dokaza se uporabljajo v matematiki za dokaz obstoja ali neobstoja določenih objektov. Denimo, standardni dokaz nerešljivosti [[problem ustavitve|problema ustavitve]] je v bistvu diagonalni dokaz.
 
Diagonalni dokaz nam pokaže, da je množica realnih števil »večja« kot množica celih števil. VprašamoVpraša se lahko, ali obstaja množica, katere [[kardinalnost]] je »vmes« med kardinalnostjo množice celih in kardinalnostjo množice realnih števil. To vprašanje nas privede do slavne [[domneva kontinuuma|domneve kontinuuma]]. Podobno nas vprašanje ali za neko množico ''s'' obstaja množica, katere kardinalnost je med močjo ''s'' in '''P'''(''s''), pripelje do [[posplošena domneva kontinuuma|posplošene domneve kontinuuma]].
 
[[Kategorija:Teorija množic]]
[[Kategorija:Dokazi]]
[[Kategorija:1877 v znanosti]]
[[Kategorija:Georg Ferdinand Cantor]]