МАТЕМАТИ́ЧЕСКАЯ ЛО́ГИКА

МАТЕМАТИ́ЧЕСКАЯ ЛО́ГИКА (тео­ре­ти­че­ская ло­ги­ка, сим­во­ли­че­ская ло­ги­ка), раз­дел ма­те­ма­ти­ки, по­свя­щён­ный изу­че­нию ма­те­ма­тич. до­ка­за­тельств и во­про­сов, свя­зан­ных с ос­но­ва­ния­ми ма­те­ма­ти­ки.

Исторический очерк

Идея по­строе­ния уни­вер­саль­но­го язы­ка для всей ма­те­ма­ти­ки и фор­ма­ли­за­ции на ба­зе та­ко­го язы­ка ма­те­ма­тич. до­ка­за­тельств вы­дви­га­лась в 17 в. Г. В. Лейб­ни­цем. В сер. 19 в. по­яви­лись пер­вые ра­бо­ты по ал­геб­раи­за­ции ари­сто­те­ле­вой ло­ги­ки (Дж. Буль, 1847, и О. де Мор­ган, 1858). По­сле то­го как Г. Фре­ге (1879) и Ч. Пирс (1885) вве­ли в язык ал­геб­ры ло­ги­ки пре­ди­ка­ты, пред­мет­ные пе­ре­мен­ные и кван­то­ры, воз­ник­ла ре­аль­ная воз­мож­ность при­ме­нить этот язык к во­про­сам, свя­зан­ным с ос­но­ва­ния­ми ма­те­ма­ти­ки.

Соз­да­ние не­евк­ли­до­вых гео­мет­рий силь­но по­ко­ле­ба­ло уве­рен­ность ма­те­ма­ти­ков в аб­со­лют­ной на­дёж­но­сти гео­мет­рич. по­строе­ний, на ко­то­рых бы­ла ос­но­ва­на евк­ли­до­ва гео­мет­рия. По­ми­мо это­го в ре­зуль­та­те раз­ви­тия ис­чис­ле­ния бес­ко­неч­но ма­лых бы­ли об­на­ру­же­ны не­ожи­дан­ные при­ме­ры всю­ду не­пре­рыв­ных, но не диф­фе­рен­ци­руе­мых функ­ций. По­я­ви­лась по­треб­ность от­де­лить по­ня­тие дей­ст­ви­тель­но­го чис­ла от не­яс­но­го по­ня­тия «ве­ли­чи­ны», ко­то­рое бы­ло ос­но­ва­но на гео­мет­рич. пред­став­ле­ни­ях. Эта за­да­ча бы­ла ре­ше­на (с по­мо­щью разл. под­хо­дов) в ра­бо­тах К. Вей­ер­шт­рас­са, Р. Де­де­кин­да и Г. Кан­то­ра. Они по­каза­ли воз­мож­ность «ариф­ме­ти­за­ции» ана­ли­за и тео­рии функ­ций, в ре­зуль­та­те че­го в ка­че­ст­ве фун­да­мен­та всей клас­сич. ма­те­ма­ти­ки ста­ла рас­смат­ри­вать­ся ариф­ме­ти­ка це­лых чи­сел. За­тем бы­ла пред­при­ня­та ак­сио­ма­ти­за­ция ариф­ме­ти­ки (Де­де­кинд, 1888, Дж. Пеа­но, 1891). При этом Пеа­но соз­дал удоб­ную сим­во­ли­ку для ло­гич. язы­ка. Позд­нее этот язык был усо­вер­шен­ст­во­ван в ра­бо­те Б. Рас­се­ла и А. Уайт­хе­да «Прин­ци­пы ма­те­ма­ти­ки» (т. 1–3, 1910–13), где бы­ла пред­при­ня­та по­пыт­ка све­де­ния всей ма­те­ма­ти­ки к ло­ги­ке. Эта по­пыт­ка не увен­ча­лась ус­пе­хом, т. к. ока­за­лось не­воз­мож­ным вы­вес­ти из чис­то ло­гич. ак­си­ом су­ще­ст­во­ва­ние бес­ко­неч­ных мно­жеств. Хо­тя ло­гич. про­грам­ма Фре­ге – Рас­се­ла в ос­но­ва­ни­ях ма­те­ма­ти­ки не дос­тиг­ла сво­ей гл. це­ли – све­де­ния ма­те­ма­ти­ки к ло­ги­ке, в их ра­бо­тах был соз­дан бо­га­тый ло­гич. ап­па­рат, без ко­то­ро­го ста­нов­ле­ние М. л. как пол­но­цен­ной ма­те­ма­тич. дис­ци­п­ли­ны бы­ло бы не­воз­мож­но.

