Колмогоров, Драгалин - Введение в математическую логику, страница 2

пятому словоупотреблению. Подъем широкого интереса к математической логике не только среди математиков, ио и сред~и техников, произошел тогда, когда обнаружилось, что в рамках математической логики уже создан аппарат для расчета действия самых различных вычислительных и управляющих дискретных устройств. 2. В математической логике предметом исследования часто оказываются математические теории, такие как математический анализ, алгебра, элементарная геометрия, арифметика и др.

В логике математические теории изучаются в целом— и это одна из особенностей математической логики по сравнению с другими математическими дисциплинами. Прежде всего, изучаемую математическую теорию уточняют и описывают на базе строгого логико-математического языка. Этот этап называется формализацией теории и составляет.важную, хотя и предварительную, часть исследования теории. После формализации полученную формальную аксиоматическую теорию уже можно подвергнуть точному математическому изучению, можно ставить точные проблемы, получать математические результаты. Какие же вопросы можно ставить относительно теории в целом? Можно интересоваться непротиворечивостью теории, т.

е. интересоваться вопросом, не выводится ли в данной теории некоторое утверждение и его отрицание. Тай, Е помощью ме-. тода интерпретаций. Кэли и Клейн показали, что геометрия Лобачевского непротиворечива, если непротиворечива обычная евклидова геометрия. Вольшое впечатление на современников произвело откры- тие в начале нашего века Кантором и Расселом парадоксов в теории множеств. Это открытие свидетельствовало о том, что широко используемая и популярная (и в настоящее вре.

мя) теория множеств в ее наивном изложении является противоречивой теорией. Изучение этого явления в значительной мере способствовало развитию современных методов математической логики. Была сформулирована аксиоматическая теория Цермело =' Френкеля, в которой обычные способы вывода парадоксов уже не получаются. Программа Гильберта обоснования математики 'финитными средствами также в значительной степени связана с открытием парадоксов, Знаменитая вторая теорема Геделя, полученная в тридцатых годах нашего века, утверждает, коротко говоря, что непротиворечивость достаточно богатой теории не:может быть установлена средствами самой теории. Этот факт побуждает специалистов по основаниям математики изыскивать математические методы, с одной стороны, убедительные (с той или иной точки зрения) и, с другой стороны, не входящие в теорию, непротиворечивость которой изучается.

Очень многие исследования по неклассическим, модальным и интуиционистским логикам стимулированы этой идеей. Можно сказать, что к настоящему времени непротиворечивость таких теорий, как элементарная геометрия, арифметика, анализ, хорошо изучена и достаточно надежно обоснована. Непротиворечивость мощных аксиоматических теорий множеств, таких как система Цермело — Френкеля или теория Куайна, гораздо более проблематична. Большой интерес представляет изучение полноты той или иной теории. Во многих математических теориях время ог времени возникают конкретные проблемы, которые не удается ни доказать, ни опровергнуть.

Иногда это бываег в силу технической сложности самой проблемы, и, спустя определенное время, проблему все же удается разрешить. Однако в некоторых случаях ситуация совершенно иная; проблему просто невозможно ни доказать, ни опровергнуть в рамках исследуемой теории. Так, было показано, что подобными проблемами в теории множеств Цермело — Френкеля являются континуум-проблема Кантора и многие другие важные теоретико-множественные проблемы. Подчеркнем, что дано было точное доказательство того факта, что; например, аксиома выбора не может быть ни доказана, ни опровергнута в теории Цермело — Френкеля. Теорема Геделя о неполноте утверждает, что всякая достаточно богатая теория необходимо содержит утверждения, которые нельзя ни доказать, ни опровергнуть в рамках теории.

Тем не менее некоторые важные теории оказываются полными. Таковы, например, элементарная геометрия, теория векторных пространств. 3. Существенно бывает исследовать разрешимость той или иной теории. Так, Тарский в 1948 г. построил конкретный алгорифм, позволяющий по всякому утверждению элементарной геометрии выяснить, является ли это утверждение истинным или ложным. Каждый, кто в школьные годы трудился над задачами геометрии, может оценить зто открытие. В то же время логики умеют доказывать, что многие теории, например арифметика, анализ, теория множеств, неразрешимы, т.

