Теорема Геделя - Математика реферат
Главная
Математика
Теорема Геделя
Курт Гедель как крупнейший специалист по математической логике, краткий очерк его жизни и личностного становления, достижения в сфере профессиональной деятельности. История и основные этапы создания теоремы о неполноте, первой и второй, дискуссии вокруг н
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Курт Гёдель - крупнейший специалист по математической логике - родился 28 апреля 1906 г. В Брюнне (ныне г. Брно, Чехия). Окончил Венский университет, где защитил докторскую диссертацию, был доцентом в 1933-1938 гг. После аншлюса эмигрировал в США. С 1940 по 1963 г. Гёдель работал в Принстонском институте высших исследований. Гёдель - почетный доктор Йельского и Гарвардского университетов, член Национальной академии наук США и Американского философского общества.
В 1951 г. Курт Гёдель был удостоен высшей научной награды США - Эйнштейновской премии. В статье, посвященной этому событию, другой крупнейший математик нашего времени Джон фон Нейман писал Цитата сборника статей «Основания математики» выпущенному в Нью-Йорке в честь 60-летия К. Гёделя. : «Вклад Курта Гёделя в современную логику поистине монументален. Это - больше, чем просто монумент. Это веха, разделяющая две эпохи… Без всякого преувеличения можно сказать, что работы Гёделя коренным образом изменили сам предмет логики как науки».
Действительно, даже сухой перечень достижений Гёделя в математической логике показывает, что их автор по существу заложил основы целых разделов этой науки: теории моделей (1930 г.; так называемая теорема о полноте узкого исчисления предикатов, показывающая, грубо говоря, достаточность средств «формальной логики» для доказательства всех выражаемых на ее языке истинных предложений), конструктивной логики (1932-1933 гг.; результаты о возможности сведения некоторых классов предложений классической логики к их интуиционистским аналогам, положившие начало систематическому употреблению «погружающих операций», позволяющих осуществлять такое сведение различных логических систем друг другу), формальной арифметики (1932-1933 гг.; результаты о возможности сведения классической арифметики в интуиционистскую, показывающие в некотором смысле непротиворечивость первой относительно второй), теории алгоритмов и рекурсивных функций (1934 г.; определение понятия общерекурсивной функции, сыгравшего решающую роль в установлении алгоритмической неразрешимости ряда важнейших проблем математики, с одной стороны. И в реализации логико-математических задач на электронно-вычислительных машинах - с другой), аксиоматической теории множеств (1938 г.; доказательство относительной непротиворечивости аксиомы выбора и континуум-гипотезы Кантора от аксиом теории множеств, положившее начало серии важнейших результатов об относительной непротиворечивости и независимости теоретико-множественных принципов).
В 1931 г. В одном из немецких научных журналов появилась сравнительно небольшая статья с довольно устрашающим названием «О формально неразрешимых предложениях Principia Mathematica и родственных систем». Автором ее был двадцатипятилетний математик из Венского университета Курт Гедель, впоследствии работавший в Принстонском институте высших исследований. Работа эта сыграла решающую роль в истории логики и математики. В решении Гарвардского университета о присуждении Гёделю почетной докторской степени (1952) она была охарактеризована как одно из величайших достижений современной логики.
Однако в момент опубликования ни название гёделевской работы. Ни содержание ее ничего не говорили большинству математиков. Упомянутые в ее названии Principia Mathematica - это монументальных трехтомный трактат Альфреда Норта Уайтхеда и Бертрана Рассела, посвященный математической логике и основаниям математики; знакомство с трактатом отнюдь не являлось необходимым условием для успешной работы в большей части разделов математики. Интерес к разбираемым в работе Гёделя вопросам всегда был уделом весьма немногочисленной группы учёных. В то же время рассуждения, приведенные Гёделем в его доказательствах, были для своего времени столь необычными. Что для полного их понимания требовалось исключительное владение предметом и знакомство с литературой, посвященной этим весьма специфическим проблемам.
Первая теорема Гёделя о неполноте , по всей видимости, является наиболее знаменательным результатом в математической логике. Она звучит следующим образом:
Для произвольной непротиворечивой формальной и вычисл и мой теории, в которой можно доказать базовые арифметические высказывания, может быть построено истинноеарифметическое в ы сказывание, истинность которого не может быть доказана в рамках теории [1] . Другими словами, любая вполне полезная теория, достато ч ная для представления арифметики, не может быть одновременно непротиворечивой и полной.
Здесь слово «теория» обозначает «бесконечное множество» высказываний, некоторые из которых полагаются истинными без доказательств (такие высказывания называются аксиомами), а другие (теоремы) могут быть выведены из аксиом, а потому полагаются (доказываются) истинными. Словосочетание «доказуемый в теории» обозначает «выводимый из аксиом и примитивов теории (константных символов алфавита) при помощи стандартной логики (первого порядка)». Теория является непротиворечивой (согласованной), если в ней невозможно доказатьпротиворечивое высказывание. Словосочетание «может быть построено» обозначает, что существует некоторая механическая процедура (алгоритм), которая может построить высказывание на основе аксиом, примитивов и логики первого порядка. «Элементарная арифметика» заключается в наличии операций сложения и умножения над натуральными числами. Результирующее истинное, но недоказуемое высказывание часто обозначается для заданной теории как «последовательность Гёделя», однако существует бесконечно количество других высказываний в теории, которые имеют такое же свойство: недоказуемая в рамках теории истинность.
Предположение о том, что теория вычислима, обозначает, что в принципе возможно реализовать компьютерный алгоритм (компьютерную программу), которая (если ей разрешено вычислять произвольно долгое врея, вплоть до бесконечности) вычислит список всех теорем теории. Фактически, достаточно вычислить только список аксиом, и все теоремы могут быть эффективно получены из такого списка.
Первая теорема о неполноте была озаглавлена как «Теорема VI» в статье Гёделя от 1931 года On Formally Undecidable Propositions in Principia Mathematica and Related Systems I . В оригинальной записи Гёделя она звучала как:
«Общий вывод о существовании неразрешимых пропозиций заключается в следующем:
Для каждого ? -согласованного рекурсивного кла с са k ФОРМУЛ существуют р е курсивные ЗНАКИ r такие, что ни ( v Gen r ) , ни ¬( v Gen r ) не принадл е жат Flg ( k ) (где v есть СВОБОДНАЯ ПЕРЕМЕННАЯ r ) [2] ».
Обозначение Flg происходит от нем. Folgerungsmenge - множество последовательностей, Gen происходит от нем. Generalisation - обобщение.
Грубо говоря, высказывание Гёделя G утверждает: «истинность G не может быть доказана». Если бы G можно было доказать в рамках теории, то в таком случае теория содержала бы теорему, которая противоречит сама себе, а потому теория была бы противоречива. Но если G недоказуемо, то оно истинно, а потому теория неполна (высказывание G невыводимо в ней).
Это пояснение на обычном естественном языке, а потому не совсем математически строго. Для предоставления строгого доказательства, Гёдель пронумеровал высказывания при помощи натуральных чисел. В этом случае теория, описывающая числа, также принадлежит множеству высказываний. Вопросы о доказуемости высказываний представимы в данном случае в виде вопросов о свойствах натуральных чисел, которые должны быть вычислимы, если теория полна. В этих терминах высказывание Гёделя гласит, что не существует числа с некоторым определённым свойством. Число с этим свойством будет являться доказательством противоречивости теории. Если такое число существует, теория противоречива вопреки первоначальному предположению. Так что предполагая, что теория непротиворечива (как предполагается в посылке теоремы), получается, что такого числа не существует, и высказывание Гёделя истинно, но в рамках теории этого доказать невозможно (следовательно, теория неполна). Важное концептуальное замечание состоит в том, что необходимо предположить, что теория непротиворечива, для того чтобы объявить высказывание Гёделя истинным.
Вторая теорема Гёделя о непо л ноте
Вторая теорема Гёделя о неполноте звучит следующим образом:
Для любой формально рекурсивно перечислимой (то есть э ф фективно ген е рируемой) теории T , включая базовые арифметические истинностные высказывания и определённые высказывания о фо р мальной доказуемости, данная те о рия T включает в себя утверждение о своей непротиворечивости тогда и только тогда, когда те о рия T противоречива.
Иными словами, непротиворечивость достаточно богатой теории не может быть доказана средствами этой теории. Однако вполне может оказаться, что непротиворечивость одной конкретной теории может быть установлена средствами другой, более мощной формальной теории. Но тогда встаёт вопрос о непротиворечивости этой второй теории, и т.д.
Использовать эту теорему для доказательства того, что разумная деятельность не сводится к вычислениям, пытались многие. Например, еще в 1961 году известный логик Джон Лукас (John Lucas) выступал с подобной программой. Его рассуждения оказались довольно уязвимыми - однако он и задачу ставил более широко. Роджер Пенроуз использует несколько другой подход, который излагается в книге полностью, «с нуля».
Следствия теорем затрагивают философию математики, особенно такие формализмы, которые используют формальную логику для определения своих принципов. Можно перефразировать первую теорему о неполноте следующим образом: « невозможно найти всеохватывающую систему аксиом, которая была бы способна доказать все математические истины, и ни о д ной лжи ». С другой стороны, с точки зрения строгой формальности, эта переформулировка не имеет особого смысла, поскольку она предполагает понятия «истина» и «ложь» определёнными в абсолютном смысле, нежели в относительном для каждой конкретной системы.
А вот такое перефразирование второй теоремы является ещё более тревожным для основ математики:
Если невозможно доказать непротиворечивость и полн о ту системы в рамках неё с а мой, то эта система противоречива.
Следовательно, для установления факта непротиворечивости некоторой системы S необходимо использовать более мощную систему T , но доказательство в рамках T не может быть полностью законченным, пока не доказана непротиворечивость самой T (причём без использования системы S ).
Вначале казалось, что всё-таки теоремы Гёделя оставляют немного надежды, поскольку можно создать общий алгоритм, который решает, является ли заданное утверждение разрешимым или нет. Этот алгоритм позволит математикам обойти все неразрешимые проблемы сразу вместе. Однако, отрицательный ответ на проблемы выбора, полученный в 1936 году, показал, что такого алгоритма не существует.
Некоторые исследователи предполагают, что утверждение, которое недоказуемо в рамках дедуктивной системы, может быть совершенно доказуемо на некотором метаязыке. А то, что не может быть доказано на этом метаязыке, может, в свою очередь, быть доказано на мета- метаязыке , и так до бесконечности. Применяя такие системы типизированных метаязыков совместно с аксиомой редуцируемости, которая по индуктивному предположению применяется ко всему набору языков, можно для любых областей знаний обходить проблему неполноты.
Необходимо также отметить, что теоремы Гёделя применимы только к достаточно сильным системам аксиом. «Достаточно сильный» в данном контексте обозначает, что теория содержит достаточно средств для представления данных, необходимых для доказательства первой теоремы о неполноте. Существенно то, что для этого нужны базовые аксиомы, представляющие операции сложения и умножения, как, к примеру, в арифметике Робинсона Q. Существуют более слабые системы аксиом, которые полны и непротиворечивы, например, арифметика Пресбургера, которая доказывает истинность утверждений первого порядка только относительно сложения.
Система аксиом может содержать бесконечное количество аксиом (как, к примеру, арифметика Пеано первого порядка), но для применимости к такой системе теоремы Гёделя. должен быть эффективный алгоритм, который позволяет проверять корректность. Например, можно рассмотреть множество всех высказываний первого порядка, который истинны в стандартной модели натуральных чисел. Эта система полна, но теорема Гёделя неприменима в данном случае, поскольку не существует эффективной процедуры, которая определяет, является ли заданная последовательность аксиомой. Фактически, это так по следствию из первой теоремы Гёделя о неполноте.
Другой пример теории, к которой неприменима первая теорема Гёделя о неполноте, может быть построен следующим образом: необходимо отсортировать все возможные истинные утверждения относительно натуральных чисел сначал по длине строки, а затем лексикографически. Далее система аксиом строится так - вначале берётся система аксиом Пеано, после чего необходимо в списке утверждений выбирать первое по порядку утверждение, которое не может быть доказано. Далее это утверждение вносится в список аксиом новой системы. И так до конца. В конечном итоге этот процесс создаст полную, непротиворечивую и достаточно мощную формальную систему, которая, однако, не будет перечислимой.
Сам Гёдель доказал технически более слабые версии теорем. Первое доказательство теорем в приведённых в статье формулировках впервые было приведено Д.Б. Россером в 1936 году.
По существу, доказательство первой теоремы содержит процесс конструирования утверждения p в рамках формальной системы, которое можно описать на метаязыке следующим образом:
p = «Это утверждение не может быть доказано в рассматриваемой формальной системе»
Как видно, это, всего лишь, современный вариант парадокса лжеца, который в отличие от классической формулировки, не совсем парадоксальный.
Если система аксиом непротиворечива, доказательство теоремы Гёделя показывает, что p (и его отрицание) не могут быть доказаны в рамках системы. Следовательно утверждение p истинно (это утверждение о том, что оно само недоказуемо, и оно действительно недоказуемо). Если система аксиом ? -непротиворечива, то отрицание p также не может быть доказано, и таким образом p невычислимо. В системах, которые ? -противоречивы (но непротиворечивы), либо имеется такая же ситуация, либо утверждение ¬ p может быть доказано.
Добавление утверждения p в качестве аксиомы не решает проблемы, поскольку для такой расширенной системы будет существовать иное утверждение Гёделя. Такие теории, как арифметика Пеано, для которых не может быть построено перечислимого расширения, называются существенно н е полными .
гедель математический теорема неполнота
1. В.А. Успенский. Теорема Геделя о неполноте. - М.: Наука, 1982.
2. Теорема Геделя / Э. Нагель, Дж.Р. Ньюмен. - М.: Красанд, 2010. - 120 с.
3. Традиция. Русская энциклопедия: URL: http://traditio.ru/wiki/
Краткий биографический очерк жизненного пути Пифагора. История появления теоремы Пифагора, ее дальнейшее распространение в мире. Формулировка и доказательство теоремы с помощью различных методов. Возможности применения теоремы Пифагора к вычислениям. презентация [309,4 K], добавлен 17.11.2011
Жерар Дезарг как известный французский математик, краткий очерк его жизни и деятельности. Сущность и содержание теоремы данного ученого, исторические основы ее создания и развития, особенности применения к решению задач, на евклидовой плоскости. курсовая работа [151,3 K], добавлен 28.04.2011
История создания теоремы. Краткая биографическая справка из жизни Пифагора Самосского. Основные формулировки теоремы. Доказательство Евклида, Хоукинса. Доказательство через: подобные треугольники, равнодополняемость. Практическое применение теоремы. презентация [3,6 M], добавлен 21.10.2011
Доказательство первой, второй и третей теоремы Силова. Описание групп порядка pq. Смежные классы по подгруппе и теорема Лагранжа. Классы сопряженных элементов. Нормализатор множества в группе. Теоремы о гомоморфизмах. Примеры силовских подгрупп. курсовая работа [246,9 K], добавлен 21.04.2011
Пифагор Самосский как древнегреческий философ, математик и мистик, создатель религиозно-философской школы пифагорейцев. Краткий очерк его жизни, этапы личностного творческого становления, оценка места и значения в истории. Анализ достижений Пифагора. презентация [397,9 K], добавлен 14.12.2012
Биография и достижения великого ученого, творца математической школы древней Греции – Пифагора. Пифагорейское учение о натуральном числе как основе мироздания. Использование числовых отношений в геометрических построениях. Формулировка теоремы Пифагора. реферат [29,6 K], добавлен 07.01.2012
Краткая биографическая справка из жизни Пьера Ферма. Общее понятие про правильные многоугольники. Числа математика, их история. Великая теорема Ферма, случаи доказательства. Особенности облегченной и малой теоремы. Роль математики в деятельности Уайлсома. контрольная работа [501,2 K], добавлен 14.06.2012
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .
© 2000 — 2021
Теорема Геделя реферат. Математика.
Курсовая работа по теме Инфляция как неизбежный спутник современного экономического развития
Деловой Этикет и имидж делового человека
Вак Защиты Диссертаций Пгниу 2022 Дсг
Философия Личность И Общество Реферат Введение
Курсовая Учет Временных Зданий И Сооружений
Реферат: Проблема Карибского кризиса в историографии
Курсовая работа по теме Шкідливі речовини в технології консервування. Джерела забруднення харчових продуктів
Реферат: Опыт работы подростковых психоаналитических групп
Курсовая работа по теме Расчет зубчатых пар редуктора
Реферат: Генофонд и причины гибели видов
Реферат: Circular Flow Of Economics Essay Research Paper
Роль Микроорганизмов Эссе
Шпаргалка: Социальная работа как знание, деятельность и специальность
Курсовая Работа Приоритетные Национальные Проекты 2022 2024
Контрольная работа по теме Анализ экономического потенциала машиностроения и металлообработки
Искусство Судебной Речи Реферат
Реферат: Горн, Арвид
Реферат: Свобода экономической инициативы как гарантия правового государства
Реферат По Научной Статье Образец
Реферат по теме Шлифовальные станки, обрабатывающие центры и гибкие производственные модули (ГПМ)
Внешняя политика России в первой половине XIX в. - История и исторические личности контрольная работа
Соучастие в преступлении - Государство и право реферат
Договор купли-продажи предприятия - Государство и право курсовая работа