На ру­бе­же 19–20 вв. бы­ли об­на­ру­жены ан­ти­но­мии, свя­зан­ные с осн. по­ня­тия­ми тео­рии мно­жеств. Наи­бо­лее силь­ное впе­чат­ле­ние на со­вре­мен­ни­ков про­из­ве­ла ан­ти­но­мия Рас­се­ла (1903), ко­то­рая со­сто­ит в сле­дую­щем. Пусть $M$ есть мно­же­ст­во всех та­ких мно­жеств, ка­ж­дое из ко­то­рых не яв­ля­ет­ся сво­им собств. эле­мен­том. Мож­но убе­дить­ся, что мно­же­ст­во $M$ яв­ля­ет­ся сво­им эле­мен­том то­гда и толь­ко то­гда, ко­гда $M$ не яв­ля­ет­ся сво­им эле­мен­том. Вый­ти из соз­дав­ше­го­ся про­ти­во­ре­чия мож­но по­пы­тать­ся, сде­лав за­клю­че­ние, что та­ко­го мно­же­ст­ва $M$ не су­ще­ст­ву­ет. Од­на­ко ес­ли не мо­жет су­ще­ст­во­вать мно­же­ст­во, со­стоя­щее в точ­но­сти из всех эле­мен­тов, удов­ле­тво­ряю­щих чёт­ко оп­ре­де­лён­но­му ус­ло­вию, при­ве­дён­но­му вы­ше в оп­ре­де­ле­нии мно­же­ст­ва $M$, то нет га­ран­тий то­го, что не при­дёт­ся столк­нуть­ся с мно­же­ст­ва­ми, ко­то­рые так­же не су­ще­ст­ву­ют. Воз­ни­ка­ет во­прос, ка­ким долж­но быть оп­ре­де­ле­ние мно­же­ст­ва для то­го, что­бы это мно­же­ст­во су­ще­ст­во­ва­ло? Па­ра­докс Рас­се­ла по­ка­зал, что нуж­но как-то ог­ра­ни­чить кан­то­ров­скую тео­рию мно­жеств.

Л. Брау­эр вы­сту­пил (1908) про­тив при­ме­не­ния пра­вил клас­сич. ло­ги­ки к бес­ко­неч­ным мно­же­ст­вам. В вы­дви­ну­той им ин­туи­цио­ни­ст­ской про­грам­ме пред­ла­га­лось от­ка­зать­ся от рас­смот­ре­ния аб­ст­рак­ции ак­ту­аль­ной бес­ко­неч­но­сти, т. е. рас­смот­ре­ния бес­ко­неч­ных мно­жеств как за­вер­шён­ных со­во­куп­но­стей. До­пус­кая су­ще­ст­во­ва­ние сколь угод­но боль­ших на­ту­раль­ных чи­сел, ин­туи­цио­ни­сты вы­сту­па­ют про­тив рас­смот­ре­ния на­ту­раль­но­го ря­да как за­вер­шён­но­го мно­же­ст­ва. Они счи­та­ют, что в ма­те­ма­ти­ке вся­кое до­ка­за­тель­ст­во су­ще­ст­во­ва­ния то­го или ино­го объ­ек­та долж­но быть кон­ст­рук­тив­ным, т. е. долж­но со­про­во­ж­дать­ся по­строе­ни­ем это­го объ­ек­та. Ес­ли пред­по­ло­же­ние о том, что ис­ко­мый объ­ект не су­ще­ст­ву­ет, при­ве­ло к про­ти­во­ре­чию, то это, по мне­нию ин­туи­цио­ни­стов, не мо­жет рас­смат­ри­вать­ся как до­ка­за­тель­ст­во его су­ще­ст­во­ва­ния. Осо­бой кри­ти­ке со сто­ро­ны ин­туи­цио­ни­стов под­вер­га­ет­ся т. н. ис­клю­чён­но­го третье­го за­кон. Вви­ду то­го что этот за­кон пер­во­на­чаль­но рас­смат­ри­вал­ся при­ме­ни­тель­но к ко­неч­ным мно­же­ст­вам, а мно­гие свой­ст­ва ко­неч­ных мно­жеств не спра­вед­ли­вы для бес­ко­неч­ных мно­жеств (напр., что вся­кая собств. часть мень­ше це­ло­го), ин­туи­цио­ни­сты счи­та­ют не­пра­во­мер­ным при­ме­не­ние это­го за­ко­на к бес­ко­неч­ным мно­же­ст­вам. Так, напр., что­бы ут­вер­ждать, что Фер­ма Ве­ли­кая тео­ре­ма спра­вед­ли­ва или нет, ин­туи­цио­нист дол­жен ука­зать со­от­вет­ст­вую­щее до­ка­за­тель­ст­во, т. е. по­ка тео­ре­ма Фер­ма не до­ка­за­на, не до­пус­ка­ет­ся ут­вер­ждать, что эта тео­ре­ма ли­бо вер­на, ли­бо нет. Та­кое тре­бо­ва­ние ин­туи­цио­ни­стов мо­жет соз­дать за­труд­не­ние и для за­дач, свя­зан­ных с ко­неч­ны­ми мно­же­ст­ва­ми. Пусть из ур­ны, со­дер­жа­щей три чёр­ных и три бе­лых ша­ра, нек­то, за­крыв гла­за, дос­та­ёт один шар и тут же кла­дёт его об­рат­но. Ес­ли ни­кто не ви­дел этот шар, то мы не име­ем воз­мож­но­сти уз­нать, ка­ко­го он был цве­та. Од­на­ко вряд ли мож­но все­рь­ёз ос­па­ри­вать дос­то­вер­ность ут­вер­жде­ния, что этот шар был ли­бо чёр­но­го, ли­бо бе­ло­го цве­та.

Ин­туи­цио­ни­сты по­строи­ли свою, имею­щую ин­те­рес­ные осо­бен­но­сти, ма­те­ма­ти­ку, ко­то­рая яв­ля­ет­ся бо­лее слож­ной и гро­мозд­кой, чем клас­сич. ма­те­ма­ти­ка. По­ло­жи­тель­ный вклад ин­туи­цио­ни­стов в ис­сле­до­ва­ние во­про­сов ос­но­ва­ний ма­те­ма­ти­ки вы­ра­зил­ся в том, что они ещё раз под­черк­ну­ли раз­ли­чие ме­ж­ду кон­ст­рук­тив­ным и не­кон­ст­рук­тив­ным в ма­те­ма­ти­ке, про­ве­ли тща­тель­ный ана­лиз мн. труд­но­стей, с ко­то­ры­ми столк­ну­лась ма­те­ма­ти­ка в сво­ём раз­ви­тии, и тем са­мым спо­соб­ст­во­ва­ли их пре­одо­ле­нию.