е. что не существует алгорифма, позволяющего по всякому суждению теории узнавать, истинно оно или ложно. Вопрос о существовании тех или иных, алгорифмов занимает важное место в исследованиях логиков. Так, доказано, что не существует алгоритма, позволяющего решать вопрос о существовании решения у системы полиномнальных уравнений в целых' числах. В последнее время большое внимание уделяется изучению сложности алгорифмов. Так, например, недавно было показано, что арифметика сложения натуральных чисел, являющаяся разрешимой теорией, может иметь только очень сложные разрешающие алгорифмы. Вопросы построения оптимальных по сложности и по времени работы вычислительных устройств занимают важное место в теоретической кибернетике — науке, тесно.

связанной с математической логикой. Глава 1 НАЧАЛЬНЫЕ ПОНЯТИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ И ТЕОРИИ МНОЖЕСТВ й 1. СИНТАКСИС ЯЗЫКА МАТЕМАТИЧЕСКИХ И ЛОГИЧЕСКИХ ЗНАКОВ Некоторым знакам н комбинациям знаков мы приписываем самостоятельный смысл. Таковы следующие знаки н комбинации знаков: 5 2+2 2+2=5 (с которыми читатель, несомненно, встречался), Но таким отдельно взятым знакам, как +, = нли таким комбинациям знаков, как. 2+ 2+2= мы не придаем самостоятельного смысла. Среди имеющих самостоятельный смысл знаков и комбинаций знаков выделяются прежде всего 1. Имена предметов.

Таковы ех — 1 1, 2, 2/3, 412, е (как обозначение числа е), 5 — 3, 1пп х->9 х Здесь написаны семь имен четырех предметов, так как ех — 1 1= 1нп —, 2=4(2=5 — 3, х»а з т. е., например, 2 н 5 — 3 являются именами одного н того же ,предмета. Заметим, что такая комбинация знаков, как Э(ппь тоже является именем', а именно именем функции «сннус». Из имени функцииз1п н имени числа5можнообразовать нмя действительного числа з(п 5. Но что такое комбинация знаков х Это не имя предмета, а 2.

Им е н н а я ф о р м а. Именной формой называется выражение (комбинация знаков), содержащее знаки «переменных», которое превра- 1а щается в имя предмета, если вместо «переменных» поставить надлежащим образом выбранные имена предметов (в нашем примере вместо х можно подставлять имя любого числа, отличного от нуля). Данное общее представление.об-именных формах делается совершенно отчетливым только после дополнительных пояснений о подстановке вместо переменных. их частных «значений».

К этому мы будем еще неоднократно возвращаться. Заметьте, что е» вЂ” 1 1йп— » О х есть имя, а не именная форма с цеременным х. В этом выражении вместо х нельзя подставить имя какого-либо определенного числа: запись еее 1 1нп 1Ь Ю 15, бессмысленна. Можно лишь изменить обозначение переменной х на переменную у. Полученная запись 1йп ее — 1 е-ге У является именем того же числа 1. Приведем еще несколько примеров именных форм: Хе+ 2, ай!(а+ Я, 1йи — (" » В последнем из этих примеров «свободной переменной», вместо которой можно что-либо «подставлять», является только буква у. Соединяя два имени чисел знаками равенства или неравенства, получаем записи некоторых утверждений: 2+2 — 4 2~о..З« 2+2 5' Первые два из записанных утверждений верны, а третье ложно.

Но все это 3. Высказывания. Более сложный пример высказывания: ее е-~Е х Но что такое запись х= 1х~? Здесь нельзя поставить вопрос об истинности илн ложности. Не содержится никакого утверждения. Подставляя вместо х 11 обозначения неотрицательных чисел, будем получать верные высказывания 0=101 2=12~ 1000=11000~,- подставляя же обозначения отрицательных чисел — ложные: — 1= ~ — 11, — 1000= ~ — 1000~. Запись х= 1х1 есть 4.

Вы ска з ывательн ая форма. Так называют комбинации знаков, содержащие знаки переменных, которые превращаются в высказывания при замене переменных именами предметов. Имена предметов и именные формы называют, термами, высказывания и высказывательные формы — формулами, Термами и формуламн .исчерпываются комбинации знаков, которым приписывается самостоятельный смысл.

Иногда в математической логике термины «терм» н «формула» понимаются более узким образом, как комбинации знаков в некоторых точных логико-математических языках, например в так называемых языках первого порядка (см. гл, 11, $1). Рис. 1 Мы уже видели, что из термов можно сооружать новые термы и формулы. Рассмотрим в качестве примера «родословную» формулы «« — 1 1нп = 1 (см. рис. 1).