მათემატიკური ლოგიკის ერთ-ერთი ყველაზე ცნობილი თეორემა, იღბლიანი და უიღბლო ერთდროულად. ამაში ის აინშტაინის ფარდობითობის სპეციალურ თეორიას ჰგავს. ერთის მხრივ, თითქმის ყველას სმენია მათ შესახებ რაღაც. მეორეს მხრივ, პოპულარული ინტერპრეტაციით, აინშტაინის თეორია, როგორც მოგეხსენებათ, "ამბობს, რომ სამყაროში ყველაფერი შედარებითია". და გოდელის არასრულყოფილების თეორემა (შემდგომში უბრალოდ TGN), დაახლოებით თანაბრად თავისუფალ ხალხურ ფორმულირებაში, "ადასტურებს, რომ არის რაღაცეები გაუგებარი ადამიანის გონებისთვის". და ამიტომ ზოგი ცდილობს მის მორგებას, როგორც მატერიალიზმის წინააღმდეგ არგუმენტს, ზოგი კი პირიქით, მისი დახმარებით ამტკიცებს, რომ ღმერთი არ არსებობს. სასაცილოა არა მხოლოდ ის, რომ ორივე მხარე ერთდროულად არ შეიძლება იყოს მართალი, არამედ ისიც, რომ არც ერთი და არც მეორე არ აწუხებს იმის გარკვევას, თუ რას ამბობს სინამდვილეში ეს თეორემა.

Მერე რა? ქვემოთ შევეცდები "თითებზე" ვისაუბრო ამაზე. ჩემი ექსპოზიცია, რა თქმა უნდა, არ იქნება მკაცრი და ინტუიციური, მაგრამ მათემატიკოსებს ვთხოვ, მკაცრად არ განსაჯონ. შესაძლებელია არამათემატიკოსებისთვის (რომლებსაც, ფაქტობრივად, მეც ვეკუთვნი) ქვემოთ მოთხრობილი რაღაც ახალი და სასარგებლო იყოს.

მათემატიკური ლოგიკა მართლაც საკმაოდ რთული მეცნიერებაა და რაც მთავარია, არც ისე ნაცნობი. ის მოითხოვს ფრთხილად და მკაცრ მანევრებს, რომლებშიც მნიშვნელოვანია, რომ არ ავურიოთ მართლაც დადასტურებული ფაქტი იმაში, რომ „ეს უკვე გასაგებია“. თუმცა, იმედი მაქვს, რომ შემდეგი „TGN-ის დადასტურების მონახაზის“ გასაგებად მკითხველს დასჭირდება მხოლოდ სასკოლო მათემატიკის/კომპიუტერული მეცნიერების ცოდნა, ლოგიკური აზროვნების უნარი და 15-20 წუთი დრო.

გარკვეულწილად გამარტივებით, TGN ამტკიცებს, რომ საკმარისად რთულ ენებში არის დაუმტკიცებელი წინადადებები. მაგრამ ამ ფრაზაში თითქმის ყველა სიტყვას ახსნა სჭირდება.

დავიწყოთ იმით, რომ გავიგოთ რა არის მტკიცებულება. ავიღოთ რამდენიმე სასკოლო პრობლემა არითმეტიკაში. მაგალითად, მოითხოვოს შემდეგი გაურთულებელი ფორმულის სისწორის დამტკიცება: "" (შეგახსენებთ, რომ სიმბოლო იკითხება "ნებისმიერისთვის" და ეწოდება "უნივერსალური რაოდენობრივი მაჩვენებელი"). ეს შეიძლება დადასტურდეს იდენტურად გარდაქმნით, ვთქვათ, ასე:

ერთი ფორმულიდან მეორეზე გადასვლა ხდება გარკვეული ცნობილი წესების მიხედვით. მე-4 ფორმულიდან მე-5-ზე გადასვლა მოხდა, ვთქვათ, იმიტომ, რომ ყველა რიცხვი თავის ტოლია - ასეთია არითმეტიკის აქსიომა. და ამგვარად, დადასტურების მთელი პროცედურა ფორმულას თარგმნის ლოგიკურ მნიშვნელობად TRUE. შედეგი შეიძლება იყოს FALSE - თუ ჩვენ უარვყოფთ რაიმე ფორმულას. ამ შემთხვევაში ჩვენ დავამტკიცებთ მის უარყოფას. შესაძლებელია წარმოვიდგინოთ პროგრამა (და ასეთი პროგრამები რეალურად იწერება), რომელიც დაამტკიცებს ასეთ (და უფრო რთულ) წინადადებებს ადამიანის ჩარევის გარეშე.

ცოტა უფრო ფორმალურად განვაცხადოთ იგივე. დავუშვათ, გვაქვს კომპლექტი, რომელიც შედგება რომელიმე ანბანის სიმბოლოების სტრიქონებისგან და არსებობს წესები, რომლითაც ქვეჯგუფი ე.წ. განცხადებები- ანუ გრამატიკულად მნიშვნელოვანი ფრაზები, რომელთაგან თითოეული არის ჭეშმარიტი ან მცდარი. შეგვიძლია ვთქვათ, რომ არის ფუნქცია, რომელიც ემთხვევა განცხადებებს ორიდან ერთ-ერთი მნიშვნელობიდან: TRUE ან FALSE (ანუ ასახავს მათ ორი ელემენტისგან შემდგარი ლოგიკური სიმრავლით).

მოდით ვუწოდოთ ასეთ წყვილს - განცხადებების ერთობლიობა და ფუნქცია -დან - "განცხადებების ენა". გაითვალისწინეთ, რომ ყოველდღიური გაგებით ენის ცნება გარკვეულწილად უფრო ფართოა. მაგალითად, რუსული ფრაზა "კარგი, მოდი აქ!"არ არის ჭეშმარიტი და არა მცდარი, ანუ მათემატიკური ლოგიკის თვალსაზრისით, ეს არ არის განცხადება.

შემდგომში, ჩვენ გვჭირდება ალგორითმის ცნება. მის ოფიციალურ განმარტებას აქ არ მივცემ - ეს საკმაოდ შორს წაგვიყვანს. შემოვიფარგლები არაფორმალურად: "ალგორითმი"- ცალსახა ინსტრუქციების ეს თანმიმდევრობა („პროგრამა“), რომელიც სასრული რაოდენობის ნაბიჯებითაკონვერტებს შეყვანის მონაცემებს გამომავალში. დახრილი ფუნდამენტურად მნიშვნელოვანია - თუ პროგრამა ჩამოკიდებულია ზოგიერთ საწყის მონაცემზე, მაშინ ის არ აღწერს ალგორითმს. სიმარტივისთვის და ჩვენს შემთხვევაში გამოსაყენებლად, მკითხველს შეუძლია ჩათვალოს, რომ ალგორითმი არის მისთვის ცნობილ პროგრამირების ნებისმიერ ენაზე დაწერილი პროგრამა, რომელიც, მოცემული კლასის ნებისმიერი შეყვანის მონაცემისთვის, გარანტირებულია, რომ დაასრულებს მუშაობას ლოგიკური შედეგით.

მოდით ვკითხოთ საკუთარ თავს: არის თუ არა „დამმტკიცებელი ალგორითმი“ ყველა ფუნქციისთვის (ან, მოკლედ, "დედუქციური") ამ ფუნქციის ექვივალენტურია, ანუ თითოეული განცხადების თარგმნა ზუსტად იმავე ლოგიკურ მნიშვნელობად, როგორც მას? უფრო მოკლედ, იგივე კითხვა შეიძლება ჩამოყალიბდეს შემდეგნაირად: არის ყოველი ფუნქცია წინადადებების ერთობლიობაზე გამოთვლითი? როგორც უკვე მიხვდით, TGN-ის მოქმედებიდან გამომდინარეობს, რომ არა, არცერთი - არსებობს ამ ტიპის არაგამომთვლელი ფუნქციები. სხვა სიტყვებით რომ ვთქვათ, ყველა ჭეშმარიტი განცხადება არ შეიძლება დადასტურდეს.

შესაძლოა, ამ განცხადებამ შიდა პროტესტი გამოიწვიოს. ეს გამოწვეულია რამდენიმე გარემოებით. ჯერ ერთი, როცა სასკოლო მათემატიკას გვასწავლიან, ზოგჯერ ჩნდება მცდარი შთაბეჭდილება, რომ ფრაზები „თეორემა მართალია“ და „შესაძლებელია თეორემის დამტკიცება ან გადამოწმება“ თითქმის იდენტურია. მაგრამ თუ დაფიქრდებით, ეს სულაც არ არის აშკარა. ზოგიერთი თეორემა დადასტურებულია საკმაოდ მარტივად (მაგალითად, მცირე რაოდენობის ვარიანტების ჩამოთვლით), ზოგი კი ძალიან რთულია. განვიხილოთ, მაგალითად, ფერმას ცნობილი ბოლო თეორემა:

რომლის მტკიცებულებაც პირველი ფორმულირებიდან სამნახევარი საუკუნის შემდეგ იქნა ნაპოვნი (და ის შორს არის ელემენტარულისგან). აუცილებელია განვასხვავოთ განცხადების ჭეშმარიტება და მისი დამტკიცება. არსად არ გამომდინარეობს, რომ არ არსებობს ჭეშმარიტი, მაგრამ დაუმტკიცებელი (და არა სრულად გადამოწმებული) განცხადებები.