Д. Гиль­берт на­ме­тил др. путь пре­одо­ле­ния труд­но­стей, воз­ник­ших в ос­но­ва­ни­ях ма­те­ма­ти­ки на ру­бе­же 19–20 вв. Этот путь, ба­зи­ро­вав­ший­ся на при­ме­нении ак­сио­ма­тич. ме­то­да рас­смот­ре­ния фор­маль­ных мо­де­лей со­дер­жа­тель­ной ма­те­ма­ти­ки и на ис­сле­до­ва­нии во­про­сов не­про­ти­во­ре­чи­во­сти та­ких мо­де­лей на­дёж­ны­ми фи­нит­ны­ми (ко­неч­ны­ми) сред­ст­ва­ми, по­лу­чил в ма­те­ма­ти­ке назв. фи­ни­тиз­ма Гиль­бер­та. При­зна­вая не­на­дёж­ность гео­мет­рич. ин­туи­ции, Гиль­берт пре­ж­де все­го тща­тель­но пе­ре­ра­бо­тал евк­ли­до­ву гео­мет­рию, ос­во­бо­ж­дая её от об­ра­ще­ния к ин­туи­ции. Ре­зуль­та­том та­кой пе­ре­ра­бот­ки яви­лись его «Ос­но­ва­ния гео­мет­рии» (1899).

Во­про­сы не­про­ти­во­ре­чи­во­сти разл. тео­рий по су­ще­ст­ву рас­смат­ри­ва­лись и до Д. Гиль­бер­та. Так, по­стро­ен­ная Ф. Клей­ном (1871) про­ек­тив­ная мо­дель Ло­ба­чев­ско­го гео­мет­рии сво­дит во­прос о не­про­ти­во­ре­чи­во­сти гео­мет­рии Ло­ба­чев­ско­го к не­про­ти­во­ре­чи­во­сти евк­ли­до­вой гео­мет­рии. Ана­ло­гич­но, не­про­ти­во­ре­чи­вость евк­ли­до­вой гео­мет­рии мож­но све­сти к не­про­ти­во­ре­чи­во­сти ма­те­ма­тич. ана­ли­за, т. е. к не­про­ти­во­ре­чи­во­сти тео­рии дей­ст­вит. чи­сел. Од­на­ко во­прос о том, ка­ки­ми сред­ст­ва­ми мож­но стро­ить мо­де­ли ана­ли­за и ариф­ме­ти­ки для до­ка­за­тель­ст­ва их не­про­ти­во­ре­чи­во­сти, ос­та­вал­ся от­кры­тым. За­слу­га Гиль­бер­та со­сто­ит в том, что он ука­зал пря­мой путь для ис­сле­дова­ния это­го во­про­са. Не­про­ти­во­ре­чи­вость дан­ной тео­рии оз­на­ча­ет, что в ней не мо­жет быть по­лу­че­но про­ти­во­ре­чие, т. е. не мо­жет быть до­ка­за­но не­ко­то­рое ут­вер­жде­ние $A$ и его от­ри­ца­ние $¬A$. Гиль­берт пред­ло­жил пред­став­лять рас­смат­ри­вае­мую тео­рию в ви­де фор­маль­ной ак­сио­ма­тич. сис­те­мы, в ко­то­рой бу­дут вы­во­ди­мы все те и толь­ко те ут­вер­жде­ния, ко­то­рые яв­ля­ют­ся тео­ре­ма­ми этой тео­рии. То­гда для до­ка­за­тель­ст­ва не­про­ти­во­ре­чи­во­сти дос­та­точ­но ус­та­но­вить не­вы­во­ди­мость в рас­смат­ри­вае­мой тео­рии не­ко­то­рых оп­ре­де­лён­ных ут­вер­жде­ний. Т. о., ма­те­ма­тич. тео­рия, не­про­ти­во­ре­чи­вость ко­то­рой мы хо­тим до­ка­зать, ста­но­вит­ся пред­ме­том изу­че­ния ма­те­ма­тич. нау­ки, ко­то­рую Гиль­берт на­звал ме­та­ма­те­ма­ти­кой (см. Ме­та­те­о­рия) или тео­ри­ей до­ка­за­тельств.

Д. Гиль­берт счи­тал, что па­ра­док­сы тео­рии мно­жеств вы­зва­ны не за­ко­ном ис­клю­чён­но­го третье­го, а «ско­рее тем, что ма­те­ма­ти­ки поль­зу­ют­ся не­до­пус­ти­мы­ми и бес­смыс­лен­ны­ми об­ра­зо­ва­ния­ми по­ня­тий, ко­то­рые в мо­ей тео­рии до­ка­за­тельств ис­клю­ча­ют­ся са­ми со­бой… От­нять у ма­те­ма­ти­ков за­кон ис­клю­чён­но­го третье­го – это то же, что за­брать у ас­тро­но­мов те­ле­скоп или за­пре­тить бок­сё­рам ис­поль­зо­вать ку­ла­ки». Гиль­берт пред­ла­гал раз­ли­чать «дей­ст­ви­тель­ные» и «иде­аль­ные» пред­ло­же­ния клас­сич. ма­те­ма­ти­ки. Пер­вые име­ют со­дер­жа­тель­ный смысл, а вто­рые не обя­за­ны его иметь. Пред­ло­же­ния, со­от­вет­ст­вую­щие упот­реб­ле­нию ак­ту­аль­ной бес­ко­неч­но­сти, иде­аль­ны. Иде­аль­ные пред­ло­же­ния при­сое­ди­ня­ют­ся к дей­ст­ви­тель­ным для то­го, что­бы про­стые пра­ви­ла ло­ги­ки бы­ли при­ме­ни­мы и к рас­су­ж­де­ни­ям о бес­ко­неч­ных мно­же­ст­вах. Это су­ще­ст­вен­но уп­ро­ща­ет струк­ту­ру всей тео­рии, по­доб­но то­му, как при рас­смот­ре­нии про­ек­тив­ной гео­мет­рии на плос­ко­сти до­бав­ля­ет­ся бес­ко­неч­но уда­лён­ная пря­мая, пе­ре­се­каю­щая лю­бые две па­рал­лель­ные пря­мые в не­ко­то­рой точ­ке.

