Идејата за докажување е да се конструира израз што ќе го означи неговото
сопствена недокажливост. Оваа конструкција може да се направи во три фази:
Првата фаза е воспоставување кореспонденција помеѓу формална аритметикаи множество од цели броеви (Геделизација);
Втората фаза е изградба на некое посебно својство за кое не се знае дали е теорема на формална аритметика или не;
Третата фаза е замена на местото на x на одреден цел број поврзан со себе, т.е., замена на сите со овие броеви
Прва фаза. Геделизација на формалната аритметика
Формалната аритметика може да се аритметизира (т.е. Годелизира) на следниот начин: секоја нејзина теорема е поврзана со одреден број. Меѓутоа, бидејќи секој број е исто така теорема, тогаш секоја теорема може да се смета, од една страна, како теорема на формалната аритметика, а од друга, како теорема над множеството теореми на формалната аритметика, т.е. метатеорема што одговара на доказот на одредена теорема.
Така, можеме да заклучиме дека системот на формална аритметика содржи и свој метасистем.
Сега ќе ги претставиме добиените резултати поконкретно и подетално.
Прво, можеме да поврземе со секој симбол и формална аритметика посебна ознака на код, повикана во овој случајБрој на Гедел
Второ, секоја низа од симболи ја поврзуваме со истиот Геделов број користејќи некоја композициска функција.
Трето (и ова е од суштинско значење), секој доказ за низа од аксиоми и правила за замена (или правила за замена) е поврзан со број каде што се означува низата теореми користени во доказот
Така, секој доказ во формалната аритметика одговара на одреден број - неговиот Геделски број.Секое расудување во формалната аритметика се трансформира во пресметки на множество природни броеви.
Значи, наместо да манипулирате со симболи, теореми и докази, можете да користите
пресметки на множество од цели броеви. Секој израз како, на пример, следново: „докажлив во формална аритметика“ сега одговара на одреден број, што ќе го означиме како
Да ја формулираме следната позиција.
Формалната метааритметика е содржана во множеството природни броеви, кое самото е содржано во толкувањето на формалната аритметика.
Оваа ситуација со формалната аритметика потсетува на ситуацијата со природниот јазик: на крајот на краиштата, ништо не нè спречува да го користиме за да ги формулираме неговите основни концепти и правила во него.
Правилниот избор на функција овозможува недвосмислена транзиција од А на, т.е., доделување два различни броеви на два разни докази. На пример, може да се изберат Геделови броеви на таков начин што секој симбол од азбуката на формалната аритметика одговара на својот прост број, како што е прикажано, на пример, во Табела. 3.2.
Табела 3.2
Секоја формула (која се состои од знаци кои варираат од 1 до е за возврат кодирана со низа која се состои од првиот примарни броеви, односно број
каде е прост број.
За возврат, доказот, т.е. низата формули ќе бидат кодирани на сличен начин со бројот
И обратно, благодарение на овој метод на конструирање броеви, станува возможно, почнувајќи од одреден број, со негово разложување на главните фактори(поради уникатноста на разложувањето на природните броеви во производи на силите на простите броеви) се враќаат во два чекора до експоненти, т.е. до примитивни симболи на формалната аритметика. Се разбира, ова е главно само теоретски, бидејќи бројките брзо стануваат преголеми
за да може да се манипулира со нив. Сепак, треба да се забележи дека основната можност за оваа операција е од суштинско значење.
Пример. Нека е даден број Т, кој одговара на некој доказ и претставува производ од прости броеви:
Ова проширување значи дека доказот на теоремата содржи две фази: едната одговара на бројот 1981027125 253, а другата на бројот 1981027125 211. Факторирајќи го секој од овие броеви повторно во прости множители, добиваме
Од табела за кодирање на азбуката на формалната аритметика (Табела 3.2) откриваме дека нашите Геделови броеви за овие два броја
ќе одговара следниот доказ:
Од формулата следи формулата
Така, во метааритметиката, вредноста на оригиналниот број се добива од формалната аритметика.
Втора фаза. Лема на Гедел
Секој број Т поврзан со доказ одговара на теорема докажлива во формалната аритметика. „Геделизирана“ формална аритметика се нарекува аритметикувана формална аритметика. Бидејќи секоја аксиома и секое правило на аритметизираната формална аритметика одговара на некои аритметичка операција, потоа со помош на систематски тест може да се утврди дали на даден бројТ доказ за некоја теорема.Броевите Т во овој случај формираат пар од конјугирани броеви. Изразот и се конјугирани“ Претставливи во рамките на самата аритметизирана формална аритметика. Ова значи дека постои број на Гедел кој дигитално ја изразува оваа изјава.
Стигнавме до критичната точка на доказот на Гедел. Нека A е израз на аритметизирана формална аритметика што содржи некоја слободна променлива. Наместо тоа, можете да замените некој термин. Конкретно, можете да го замените изразот А со самиот израз А. Во овој случај, бројот-изразот А извршува две функции истовремено различни улоги(види погоре конструкција
Кантор и Ричард): тоа е во исто време вистински изразза замена и добиениот термин. Оваа специјална замена ќе ја означиме како Значи формулата значи дека бројот е Геделовиот број добиен со извршување на замената - на изразот А:
Потоа Гедел конструира израз (кој не се знае дали е теорема или не-теорема) во кој ја воведува оваа замена. Изразот изгледа вака:
Трета фаза. Конечна замена
Во аритметизираната формална аритметика, овој израз е претставен во дигитална форма. Нека Е е неговиот Геделски број. Бидејќи изразот содржи слободна променлива, имаме право да извршиме замена - преку замена на бројот Е и означување - замена Е:
Овој втор израз го означуваме со a, а неговиот Геделов број со E. Да дадеме толкувања на изразот e.
Прво толкување. Не постои таков пар за кој истовремено би важело следново: од една страна, Т е бројот на аритметизираниот доказ на теоремата сам по себе, а од друга страна, би имало замена. истата трансформација како и другите, таа е претставена во термини и во нивните кодни ознаки - Геделови броеви и, според тоа, таков број постои. Тогаш можеби Т-бројот не постои.
Второ толкување. Не постои аритметизиран доказ за теоремата Т што би била -замена на Е. Значи, ако нема доказ, тоа е затоа што самата таа не е теорема. Ова води до третото толкување.
Трето толкување. Изразот за кој Геделовиот број е -замена Е не е теорема на аритметизирана формална аритметика. Но, токму тука лежи противречноста, бидејќи по конструкција тој самиот е -замена на Е, а бројот по конструкција не е ништо друго освен самиот број Е. Оттука следи конечната интерпретација на e.
Признавам дека ја прочитав самата идеја за разгледување на прашањето за постоењето на Бог од оваа страна од Анатолиј Александрович Васерман:
http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D1%82%D0%BE%D0%BB%D0%B8%D0%B9_%D0%90%D0 %BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87_%D0%92 %D0%B0%D1%81%D1%81%D0%B5%D1%80%D0%BC%D0%B0%D0%BD#.D0.A0.D0.B5.D0.BB.D0.B8. D0.B3.D0.B8.D0.BE.D0.B7.D0.BD.D1.8B.D0.B5_.D0.B2.D0.B7.D0.B3.D0.BB.D1.8F.D0. Б4.Д1.8Б
Но, би сакал да ја развијам оваа идеја и да ја опишам малку подетално.
Во религијата (како и во нерелигијата) постои одредена аксиоматика на конструкцијата. Барем во идеално, ако ова не е само слепо верување, туку свесен и информиран избор. На пример, една аксиома на физиката може да се смета „природата се познава преку разумот и логичките заклучоци, сите закони на физиката се исти во сите точки во просторот и во секое време“. На пример, аксиомата на религијата може да се смета за изјавата „Бог постои и е првата причина за сите нешта“. Со други зборови, нема сомнеж дека сите бројни поединости и гранки можат да се сведат на неколку важни, недокажливи изјави, кои се токму тие аксиоми.
Да разгледаме од овие позиции религиозни верувања. Најважната аксиома на религијата: „Бог постои и е првата причина за сите нешта“.
Сега да се потсетиме на една од најважните математички теореми, Геделова теорема.
http://elementy.ru/trefil/21142
Слаба теорема на Гедел: „Секој формален систем на аксиоми содржи нерешени претпоставки“ или „ако системот на аксиоми е целосен, тогаш тој е неконзистентен“.
Силната теорема на Гедел: "Логичката комплетност (или нецелосност) на кој било систем на аксиоми не може да се докаже во рамките на овој систем. За да се докаже или побие, потребни се дополнителни аксиоми (зајакнување на системот).
Да се потсетиме на некои дефиниции. Системот на аксиоми е целосен ако било кое тврдење формулирано за даден систем на аксиоми е докажливо (односно, тоа е или точно или неточно). Нерешена претпоставка е исказ за кој не може да се докаже ниту неговата вистинитост ниту невистинита, односно изјавата не е логички докажлива. Системот на аксиоми е контрадикторен ако може да се докаже дека една иста изјава е вистинита и неточна.
Од Геделовата теорема произлегува дека ако концептот на Бог е вклучен во аксиоматски систем, тогаш овој систем не е целосен, односно има последици (појави) кои не се докажливи, односно може да постојат или не, ова не е докажлив.
Но, ова е во спротивност со следните две одредби (одберете која е најубедливата): природата не содржи феномени што може да се сметаат и за постоечки и непостоечки; секој природен феномен или постои или не постои. Втората позиција вели дека, по дефиниција, Бог е основната причина за сè, затоа Бог или води до постоење на одредени нешта (изјави) или до нивно непостоење, а повикувањето на Бог може или да докаже или да го побие секое тврдење. Ова е во спротивност со некомплетноста на системот.
Или друго. Ако го вклучиме концептот на Бог во аксиоматскиот систем и претпоставиме дека е целосен (секое тврдење во целосен систем на аксиоми е докажливо), тогаш според теоремата на Гедел таквиот систем на аксиоми ќе биде контрадикторен, односно ќе има феномени за што може да се докаже дека и постојат и не постојат.
Нема смисла да се вклучи Бог во контрадикторен систем на аксиоми, бидејќи тој е контрадикторен, односно содржи феномени за кои може да се докаже дека постојат и не постојат, што, како што е наведено, е во спротивност со природата и концептот на Бога.
Конечно, ако концептот за Бог не е вклучен во аксиоматскиот систем, тогаш тој не може да се смета за фундаментална основа на вселената, од која произлегува сето она што постои, што суштински е во спротивност со дефиницијата за Бог.
За валидноста на овој доказ, неопходно е да се препознае валидноста на законите на математичката логика (пропозициска логика + пресметување на предикат), кои овозможуваат да се утврдат законите на последица, вистина, неточност, недоследност, конзистентност на искази и друго. својства и односи меѓу изјавите.
Ако претпоставиме дека математичката логика не е применлива за проучување на прашањето за постоењето на Бог, тогаш последицата ќе биде тоа што не е можно да се проучува ова прашање со помош на расудување, со помош на разумот. Со други зборови, конзистентниот разум секогаш доаѓа до негативен одговор на прашањето за постоењето на Бога.
Што се случува на крајот... секој дури и оддалеку рационален човек, се разбира, ја препознава валидноста на законите на логиката, што значи дека тој секогаш доаѓа до заклучок дека Бог во дефиницијата за „причината за сите нешта“ не постои. . Нерационален човек кој тврди дека Бог може да се познава само преку чувства (а не со разум), се разбира, може да го каже тоа, но не постои начин да се убеди друг во ова; чувствата не можат да се пренесат. Згора на тоа, концептот за Бог е концепт формулиран од разумот. Како се предлага да се преведе концептот на разумот во сензација, па дури и на таков начин што може да се пренесе на друго лице, не е јасно. Повторно, дури и донекаде рационална личност ќе рече дека тоа не е можно: да се преведе апстрактниот концепт на разумот во чувство и да се почувствува.
Конечно, постои уште една опција: „Бог не е првата причина за сè“. Тогаш таквите противречности не се појавуваат, меѓутоа, ова е значително слабеење на позицијата на религијата, бидејќи токму фактот дека Бог создал сè, дека Бог е почеток на сите почетоци, тоа е основа за многубројните изјави на религијата и оправдувања во спорови.
П.С. Вреди да се забележи уште една љубопитна работа, интересна за физичарите. ВО оваа дефиницијаБог не кажува ништо за неговата рационалност. Односно, може да се додаде „Бог е рационална причина за сите нешта“, но ова е стеснување на дефиницијата, која првично не е потребна за докажување. Без интелигенција, концептот на „бог“ лесно може да се замени со „единственост и големата експлозија- причината за се што постои.“ А одговорот ќе биде ист: сингуларноста и големата експлозија не се основната причина за сè што постои.
Спроведувајќи уште поголема апстракција, можеме да кажеме дека ниту една појава или причина не може да биде основната причина за сите нешта, односно основната причина во принцип не постои. Расудувајќи во рамките на која било аксиоматика, може да се дојде до заклучок дека основната причина за сè не постои. Многу едноставно кажано, без разлика колку фундаментално го разбираме универзумот, прашањата секогаш ќе останат во духот на: „од каде дојде големата експлозија, од каде дојде сингуларноста, од каде пулсирачкиот универзум, од каде од каде доаѓа мултиверзумот, зошто универзумот секогаш постои?“ и така натаму. Основната причина за сè не може да се најде во принцип, таа не е содржана во ниту еден предмет, феномен или концепт. Затоа, за една личност ова е еквивалентно на неговото отсуство. Теоретски, може да се претпостави постоење на надворешен набљудувач надвор од нашиот универзум, кој ќе одговори на прашањето од каде потекнува сè (иста дополнителна аксиома, проширување во теоремата на Гедел), но тогаш ќе се појави прашањето каде надворешниот набљудувач, неговиот универзумот и основната причина за сето ова потекнува.
Екологија на животот. Наука и откритие: Теоремата за нецелосност на Гедел, една од најпознатите теореми на математичката логика, е и среќна и несреќна. Во ова таа е слична на посебна теоријарелативноста на Ајнштајн. Од една страна, речиси сите слушнале нешто за нив. Од друга интерпретација, теоријата на Ајнштајн „вели дека сè во светот е релативно“.
Теорема Гедел за нецелосноста, една од најпознатите теореми на математичката логика, е среќна и несреќна во исто време. Во ова е слично на специјалната теорија на релативноста на Ајнштајн.
Од една страна, речиси сите слушнале нешто за нив. Од друга страна, во народното толкување Ајнштајновата теорија, како што е познато, " вели дека се во светот е релативно" А Теорема за нецелосност на Гедел(во натамошниот текст едноставно TGN), во приближно истата слободна народна формулација, “ докажува дека постојат работи неразбирливи за човечкиот ум».
И така некои се обидуваат да го приспособат како аргумент против пцуењетоеријализмот , додека други, напротив, докажуваат со негова помош,дека нема бог . Смешното не е само што двете страни не можат да бидат во право во исто време, туку и што ниту едната ниту другата не се мачат да сфатат што всушност кажува оваа теорема.
Па што? Подолу ќе се обидам да ви кажам за тоа „на прсти“. Мојата презентација, се разбира, ќе биде неригорозна и интуитивна, но ќе ги замолам математичарите да не ме осудуваат строго. Можно е за не-математичари (од кои, всушност, и јас сум), да има нешто ново и корисно во она што е опишано подолу.
Математичката логика е навистина прилично сложена наука, и што е најважно, не многу позната.Потребни се внимателни и строги маневри, во кои е важно да не се меша она што всушност е докажано со она што е „веќе јасно“. Сепак, се надевам дека за да го разбере следниов „преглед на доказ за TGN“ на читателот ќе му треба само знаење од училишна математика/компјутерски науки, вештини логично размислувањеи 15-20 минути време.
Да се поедностави малку, TGN тврди дека во доволно сложени јазициима недокажливи изјави.Но, во оваа фраза речиси секој збор треба да се објасни.
Да почнеме со обидот да откриеме што е доказ.Да земеме некој училишен аритметички проблем. На пример, да претпоставиме дека треба да ја докажете точноста на следната едноставна формула: „∀x(x−1)(x−2)−2=x(x−3)“ (да ве потсетам дека симболот ∀ се чита „за кој било“ и се нарекува „универзален квантификатор“). Можете да го докажете тоа со идентично трансформирање, на пример, вака:
∀x(x−1)(x−2)−2=x(x−3)
∀xx2−3x+2−2=x2−3x
∀xx2−3x–x2+3x=0
∀x0=0
ВИСТИНА
Преминот од една формула во друга се случува според одредени добро познати правила. Преминот од 4-та формула до 5-та се случи, да речеме, затоа што секој број е еднаков на себе - ова е аксиома на аритметиката. Така, целата процедура за докажување ја преведува формулата во Буловата вредност ВИСТИНА. Резултатот може да биде и ЛАГА - ако побиеме некоја формула. Во овој случај, ќе го докажеме неговото негирање. Може да се замисли програма (а такви програми всушност се напишани) што ќе докаже слични (и посложени) изјави без човечка интервенција.
Да го кажеме истото малку поформално.Дозволете ни да имаме множество што се состои од низи од знаци од некоја азбука, и постојат правила според кои од овие низи можеме да избереме подмножество S таканаречени изјави - односно граматички значајни фрази, од кои секоја е точно или неточна. Можеме да кажеме дека постои функција P која доделува изјави од S една од двете вредности: TRUE или FALSE (односно, ги пресликува на Булово множество B од два елементи).
Ајде да го наречеме овој пар- множество искази S и функција P од >S до B - „јазик на изјави“. Забележете дека во секојдневна смисла концептот на јазикот е нешто поширок. На пример, руската фраза „ Дојди овде!„Не е ниту точно ниту лажно, односно од гледна точка на математичката логика, тоа не е изјава.
За она што следи, ни треба концепт на алгоритам.Овде нема да дадам формална дефиниција - тоа би не одвело доста далеку. Ќе се ограничам на неформално: „алгоритам“ е низа од недвосмислени инструкции („програма“), кои конечен бројчекорите ги преведуваат влезните податоци во излезни.
Она што е во закосени букви е фундаментално важно - ако програмата се врти на некои почетни податоци, тогаш таа не го опишува алгоритмот. За едноставност и примена во нашиот случај, читателот може да смета дека алгоритам е програма напишана на кој било програмски јазик познат нему, кој, за кој било влезен податок од дадена класа, гарантирано ќе ја заврши својата работа создавајќи Булова резултат.
Да се запрашаме: за секоја функција P постои „алгоритам за докажување“ (или, накратко, „ дедуктивен"), еквивалентно на оваа функција, односно трансформирање на секоја изјава во точно иста Булова вредност како неа? Истото прашање може да се формулира попрецизно: Дали секоја функција над множество изјави е пресметлива?
Како што веќе погодивте, од валидноста на TGN произлегува дека не, не секоја функција - има непресметливи функции од овој тип. Со други зборови, Не може да се докаже секоја вистинита изјава.
Многу е можно оваа изјава да предизвика внатрешен протест кај вас. Ова се должи на неколку околности. Прво, кога сме научени училишна математика, тогаш понекогаш постои лажен впечаток за речиси целосен идентитет на фразите „Теоремата X е вистинита“ и „Теоремата X може да се докаже или потврди“.
Но, ако размислите за тоа, ова воопшто не е очигледно. Некои теореми се докажуваат прилично едноставно (на пример, со обид за мал број опции), додека други се многу тешки. Да се потсетиме, на пример, на познатиот Велики Теорема на Ферма:
Нема такви природни x,y,zи n>2, дека xn+yn=zn,
чиј доказ е пронајден само три и пол века по првата формулација (а тоа е далеку од елементарно). СО Мора да се направи разлика помеѓу вистинитоста на изјавата и нејзината докажливост.Од никаде не произлегува дека нема вистинити, но недокажливи (и не целосно проверливи) изјави.
Вториот интуитивен аргумент против TGN е посуптилен.Да речеме дека имаме некоја недокажлива (во рамките на оваа дедуктивна) изјава. Што не спречува да го прифатиме како нова аксиома? Така, малку ќе го искомплицираме нашиот систем на докази, но ова не е страшно.
Овој аргумент би бил сосема точен доколку има конечен број на недокажливи изјави. Во пракса, следново може да се случи: откако постулираш нова аксиома, наидуваш на нова недокажлива изјава. Ако ја прифатиш како друга аксиома, ќе се сопнеш на третата. И така натаму бесконечно.
Тие го велат тоа одбивањето ќе остане нецелосно. Ние, исто така, можеме да го принудиме алгоритмот за докажување да заврши во конечен број чекори со одреден резултат за кој било исказ на јазикот. Но, во исто време, тој ќе почне да лаже - води кон вистината за неточни изјави или до лаги - за верните.
Во такви случаи велат дека одбивањето е контрадикторно. Така, друга формулација на TGN звучи вака: Постојат пропозициски јазици за кои е невозможен целосен конзистентен дедуктивен процес.“ – оттука и името на теоремата.
Понекогаш наречена „Годелова теорема“, изјавата е дека секоја теорија содржи проблеми што не можат да се решат во рамките на самата теорија и бараат нејзино генерализирање. Во извесна смисла ова е точно, иако оваа формулација има тенденција да го прикрие прашањето наместо да го разјасни.
Исто така, ќе забележам дека ако зборувавме за познати функции кои мапираат множество реални броеви во него, тогаш „непресметливоста“ на функцијата не би изненадила никого (само не мешајте „пресметливи функции“ и „пресметливи броеви“ “ - тоа се различни работи).
Курт Гедел
Секој ученик знае дека, да речеме, во случајот на функцијата sinx, треба да имате многу среќа со аргументот за да може процесот на пресметување на точната децимален приказВредноста на оваа функција завршуваше со конечен број чекори.
Но, најверојатно, ќе го пресметате користејќи бесконечна серија, и оваа пресметка никогаш нема да доведе до точен резултат, иако може да се приближи колку што сакате - едноставно затоа што синусната вредност на повеќето аргументи е ирационална. TGN едноставно ни кажува дека дури и меѓу функциите чии аргументи се низи и чии вредности се нула или една, има и непресметливи функции, иако тие имаат сосема поинаква структура.
За понатамошни цели, ќе го опишеме „јазикот на формалната аритметика“.Размислете за класа текстуални низи со конечна должина, составена од арапски бројки, променливи (букви Латинска азбука), примање природните вредности, празни места, ликови аритметички операции, еднаквост и нееднаквост, квантификатори ∃ („постои“) и ∀ („за кој било“) и, можеби, некои други симболи (нивниот точен број и состав не ни се важни).
Јасно е дека не сите такви линии се значајни (на пример, „12=+∀x>“ е бесмислица). Подмножеството значајни изрази од оваа класа (т.е. низи кои се вистинити или неточни од гледна точка на обичната аритметика) ќе биде нашиот сет на искази.
Примери на формални аритметички искази:
1=1
2×2=5
∃xx>3
∀y∀zy×z>y+ z
итн. Сега да ја наречеме „формула со слободен параметар“ (FSP) низа што станува исказ ако природен број се замени во него како овој параметар. Примери на FSP (со параметар x):
x=0
2×2=x
∃yx+y>x
итн. Со други зборови, FSP се еквивалентни на природните аргументи со Булови вредности.
Да го означиме множеството од сите FSP со буквата F. Јасно е дека може да се подреди (на пример, прво пишуваме формули со една буква подредени по азбучен ред, проследено со формули со две букви итн.; не е важно до нас која азбука ќе се изврши подредувањето). Така, секој FSP одговара на неговиот број k во подредената листа, а ние ќе го означиме Fk.
Сега да преминеме на скица на доказот за TGN во следната формулација:
За исказниот јазик на формалната аритметика не постои целосен конзистентен дедуктивен систем.
Ќе го докажеме тоа со контрадикторност.
Значи, да претпоставиме дека постои таков дедуктивен систем. Дозволете ни да го опишеме следниот помошен алгоритам А, кој доделува Булова вредност на природен број k на следниов начин:
1. Најдете kth формулаво списокот Ф.
2. Заменете го бројот k во него како аргумент.
3. Ние го применуваме нашиот алгоритам за докажување на добиената изјава (според нашата претпоставка, таа постои), што ја преведува во ТОЧНО или НЕТОЧНО.
4. Примени логичка негација на добиениот резултат.
Едноставно кажано, алгоритмот резултира со вредноста ТОЧНО ако и само ако резултатот од замената на сопствениот број во FSP во нашата листа дава лажна изјава.
Овде доаѓаме до единственото место каде што ќе го замолам читателот да ми го земе зборот.
Очигледно е дека, според претпоставката направена погоре, секој FSP од F може да се поврзе со алгоритам кој содржи природен број на влезот и Булова вредност на излезот.
Разговорот е помалку очигледен:
Лема: Секој алгоритам што конвертира природен број во Булова вредност одговара на некои FSP од множеството F.
Доказот за оваа лема ќе бара, во најмала рака, формална, наместо интуитивна, дефиниција на концептот на алгоритам. Меѓутоа, ако размислите малку за тоа, тоа е сосема веродостојно.
Всушност, алгоритмите се напишани во алгоритамски јазици, меѓу кои има такви егзотични како, на пример, Brainfuck, кој се состои од осум зборови со еден знак, на кои, сепак, може да се имплементира секој алгоритам. Би било чудно ако побогатиот јазик на формули за формална аритметика што го опишавме се покаже како посиромашен - иако, без сомнение, не е многу погоден за обично програмирање.
Откако го поминавме ова лизгаво место, брзо стигнуваме до крајот.
Така, погоре го опишавме Алгоритамот А. Според лемата во која ве замолив да верувате, постои еквивалентен FSP. Има одреден број во списокот F - да речеме, n. Да се запрашаме, што е Fn(n)? Ова нека биде ВИСТИНАТА. Потоа, според конструкцијата на алгоритмот A (а со тоа и еквивалентната функција Fn), тоа значи дека резултатот од замена на бројот n во функцијата Fn е НЕТОЧЕН.
Обратно се проверува на ист начин: од Fn(n)=FALSE следува Fn(n)=TRUE. Дојдовме до контрадикција, што значи дека првичната претпоставка е неточна. Така, не постои целосен конзистентен дедуктивен систем за формална аритметика. Q.E.D.
Тука е соодветно да се потсетиме на Епименид, кој, како што е познато, изјавил дека сите Критјани се лажговци, а и самиот е Критјанец. Во попрецизна формулација на неговата изјава (познат како „лажлив парадокс“)може да се формулира на следниов начин: лажам" Токму ваквата изјава, која самата ја прокламира својата неточност, ја користевме за докажување.
Како заклучок, сакам да забележам дека TGN не тврди ништо особено изненадувачки. На крајот на краиштата, сите одамна се навикнати на фактот дека не сите броеви можат да се претстават како сооднос од два цели броеви (запомнете, оваа изјава има многу елегантен доказ кој е стар повеќе од две илјади години?).И корените на полиномите со рационални коефициентине се ни сите броеви . И сега излегува дека не сите функции на природниот аргумент се пресметливи.
Скицата на дадениот доказ беше за формална аритметика, но лесно е да се види дека TGN е применлив за многу други пропозициски јазици. Се разбира, не сите јазици се вака. На пример, да дефинираме јазик на следниов начин:
„Било која фраза Кинески јазике вистинска изјава ако е содржана во цитатот на другарот Мао Цетунг и неточна ако не е содржана“.
Тогаш соодветниот целосен и конзистентен алгоритам за докажување (кој би можел да го нарече „догматски дедуктивен“) изгледа отприлика вака:
„Прелистајте ја книгата со цитати на другарот Мао Це Тунг додека не ја најдете изреката што ја барате. Ако се најде, тогаш е точно, но ако цитатот е завршен и изјавата не се најде, тогаш е неточна“.
Она што нè спасува овде е што секоја книга со цитати е очигледно конечна, така што процесот на „докажување“ неизбежно ќе заврши. Така, TGN не се применува на јазикот на догматските изјави. Но, ние зборувавме за сложени јазици, нели?објавено
Секој систем на математички аксиоми почнувајќи од одредено нивокомплексноста е или внатрешно контрадикторна или нецелосна.
Во 1900 година, во Париз се одржа Светската конференција на математичари, на која Дејвид Хилберт (1862–1943) во форма на тези ги презентираше 23-те најважни, според него, проблеми што требаше да ги решат теоретичарите од наредниот дваесетти век. Број два на неговата листа беше еден од нив едноставни задачи, чиј одговор изгледа очигледен додека не закопате малку подлабоко. Зборувајќи модерен јазик, беше прашање: дали математиката е самодоволна? Втората задача на Хилберт се сведуваше на потребата строго да се докаже дека системот на аксиоми - основни искази прифатени во математиката како основа без доказ - е совршен и целосен, односно овозможува математички да се опише сè што постои. Требаше да се докаже дека е можно да се дефинира таков систем на аксиоми што тие, прво, би биле меѓусебно конзистентни, а второ, од нив може да се извлече заклучок за вистинитоста или неточноста на која било изјава.
Да земеме пример од училишната геометрија. Во стандардната Евклидова планиметрија (геометрија на рамнина), несомнено може да се докаже дека изјавата „збирот на аглите на триаголникот е 180°“ е точно, а изјавата „збирот на аглите на триаголникот е 137 °“ е неточно. Во суштина, во Евклидовата геометрија секоја изјава е или лажна или вистинита, и нема трета опција. И на почетокот на дваесеттиот век, математичарите наивно веруваа дека истата ситуација треба да се набљудува во секој логички конзистентен систем.
И тогаш, во 1931 година, некој виенски математичар Курт Гедел со очила објави кратка статија која едноставно го вознемири целиот свет на таканаречената „математичка логика“. По долги и сложени математички и теоретски преамбули, тој буквално го утврди следново. Да земеме каква било изјава како: „Претпоставката бр. 247 во овој систем на аксиоми е логично недокажлива“ и да ја наречеме „претпоставка А“. Така, Гедел едноставно го докажа следново неверојатен имоткој било систем на аксиоми:
„Ако изјавата А може да се докаже, тогаш изјавата не-А може да се докаже“.
Со други зборови, ако може да се докаже вистинитоста на изјавата „претпоставката 247 е недокажлива“, тогаш може да се докаже и вистинитоста на изјавата „претпоставката 247 е докажлива“. Односно, враќањето на формулацијата на вториот проблем на Хилберт, ако системот на аксиоми е целосен (односно, секоја изјава во него може да се докаже), тогаш тоа е контрадикторно.
Единствениот излез од оваа ситуација е да се прифати нецелосен систем на аксиоми. Односно, мораме да го трпиме фактот дека во контекст на кој било логички систем сè уште ќе имаме изјави од „тип А“ кои се очигледно вистинити или лажни - и можеме да ја процениме нивната вистина само надвор од рамката на аксиоматиката што ја имаме. прифатени. Ако нема такви изјави, тогаш нашата аксиоматика е контрадикторна и во нејзините рамки неминовно ќе има формулации кои ќе можат и да се докажат и да се демантираат.
Значи, формулацијата на првата, или слаба, теорема за нецелосност на Гедел: „Секој формален систем на аксиоми содржи нерешени претпоставки“. Но, Гедел не застана тука, формулирајќи и докажувајќи ја втората, или силна, теорема за нецелосност на Гедел: „Логичката комплетност (или нецелосност) на кој било систем на аксиоми не може да се докаже во рамките на овој систем. За да се докаже или побие, потребни се дополнителни аксиоми (зајакнување на системот).“
Би било побезбедно да се мисли дека теоремите на Гедел се апстрактни по природа и не се однесуваат на нас, туку само области на возвишена математичка логика, но всушност се покажа дека тие се директно поврзани со структурата на човечкиот мозок. Англискиот математичар и физичар Роџер Пенроуз (р. 1931) покажа дека теоремите на Гедел може да се користат за да се докаже постоењето фундаментални разликипомеѓу човечкиот мозок и компјутерот. Значењето на неговото размислување е едноставно. Компјутерот дејствува строго логично и не е во состојба да одреди дали изјавата А е точно или неточна ако оди подалеку од аксиоматиката, а таквите искази, според теоремата на Гедел, неизбежно постојат. Човек, соочен со таква логички недокажлива и непобитна изјава А, секогаш е способна да ја одреди нејзината вистина или неточност - врз основа на секојдневното искуство. Барем во ова човечки мозоксупериорен во однос на компјутерот врзан со чист логички кола. Човечкиот мозок е способен да ја разбере целата длабочина на вистината содржана во теоремите на Гедел, но компјутерскиот мозок никогаш не може. Затоа, човечкиот мозок е сè освен компјутер. Тој е способен да донесува одлуки и да тестира Туринг ќе поминеуспешно.
Се прашувам дали Хилберт имал идеја до каде ќе не одведат неговите прашања?
Курт ГОДЕЛ
Курт Годел, 1906–78
Австриски, а потоа американски математичар. Роден во Брун (сега Брно, Чешка). Дипломирал на Универзитетот во Виена, каде што останал учител на отсекот математика (од 1930 година - професор). Во 1931 година објавил теорема која подоцна го добила неговото име. Како чисто аполитична личност, тој имаше исклучително тешко убиство на неговиот пријател и колега од одделот од страна на нацистички студент и падна во длабока депресија, чии рецидиви го прогонуваа до крајот на неговиот живот. Во 1930-тите емигрирал во САД, но се вратил во родната Австрија и се оженил. Во 1940 година, во екот на војната, тој беше принуден да побегне во Америка транзитирајќи низ СССР и Јапонија. Работел извесно време во Институтот за напредни студии Принстон. За жал, психата на научникот не можеше да издржи и тој почина во психијатриска клиника од глад, одбивајќи да јаде, бидејќи беше убеден дека ќе го отрујат.
| Коментари: 0 |
Како се развива научниот модел во природните науки? Секојдневните работи се акумулираат или научно искуство, неговите пресвртници се внимателно формулирани во форма на постулати и ја формираат основата на моделот: збир на изјави прифатени од секој што работи во рамките на овој модел.
Анатолиј Васерман
Во 1930 година, Курт Гедел докажал две теореми кои, преведени од математички јазик на човечки јазик, значат приближно следново: Секој систем на аксиоми доволно богат за да се користи за дефинирање на аритметиката ќе биде или нецелосен или контрадикторен. Не комплетен систем- тоа значи дека во системот е можно да се формулира изјава што не може ниту да се докаже ниту да се побие со средствата на овој систем. Но Бог, по дефиниција, е конечната причина за сите причини. Од гледна точка на математиката, тоа значи дека воведувањето на аксиомата за Бог ја прави целосна наша аксиоматика. Ако постои Бог, тогаш секоја изјава може или да се докаже или да се побие, упатувајќи се, на овој или оној начин, на Бога. Но, според Гедел, целосниот систем на аксиоми е неизбежно контрадикторен. Односно, ако веруваме дека Бог постои, тогаш сме принудени да дојдеме до заклучок дека во природата се можни противречности. И бидејќи нема противречности, инаку целиот наш свет би се урнал од овие противречности, мораме да дојдеме до заклучок дека постоењето на Бог е некомпатибилно со постоењето на природата.
Сосински А.Б.
Геделовата теорема, заедно со откривањето на теоријата на релативноста, квантна механикаи ДНК, обично се смета за најголема научно достигнување XX век. Зошто? Која е нејзината суштина? Кое е неговото значење? Овие прашања во неговото предавање како дел од проектот „ Јавни предавања„Полит.ру“ открива Алексеј Брониславович Сосински, математичар, професор на независниот московски универзитет, офицер на Орденот на академските палми на Француската Република, лауреат на наградата на Владата на Русија во областа на образованието во 2012 година. Конкретно, беа дадени неколку различни формулации за него, беа опишани три пристапи кон неговото докажување (Колмогоров, Чаитин и самиот Гедел) и неговото значење за математиката, физиката, Компјутерски наукии филозофијата.
Успенски В.А.
Предавањето е посветено на синтаксичката верзија на Геделовата теорема за нецелосност. Самиот Гедел ја докажал синтаксичката верзија користејќи посилна претпоставка од конзистентноста, имено таканаречената омега конзистентност.
Успенски В.А.
Предавања летно училиште « Модерна математика“, Дубна.
на тема: „ГОДЕЛОВА ТЕОРЕМА“
Курт Гедел
Курт Гедел е водечки експерт за математичка логика– роден на 28 април 1906 година во Брун (сега Брно, Чешка). Дипломирал на Универзитетот во Виена, каде ја одбранил својата докторска дисертација, а во 1933–1938 година бил доцент. По Аншлусот емигрирал во САД. Од 1940 до 1963 година Гедел работел во Институтот Принстон виши студии. Гедел - почесен доктор на универзитетите Јеил и Харвард, член Национална академијаНауки на САД и Американското филозофско друштво.
Во 1951 година, Курт Гедел беше награден со највисоко научна наградаСАД - Ајнштајн награда. Во една статија посветена на овој настан, друг голем математичар на нашето време, Џон фон Нојман, напиша: „Придонесот на Курт Гедел во модерната логика е навистина монументален. Ова е повеќе од обичен споменик. Ова е пресвртница што одвојува две епохи... Без никакво претерување, може да се каже дека работата на Гедел радикално ја промени темата на логиката како наука“.
Навистина, дури и сувиот список на достигнувањата на Гедел во математичката логика покажува дека нивниот автор во суштина ги поставил темелите за цели делови од оваа наука: теоријата на модели (1930; таканаречената теорема за комплетноста на пресметувањето на тесните предикати, покажувајќи, грубо кажано, доволноста на средствата на „формалната логика“ „за докажување на сите вистинити реченици изразени на нејзиниот јазик), конструктивната логика (1932–1933; резултира со можноста за редуцирање на одредени класи реченици од класичната логика на нивните интуиционистички аналози, што го постави основа за систематска употреба на „операции за вградување“ кои овозможуваат такво намалување на различни логички системиедни со други), формална аритметика (1932–1933; резултати за можноста за редуцирање на класичната аритметика на интуиционистичка аритметика, покажувајќи ја во извесна смисла конзистентноста на првата во однос на втората), теоријата на алгоритми и рекурзивни функции (1934; дефиниција на концептот на општа рекурзивна функција, која играше одлучувачка улогаво утврдувањето на алгоритамската нерешливост на голем број најважни проблеми во математиката, од една страна. И во имплементацијата на логички и математички проблеми на електронските компјутери - од друга страна), аксиоматска теорија на множества (1938; доказ за релативната конзистентност на аксиомата на избор и хипотезата за континуум на Кантор од аксиомите на теоријата на множества, која го означи почетокот на серијата најважните резултатина релативната конзистентност и независност на множества-теоретските принципи).
Теорема за нецелосност на Гедел
Вовед
Во 1931 година, во еден од германските научни списанијасе појави релативно мала статија со прилично застрашувачки наслов „За формално нерешливите предлози на Principia Mathematica и сродните системи“. Нејзиниот автор бил дваесет и петгодишен математичар од Универзитетот во ВиенаКурт Гедел, кој подоцна работел во Институтот за напредни студии Принстон. Ова дело одигра одлучувачка улога во историјата на логиката и математиката. Во одлуката Универзитетот Харвардза доделување почесна награда на Гедел докторат(1952) таа беше окарактеризирана како една од најголеми достигнувањамодерна логика.
Меѓутоа, во времето на објавувањето, ниту името на делото на Гедел. Ниту неговата содржина не значеше ништо за повеќето математичари. Споменато во нејзиниот наслов, Principia Mathematica е монументална расправа во три тома од Алфред Норт Вајтхед и Бертранд Расел за математичката логика и основите на математиката; запознавање со трактатот во никој случај не беше неопходен условЗа успешна работаво повеќето гранки од математиката. Интересот за прашањата обработени во работата на Гедел отсекогаш бил во сопственост на многу мала група научници. Во исто време, расудувањето дадено од Гедел во неговите докази беше толку невообичаено за своето време. Дека за нивно целосно разбирање беше потребно исклучително владеење на темата и познавање на литературата посветена на овие многу специфични проблеми.
Првата теорема за некомплетност
Првата теорема за нецелосност на Гедел, очигледно, е најзначајниот резултат во математичката логика. Звучи вака:
За произволна конзистентна формална и пресметлива теорија во која може да се докажат основните аритметички искази, може да се конструира вистинска аритметичка изјава, чија вистинитост не може да се докаже во рамките на теоријата. Со други зборови, било целосно корисна теорија, доволно за да ја претстави аритметиката, не може да биде и конзистентна и целосна.
Овде зборот „теорија“ значи „ бесконечно множество„Искази, од кои некои се верува дека се вистинити без доказ (таквите изјави се нарекуваат аксиоми), додека други (теореми) може да се заклучат од аксиомите, и затоа се верува (докажано) дека се вистинити. Фразата „теоретски докажлива“ значи „изведена од аксиомите и примитивите на теоријата (постојани симболи на азбуката) користејќи стандардна (прв ред) логика“. Теоријата е конзистентна (конзистентна) ако е невозможно да се докаже контрадикторна изјава во неа. Фразата „може да се конструира“ значи дека постои некоја механичка процедура (алгоритам) што може да конструира изјава заснована на аксиоми, примитиви и логика од прв ред. „Елементарната аритметика“ се состои од операции на собирање и множење на природни броеви. Добиената вистинита, но недокажлива изјава често се нарекува за дадена теорија како „Годелова секвенца“, но има бесконечен број други изјави во теоријата кои го имаат истото својство: недокажлива вистина во теоријата.
Претпоставката дека една теорија е пресметлива значи дека во принцип е можно да се имплементира компјутерски алгоритам ( компјутерска програма), кој (ако е дозволено да се пресметува за произволно долго време, до бесконечност) ќе пресмета список на сите теореми на теоријата. Всушност, доволно е да се пресмета само списокот на аксиоми и сите теореми можат ефикасно да се добијат од таков список.
Првата теорема за нецелосност беше насловена „Теорема VI“ во трудот на Гедел од 1931 година. За формално нерешливите предлози во Principia Mathematica и сродни системи I. Во оригиналната снимка на Гедел звучеше вака:
„Општиот заклучок за постоењето на нерешливи предлози е овој:
Теорема VI .
За секоја ω-конзистентна рекурзивна класа kФОРМУЛА постојат рекурзивниЗНАЦИ р такви што ниту (vген р), ниту ¬( vген р)не припаѓаат на Flg (к)(каде што е vБЕСПЛАТНА ПРОМЕНЛИВА р ) ».
Означување Flgдоаѓа од него. Folgerungsmenge- многу секвенци, гендоаѓа од него. Генерализација– генерализација.
Грубо кажано, изјавата на Гедел Гвели: „Вистината Гне може да се докаже“. Ако Гби можело да се докаже во рамките на теоријата, тогаш во овој случај теоријата би содржела теорема што се противречи на самата себе и затоа теоријата би била контрадикторна. Но ако Гнедокажливо, тогаш тоа е точно, и затоа теоријата е нецелосна (изјава Гне може да се заклучи во него).
Ова е објаснување на обичен англиски јазик природен јазик, и затоа не е целосно математички ригорозен. За да обезбеди ригорозен доказ, Гедел ги нумерирал исказите користејќи природни броеви. Во овој случај, теоријата што ги опишува броевите, исто така, припаѓа на множеството изјави. Прашањата за докажливоста на исказите во овој случај може да се претстават во форма на прашања за својствата на природните броеви, кои мора да бидат пресметливи доколку теоријата е целосна. Во овие термини, во изјавата на Гедел се наведува дека кај некои нема бројка одреден имот. Бројката со ова својство ќе биде доказ за недоследноста на теоријата. Ако постои таков број, теоријата е неконзистентна, спротивно на првичната претпоставка. Значи, под претпоставка дека теоријата е конзистентна (како што се претпоставува во премисата на теоремата), излегува дека таков број не постои, а изјавата на Гедел е вистинита, но во рамките на теоријата тоа е невозможно да се докаже ( па оттука и теоријата е нецелосна). Важен концептуален момент е дека е неопходно да се претпостави дека теоријата е конзистентна за да се прогласи за вистинита изјавата на Гедел.
Втората теорема за нецелосност на Гедел
Втората теорема за нецелосност на Гедел гласи вака:
За секоја формално рекурзивно набројлива (т.е. ефективно генерирана) теорија Т, вклучувајќи ги основните аритметички изјави за вистинитост и одредени формални изјави за докажливост, оваа теоријаТ вклучува тврдење за само-конзистентност ако и само ако теоријата Т е неконзистентна.
Со други зборови, доследноста на доволно богата теорија не може да се докаже со помош на оваа теорија. Сепак, може да испадне дека конзистентноста на еден специфична теоријаможе да се утврди со помош на друга, помоќна формална теорија. Но, тогаш се поставува прашањето за доследноста на оваа втора теорија итн.
Користете ја оваа теорема за да го докажете тоа интелигентна активностНе се сведува на пресметки, многумина се обидоа. На пример, уште во 1961 година, познатиот логичар Џон Лукас излезе со слична програма. Неговото размислување се покажа доста ранливо - сепак, тој ја постави задачата пошироко. Роџер Пенроуз зазема малку поинаков пристап, кој е целосно наведен во книгата, „од нула“.
Дискусии
Последиците од теоремите влијаат на филозофијата на математиката, особено оние формализми кои користат формална логикада ги дефинирате вашите принципи. Првата теорема за непотполност можеме да ја преформулираме на следниов начин: невозможно е да се најде сеопфатен систем на аксиоми што би можел да докаже Ситематематички вистини, а ниту една лага" Од друга страна, од гледна точка на строга формалност, оваа преформулација нема посебно значење, бидејќи претпоставува дека концептите „вистина“ и „лага“ се дефинирани во апсолутна смисла наместо во релативна смисла за секој конкретен систем.