მეორე ინტუიციური არგუმენტი TGN-ის წინააღმდეგ უფრო დახვეწილია. დავუშვათ, გვაქვს რაიმე დაუმტკიცებელი (ამ დედუქციური ჩარჩოში) განცხადება. რა გვიშლის ხელს მის ახალ აქსიომად მიღებაში? ამრიგად, ჩვენ ოდნავ გავართულებთ ჩვენს მტკიცებულებათა სისტემას, მაგრამ ეს არ არის საშინელი. ეს არგუმენტი სავსებით სწორი იქნებოდა, თუ იქნებოდა სასრული რაოდენობის დაუმტკიცებელი წინადადებები. პრაქტიკაში შეიძლება მოხდეს შემდეგი - ახალი აქსიომის პოსტულაციის შემდეგ, წააწყდებით ახალ დაუმტკიცებელ განცხადებას. მიიღეთ ეს სხვა აქსიომად - წააწყდებით მესამეს. და ასე უსასრულოდ. ამბობენ დედუქტიკა დარჩებაო არასრული. ჩვენ ასევე შეგვიძლია მივიღოთ ძალისმიერი ზომები ისე, რომ დამადასტურებელი ალგორითმი დასრულდეს სასრული რაოდენობის ნაბიჯების შემდეგ, გარკვეული შედეგით ნებისმიერი ენის განცხადებისთვის. მაგრამ ამავე დროს, ის დაიწყებს ტყუილს - მიიყვანს სიმართლეს არასწორი განცხადებებისთვის, ან სიცრუისკენ - ერთგულისთვის. ასეთ შემთხვევებში ნათქვამია, რომ დედუქციური წინააღმდეგობრივი. ამრიგად, TGN-ის კიდევ ერთი ფორმულირება ასე ჟღერს: ”არსებობს წინადადების ენები, რომლებისთვისაც შეუძლებელია სრული თანმიმდევრული დედუქციები” - აქედან გამომდინარეობს თეორემის სახელი.

ზოგჯერ "გოდელის თეორემას" უწოდებენ განცხადებას, რომ ნებისმიერი თეორია შეიცავს პრობლემებს, რომელთა გადაჭრა შეუძლებელია თავად თეორიის ფარგლებში და მოითხოვს მის განზოგადებას. გარკვეული გაგებით, ეს მართალია, თუმცა ასეთი ფორმულირება უფრო აბნელებს საკითხს, ვიდრე არკვევს.

მე ასევე აღვნიშნავ, რომ თუ ჩვენ ვსაუბრობთ ჩვეულებრივ ფუნქციებზე, რომლებიც მასზე ასახავს რეალური რიცხვების სიმრავლეს, მაშინ ფუნქციის „გამოთვლადობა“ არავის გააკვირვებს (უბრალოდ არ აურიოთ „გამოთვლითი ფუნქციები“ და „გამოთვლითი რიცხვები“ - ეს სხვადასხვა რამეა). ნებისმიერმა სკოლის მოსწავლემ იცის, რომ, ვთქვათ, ფუნქციის შემთხვევაში, ძალიან უნდა გაგიმართლოს არგუმენტი, რათა ამ ფუნქციის მნიშვნელობის ზუსტი ათობითი წარმოდგენის გამოთვლის პროცესი სასრული რაოდენობის საფეხურებით დასრულდეს. და, სავარაუდოდ, თქვენ გამოთვალებთ მას უსასრულო სერიების გამოყენებით და ეს გაანგარიშება არასოდეს მიგვიყვანს ზუსტ შედეგამდე, თუმცა შეიძლება მიუახლოვდეს მას - უბრალოდ იმიტომ, რომ არგუმენტების უმეტესობის სინუსის მნიშვნელობა ირაციონალურია. TGN უბრალოდ გვეუბნება, რომ თუნდაც იმ ფუნქციებს შორის, რომელთა არგუმენტები არის სტრიქონები და რომელთა მნიშვნელობები არის ნული ან ერთი, არაგამოთვლითი ფუნქციები, თუმცა სრულიად განსხვავებულად არის მოწყობილი, ასევე არსებობს.

შემდგომში ჩვენ აღვწერთ "ფორმალური არითმეტიკის ენას". განვიხილოთ სასრული სიგრძის ტექსტის სტრიქონების კლასი, რომელიც შედგება არაბული ციფრებისგან, ცვლადებისაგან (ლათინური ანბანის ასოები), რომლებიც იღებენ ბუნებრივ მნიშვნელობებს, სივრცეებს, არითმეტიკული მოქმედებების ნიშნებს, თანასწორობას და უტოლობას, რაოდენობებს („არსებობს“) და („არსებობს“) ნებისმიერი“) და, შესაძლოა, კიდევ რამდენიმე სიმბოლო (მათი ზუსტი რიცხვი და შემადგენლობა ჩვენთვის უმნიშვნელოა). ნათელია, რომ ყველა ასეთი სტრიქონი არ არის მნიშვნელოვანი (მაგალითად, "" არის სისულელე). ამ კლასის მნიშვნელოვანი გამონათქვამების ქვეჯგუფი (ანუ სტრიქონები, რომლებიც ჭეშმარიტი ან მცდარია ჩვეულებრივი არითმეტიკის თვალსაზრისით) იქნება ჩვენი განცხადებების ნაკრები.

ფორმალური არითმეტიკული განცხადებების მაგალითები:

და ა.შ. ახლა მოდით ვუწოდოთ "ფორმულა თავისუფალი პარამეტრით" (FSP) სტრიქონი, რომელიც ხდება განცხადება, თუ მასში ამ პარამეტრის სახით ჩანაცვლდება ბუნებრივი რიცხვი. FSP-ის მაგალითები (პარამეტრით):

და ა.შ. სხვა სიტყვებით რომ ვთქვათ, FSPs ექვივალენტურია ბუნებრივი არგუმენტის ფუნქციების ლოგიკური მნიშვნელობით.

აღნიშნეთ ყველა FSP-ის სიმრავლე ასოებით. გასაგებია, რომ მისი შეკვეთა შესაძლებელია (მაგალითად, ჩვენ ჯერ ვწერთ ანბანის მიხედვით დალაგებულ ერთასოიან ფორმულებს, შემდეგ ორასოიან ფორმულებს და ა.შ. ჩვენთვის ფუნდამენტური არ არის, რომელ ანბანში იქნება შეკვეთა). ამრიგად, ნებისმიერი FSP შეესაბამება მის ნომერს შეკვეთილ სიაში და ჩვენ აღვნიშნავთ მას.

მოდით ახლა მივმართოთ TGN-ის დადასტურების ესკიზს შემდეგი ფორმულირებით:

• ფორმალური არითმეტიკის წინადადებების ენისთვის არ არსებობს სრული თანმიმდევრული გამოყვანა.

წინააღმდეგობით დავამტკიცებთ.

ასე რომ, დავუშვათ, რომ ასეთი დედუქციური არსებობს. მოდით აღვწეროთ შემდეგი დამხმარე ალგორითმი, რომელიც ბუნებრივ რიცხვს ანიჭებს ლოგიკურ მნიშვნელობას შემდეგნაირად:

მარტივად რომ ვთქვათ, ალგორითმი იძლევა მნიშვნელობას TRUE, თუ და მხოლოდ იმ შემთხვევაში, თუ FSP-ში ჩვენი ნომრის ჩანაცვლების შედეგი ჩვენს სიაში იძლევა ცრუ განცხადებას.

აქ ჩვენ მივედით ერთადერთ ადგილას, სადაც მკითხველს ვთხოვ, ჩემი სიტყვა აღიქვას.

ცხადია, ზემოაღნიშნული დაშვებით, ნებისმიერი FSP-დან შეიძლება ასოცირებული იყოს ალგორითმთან, რომელიც შეიცავს ბუნებრივ რიცხვს შესასვლელში და ლოგიკურ მნიშვნელობას გამოსავალზე. ნაკლებად აშკარაა პირიქით:

ამ ლემის დადასტურება მოითხოვს ალგორითმის ცნების ფორმალურ და არა ინტუიციურ განმარტებას. თუმცა, თუ ცოტა დაფიქრდებით, საკმაოდ დამაჯერებელია. მართლაც, ალგორითმები იწერება ალგორითმულ ენებზე, რომელთა შორის არის ისეთი ეგზოტიკური, როგორიცაა, მაგალითად, Brainfuck, რომელიც შედგება რვა ერთსიმიანი სიტყვისგან, რომელშიც, მიუხედავად ამისა, ნებისმიერი ალგორითმის განხორციელება შესაძლებელია. უცნაური იქნება, თუ ფორმალური არითმეტიკული ფორმულების უფრო მდიდარი ენა, რომელიც ჩვენ აღვწერეთ, უფრო ღარიბი აღმოჩნდება - თუმცა, ეჭვგარეშეა, ის არც თუ ისე შესაფერისია ჩვეულებრივი პროგრამირებისთვის.