Вы­дви­ну­тая Д. Гиль­бер­том про­грам­ма обос­но­ва­ния ма­те­ма­ти­ки вдох­но­ви­ла со­вре­мен­ни­ков на раз­ра­бот­ку ак­сио­ма­ти­че­ско­го ме­то­да. Имен­но с пред­при­ня­той в нач. 20 в. Гиль­бер­том и его по­сле­до­ва­те­ля­ми раз­ра­бот­кой тео­рии до­ка­за­тельств на ба­зе раз­ви­то­го в ра­бо­тах Г. Фре­ге, Дж. Пеа­но и Б. Рас­се­ла ло­гич. язы­ка свя­зы­ва­ют ста­нов­ле­ние М. л. как са­мо­сто­ят. ма­те­ма­тич. дис­ци­п­ли­ны.

Пер­вы­ми ра­бо­та­ми по М. л. в Рос­сии бы­ли ра­бо­ты П. С. По­рец­ко­го (1885–1904). Во­про­сам ос­но­ва­ний ма­те­ма­ти­ки и М. л. боль­шое вни­ма­ние уде­ля­ли Н. Н. Лу­зин и его уче­ни­ки А. Н. Кол­мого­ров и П. С. Но­ви­ков. Кол­мо­го­ров сфор­му­ли­ро­вал (1925) ак­сио­мы для ло­ги­ки вы­ска­зы­ва­ний, при­ем­ле­мые с точ­ки зре­ния фи­ло­со­фии ин­туи­цио­низ­ма Л. Брау­эра и пред­ло­жил (1932) ес­теств. ин­тер­пре­та­цию ин­туи­цио­ни­ст­ской ло­ги­ки Брау­эра как ло­ги­ки за­дач. А. И. Маль­цев до­ка­зал (1936) тео­ре­му о ком­пакт­но­сти, со­стоя­щую в том, что про­из­воль­ная сис­те­ма фор­мул в язы­ке ло­ги­ки пре­ди­ка­тов не­про­ти­во­ре­чи­ва, ес­ли не­про­ти­во­ре­чи­во лю­бое её ко­неч­ное под­мно­же­ст­во. Этот ре­зуль­тат стал сред­ст­вом до­ка­за­тель­ст­ва ло­каль­ных тео­рем для разл. ал­геб­ра­ич. сис­тем. Но­ви­ков раз­ра­бо­тал (1941) ме­тод до­ка­за­тель­ст­ва не­про­ти­во­ре­чи­во­сти клас­сич. фор­маль­ных сис­тем, ос­но­ван­ный на вве­дён­ном им по­ня­тии ре­гу­ляр­ной фор­му­лы и сво­дя­щий этот во­прос к во­про­су о не­про­ти­во­ре­чи­во­сти ин­туи­цио­ни­ст­ской ма­те­ма­ти­ки. Про­дол­жая ис­сле­до­ва­ния К. Гё­де­ля о не­про­ти­во­ре­чи­во­сти кон­ти­ну­ум-ги­по­те­зы, Но­ви­ков ус­та­но­вил (1951) не­про­ти­во­ре­чи­вость ря­да др. важ­ных пред­ло­же­ний тео­рии мно­жеств, до­ка­за­тель­ст­ва ко­то­рых пред­став­ля­ли боль­шие труд­но­сти.

