24. Арифметика Пеано. Теорема Геделя о неполноте (В.А. Захаров - Лекции)

Основыматематическойлогики и логическогопрограммированияЛЕКТОР: В.А. ЗахаровЛекция 18.Как устроена математика.Исчисление предикатов первогопорядка.Аксиоматические теории.Элементарная геометрия.Теория множествЦермело–Френкеля.Арифметика Пеано.Теорема Геделя о неполноте.модальныелогикиy6интуиционистскаялогикаyI@yдругиелогическиеоперации@@другаятеориядоказательствсемантика@логических@связок@другиеформылогическоговывода@@yдругие кванторылогикивысших порядков@iспециальные интерпретации-КЛАССИЧЕСКАЯЛОГИКАyаксиоматическиетеорииКак устроена математикаМатематика — это специфическая наука.Она не относится к числу естественных наук (физика,ботаника, геология, и пр.), т.

к. она не имеет дела ни сприродными явлениями, ни с эмпирическими знаниями.Она не относится к числу гуманитарных наук (философия,история, политология и пр. болтология), т. к она не занимаетсяни людской деятельностью, ни людскими воззрениями.Она занимается созданием, развитием и изучениемматематических теорий — умозрительных конструкций,которые строятся по строгим объективным законамформальной логики .Как устроена математикаСтанислав Лем сравнивал математику сбезумным портным, который шьет одеждудля неведомых существ.Портного не беспокоит, кому придетсявпору его одежда.Он лишь хочет, чтобы платье было сшитопрочно.Как устроена математикаС чего начинается рассказ о каждом разделе математики?IIIIВначале уславливаются о системе обозначений,определяют язык, на котором будут записыватьматематические утверждения (определяется синтаксисматематического языка ).Затем приходят к соглашению об основополагающихсвойствах, законах, которым должны удовлетворятьинтересующие нас операции и отношения надвоображаемыми объектами (формулируются аксиомыматематической теории ).Далее договариваются о том, какие средства обоснованияистинности математических утверждений считаютсядопустимыми (определяется аппарат логического вывода ).И после этого приступают к получению логическиобоснованных утверждений сформулированнойматематической теории (вывод теорем ).Вот так строятся формальные аксиоматические теории .Классическое исчисление предикатовКак можно аксиоматизировать теорию общезначимыхутверждений (формул)? Например, так:АКСИОМЫ.1.

Ax1. ϕ1 → (ϕ2 → ϕ1 ),2. Ax2. (ϕ1 → (ϕ2 → ϕ3 )) → ((ϕ1 → ϕ2 ) → (ϕ1 → ϕ3 )),3. Ax3. (ϕ1 & ϕ2 ) → ϕ1 ,4. Ax4. (ϕ1 & ϕ2 ) → ϕ2 ,5. Ax5. ϕ1 → (ϕ2 → (ϕ1 & ϕ2 )),6. Ax6. ϕ1 → (ϕ1 ∨ ϕ2 ),7. Ax7. ϕ2 → (ϕ1 ∨ ϕ2 ),8. Ax8. (ϕ1 → ϕ0 ) → ((ϕ2 → ϕ0 ) → ((ϕ1 ∨ ϕ2 ) → ϕ0 )),9. Ax9. ϕ1 → (¬ϕ1 → ϕ0 ),10. Ax10. ϕ1 ∨ ¬ϕ1 ,Классическое исчисление предикатовАКСИОМЫ.1. Ax11. ∀X ϕ(X ) → ϕ(t),2. Ax12. ϕ(t) → ∃X ϕ(X ),3. Ax13. ∀X (ϕ1 → ϕ2 (X )) → (ϕ1 → ∀X ϕ2 (X )),4. Ax14.

∀X (ϕ1 (X ) → ϕ2 ) → (∃X ϕ1 (X ) → ϕ2 ).ПРАВИЛА ВЫВОДА.1. Правило отделения (modus ponens)ϕ2. Правило обобщения∀X ϕϕ, ϕ → ψ,ψКлассическое исчисление предикатовЛОГИЧЕСКИЙ ВЫВОД.Пусть задано некоторое множество формул (гипотез) Γ .Тогда логическим выводом из множества гипотез Γназывается конечная последовательность формулϕ1 , ϕ 2 , . . . , ϕ n ,в которой каждая формула ϕi удовлетворяет одному изследующих условий:1. либо ϕi является аксиомой,2. либо ϕi является гипотезой, т. е.