ამ მოლიპულ ადგილის გავლის შემდეგ სწრაფად მივდივართ ბოლომდე.

ასე რომ, ჩვენ ზემოთ აღვწერეთ ალგორითმი. ლემის მიხედვით, რომლის დაჯერება გთხოვე, არსებობს ექვივალენტური FSP. მას აქვს გარკვეული ნომერი სიაში - ვთქვათ. ვკითხოთ საკუთარ თავს, რა აზრი აქვს? დაე ეს იყოს ჭეშმარიტი. შემდეგ, ალგორითმის კონსტრუქციის მიხედვით (და, შესაბამისად, მისი ექვივალენტური ფუნქციის) მიხედვით, ეს ნიშნავს, რომ რიცხვის ფუნქციაში ჩანაცვლების შედეგი არის FALSE. საპირისპირო მოწმდება იმავე გზით: FALSE-დან მოყვება TRUE. ჩვენ მივედით წინააღმდეგობაში, რაც ნიშნავს, რომ თავდაპირველი ვარაუდი მცდარია. ამრიგად, ფორმალური არითმეტიკისთვის არ არსებობს სრული თანმიმდევრული გამოქვითვა. ქ.ე.დ.

აქ მიზანშეწონილია გავიხსენოთ ეპიმენიდესი (იხ. პორტრეტი სათაურში), რომელმაც, როგორც მოგეხსენებათ, განაცხადა, რომ ყველა კრეტეელი მატყუარაა, რადგან თავადაც კრეტელია. უფრო ლაკონური ფორმულირებით, მისი განცხადება (ცნობილია როგორც "მატყუარა პარადოქსი") შეიძლება ჩამოყალიბდეს ასე: "მე ვიტყუები". სწორედ ასეთი განცხადება, რომელიც თავისთავად ამტკიცებს მის სიცრუეს, გამოვიყენეთ დასამტკიცებლად.

დასასრულს, მინდა აღვნიშნო, რომ TGN არ აცხადებს რაიმე განსაკუთრებულ გასაკვირს. ყოველივე ამის შემდეგ, ყველა დიდი ხანია მიჩვეულია იმ ფაქტს, რომ ყველა რიცხვი არ შეიძლება იყოს წარმოდგენილი ორი მთელი რიცხვის თანაფარდობით (გახსოვდეთ, ამ განცხადებას აქვს ძალიან ელეგანტური მტკიცებულება, რომელიც ორ ათასზე მეტი წლისაა?). და რაციონალური კოეფიციენტების მრავალწევრების ფესვები ასევე არ არის ყველა რიცხვი. ახლა კი აღმოჩნდა, რომ ბუნებრივი არგუმენტის ყველა ფუნქცია არ არის გამოთვლადი.

მოცემული მტკიცებულების ესკიზი იყო ფორმალური არითმეტიკისთვის, მაგრამ ძნელი არ არის იმის დანახვა, რომ THN ვრცელდება ბევრ სხვა წინადადების ენაზეც. რა თქმა უნდა, ყველა ენა ასე არ არის. მაგალითად, მოდით განვსაზღვროთ ასეთი ენა:

• ”ნებისმიერი ფრაზა ჩინურ ენაზე არის ჭეშმარიტი განცხადება, თუ იგი შეიცავს ამხანაგ მაო ცე ტუნგის ციტატათა წიგნში და არასწორია, თუ ის არ შეიცავს.”

შემდეგ შესაბამისი სრული და თანმიმდევრული დამადასტურებელი ალგორითმი (მას შეიძლება ეწოდოს "დოგმატური დედუქციური") ასე გამოიყურება:

• „გადახედეთ ამხანაგ მაო ცე ტუნგის ციტატების წიგნს, სანამ არ იპოვით განცხადებას, რომელსაც ეძებთ. თუ ის ნაპოვნია, მაშინ ის მართალია, ხოლო თუ ციტატების წიგნი დასრულდა და განცხადება არ არის ნაპოვნი, მაშინ ის მცდარია.

აქ გვიშველის ის ფაქტი, რომ ნებისმიერი ციტატა აშკარად სასრულია, ამიტომ „დამტკიცების“ პროცესი აუცილებლად დასრულდება. ამრიგად, TGN არ გამოიყენება დოგმატური განცხადებების ენაზე. მაგრამ ჩვენ ვსაუბრობდით რთულ ენებზე, არა?

მტკიცებულების იდეა არის გამოხატვის აგება, რომელიც მოწმობს მის შესახებ

საკუთარი დაუმტკიცებლობა. ეს აშენება შეიძლება გაკეთდეს სამ ეტაპად:

პირველი ეტაპი არის ფორმალურ არითმეტიკასა და მთელ რიცხვთა სიმრავლეს შორის შესაბამისობის დადგენა (გედელიზაცია);

მეორე ეტაპი არის რაიმე განსაკუთრებული ქონების აგება, რომლის შესახებაც უცნობია არის თუ არა ფორმალური არითმეტიკის თეორემა;

მესამე ეტაპი არის x-ის ნაცვლად გარკვეული მთელი რიცხვის ჩანაცვლება, რომელიც დაკავშირებულია თავისთან, ანუ ჩანაცვლება ყველა ამ რიცხვით.

პირველი ეტაპი. ფორმალური არითმეტიკის გოდელიზაცია

ფორმალური არითმეტიკა შეიძლება იყოს არითმეტიზებული (ე.ი. გადელიზირებული) შემდეგნაირად: მის თითოეულ თეორემას ენიჭება გარკვეული რიცხვი. თუმცა, ვინაიდან ნებისმიერი რიცხვი ასევე თეორემაა, მაშინ ნებისმიერი თეორემა შეიძლება ჩაითვალოს, ერთის მხრივ, როგორც ფორმალური არითმეტიკის თეორემა, ხოლო მეორე მხრივ, როგორც თეორემა ფორმალური არითმეტიკის თეორემების სიმრავლეზე, ე.ი. გარკვეული თეორემის დადასტურების შესაბამისი მეტათეორემა.

ამრიგად, შეგვიძლია დავასკვნათ, რომ ფორმალური არითმეტიკის სისტემა ასევე შეიცავს საკუთარ მეტასისტემას.

ჩვენ ახლა უფრო კონკრეტულად და დეტალურად წარმოგიდგენთ ჩვენს შედეგებს.

პირველ რიგში, თითოეულ სიმბოლოს და ფორმალურ არითმეტიკას შეგვიძლია დავაკავშიროთ სპეციალური კოდის აღნიშვნა, რომელსაც ამ შემთხვევაში გოდელის რიცხვს უწოდებენ.

მეორეც, სიმბოლოების თითოეულ თანმიმდევრობას მივანიჭებთ იგივე გოდელის რიცხვს ზოგიერთი კომპოზიციის ფუნქციის გამოყენებით. მოდით, სად არის სიმბოლოების თანმიმდევრობა, რომლებიც ქმნიან.

მესამე (და ეს არსებითია), აქსიომებისა და ჩანაცვლების წესების (ან ჩანაცვლების წესების) თანმიმდევრობის თითოეულ მტკიცებულებას ენიჭება რიცხვი, სადაც აღნიშნავს მტკიცებულებაში გამოყენებული თეორემების თანმიმდევრობას.

ამგვარად, ფორმალურ არითმეტიკაში ნებისმიერ მტკიცებულებას შეესაბამება გარკვეული რიცხვი - მისი გოდელის რიცხვი.ფორმალური არიმეტიკის ნებისმიერი მსჯელობა გარდაიქმნება გამოთვლებად ნატურალური რიცხვების სიმრავლეზე.

ასე რომ, სიმბოლოებით, თეორემებით, მტკიცებულებებით მანიპულირების ნაცვლად, შეგიძლიათ გამოიყენოთ

გამოთვლები მთელი რიცხვების სიმრავლეზე. ნებისმიერი გამოთქმა, როგორიცაა, მაგალითად, შემდეგი: დასამტკიცებელია ფორმალურ არითმეტიკაში“, ახლა შეესაბამება გარკვეულ რიცხვს, რომელსაც აღვნიშნავთ როგორც

ჩამოვაყალიბოთ შემდეგი წინადადება.

ფორმალური მეტაარითმეტიკა შეიცავს ნატურალური რიცხვების სიმრავლეს და ის თავად შედის ფორმალური არითმეტიკის ინტერპრეტაციაში.

ფორმალური არითმეტიკის ეს მდგომარეობა წააგავს ბუნებრივ ენას: ბოლოს და ბოლოს, არაფერი გვიშლის ხელს, გამოვიყენოთ იგი მასში მისი ძირითადი ცნებებისა და წესების ჩამოსაყალიბებლად.

ფუნქციის სწორი არჩევანი საშუალებას აძლევს ადამიანს გააკეთოს ცალსახა გადასვლა A-დან A-ზე, ანუ მივანიჭოთ ორი განსხვავებული რიცხვი-რიცხვი ორ სხვადასხვა მტკიცებულებას. მაგალითად, შეგიძლიათ აირჩიოთ გოდელის რიცხვები ისე, რომ ფორმალური არითმეტიკის ანბანის თითოეულ სიმბოლოს ჰქონდეს თავისი მარტივი რიცხვი, როგორც ეს ნაჩვენებია, მაგალითად, ცხრილში. 3.2.