По­яв­ле­ние в М. л. точ­но­го оп­ре­де­ле­ния по­ня­тия ал­го­рит­ма по­зво­ли­ло ус­та­нав­ли­вать раз­ре­ши­мость и не­раз­ре­ши­мость ал­го­рит­ми­че­ских про­блем в ма­те­ма­ти­ке. Пер­вые ре­зуль­та­ты в этом направ­ле­нии бы­ли по­лу­че­ны в ал­го­рит­мов тео­рии и в М. л. (напр., ре­зуль­таты, свя­зан­ные с про­бле­мой ос­та­нов­ки ра­бо­ты ма­ши­ны Тью­рин­га и тео­ре­мой Чёр­ча о не­раз­ре­ши­мо­сти ло­ги­ки пре­ди­ка­тов). В свя­зи с эти­ми ре­зуль­та­та­ми воз­ник во­прос: не яв­ля­ют­ся ли не­раз­ре­ши­мые ал­го­рит­мич. про­бле­мы спе­ци­фи­че­ски­ми для тео­рии ал­го­рит­мов и М. л.? Ока­за­лось, что это не так и су­ще­ст­вен­ный вклад в ис­сле­до­ва­ние раз­ре­ши­мо­сти ал­го­рит­мич. про­блем тра­диц. ма­те­ма­ти­ки вне­сли рос. учё­ные. А. А. Мар­ков и амер. ма­те­ма­тик Э. Пост не­за­ви­си­мо и од­но­вре­мен­но (1947) до­ка­за­ли, что не су­ще­ст­ву­ет ал­го­ритм рас­по­зна­ва­ния про­бле­мы ра­вен­ст­ва слов в по­лу­груп­пах, за­да­вае­мых ко­неч­ным чис­лом оп­ре­де­ляю­щих со­от­но­ше­ний. Эта про­бле­ма воз­ник­ла за­дол­го до уточ­не­ния по­ня­тия ал­го­рит­ма. П. С. Но­ви­ков до­ка­зал (1955) не­раз­ре­ши­мость про­бле­мы то­ж­де­ст­ва слов для ко­неч­но оп­ре­де­лён­ных групп. На ос­но­ве это­го ре­зуль­та­та С. И. Адян до­ка­зал (1955) ал­го­рит­мич. не­раз­ре­ши­мость ча­ст­ной про­бле­мы изо­мор­физ­ма для лю­бой фик­си­ров. груп­пы, а так­же ал­го­рит­мич. не­рас­по­зна­вае­мость поч­ти всех ин­ва­ри­ант­ных груп­по­вых свойств (напр., еди­нич­но­сти, ко­неч­но­сти, ком­му­та­тив­но­сти). Мар­ков, ис­поль­зуя ре­зуль­тат Адя­на, до­ка­зал (1958) ал­го­рит­мич. не­раз­ре­ши­мость важ­ной ал­го­рит­мич. про­бле­мы в то­по­ло­гии – про­бле­мы рас­по­зна­ва­ния го­мео­мор­физ­ма мно­го­об­ра­зий раз­мер­но­сти, боль­шей трёх. Ю. В. Ма­тия­се­вич до­ка­зал (1970) ал­го­рит­мич. не­рас­по­зна­вае­мость су­ще­ст­во­ва­ния ре­ше­ний у дио­фан­то­вых урав­не­ний, ре­шив тем са­мым (от­ри­ца­тель­но) 10-ю про­бле­му Гиль­бер­та. Эта ра­бо­та Ма­тия­се­ви­ча яви­лась за­вер­ше­ни­ем ра­бот, про­во­див­ших­ся груп­пой амер. учё­ных в нач. 1960-х гг. (Б. Дэ­вис, Дж. Ро­бин­сон, Р. Ро­бин­сон, Х. Пут­нем).

В 1957 по ре­ко­мен­да­ции 3-го Все­со­юз­но­го съез­да ма­те­ма­ти­ков в Ма­те­ма­тич. ин-те име­ни В. А. Стек­ло­ва АН СССР был об­ра­зо­ван от­дел М. л., ко­то­рый воз­гла­вил П. С. Но­ви­ков; в 1959 на ме­хани­ко-ма­те­ма­тич. ф-те МГУ об­ра­зо­ва­на ка­фед­ра М. л., ко­то­рую воз­гла­вил А. А. Мар­ков, соз­да­тель тео­рии ал­го­риф­мов и ос­но­ва­тель шко­лы кон­ст­рук­тив­ной ма­те­ма­ти­ки в Рос­сии. В шко­ле Мар­ко­ва по­лу­че­ны ре­зуль­та­ты по кон­ст­рук­тив­ной ло­ги­ке и ма­те­ма­ти­ке, слож­но­сти ал­го­рит­мов, по­ис­ку ло­гич. вы­во­да, ло­ги­ке до­ка­зуе­мо­сти, мо­даль­ным ло­ги­кам. А. Н. Кол­мо­го­ров за­ло­жил (1968) ос­новы ал­го­рит­мич. тео­рии ин­фор­ма­ции, пред­ло­жив по­ня­тие слож­но­сти опи­са­ния ко­неч­но­го объ­ек­та (слож­ность по Кол­мо­го­ро­ву). В от­де­ле М. л. Ма­те­ма­тич. ин-та ве­лись ис­сле­до­ва­ния по тео­рии до­ка­за­тельств, ал­го­рит­мич. про­бле­мам ал­геб­ры и ло­ги­ки и тео­рии слож­но­сти вы­чис­ле­ний. В ча­ст­но­сти, бы­ла до­ка­за­на рас­по­зна­вае­мость су­ще­ст­во­ва­ния ре­ше­ний урав­не­ний в сво­бод­ных по­лу­груп­пах и в сво­бод­ных груп­пах (Г. С. Ма­ка­нин, 1977, 1982), до­ка­за­на раз­ре­ши­мость уни­вер­саль­ной и по­зи­тив­ной тео­рий сво­бод­ной груп­пы (Ма­ка­нин, 1984). Бы­ли по­лу­че­ны сверх­по­ли­но­ми­аль­ные ниж­ние оцен­ки слож­но­сти реа­ли­за­ции мо­но­тон­ных бу­ле­вых функ­ций схе­ма­ми в ба­зи­се без от­ри­ца­ния (А. А. Раз­бо­ров, 1985) и пол­ная клас­си­фи­ка­ция про­по­зи­цио­наль­ных ло­гик до­ка­зуе­мо­сти (Л. Д. Бек­ле­ми­шев, 1989). Боль­шую из­вест­ность в М. л. и ал­геб­ре при­об­ре­ла про­бле­ма Бёрн­сай­да о пе­рио­дич. груп­пах (сфор­му­ли­ро­ва­на в 1902), в ко­то­рой ста­вил­ся во­прос о том, бу­дет ли лю­бая ко­неч­но по­ро­ж­дён­ная груп­па, для эле­мен­тов ко­то­рой спра­вед­ли­во то­ж­де­ст­во $x^n=1$, ко­неч­ной. В се­рии совм. ра­бот П. С. Но­ви­ков и С. И. Адян до­ка­за­ли (1968, 1975), что не­цик­лич. груп­па $B(m,n)$, за­дан­ная $m$ по­ро­ж­даю­щи­ми и то­ж­деств. со­от­но­ше­ни­ем $x^n= 1$, бес­ко­неч­на при по­ка­за­те­лях $n$, крат­ных лю­бо­му не­чёт­но­му $k>665$. Эти ис­сле­до­ва­ния бы­ли про­дол­же­ны Адя­ном (1975). С. В. Ива­нов и И. Г. Лы­сё­нок до­ка­за­ли, что не­цик­лич. груп­пы $B(m,n)$ бес­ко­неч­ны при всех $n$, на­чи­ная с 2⁴⁸ (Ива­нов, 1994), 8000 (Лысё­нок, 1996).

