Спирина, М.С. Дискретная математика

Примером может служить пятый постулат Евклида, который на про­ тяжении двух тысячелетий пытались доказать или опровергнуть матема­ тики различных эпох и национальностей. Но лишь в середине XIX в. не­ зависимо друг от друга наш гениальный соотечественник, будущий рек­ тор Казанского университета Н. И.Лобачевский и молодой венгерский математик Я.Бойаи, а также великий Карл Гаусс доказали независи­ мость аксиомы параллельных (пятый постулат Евклида) от остальных аксиом и возможность отказа от него. Поэтому и геометрия Евклида, и геометрия Лобачевского являются независимыми системами, аксиома­ тика которых отличается лишь аксиомой параллельных. Однако это пол­ ностью изменяет выводы, получаемые в этих геометриях на основе сфор­ мулированной аксиоматики. Схематически эти геометрии можно представить в виде пересека­ ющихся множеств, общая часть которых включает в себя множество те­ орем, выводимых из общего для них набора аксиом. Это так называемая абсолютная геометрия. Различия в геометриях Евклида и Лобачевского, возникшие из-за включения в них разных по смыслу аксиом о параллельных прямых, можно увидеть из сравнительного неполного анализа, приведенного в табл. 5.1. Эти и другие теоремы геометрии Лобачевского, такие непо­ нятные и противоречивые на первый взгляд, послужили толчком для анализа непротиворечивости построения формальной систе­ мы. Дело в том, что неприятие противоречивых теорем основано на нашем личном опыте и здравом смысле, что послужило причи­ ной неприятия неевклидовой геометрии математиками различ­ ных уровней. И только когда была установлена возможность реа­ лизации неевклидовой геометрии, тогда удалось увидеть, что это стройная, логически выводимая система, которая отвечает требо­ ваниям полноты, непротиворечивости, независимости. Одной из главных задач формальной теории систем является выявление необходимого минимума средств, с помощью которых можно описать любую формальную систему. Для формальных си ­ стем доказана теорема: В любой формальной системе множество доказуемых в ней формул перечислимо. Для любого не более чем счетного множества М существует система подстановок, все выведенные слова которой содержатся в М. Наглядно формальную систему можно представить в виде графа с выделенной вершиной — аксиомой, у которого осталь­ ные вершины — слова, порождаемые этой системой в заданном алфавите. Ребра такого графа — применения продукций, а путь от корневой вершины к заданной — возможные выводы данного слова. Полученные выводы вдохновили математиков. Идея построе­ ния таких непротиворечивых полных функционально замкнутых систем на рубеже XIX и XX вв. казалась реальной и достижимой в ближайшее время. Математики различных направлений работали 215