ცხრილი 3.2

თითოეული ფორმულა (რომელიც შედგება 1-დან თავის მხრივ ცვალებადი სიმბოლოებისგან, კოდირებულია მიმდევრობით, რომელიც შედგება პირველი მარტივი რიცხვებისგან, ანუ რიცხვისგან.

სად არის მარტივი რიცხვი.

თავის მხრივ, მტკიცებულება, ანუ ფორმულების თანმიმდევრობა მსგავსი გზით იქნება კოდირებული რიცხვით.

და პირიქით, რიცხვების აგების ამ მეთოდის წყალობით, შესაძლებელი ხდება, გარკვეული რიცხვიდან დაწყებული, მისი მარტივ ფაქტორებად დაშლით (ნატურალური რიცხვების დაშლის უნიკალურობის გამო, მარტივი რიცხვების ხარისხების ნამრავლებად), დაბრუნება ორად. ნაბიჯები ექსპონენტებისკენ, ანუ პრიმიტიული სიმბოლოების ფორმალურ არითმეტიკამდე. რა თქმა უნდა, ამას ძირითადად თეორიული მნიშვნელობა აქვს, რადგან რიცხვები სწრაფად იზრდება.

რათა მათი მანიპულირება მოხდეს. თუმცა, უნდა აღინიშნოს, რომ ამ ოპერაციის ფუნდამენტური შესაძლებლობა აუცილებელია.

მაგალითი. მიეცით რიცხვი T, რომელიც შეესაბამება გარკვეულ მტკიცებულებას და წარმოადგენს მარტივი რიცხვების ნამრავლს:

ეს დაშლა ნიშნავს, რომ თეორემის მტკიცებულება შეიცავს ორ ეტაპს: ერთი შეესაბამება რიცხვს 1981027125 253, ხოლო მეორე რიცხვს 1981027125 211. ყოველი ამ რიცხვიდან ისევ მარტივ ფაქტორებად დაშლით, მივიღებთ.

ფორმალური არითმეტიკული ანბანის კოდირების ცხრილიდან (ცხრილი 3.2) ვხვდებით, რომ ჩვენი გოდელის რიცხვები ამ ორი რიცხვისთვის

დაემთხვევა შემდეგ მტკიცებულებას:

ფორმულა გამომდინარეობს ფორმულიდან

ამრიგად, მეტაარითმეტიკაში, ორიგინალური რიცხვის მნიშვნელობა მიიღება ფორმალური არითმეტიკიდან.

მეორე ფაზა. გოდელის ლემა

მტკიცებულებასთან დაკავშირებული ყველა T რიცხვი შეესაბამება ფორმალურ არითმეტიკაში დასამტკიცებელ თეორემას. „გაუდელიზებულ“ ფორმალურ არითმეტიკას არითმეტიზებულ ფორმალურ არითმეტიკას უწოდებენ. ვინაიდან ყოველი აქსიომა და არითმეტიზებული ფორმალური არითმეტიკის თითოეული წესი შეესაბამება რაიმე არითმეტიკულ ოპერაციას, მაშინ სისტემატიზებული შემოწმების დახმარებით შესაძლებელია დადგინდეს, შეესაბამება თუ არა მოცემული რიცხვი T T რიცხვის რომელიმე თეორემის მტკიცებულებას და ამ შემთხვევაში ფორმას. შერწყმული რიცხვების წყვილი. გამოხატულება და არიან კონიუგატები“ წარმოდგენილია ყველაზე არითმეტიზებულ ფორმალურ არითმეტიკაში. ეს ნიშნავს, რომ არსებობს გოდელის ნომერი, რომელიც ციფრულად ახდენს ამ განცხადებას.

ჩვენ მივედით გოდელის მტკიცების კრიტიკულ წერტილამდე. მოდით A იყოს არითმეტიზებული ფორმალური არითმეტიკის გამოხატულება, რომელიც შეიცავს თავისუფალ ცვლადს. ამის ნაცვლად, შეგიძლიათ გააკეთოთ რაიმე ტერმინის ჩანაცვლება. კერძოდ, შესაძლებელია A გამოსახულების ჩანაცვლება თავად A გამოსახულებით. ამ შემთხვევაში რიცხვ-გამოხატვა A ერთდროულად ასრულებს ორ განსხვავებულ როლს (იხ. ზემოაღნიშნული კონსტრუქციები

კანტორი და რიჩარდ): ეს არის როგორც ჩანაცვლების, ასევე მიღებული ტერმინის ნამდვილი გამოხატულება. ეს სპეციალური ჩანაცვლება აღინიშნა, როგორც So ფორმულა ნიშნავს, რომ რიცხვი არის გოდელის რიცხვი, რომელიც მიღებულია A გამოთქმის ჩანაცვლებით:

შემდეგ გოდელი აყალიბებს გამონათქვამს (რომელიც არ არის ცნობილი თეორემაა თუ არათეორემა), რომელშიც შემოაქვს ეს ჩანაცვლება. გამოთქმა ასე გამოიყურება:

მესამე ეტაპი. საბოლოო ჩანაცვლება

არითმეტიზებულ ფორმალურ არითმეტიკაში ეს გამონათქვამი წარმოდგენილია რიცხვითი ფორმით. დაე, E იყოს მისი გოდელის რიცხვი. ვინაიდან გამოთქმა შეიცავს თავისუფალ ცვლადს, ჩვენ გვაქვს უფლება შევასრულოთ ჩანაცვლება - მეტი შეცვალოს რიცხვი E და აღვნიშნოთ - ჩაანაცვლოს E:

ამ მეორე გამონათქვამს აღვნიშნავთ a-ით და მის გოდელის რიცხვს E-ით. მოდით მივცეთ გამოხატვის e-ს ინტერპრეტაცია.

პირველი ინტერპრეტაცია. არ არსებობს ისეთი წყვილი, რომლისთვისაც ერთდროულად მართებულია შემდეგი: ერთი მხრივ, T არის თავისთავად არითმეტიზებული თეორემის არითმეტიზებული მტკიცებულების რიცხვი და, მეორე მხრივ, იქნება ჩანაცვლება, მაგრამ რადგან არსებობს იგივე ტრანსფორმაცია, როგორც სხვები, გამოსახულია ტერმინებით და მათი კოდური აღნიშვნით - გოდელის რიცხვები და, შესაბამისად, ასეთი რიცხვი არსებობს. მაშინ შესაძლოა რიცხვი T არ არსებობს.

მეორე ინტერპრეტაცია. არ არსებობს თეორემის T არითმეტიზებული მტკიცებულება, რომელიც იქნება E-ს -ჩანაცვლება. ასე რომ, თუ მტკიცებულება არ არსებობს, ეს იმიტომ ხდება, რომ ის თავისთავად არ არის თეორემა. ეს იწვევს მესამე ინტერპრეტაციას.

მესამე ინტერპრეტაცია. გამოთქმა, რომლის გოდელის რიცხვი არის E-ის ჩანაცვლება, არ არის თეორემა არითმეტიზებულ ფორმალურ არითმეტიკაში. მაგრამ სწორედ აქ მდგომარეობს წინააღმდეგობა, რადგან კონსტრუქციით ის თავისთავად არის E-ის ჩანაცვლება, ხოლო რიცხვი კონსტრუქციით სხვა არაფერია, თუ არა თავად რიცხვი E. ეს გულისხმობს e-ის ბოლო ინტერპრეტაციას.

09სენ

მათემატიკური აქსიომების ნებისმიერი სისტემა, დაწყებული სირთულის გარკვეული დონიდან, არის შინაგანად არათანმიმდევრული ან არასრული.

1900 წელს პარიზში გაიმართა მათემატიკოსთა მსოფლიო კონფერენცია, სადაც დევიდ გილბერტი(დევიდ ჰილბერტი, 1862–1943) თეზისების სახით გამოკვეთა 23 ყველაზე მნიშვნელოვანი, მისი აზრით, ამოცანა, რომლებიც უნდა გადაეჭრათ მომავალი მეოცე საუკუნის თეორეტიკოსებს. მისი სიის მეორე ნომერი იყო ერთ-ერთი იმ მარტივი პრობლემისგან, რომელიც აშკარად ჩანს, სანამ ცოტა ღრმად არ ჩათხარავთ. თანამედროვე თვალსაზრისით, ეს იყო კითხვა: საკმარისია მათემატიკა თავისთავად? ჰილბერტის მეორე დავალება შემცირდა მკაცრად დამტკიცების აუცილებლობით, რომ აქსიომების სისტემა - მათემატიკაში მიღებული ძირითადი განცხადებები, როგორც საფუძველი მტკიცებულების გარეშე - არის სრულყოფილი და სრული, ანუ ის საშუალებას აძლევს მათემატიკურ აღწერას ყველაფერი, რაც არსებობს. საჭირო იყო იმის დამტკიცება, რომ შესაძლებელია აქსიომათა ისეთი სისტემის დაყენება, რომელიც, პირველ რიგში, იქნება ურთიერთთანმიმდევრული და მეორეც, მათგან შეიძლება გამოვიტანოთ დასკვნა ნებისმიერი განცხადების ჭეშმარიტებასთან ან მცდარობასთან დაკავშირებით.

ავიღოთ მაგალითი სკოლის გეომეტრიიდან. სტანდარტულ ევკლიდეს პლანიმეტრიაში (სიბრტყეზე გეომეტრია) უპირობოდ შეიძლება დადასტურდეს, რომ დებულება „სამკუთხედის კუთხეების ჯამი არის 180°“ მართალია, ხოლო დებულება „სამკუთხედის კუთხეების ჯამი არის 137°. "ყალბია. არსებითად საუბრისას, ევკლიდეს გეომეტრიაში ნებისმიერი განცხადება არის მცდარი ან ჭეშმარიტი, ხოლო მესამე არ არის მოცემული. და მეოცე საუკუნის დასაწყისში მათემატიკოსებს გულუბრყვილოდ სჯეროდათ, რომ იგივე სიტუაცია უნდა შეინიშნოს ნებისმიერ ლოგიკურად თანმიმდევრულ სისტემაში.

შემდეგ კი 1931 წელს ზოგიერთი ვენელი სათვალე მათემატიკოსი კურტ გოდელი- აიღო და გამოაქვეყნა მოკლე სტატია, რომელმაც უბრალოდ დაამყარა ეგრეთ წოდებული „მათემატიკური ლოგიკის“ მთელი სამყარო. გრძელი და რთული მათემატიკური და თეორიული პრეამბულების შემდეგ, მან ფაქტიურად დაადგინა შემდეგი. ავიღოთ ნებისმიერი განცხადება, როგორიცაა: „დაშვება #247 ლოგიკურად დაუმტკიცებელია აქსიომების ამ სისტემაში“ და ვუწოდოთ მას „განცხადება A“. ასე რომ, გედელმა უბრალოდ დაამტკიცა აქსიომების ნებისმიერი სისტემის შემდეგი საოცარი თვისება:

„თუ A დებულება შეიძლება დადასტურდეს, მაშინ არა-ა განცხადება შეიძლება დადასტურდეს“.

სხვა სიტყვებით რომ ვთქვათ, თუ შესაძლებელია დებულების „დაშვება 247 არ არის დასამტკიცებელი“ მართებულობის დადასტურება, მაშინ ასევე შესაძლებელია დადასტურდეს განცხადების მართებულობა „დაშვება 247 დასამტკიცებელია“. ანუ, ჰილბერტის მეორე პრობლემის ფორმულირებას დავუბრუნდეთ, თუ აქსიომების სისტემა დასრულებულია (ანუ მასში არსებული ნებისმიერი განცხადება შეიძლება დადასტურდეს), მაშინ ის არათანმიმდევრულია.

ერთადერთი გამოსავალი ამ სიტუაციიდან არის აქსიომების არასრული სისტემის მიღება. ანუ უნდა შევეგუოთ იმ ფაქტს, რომ ნებისმიერი ლოგიკური სისტემის კონტექსტში კვლავ გვექნება „ა“ ტიპის განცხადებები, რომლებიც აშკარად ჭეშმარიტი ან მცდარია და მათი ჭეშმარიტების მსჯელობა მხოლოდ აქსიომატიკის ფარგლებს გარეთ შეგვიძლია. მიღებული. თუ ასეთი განცხადებები არ არის, მაშინ ჩვენი აქსიომატიკა წინააღმდეგობრივია და მის ფარგლებში აუცილებლად იქნება ფორმულირებები, რომელთა დამტკიცებაც და უარყოფაც შეიძლება.

ასე რომ, გოდელის პირველი, ანუ სუსტი, არასრულყოფილების თეორემის ფორმულირება არის: "აქსიომების ნებისმიერი ფორმალური სისტემა შეიცავს გადაუჭრელ ვარაუდებს". მაგრამ გოდელი აქ არ გაჩერებულა, ჩამოაყალიბა და დაამტკიცა გოდელის მეორე ან ძლიერი არასრულყოფილების თეორემა: „აქსიომების ნებისმიერი სისტემის ლოგიკური სისრულე (ან არასრული) ამ სისტემის ფარგლებში ვერ დადასტურდება. მის დასამტკიცებლად ან უარყოფისთვის საჭიროა დამატებითი აქსიომები (სისტემის გაძლიერება).

უფრო უსაფრთხო იქნებოდა ვიფიქროთ, რომ გოდელის თეორემები აბსტრაქტულია და არ გვეხება, არამედ მხოლოდ ამაღლებული მათემატიკური ლოგიკის სფეროებს, მაგრამ სინამდვილეში აღმოჩნდა, რომ ისინი პირდაპირ კავშირშია ადამიანის ტვინის სტრუქტურასთან. ინგლისელმა მათემატიკოსმა და ფიზიკოსმა როჯერ პენროზმა (დაიბადა 1931 წელს) აჩვენა, რომ გოდელის თეორემებიშეიძლება გამოყენებულ იქნას ადამიანის ტვინსა და კომპიუტერს შორის ფუნდამენტური განსხვავებების არსებობის დასამტკიცებლად. მისი მსჯელობის აზრი მარტივია. კომპიუტერი მუშაობს მკაცრად ლოგიკურად და არ ძალუძს დარწმუნდეს, არის თუ არა დებულება A ჭეშმარიტი თუ მცდარი, თუ ის სცილდება აქსიომატიკის ფარგლებს და ასეთი დებულებები, გოდელის თეორემის მიხედვით, აუცილებლად არსებობს. ადამიანს, რომელსაც აწყდება ასეთი ლოგიკურად დაუსაბუთებელი და უტყუარი განცხადება A, ყოველთვის შეუძლია განსაზღვროს მისი სიმართლე ან სიცრუე - ყოველდღიური გამოცდილებიდან გამომდინარე. ყოველ შემთხვევაში, ამ მხრივ, ადამიანის ტვინი აღემატება სუფთა ლოგიკური სქემებით შებოჭილ კომპიუტერს. ადამიანის ტვინს შეუძლია გაიგოს გოდელის თეორემებში მოცემული ჭეშმარიტების სრული სიღრმე, მაგრამ კომპიუტერი ვერასოდეს შეძლებს. ამრიგად, ადამიანის ტვინი არის ყველაფერი, თუ არა კომპიუტერი. მას შეუძლია გადაწყვეტილების მიღება და ტურინგის ტესტი გაივლის.

მათემატიკური აქსიომების ნებისმიერი სისტემა, დაწყებული სირთულის გარკვეული დონიდან, არის შინაგანად არათანმიმდევრული ან არასრული.

1900 წელს პარიზში გაიმართა მათემატიკოსთა მსოფლიო კონფერენცია, რომელზეც დევიდ ჰილბერტმა (1862-1943) აბსტრაქტების სახით წარმოადგინა მის მიერ ჩამოყალიბებული 23 ყველაზე მნიშვნელოვანი, მისი აზრით, პრობლემა, რომლებიც უნდა გადაეჭრათ თეორიტიკოსების მიერ. მომავალი მეოცე საუკუნის. მისი სიის მეორე ნომერი იყო ერთ-ერთი იმ მარტივი პრობლემისგან, რომელიც აშკარად ჩანს, სანამ ცოტა ღრმად არ ჩათხარავთ. თანამედროვე თვალსაზრისით, ეს იყო კითხვა: საკმარისია მათემატიკა თავისთავად? ჰილბერტის მეორე პრობლემა იყო სისტემის მკაცრად დამტკიცება აქსიომები- მათემატიკაში მიღებული ძირითადი განცხადებები, როგორც საფუძველი მტკიცებულების გარეშე - არის სრულყოფილი და სრული, ანუ საშუალებას გაძლევთ მათემატიკურად აღწეროთ ყველაფერი, რაც არსებობს. საჭირო იყო იმის დამტკიცება, რომ შესაძლებელია აქსიომათა ისეთი სისტემის დაყენება, რომელიც, პირველ რიგში, იქნება ურთიერთთანმიმდევრული და მეორეც, მათგან შეიძლება გამოვიტანოთ დასკვნა ნებისმიერი განცხადების ჭეშმარიტებასთან ან მცდარობასთან დაკავშირებით.

ავიღოთ მაგალითი სკოლის გეომეტრიიდან. სტანდარტული ევკლიდეს პლანიმეტრია(გეომეტრია სიბრტყეზე) შესაძლებელია უპირობოდ დაამტკიცოს, რომ დებულება „სამკუთხედის კუთხეების ჯამი არის 180°“ არის ჭეშმარიტი, ხოლო დებულება „სამკუთხედის კუთხეების ჯამი არის 137°“ მცდარი. არსებითად საუბრისას, ევკლიდეს გეომეტრიაში ნებისმიერი განცხადება არის მცდარი ან ჭეშმარიტი, ხოლო მესამე არ არის მოცემული. და მეოცე საუკუნის დასაწყისში მათემატიკოსებს გულუბრყვილოდ სჯეროდათ, რომ იგივე სიტუაცია უნდა შეინიშნოს ნებისმიერ ლოგიკურად თანმიმდევრულ სისტემაში.

შემდეგ კი, 1931 წელს, ზოგიერთმა ვენელმა სათვალე მათემატიკოსმა კურტ გოდელმა აიღო და გამოაქვეყნა მოკლე სტატია, რომელმაც უბრალოდ გადააქცია ეგრეთ წოდებული „მათემატიკური ლოგიკის“ მთელი სამყარო. გრძელი და რთული მათემატიკური და თეორიული პრეამბულების შემდეგ, მან ფაქტიურად დაადგინა შემდეგი. ავიღოთ ნებისმიერი განცხადება, როგორიცაა: „დაშვება #247 ლოგიკურად დაუმტკიცებელია აქსიომების ამ სისტემაში“ და ვუწოდოთ მას „განცხადება A“. ასე რომ, გედელმა უბრალოდ დაამტკიცა შემდეგი საოცარი თვისება ნებისმიერიაქსიომური სისტემები:

„თუ A დებულება შეიძლება დადასტურდეს, მაშინ არა-ა განცხადება შეიძლება დადასტურდეს“.

სხვა სიტყვებით რომ ვთქვათ, თუ შესაძლებელია განცხადების მართებულობის დადასტურება „ვარაუდი 247 არა დასამტკიცებელია“, მაშინ შესაძლებელია დადასტურდეს განცხადების მართებულობა „ვარაუდი 247 დასამტკიცებლად". ანუ, ჰილბერტის მეორე პრობლემის ფორმულირებას დავუბრუნდეთ, თუ აქსიომების სისტემა დასრულებულია (ანუ მასში არსებული ნებისმიერი განცხადება შეიძლება დადასტურდეს), მაშინ ის არათანმიმდევრულია.

ერთადერთი გამოსავალი ამ სიტუაციიდან არის აქსიომების არასრული სისტემის მიღება. ანუ, ჩვენ უნდა შევეგუოთ იმ ფაქტს, რომ ნებისმიერი ლოგიკური სისტემის კონტექსტში დაგვრჩება "ა" ტიპის განცხადებები, რომლებიც აშკარად მართალია ან მცდარია - და ჩვენ შეგვიძლია ვიმსჯელოთ მხოლოდ მათი ჭეშმარიტების შესახებ. გარეთჩვენ მიერ მიღებული აქსიომატიკის ჩარჩო. თუ ასეთი განცხადებები არ არის, მაშინ ჩვენი აქსიომატიკა წინააღმდეგობრივია და მის ფარგლებში აუცილებლად იქნება ფორმულირებები, რომელთა დამტკიცებაც და უარყოფაც შეიძლება.

ასე რომ, ფორმულირება პირველი, ან სუსტი გოდელის არასრულყოფილების თეორემები: "აქსიომების ნებისმიერი ფორმალური სისტემა შეიცავს გადაუჭრელ ვარაუდებს." მაგრამ გოდელი აქ არ გაჩერებულა, ფორმულირება და დამტკიცება მეორე,ან ძლიერი გოდელის არასრულყოფილების თეორემა: „არცერთი აქსიომათა სისტემის ლოგიკური სისრულე (ან არასრულყოფილება) ამ სისტემის ფარგლებში ვერ დადასტურდება. მის დასამტკიცებლად ან უარყოფისთვის საჭიროა დამატებითი აქსიომები (სისტემის გაძლიერება).“

უფრო უსაფრთხო იქნებოდა ვიფიქროთ, რომ გოდელის თეორემები აბსტრაქტულია და არ გვეხება, არამედ მხოლოდ ამაღლებული მათემატიკური ლოგიკის სფეროებს, მაგრამ სინამდვილეში აღმოჩნდა, რომ ისინი პირდაპირ კავშირშია ადამიანის ტვინის სტრუქტურასთან. ინგლისელმა მათემატიკოსმა და ფიზიკოსმა როჯერ პენროზმა (დაიბადა 1931 წელს) აჩვენა, რომ გოდელის თეორემების გამოყენება შესაძლებელია ადამიანის ტვინსა და კომპიუტერს შორის ფუნდამენტური განსხვავებების დასამტკიცებლად. მისი მსჯელობის აზრი მარტივია. კომპიუტერი მუშაობს მკაცრად ლოგიკურად და არ ძალუძს A დებულების ჭეშმარიტი თუ მცდარი დადგენა, თუ ის სცილდება აქსიომატიკის ფარგლებს და ასეთი დებულებები, გოდელის თეორემის მიხედვით, აუცილებლად არსებობს. ადამიანს, რომელსაც აწყდება ასეთი ლოგიკურად დაუმტკიცებელი და დაუსაბუთებელი განცხადება A, ყოველთვის შეუძლია განსაზღვროს მისი სიმართლე ან სიცრუე - ყოველდღიური გამოცდილებიდან გამომდინარე. ყოველ შემთხვევაში, ამ მხრივ, ადამიანის ტვინი აღემატება სუფთა ლოგიკური სქემებით შებოჭილ კომპიუტერს. ადამიანის ტვინს შეუძლია გაიგოს გოდელის თეორემებში მოცემული ჭეშმარიტების სრული სიღრმე, მაგრამ კომპიუტერი ვერასოდეს შეძლებს. ამრიგად, ადამიანის ტვინი არის ყველაფერი, თუ არა კომპიუტერი. მას შეუძლია გადაწყვეტილების მიღება, და ტურინგის ტესტი გაივლის.

მაინტერესებს ჰილბერტს ჰქონდა თუ არა წარმოდგენა, სადამდე მიგვიყვანს მისი კითხვები?

კურტ გოდელი, 1906-78 წწ

ავსტრიელი, შემდეგ ამერიკელი მათემატიკოსი. დაიბადა ბრუნში (ბრუნი, ახლა ბრნო, ჩეხეთი). დაამთავრა ვენის უნივერსიტეტი, სადაც დარჩა მათემატიკის განყოფილების მასწავლებლად (1930 წლიდან - პროფესორი). 1931 წელს მან გამოაქვეყნა თეორემა, რომელმაც მოგვიანებით მიიღო მისი სახელი. როგორც წმინდა აპოლიტიკური პიროვნება, ის უკიდურესად მძიმედ გადაურჩა ნაცისტი სტუდენტის მიერ მეგობრისა და დეპარტამენტის თანამშრომლის მკვლელობას და ღრმა დეპრესიაში ჩავარდა, რომლის რეციდივები მას სიცოცხლის ბოლომდე აწუხებდა. 1930-იან წლებში ის ემიგრაციაში წავიდა შეერთებულ შტატებში, მაგრამ დაბრუნდა მშობლიურ ავსტრიაში და დაქორწინდა. 1940 წელს, ომის მწვერვალზე, იგი იძულებული გახდა გაქცეულიყო ამერიკაში ტრანზიტით სსრკ-სა და იაპონიაში. გარკვეული პერიოდის განმავლობაში მუშაობდა პრინსტონის უმაღლესი განათლების ინსტიტუტში. სამწუხაროდ, მეცნიერის ფსიქიკამ ვერ გაუძლო და ის შიმშილით გარდაიცვალა ფსიქიატრიულ კლინიკაში, უარი თქვა ჭამაზე, რადგან დარწმუნებული იყო, რომ მის მოწამვლას აპირებდნენ.

უსპენსკი V.A.

გოდელის არასრულყოფილების თეორემა 1994 წ.

თეორიული კომპიუტერული მეცნიერება 130,1994, გვ.273-238.

შესაძლოა გოდელის არასრულყოფილების თეორემა მართლაც უნიკალურია. უნიკალური იმით, რომ ისინი მას მოიხსენიებენ, როდესაც სურთ დაამტკიცონ „ყველაფერი მსოფლიოში“ - ღმერთების არსებობიდან გონების არარსებობამდე. მე ყოველთვის მაინტერესებდა უფრო „პირველადი კითხვა“ – და ვინ არასრულობის თეორემას ეხება, არათუ ჩამოაყალიბა, არამედ დაამტკიცა? მე ვაქვეყნებ ამ სტატიას იმ მიზეზით, რომ იგი წარმოადგენს გოდელის თეორემის ძალიან მისაწვდომ ფორმულირებას. გირჩევთ, ჯერ წაიკითხოთ Tullio Regge Kurt Gödel-ის სტატია და მისი ცნობილი თეორემა

დასკვნა ჭეშმარიტების უნივერსალური კრიტერიუმის შეუძლებლობის შესახებ არის

ტარსკის მიერ კომბინაციით მიღებული შედეგის პირდაპირი შედეგი

გოდელის გადაუჭრელობის თეორემა ჭეშმარიტების საკუთარი თეორიით, შესაბამისად

რომელიც არ შეიძლება არსებობდეს ჭეშმარიტების უნივერსალური კრიტერიუმი თუნდაც შედარებით

რიცხვების თეორიის ვიწრო არეალი და, შესაბამისად, ნებისმიერი მეცნიერებისთვის, რომელიც იყენებს

არითმეტიკა. ბუნებრივია, ეს შედეგი უფრო მეტად ეხება ჭეშმარიტების ცნებას

ცოდნის ნებისმიერ არამათემატიკურ სფეროში, რომელშიც ის ფართოდ არის

არითმეტიკა გამოიყენება.

კარლ პოპერი

უსპენსკი ვლადიმერ ანდრეევიჩი დაიბადა 1930 წლის 27 ნოემბერს მოსკოვში. დაამთავრა მოსკოვის სახელმწიფო უნივერსიტეტის მექანიკა-მათემატიკის ფაკულტეტი (1952). ფიზიკა-მათემატიკის მეცნიერებათა დოქტორი (1964). პროფესორი, მექანიკა-მათემატიკის ფაკულტეტის მათემატიკური ლოგიკისა და ალგორითმების თეორიის კათედრის გამგე (1966 წ.). კითხულობს ლექციების კურსებს „შესავალი მათემატიკური ლოგიკაში“, „გამოთვლითი ფუნქციები“, „გოდელის სისრულის თეორემა“. მოამზადა 25 კანდიდატი და 2 მეცნიერებათა დოქტორი

1. პრობლემის განცხადება

არასრულყოფილების თეორემა, რომლის ზუსტ ფორმულირებასაც ამ თავის დასასრულს და შესაძლოა მოგვიანებით (თუ მკითხველს ეს აინტერესებს) და მტკიცებულება, დაახლოებით შემდეგს ამტკიცებს: გარკვეულ პირობებში ნებისმიერ ენაზე არის ჭეშმარიტი, მაგრამ დაუმტკიცებელი განცხადებები.

როდესაც თეორემას ასე ვაყალიბებთ, თითქმის ყველა სიტყვა გარკვეულ ახსნას მოითხოვს. ამიტომ, ჩვენ დავიწყებთ იმ სიტყვების მნიშვნელობის ახსნას, რომლებსაც ვიყენებთ ამ ფორმულირებაში.

ჩვენ არ მივცემთ ენის ყველაზე ზოგად შესაძლო განმარტებას, მირჩევნია შემოვიფარგლოთ იმ ენობრივი ცნებებით, რომლებიც მოგვიანებით დაგვჭირდება. არსებობს ორი ასეთი ცნება: „ენის ანბანი“ და „ენის ჭეშმარიტი განცხადებების ერთობლიობა“.

1.1.1. ანბანი

ანბანში ჩვენ ვგულისხმობთ ელემენტარული ნიშნების სასრულ ერთობლიობას (ანუ საგნებს, რომლებიც არ შეიძლება დაიყოს შემადგენელ ნაწილებად). ამ სიმბოლოებს ანბანის ასოებს უწოდებენ. ანბანის სიტყვაში ვგულისხმობთ ასოების სასრულ თანმიმდევრობას. მაგალითად, ჩვეულებრივი სიტყვები ინგლისურში (მათ შორის სათანადო სახელები) არის 54-ასოიანი ანბანის სიტყვები (26 პატარა ასო, 26 დიდი ასო, ტირე და აპოსტროფი). კიდევ ერთი მაგალითი - ნატურალური რიცხვები ათობითი აღნიშვნით არის 10-ასოიანი ანბანის სიტყვები, რომელთა ასოები ნიშნებია: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. აღსანიშნავად გამოვიყენებთ ჩვეულებრივ დიდ ასოებს. ანბანები. თუ L არის ანბანი, მაშინ L? აღნიშნავს L ანბანის ყველა სიტყვის ერთობლიობას, - მისი ასოებიდან წარმოქმნილი სიტყვები. ჩვენ ვივარაუდებთ, რომ ნებისმიერ ენას აქვს თავისი ანბანი, ასე რომ, ამ ენის ყველა გამონათქვამი (ანუ სხვადასხვა საგნების სახელები, განცხადებები ამ საგნების შესახებ და ა.შ.) ამ ანბანის სიტყვებია. მაგალითად, ნებისმიერი წინადადება ინგლისურ ენაზე, ისევე როგორც ინგლისურ ენაზე დაწერილი ნებისმიერი ტექსტი, შეიძლება ჩაითვალოს გაფართოებული 54-ასოიანი ანბანის სიტყვად, რომელიც ასევე შეიცავს პუნქტუაციის ნიშნებს, ინტერსიტყვის სივრცეს, წითელი ხაზის სიმბოლოს და შესაძლოა ზოგიერთს. სხვა სასარგებლო პერსონაჟები. თუ ვივარაუდებთ, რომ ენობრივი გამონათქვამები რაიმე ანბანის სიტყვებია, ჩვენ გამოვრიცხავთ განხილვისგან „მრავალფენიანი“ გამონათქვამებს, როგორიცაა ???f(x)dx. თუმცა, ეს შეზღუდვა არც თუ ისე მნიშვნელოვანია, რადგან ნებისმიერი ასეთი გამოთქმა, შესაბამისი კონვენციების გამოყენებით, შეიძლება "გადაჭიმული" ხაზოვან ფორმაში. რომელიმე კომპლექტი M შეიცავს L? ანბანის სიტყვათა ნაკრები L. თუ ჩვენ უბრალოდ ვიტყვით, რომ M არის სიტყვათა ნაკრები, მაშინ ვგულისხმობთ, რომ ეს არის რომელიმე ანბანის სიტყვა. ახლა ზემოაღნიშნული ენის ვარაუდი შეიძლება შემდეგნაირად ჩამოყალიბდეს: ნებისმიერ ენაში გამონათქვამების ნებისმიერი ნაკრები არის სიტყვათა ნაკრები.

1.1.2. ბევრი ჭეშმარიტი პრეტენზია

ვივარაუდოთ, რომ მოცემულია L სიმრავლის T ქვესიმრავლე? (სადაც L არის ზოგიერთი ენის ანბანი, რომელსაც ჩვენ განვიხილავთ), რომელსაც ეწოდება "ჭეშმარიტი განცხადებების" (ან უბრალოდ "ჭეშმარიტების") ნაკრები. პირდაპირ T ქვეჯგუფზე გადასვლისას, ჩვენ გამოვტოვებთ მსჯელობის შემდეგ შუალედურ საფეხურებს: ჯერ ერთი, L ანბანის რომელი სიტყვებია ენის კარგად ჩამოყალიბებული გამონათქვამები, ანუ მათ აქვთ გარკვეული მნიშვნელობა ამ ენის ინტერპრეტაციაში (მაგ. , 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 კარგად ჩამოყალიბებული გამოსახულებებია, ხოლო +=x არ არის); მეორეც, რომელი გამონათქვამებია ფორმულები, ე.ი. შეიძლება დამოკიდებული იყოს პარამეტრზე (მაგ., x=3, x=y, 2=3, 2=2); მესამე, ფორმულებიდან რომელია დახურული ფორმულები, ე.ი. განცხადებები, რომლებიც არ არის დამოკიდებული პარამეტრებზე (მაგალითად, 2=3, 2=2); და ბოლოს, რომელი დახურული ფორმულებია ჭეშმარიტი განცხადებები (მაგალითად, 2=2).

1.1.3. ფუნდამენტური ენათა წყვილი

1.2. "დაუმტკიცებელი"

„დაუმტკიცებელი“ ნიშნავს მტკიცებულებების არქონას.

1.3. მტკიცებულება

იმისდა მიუხედავად, რომ ტერმინი "მტკიცებულება" ალბათ ერთ-ერთი ყველაზე მნიშვნელოვანია მათემატიკაში (ბურბაკები თავიანთ წიგნს "მათემატიკის საფუძვლები" იწყებენ სიტყვებით: "ძველი ბერძნების დროიდან "მათემატიკა" იგივეს ნიშნავდა. ამბობს "მტკიცებულება"), მას არ აქვს ზუსტი განმარტება. ზოგადად, მტკიცების ცნება მთელი თავისი სემანტიკური განშტოებებით უფრო ფსიქოლოგიის სფეროს ეკუთვნის, ვიდრე მათემატიკას. მაგრამ როგორც ეს შეიძლება იყოს, მტკიცებულება უბრალოდ არგუმენტია, რომელიც ჩვენ თვითონ საკმაოდ დამაჯერებლად მიგვაჩნია, რათა დავარწმუნოთ ყველა.

როდესაც ჩაიწერება, მტკიცებულება ხდება სიტყვა რომელიმე ანბანში P, ისევე როგორც ნებისმიერი ინგლისური ტექსტი არის სიტყვა L ანბანში, რომლის მაგალითიც ზემოთ იყო მოყვანილი. ყველა მტკიცებულებათა სიმრავლე ქმნის P? სიმრავლის ქვესიმრავლეს (და საკმაოდ დიდ ქვესიმრავლეს). ჩვენ არ შევეცდებით ზუსტი განმარტების მიცემას ამ როგორც „გულუბრყვილო“ და „აბსოლუტური“ მტკიცებულების კონცეფციისა, ან - რაც ექვივალენტურია - განვსაზღვროთ P?-ის შესაბამისი ქვესიმრავლე. ამის ნაცვლად, ჩვენ განვიხილავთ ამ ბუნდოვანი კონცეფციის ოფიციალურ ანალოგს, რისთვისაც ჩვენ კვლავ გამოვიყენებთ ტერმინს „მტკიცებულება“ შემდგომში. ამ ანალოგს აქვს ორი ძალიან მნიშვნელოვანი მახასიათებელი, რაც განასხვავებს მას ინტუიციური კონცეფციისგან (თუმცა მტკიცებულების ინტუიციური იდეა გარკვეულწილად მაინც ასახავს ამ მახასიათებლებს). უპირველეს ყოვლისა, ჩვენ ვივარაუდებთ, რომ არსებობს მტკიცებულების განსხვავებული ცნებები, ანუ P?-ში დასაშვებია მტკიცებულებათა სხვადასხვა ქვეჯგუფი და ამაზე მეტიც: ჩვენ, ფაქტობრივად, ვივარაუდებთ, რომ თავად P-ის მტკიცებულებათა ანბანი შეიძლება შეიცვალოს. . შემდეგში, ჩვენ ვითხოვთ, რომ მტკიცებულების ყოველი ასეთი კონცეფციისთვის არსებობდეს ეფექტური მეთოდი, სხვა სიტყვებით რომ ვთქვათ, ალგორითმი, რომელიც აუცილებლად განსაზღვრავს, არის თუ არა ანბანის P მოცემული სიტყვა მტკიცებულება. ჩვენ ასევე ვვარაუდობთ, რომ არსებობს ალგორითმი, რომელიც ყოველთვის შეიძლება გამოყენებულ იქნას იმის დასადგენად, თუ რომელ განცხადებას ამტკიცებს მოცემული მტკიცებულება. (ბევრ სიტუაციაში, დადასტურებული განცხადება უბრალოდ ბოლო განცხადებაა იმ ნაბიჯების თანმიმდევრობით, რომლებიც ქმნიან მტკიცებულებას.)

ამრიგად, განმარტების ჩვენი საბოლოო ფორმულირება შემდეგია:

(1) გვაქვს ანბანი L (ენის ანბანი) და ანბანი P (მტკიცებულების ანბანი).

(2) ჩვენ გვეძლევა P სიმრავლე, რომელიც არის P?-ის ქვესიმრავლე და რომლის ელემენტებს ეწოდება "მტკიცებულებები". მომავალში ვივარაუდებთ, რომ ჩვენ ასევე გვაქვს ალგორითმი, რომელიც საშუალებას გვაძლევს განვსაზღვროთ, არის თუ არა ანბანის P თვითნებური სიტყვა P სიმრავლის ელემენტი, ანუ მტკიცებულება, თუ არა.

(3) ასევე გვაქვს ფუნქცია? (იმისთვის, რომ გავიგოთ ზუსტად რა არის დადასტურებული), ვისი დომენია? აკმაყოფილებს P???P? პირობას და ვისი დიაპაზონია P?-ში. ჩვენ ვვარაუდობთ, რომ გვაქვს ალგორითმი, რომელიც ითვლის ამ ფუნქციას (სიტყვის "ალგორითმი ითვლის ფუნქციას" ზუსტი მნიშვნელობა შემდეგია: ფუნქციის მნიშვნელობები მიიღება ამ ალგორითმის გამოყენებით - სპეციალური ტრანსფორმაციის წესების ნაკრები). ჩვენ ვიტყვით, რომ ელემენტი p? P არის სიტყვის დასტური?(p) ანბანის L.

სამეულს, რომელიც აკმაყოფილებს (1)-(3) პირობებს ეწოდება დედუქციური სისტემა L ანბანზე.

მკითხველისთვის, რომელიც იცნობს „მტკიცებულების“ განსაზღვრის ჩვეულ ხერხს „აქსიომისა“ და „დასკვნის წესის“ თვალსაზრისით, ჩვენ ახლა განვმარტავთ, თუ როგორ შეიძლება ჩაითვალოს ეს მეთოდი 1.3.2 ნაწილში მოცემული განმარტების განსაკუთრებულ შემთხვევად. ანუ, მტკიცებულება ჩვეულებრივ განისაზღვრება, როგორც ისეთი ენობრივი გამონათქვამების თანმიმდევრობა, რომელთაგან თითოეული ან აქსიომაა, ან ადრე მიღებულია უკვე არსებული დებულებებიდან ერთ-ერთი დასკვნის წესის გამოყენებით. თუ ჩვენი ენის ანბანს დავამატებთ ახალ სიტყვას *, მაშინ შეგვიძლია დავწეროთ ისეთი მტკიცებულება, როგორიცაა სიტყვა, რომელიც შედგენილია მიღებული ანბანის გამოყენებით: გამოთქმების თანმიმდევრობა ხდება სიტყვა C1*C2*...*Cn. ამ შემთხვევაში ფუნქციას, რომელიც განსაზღვრავს რა ზუსტად დადასტურდა, აქვს თავისი მნიშვნელობა ამ სიტყვის იმ ნაწილში, რომელიც მიჰყვება თანმიმდევრობით ბოლო ასოს. ალგორითმი, რომლის არსებობაც საჭიროა 1.3.2 ნაწილში. განმარტებები, ადვილად შეიძლება აშენდეს მას შემდეგ, რაც ჩვენ ზუსტად განვსაზღვრავთ სიტყვების "აქსიომა" და "დასკვნის წესი" რომელიმე მიღებული მნიშვნელობა.

1.4 ცდილობს ზუსტად ჩამოაყალიბოს არასრულობის თეორემა

1.4.1. Პირველი ცდა

"გარკვეულ პირობებში, L ანბანის ენის ფუნდამენტური წყვილისთვის და L-ზე დედუქციური სისტემისთვის, ყოველთვის არის სიტყვა T-ში, რომელსაც არ აქვს მტკიცებულება." ეს ვარიანტი კვლავ ბუნდოვნად გამოიყურება. კერძოდ, ჩვენ ადვილად შეგვეძლო შეგვექმნა ნებისმიერი რაოდენობის დედუქციური სისტემა, რომელსაც აქვს ძალიან ცოტა დასამტკიცებელი სიტყვა. მაგალითად, ცარიელ დედუქციურ სისტემაში (სადაც P = ?) საერთოდ არ არსებობს სიტყვები, რომლებსაც მტკიცებულებები ექნებათ.

1.4.2. მეორე ცდა

არის სხვა, უფრო ბუნებრივი მიდგომა. დავუშვათ, რომ მოგვცეს ენა - იმ გაგებით, რომ მოგვცეს ამ ენის ფუნდამენტური წყვილი. ახლა ჩვენ ვეძებთ ისეთ დედუქციურ სისტემას L-ზე (ინტუიციურად, ჩვენ ვეძებთ მტკიცებულების ტექნიკას), რომლითაც შეგვიძლია დავამტკიცოთ რაც შეიძლება მეტი სიტყვა T-დან, ტ. გოდელის თეორემის ყველა სიტყვა აღწერს სიტუაციას, რომელშიც ასეთი დედუქციური სისტემა (რომლითაც T-ში ყოველი სიტყვა დასამტკიცებელი იქნებოდა) არ არსებობს. ამრიგად, ჩვენ გვინდა ჩამოვაყალიბოთ შემდეგი განცხადება:

"გარკვეულ პირობებში ფუნდამენტურ წყვილთან დაკავშირებით, არ არსებობს ისეთი დედუქციური სისტემა, რომელშიც T-დან ყველა სიტყვას ჰქონდეს მტკიცებულება."

თუმცა, ასეთი განცხადება აშკარად მცდარია, რადგან საჭიროა მხოლოდ დედუქციური სისტემის აღება, რომელშიც P = L, P = P? და?(p) = p ყველა p-სთვის P?-ში; მაშინ ყოველი სიტყვა L-დან? ტრივიალურად დასამტკიცებელია. ამიტომ, ჩვენ უნდა მივიღოთ გარკვეული შეზღუდვა, თუ რომელ დედუქციურ სისტემებს ვიყენებთ.

1.5. თანმიმდევრულობა

სავსებით ბუნებრივი იქნებოდა იმის მოთხოვნა, რომ მხოლოდ „ჭეშმარიტი განცხადებები“, ანუ მხოლოდ T-დან სიტყვების დამტკიცება შეიძლება. ჩვენ ვიტყვით, რომ დედუქციური სისტემა თანმიმდევრულია ფუნდამენტური წყვილის მიმართ, თუ?(P)?T. ყველა შემდგომ მსჯელობაში ჩვენ დავინტერესდებით მხოლოდ ასეთი თანმიმდევრული დედუქციური სისტემებით. თუ ენას მოგვცემენ, მაშინ უკიდურესად მაცდური იქნება ისეთი თანმიმდევრული დედუქციური სისტემის პოვნა, რომელშიც ყველა ჭეშმარიტ განცხადებას ექნება მტკიცებულება. გოდელის თეორემის ვარიანტი, რომელიც გვაინტერესებს, ზუსტად ამბობს, რომ გარკვეულ პირობებში ფუნდამენტურ წყვილთან მიმართებაში შეუძლებელია ასეთი დედუქციური სისტემის პოვნა.

1.6. სისრულე

ნათქვამია, რომ დედუქციური სისტემა სრულია ფუნდამენტური წყვილის მიმართ, იმ პირობით, რომ ?(P)?T. მაშინ არასრულყოფილების თეორემის ჩვენი ფორმულირება იღებს შემდეგ ფორმას:

გარკვეულ პირობებში ფუნდამენტურ წყვილთან მიმართებაში, არ არსებობს ისეთი დედუქციური სისტემა L-ზე, რომელიც იქნება სრული და შედარებით თანმიმდევრული.