А. И. Маль­це­вым бы­ла ос­но­ва­на си­бир­ская шко­ла ал­геб­ры и ло­ги­ки (1960). Он и его уче­ни­ки вне­сли су­ще­ст­вен­ный вклад в изу­че­ние не­клас­сич. ло­гик и про­блем раз­ре­ши­мо­сти эле­мен­тар­ных тео­рий разл. ал­геб­ра­ич. сис­тем. Ю. Л. Ер­шов до­ка­зал (1965, од­но­вре­мен­но с амер. учё­ны­ми Дж. Ак­сом и С. Ко­че­ном) раз­ре­ши­мость эле­мен­тар­ной тео­рии по­ля $p$-адич. чи­сел. Им так­же по­лу­че­ны ре­зуль­та­ты по тео­рии ну­ме­ра­ций, тео­рии кон­ст­рук­тив­ных мо­де­лей и тео­ре­ти­ко-ре­кур­сив­ным ие­рар­хи­ям. Его уче­ни­ком С. С. Гон­ча­ро­вым раз­ви­та тео­рия т. н. ал­го­рит­мич. раз­мер­но­сти, он внёс вклад в изу­че­ние кон­ст­рук­тив­ных мо­де­лей, в осо­бен­но­сти кон­ст­рук­тив­ных бу­ле­вых ал­гебр.

Предмет и основные разделы математической логики, связь с другими областями математики

К М. л. от­но­сят­ся ис­сле­до­ва­ния ло­гич. и ло­ги­ко-ма­те­ма­тич. ис­чис­ле­ний, из ко­то­рых ос­нов­ным яв­ля­ет­ся клас­сич. пре­ди­ка­тов ис­чис­ле­ние. В 1930 К. Гё­дель до­ка­зал тео­ре­му о пол­но­те ис­чис­ле­ния пре­ди­ка­тов, со­глас­но ко­то­рой мно­же­ст­во всех чис­то ло­гич. ут­вер­жде­ний ма­те­ма­ти­ки сов­па­да­ет с мно­же­ст­вом всех фор­мул, вы­во­ди­мых в ис­чис­ле­нии пре­ди­ка­тов. Эта тео­ре­ма по­ка­за­ла, что ис­чис­ле­ние пре­ди­ка­тов яв­ля­ет­ся той ло­гич. сис­те­мой, на ба­зе ко­то­рой мож­но фор­ма­ли­зо­вать ма­те­ма­ти­ку. На ба­зе ис­чис­ле­ния пре­ди­ка­тов стро­ят­ся разл. ло­ги­ко-ма­те­ма­тич. тео­рии, пред­став­ляю­щие со­бой фор­ма­ли­за­цию со­дер­жа­тель­ных ма­те­ма­тич. тео­рий – ариф­ме­ти­ки, ма­те­ма­тич. ана­ли­за, тео­рии мно­жеств, тео­рии групп и пр. На­ря­ду с эле­мен­тар­ны­ми тео­рия­ми рас­смат­ри­ва­ют­ся так­же тео­рии выс­ших по­ряд­ков, в ко­то­рых до­пус­ка­ют­ся так­же кван­то­ры по пре­ди­катам, пре­ди­ка­ты от пре­ди­ка­тов и т. д. Тра­диц. во­про­са­ми, ко­то­рые ис­сле­ду­ют­ся для тех или иных фор­маль­ных ло­гич. сис­тем, яв­ля­ют­ся ис­сле­до­ва­ния струк­ту­ры вы­во­дов в этих сис­те­мах, вы­во­ди­мость тех или иных фор­мул, во­про­сы не­про­ти­во­ре­чи­во­сти и пол­но­ты рас­смат­ри­вае­мых сис­тем.

До­ка­зан­ная в 1931 тео­ре­ма Гё­де­ля о не­пол­но­те ариф­ме­ти­ки по­ко­ле­ба­ла оп­ти­ми­стич. на­де­ж­ды Д. Гиль­бер­та на пол­ное ре­ше­ние во­про­сов ос­но­ва­ний ма­те­ма­ти­ки на ука­зан­ном им пу­ти. Эта тео­ре­ма ут­вер­жда­ет, что в лю­бой тео­рии, со­дер­жа­щей эле­мен­тар­ную ариф­ме­ти­ку (с опе­ра­ция­ми сло­же­ния и ум­но­же­ния), мож­но сфор­му­ли­ро­вать та­кое ут­вер­жде­ние, что ни оно са­мо, ни его от­ри­ца­ние не­до­ка­зуе­мо. В ча­ст­но­сти, та­ко­вым яв­ля­ет­ся ут­вер­жде­ние о не­про­ти­во­ре­чи­во­сти са­мой рас­смат­ри­вае­мой тео­рии. Это оз­на­ча­ет, что с во­про­са­ми ос­но­ва­ний ма­те­ма­ти­ки де­ло об­сто­ит не так про­сто, как хо­те­лось или ка­за­лось Гиль­бер­ту вна­ча­ле. Од­на­ко Гё­дель за­ме­тил, что не­про­ти­во­ре­чи­вость ариф­ме­ти­ки мож­но до­ка­зы­вать, поль­зу­ясь дос­та­точ­но на­дёж­ны­ми кон­ст­рук­тив­ны­ми сред­ст­ва­ми, хо­тя и вы­хо­дя­щи­ми за рам­ки средств, фор­ма­ли­зу­е­мых в ариф­ме­ти­ке. Ана­ло­гич­ные до­ка­за­тель­ст­ва не­про­ти­во­ре­чи­во­сти ариф­ме­ти­ки бы­ли по­лу­че­ны нем. ма­те­ма­ти­ком Г. Ген­це­ном (1936) и П. С. Но­ви­ко­вым (1942).