ϕi ∈ Γ ,3. либо ϕi получается из предшествующих формул этойпоследовательности по правилу отделения или по правилуобобщения.В этом случае формула ϕn называется выводимой измножества Γ , и этот факт обозначается Γ ` ϕnФормула ϕ называется теоремой , если ∅ ` ϕ , и этот фактКлассическое исчисление предикатовИсчисление предикатов с равенством.Введем специальный двухместный предикатный символ = идобавим к аксиомам КИП следующие аксиомы равенства:1. Ax15. ∀X (X = X ),2. Ax16 ∀X , Y (X = Y → (ϕ(X , X ) → ϕ(X , Y ))).Полученную систему аксиом называют классическимисчислением предикатов с равенством КИП= .Алгебраическая система I называется нормальнойинтерпретацией , если для любой пары различных предметовd1 , d2 из области интерпретации DI верно соотношениеI 6|= d1 = d2 .Аксиоматические теории первого порядкаЭлементарная аксиоматическая теория образуется изисчисления предикатов с равенством за счетIограничения сигнатуры языка логики предикатовфиксированным конечным набором констант,функциональных и предикатных символов, обозначающихбазовые объекты, операции и отношения теории,Iдобавления к множеству аксиом исчисления предикатовспециальных (нелогических) аксиом, описывающихбазовые принципы теории.Таким образом образуются элементарная теория равенства,элементарная теория групп, элементарная теория полей,элементарная геометрия, элементарная арифметика,элементарная теория множеств, и др.Формулы ϕ , логически выводимые из аксиом элементарнойаксиоматической теории T , называются теоремами этойтеории и обозначаются записью T ` ϕ .Аксиоматические теории первого порядкаЭлементарная аксиоматическая теория T называетсяIнепротиворечивой , если не все формулы являютсятеоремами теории T , т.

е. существует такая формула ϕ ,для которой T 6` ϕ ;Iполной , если всякая формула или ее отрицание являютсятеоремами теории T , т. е. для любой формулы ϕ либоT ` ϕ , либо T ` ¬ϕ ;Iкатегоричной , если любые нормальные две моделитеории T изоморфны, т. е. для любой пары нормальныхинтерпретаций I1 , I2 верноI1 |= T и I2 |= T =⇒ I1 ∼= I2 ;Iразрешимой , если существует алгоритм, проверяющий,является ли произвольная формула теоремой теории T .Аксиоматическое устройство геометрииВпервые попытку аксиоматизировать геометрию предпринялЕвклид (3 в. до н. э.). Геометрическая теория Евклидаопиралась на 5 аксиом.К сожалению, система геометрических аксиом из «Начал»Евклида неполна.Вот пример истинного утверждения, которое нельзя вывести изаксиом и постулатов Евклида.Если прямая пересекает одну из сторон треугольника в точке,отличной от вершины треугольника, то эта прямая такжепересекает еще одну сторону треугольника.t @@@@t@@tАксиоматическое устройство геометрииСистематическое и основательное построение геометрическойсистемы аксиом было осуществлено Д.

Гильбертом (40 аксиом)в 1899 г. Более более краткую аксиоматику удалось построитьА. Тарскому и его ученика (12 аксиом).Аксиомы ТарскогоБудем рассматривать геометрический мир, все объектыкоторого — точки .На множестве точек есть всего лишь два базовых предиката:B(x, y, z)точка y лежит между точками x и z наодной прямойD(x, y, z, u)точка x отстоит от точки y на такое жерасстояние, что и точка z от точки uАксиоматическое устройство геометрииАксиомы T1–T51).

∀x, y , z (B(x, y , z) → B(z, y , x))(аксиома симметричности предиката B)2). ∀x, y , z, u (B(x, y , u)&B(y , z, u) → B(x, y , z))(аксиома транзитивности предиката B)3). ∀x, y D(x, y , y , x)(аксиома симметричности равенства длин отрезков)4). ∀x, y , z (D(x, y , z, z) → x = y )(аксиома нулевого отрезка)5). ∀x1 , y1 , x2 , y2 , x3 , y3(D(x1 , y1 , x2 , y2 )&D(x2 , y2 , x3 , y3 ) → D(x1 , y1 , x3 , y3 ))(аксиома транзитивности равенства длин отрезков)Аксиоматическое устройство геометрииАксиома T66).