В ре­зуль­та­те ана­ли­за кан­то­ров­ской тео­рии мно­жеств и свя­зан­ных с ней па­ра­док­сов бы­ли по­строе­ны разл. сис­те­мы ак­сио­ма­ти­че­ской тео­рии мно­жеств, в ко­то­рых при­ни­ма­ет­ся то или иное ог­ра­ни­че­ние на об­ра­зо­ва­ние мно­жеств, что­бы ис­клю­чить воз­ник­но­ве­ние из­вест­ных ан­ти­но­мий. В этих ак­сио­ма­тич. сис­те­мах мо­гут быть раз­ви­ты до­воль­но об­шир­ные раз­де­лы ма­те­ма­ти­ки. Во­прос о не­про­тиво­ре­чи­во­сти дос­та­точ­но бо­га­тых ак­сио­ма­тич. сис­тем тео­рии мно­жеств ос­та­ёт­ся от­кры­тым. Сре­ди наи­бо­лее зна­чит. ре­зуль­та­тов, по­лу­чен­ных в ак­сио­ма­тич. тео­рии мно­жеств, – ре­зуль­тат К. Гё­де­ля (1939) о не­про­ти­во­ре­чи­во­сти кон­ти­ну­ум-ги­по­те­зы и вы­бо­ра ак­сио­мы в сис­теме Бер­най­са – Гё­де­ля $Σ$ и результат П. Ко­эна (1963) о не­за­ви­си­мо­сти этих ак­си­ом от ак­си­ом сис­те­мы Цер­ме­ло – Френ­ке­ля $ZF$. Сис­те­мы ак­си­ом $Σ$ и $ZF$ рав­но­не­про­ти­во­ре­чи­вы. Для до­ка­за­тель­ст­ва сво­их ре­зуль­та­тов Гё­дель ввёл по­ня­тие кон­ст­рук­тив­но­го мно­же­ст­ва и по­ка­зал су­ще­ст­во­ва­ние мо­де­ли сис­те­мы $Σ$, со­стоя­щей из та­ких мно­жеств. Ме­тод Гёде­ля был ис­поль­зо­ван П. С. Но­ви­ко­вым для до­ка­за­тель­ст­ва не­про­ти­во­ре­чи­во­сти не­ко­то­рых ут­вер­жде­ний де­ск­рип­тив­ной тео­рии мно­жеств (1951). Для по­строе­ния мо­де­лей тео­рии мно­жеств $ZF$, в ко­то­рых вы­пол­ня­ют­ся от­ри­ца­ния кон­ти­ну­ум-ги­по­те­зы или ак­сио­мы вы­бо­ра, Ко­эн ввёл т. н. ме­тод вы­ну­ж­де­ния, ко­то­рый впо­след­ст­вии был усо­вер­шен­ст­во­ван и стал осн. ме­то­дом по­строе­ния мо­де­лей тео­рии мно­жеств, удов­ле­тво­ряю­щих тем или иным свой­ст­вам.

Сре­ди дос­ти­же­ний М. л. – раз­ра­бот­ка тео­рии ре­кур­сив­ных функ­ций и фор­му­ли­ров­ка те­зи­са Чёр­ча, ут­вер­ждаю­ще­го, что по­ня­тие об­ще­ре­кур­сив­ной функ­ции яв­ля­ет­ся уточ­не­ни­ем ин­туи­тив­но­го по­ня­тия ал­го­рит­ма. Из др. эк­ви­ва­лент­ных уточ­не­ний по­ня­тия ал­го­рит­ма наи­боль­шее рас­про­стра­не­ние по­лу­чи­ли по­ня­тия Тью­рин­га ма­ши­ны и нор­маль­но­го ал­го­риф­ма Мар­ко­ва. По су­ще­ст­ву, вся ма­те­ма­ти­ка свя­за­на с те­ми или ины­ми ал­го­рит­ма­ми. Но толь­ко по­сле уточ­не­ния по­ня­тия ал­го­рит­ма поя­ви­лась воз­мож­ность об­на­ру­жить су­ще­ст­во­ва­ние не­раз­ре­ши­мых ал­го­рит­ми­ч. про­блем в ма­те­ма­ти­ке. Не­раз­ре­ши­мые ал­го­рит­мич. про­бле­мы бы­ли об­на­ру­же­ны во мно­гих раз­де­лах ма­те­ма­ти­ки (ал­геб­ра, тео­рия чи­сел, то­по­ло­гия, тео­рия ве­ро­ят­но­стей и пр.), при­чём ока­за­лось, что они мо­гут встре­чать­ся сре­ди рас­про­стра­нён­ных и фун­дам. за­дач ма­те­ма­ти­ки. Ис­сле­до­ва­ние ал­го­рит­мич. про­блем в той или иной об­лас­ти ма­те­ма­ти­ки, как пра­ви­ло, со­про­во­ж­да­ет­ся про­ник­но­ве­ни­ем идей и ме­то­дов М. л. в эту об­ласть, что при­во­дит к ре­ше­нию так­же и др. про­блем, уже не имею­щих ал­го­рит­мич. ха­рак­те­ра.