∀x1 , y1 , z1 , u1 , x2 , y2 , z2 , u2(x1 6= y1 &y1 6= z1 &B(x1 , y1 , z1 )&B(x2 , y2 , z2 )&D(x1 , y1 , x2 , y2 )&D(y1 , z1 , y2 , z2 )&D(y1 , u1 , y2 , u2 )&D(x1 , u1 , x2 , u2 ) →→ D(z1 , u1 , z2 , u2 ))(аксиома пяти отрезков)tx1AtZu1AZA ZA ZZAZZAtZty1z1tx2uAtZ2AZA ZA ZZAZZZtAty2z2Аксиоматическое устройство геометрииАксиомы Аксиомы T7–T107). ∀x, y , z, u ∃v (B(x, y , z) & D(y , z, u, v ))(аксиома откладывания отрезка)8).

∀x, y , ∃z (B(x, z, y )&D(x, z, z, y ))(аксиома деления отрезка пополам)9). ∃x, y , z (¬B(x, y , z) & ¬B(x, z, y ) & ¬B(z, x, y ))(аксиома существования неколлинеарных точек)10). ∀x, y , z (¬B(x, y , z) & ¬B(x, z, y ) & ¬B(z, x, y ) →→ ∃v (D(v , x, v , y )&D(v , x, v , z)))(аксиома центра описанной окружности)Аксиоматическое устройство геометрииАксиома T1111). ∀x, y , z, u, v(D(x, u, x, v )&D(y , u, y , v )&D(z, u, z, v ) →→ (B(x, y , z) ∨ B(y , z, x) ∨ B(z, y , x)))(аксиома перпендикуляра к середине отрезка)t x@@@t yQQ @Q @QQ@Q@Q@tQHtu HHvHHHHHtzАксиоматическое устройство геометрииАксиома T1212). ∀x, y , z, u, v(B(x, u, z)&B(y , z, v ) →→ ∃w (B(y , u, w )&B(x, w , v )))(аксиома Паша)t v@t w@@t t@txu@z@ @t y@Аксиоматическое устройство геометрииАксиома T1313).

∀x ∃y , z (ϕ(y )&ψ(z) → B(x, y , z)) →→ ∀x 0 ∃y 0 , z 0 (ϕ(y 0 )&ψ(z 0 ) → B(y 0 , x 0 , z 0 ))(схема аксиом непрерывности)Аксиоматическое устройство геометрииОсновные свойства формальной геометрии ТарскогоТеоремаАксиоматическая теория T1–T13 (формальная геометрияТарского)Iнепротиворечива,Iполна,Iкатегорична,Iалгоритмически разрешима.К сожалению для школьников, разрешающая процедура,способная доказывать любую геометрическую теорему, имеетневероятно большую вычислительную сложность.Теория множествМНОЖЕСТВО — это основополагающее понятие современнойматематики. Понятие множества предложил во второйполовине 19 в. немецкий математик Георг Кантор.А что же такое множество?Поскольку это основополагающее понятие, строгогоопределения дать нельзя.

Это коллекция (семейство,совокупность, собрание) различных предметов (объектов,элементов ).Может ли математика спокойно развиваться, опираясь на стользыбкое основание?Теория множествПарадокс РасселаЭлементами множеств могут быть множества. Рассмотримколлекцию всех множеств, каждое из которых не является/ x} .своим собственным элементом: A = {x : x ∈У нас нет достаточных оснований не признавать этусовокупность множеств A множеством.Но тогда мы должны уметь давать ответ на вопрос:содержит ли множество A в качестве элемента само множествоA (т.

е. верно ли что A ∈ A ?)Ответ обескураживающий:IIесли A ∈ A , то по определению A верно A ∈/ A,а если A ∈/ A , то определению A верно A ∈ A .Теория множествЗначит, в наивной теории множеств существуютматематические утверждения, которые нельзя признать ниистинными, ни ложными. На основе такой расплывчатойтеории хорошей математики не построить.Может быть стоило бы исключить эту странную коллекцию Aиз числа множеств?Можно.