Раз­ра­бот­ка точ­но­го по­ня­тия ал­го­рит­ма да­ла воз­мож­ность раз­ви­вать кон­ст­рук­тив­ное на­прав­ле­ние в ма­те­ма­ти­ке, во­пло­тив­шее в се­бе не­ко­то­рые чер­ты ин­туи­цио­ни­ст­ско­го на­прав­ле­ния, но су­ще­ст­вен­но от­ли­чаю­щее­ся от по­след­не­го. Бы­ли соз­да­ны ос­но­вы кон­ст­рук­тив­но­го ана­ли­за, кон­ст­рук­тив­ной то­по­ло­гии, кон­ст­рук­тив­ной тео­рии ве­ро­ят­но­стей и др.

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

Ак­сио­ма­тич. ме­тод ока­зал боль­шое влия­ние на раз­ви­тие мн. раз­де­лов ма­те­ма­ти­ки. Осо­бен­но зна­чи­тель­ным бы­ло про­ник­но­ве­ние это­го ме­то­да в ал­геб­ру. Так, на сты­ке М. л. и ал­геб­ры воз­ник­ла об­щая тео­рия ал­геб­ра­ич. сис­тем, или тео­рия мо­де­лей. Это на­прав­ле­ние бы­ло за­ло­же­но в ра­бо­тах А. И. Маль­це­ва, А. Тар­ско­го и их уче­ни­ков. Про­во­дят­ся ис­сле­до­ва­ния по эле­мен­тар­ным тео­ри­ям клас­сов мо­де­лей, в ча­ст­но­сти ис­сле­ду­ют­ся во­про­сы раз­ре­ши­мо­сти этих тео­рий, ак­сио­ма­ти­зи­руе­мо­сти клас­сов мо­де­лей, изо­мор­физ­ма мо­де­лей, во­про­сы ка­те­го­рич­но­сти и пол­но­ты клас­сов мо­де­лей.

Важ­ное ме­сто в тео­рии мо­де­лей за­ни­ма­ет ис­сле­до­ва­ние т. н. не­стан­дарт­ных мо­де­лей ариф­ме­ти­ки и ма­те­ма­тич. ана­ли­за. В на­ча­ле раз­ви­тия диф­фе­рен­ци­аль­но­го ис­чис­ле­ния в ра­бо­тах Г. В. Лейб­ни­ца и И. Нью­то­на бес­ко­неч­но ма­лые и бес­ко­неч­но боль­шие ве­ли­чи­ны рас­смат­ри­ва­лись как чис­ла. Позд­нее поя­ви­лось по­ня­тие пе­ре­мен­ной ве­ли­чи­ны, и в ма­те­ма­ти­ке от­ка­за­лись от упот­реб­ле­ния бес­ко­неч­но ма­лых чи­сел, мо­дуль ко­то­рых от­ли­чен от ну­ля и мень­ше лю­бо­го по­ло­жи­тель­но­го дей­ст­ви­тель­но­го чис­ла, т. к. их упот­реб­ле­ние тре­бу­ет от­ка­за от ак­сио­мы Ар­хи­ме­да. Че­рез три сто­ле­тия в ре­зуль­та­те раз­ви­тия ме­то­дов М. л. уда­лось ус­та­но­вить, что не­стан­дарт­ный ана­лиз с бес­ко­неч­но ма­лы­ми и бес­ко­неч­но боль­ши­ми чис­ла­ми не­про­ти­во­ре­чив от­но­си­тель­но обыч­но­го (стан­дарт­но­го) ана­ли­за.

Ак­сио­ма­тич. ме­тод ока­зал влия­ние и на ин­туи­цио­ни­ст­скую ма­те­ма­ти­ку. Ни­дерл. учё­ный А. Гей­тинг в 1930 ввёл в рас­смот­ре­ние фор­маль­ные сис­те­мы ин­туи­цио­ни­ст­ской ло­ги­ки вы­ска­зы­ва­ний и пре­ди­ка­тов (кон­ст­рук­тив­ные ис­чис­ле­ния вы­ска­зы­ва­ний и пре­ди­ка­тов). Позд­нее бы­ли вве­де­ны фор­маль­ные сис­те­мы ин­туи­цио­ни­ст­ско­го ана­ли­за. Бы­ло вве­де­но по­ня­тие т. н. реа­ли­зуе­мо­сти фор­мул по Кли­ни, свя­зан­ное с од­ной из по­пы­ток ин­тер­пре­ти­ро­вать по­ня­тие ин­туи­цио­ни­ст­ской ис­тин­но­сти с точ­ки зре­ния клас­сич. ма­те­ма­ти­ки. Од­на­ко ока­за­лось, что не вся­кая реа­ли­зуе­мая фор­му­ла ис­чис­ле­ния вы­ска­зы­ва­ний вы­во­ди­ма в ин­туи­цио­ни­ст­ском (кон­ст­рук­тив­ном) ис­чис­ле­нии вы­ска­зы­ва­ний.

Фор­ма­ли­за­ции под­вер­глась так­же и мо­даль­ная ло­ги­ка. Од­на­ко, не­смот­ря на боль­шое чис­ло ра­бот по фор­маль­ным сис­те­мам мо­даль­ной ло­ги­ки и по их се­ман­ти­ке, мож­но ска­зать, что по­ка здесь ещё идёт про­цесс на­ко­п­ле­ния раз­роз­нен­ных фак­тов.

М. л. име­ет боль­шое при­клад­ное зна­че­ние; идеи и ме­то­ды М. л. про­ни­ка­ют в ин­фор­ма­ти­ку, вы­чис­ли­тель­ную ма­те­ма­ти­ку, в струк­тур­ную лин­гвис­ти­ку.