Принцесса или тигр? - [57]
>8, где A>8 — это множество тех чисел, которые машина может напечатать. Итак, A>75 = К. Но при этом и A>73 = К, потому что утверждение, что некое число x принадлежит множеству A>n, равносильно утверждению, что число х*х принадлежит множеству A>8 (согласно свойству 3, поскольку 73 = 3×24 + 1), что в свою очередь равносильно утверждению, что число х*х не принадлежит множеству A>8 (согласно свойству 2). Таким образом, A>73 — это множество всех тех чисел х, для которых число х*х не принадлежит множеству A>8 или, что то же самое, множество всех чисел х, для которых утверждение x ∈ А>x не может быть доказано машиной. Следовательно, A>73 — это то же самое множество чисел, что и A>75, поскольку оба они тождественны множеству К. Более того, для любого заданного числа n, для которого А>n = К, утверждение n ∈ А>n должно быть истинным, но недоказуемым с помощью машины. Это можно показать буквально с помощью тех же самых рассуждений, что и в рассмотренном нами частном случае n = 75 (в еще более общей форме эти рассуждения приведены в следующей главе). Тем самым мы получаем, что утверждение 73 ∈ A>73 — это еще один пример истинного утверждения, кодовый номер которого машина напечатать не может.
3. Для любого числа n множество A>9·n должно совпадать с множеством n. В самом деле, множество A>9·n есть дополнение множества A>3·n, а множество A>3·n в свою очередь есть дополнение множества A>n; следовательно, множество A>9·n совпадает с A>n. Это означает, что множество A>675 совпадает с множеством A>75, и, стало быть, утверждение 675 ∈ A>675 — это есть еще одно решение задачи. Аналогично утверждение 2175 ∈ A>2175 также является решением. Таким образом, мы получаем, что существует бесконечно много истинных утверждений, которые машина Фергюссона доказать не может: например, для любого n, которое равно произведению 75 на некоторое кратное числа 9 или произведению 73 на произвольное кратное числа 9, утверждение n ∈ А, является истинным, но недоказуемым посредством этой машины.
15. Доказуемость и истина
Крупной вехой в истории математической логики стал 1931 г. Именно в этом году Гёдель опубликовал знаменитую теорему о неполноте. Свою эпохальную работу[8] он начинает следующими словами:
«Развитие математики в направлении все большей точности привело к формализации целых ее областей, в связи с чем стало возможно проводить доказательства, пользуясь небольшим числом чисто механических правил. В настоящий момент наиболее исчерпывающими системами являются, с одной стороны, система аксиом, предложенная Уайтхедом и Расселом в работе „Princlpia Mathematica“, а с другой — система Цермело — Френкеля в аксиоматической теории множеств. Обе эти системы настолько обширны, что в них оказывается возможным формализовать все методы доказательства, используемые сегодня в математике, — иначе говоря, все эти методы могут быть сведены к нескольким аксиомам и правилам вывода. Поэтому, казалось бы, разумно предположить, что указанных аксиом и правил вполне хватит для разрешения всех математических проблем, которые могут быть сформулированы в пределах данной системы. Ниже будет показано, что дело обстоит не так. В обеих упомянутых системах имеются сравнительно простые задачи из теории обычных целых чисел, которые не могут быть решены на базе этих аксиом».[9]
Далее Гёдель объясняет, что такая ситуация обусловлена отнюдь не какими-то специфическими особенностями двух упомянутых систем, но имеет место для обширного класса математических систем.
Что имеется в виду под «обширным классом» математических систем? Это выражение интерпретировалось по-разному, и соответственно по-разному обобщалась теорема Гёделя. Как ни странно, одно из самых простых и доступных для неспециалиста объяснений остается наименее известным. Это тем более удивительно, что на такое объяснение указывал и сам Гёдель во вводной части своей первой работы. К нему мы сейчас и обратимся.
Рассмотрим систему аксиом со следующими свойствами. Прежде всего пусть у нас имеются имена для различных множеств положительных целых чисел, причем все эти «именуемые», или допускающие наименование, множества мы можем расположить в виде бесконечной последовательности A>1, A>2…, A>n… (точно так же, как в системе Фергюссона, рассмотренной в предыдущей главе). Назовем число n индексом именуемого множества А, если А=n. (Таким образом, если, например, множества A>2, A>7 и A>13 совпадают между собой, то тогда числа 2, 7 и 13 — это все индексы одного и того же множества.) Как и для системы Фергюссона, с каждым числом x и с каждым числом у мы связываем утверждение, записываемое в виде x ∈ A>y, которое называется истинным, если x принадлежит А у, и ложным, если x не принадлежит A>y. Однако в дальнейшем мы не предполагаем, что утверждения типа x ∈ A>y являются единственно возможными утверждениями в данной системе, поскольку могут существовать и другие. Предполагается также, что любое возможное утверждение обязательно классифицируется либо как истинное, либо как ложное.
Каждому утверждению в данной системе присваивается некий кодовый номер, который мы будем называть геделевым номером, причем гёделев номер утверждения
Рэймонд Смаллиан счастливо сочетает в одном лице философа, логика, математика, музыканта, фокусника, юмориста, писателя и составителя великолепных задач-головоломок. Искусный писатель и великолепный юморист, Смаллиан любит облекать свои задачи в литературную форму, нередко пародирующую какие-нибудь известные произведения. Делает он это настолько хорошо, что его книги, изобилующие всякого рода парадоксами, курьезами и задачами, с удовольствием читают и те, кто даже не пытается решать задачи.В книге, которую вы держите сейчас в руках, кэрролловская Алиса из Страны Чудес и ее друзья раскрывают перед читателем нескончаемую вереницу задач-головоломок.
Книга американского профессора Р. Смаллиана, написанная в увлекательной форме, продолжает серию книг по занимательной математике и представляет собой популярное введение в некоторые проблемы математической логики. Сюда входят более 200 новых головоломок, созданных необычайно изобретательным автором. Задачи перемежаются математическими шутками, анекдотами из повседневной жизни и неожиданными парадоксами. Завершает книгу замечательная серия беллетризованных задач, которые вводят читателя в самую суть теоремы Курта Гёделя о неполноте, — одного из замечательнейших результатов математической логики 20 века. Можно сказать — вероятно, самый увлекательный сборник задач по логике.
Логические головоломки, парадоксы и курьезы, вошедшие в этот сборник, построены на материале знаменитой «Алисы в Стране Чудес» Л. Кэрролла. Известный американский математик и логик P.M. Смаллиан приглашает читателей последовать за Алисой в Страну Головоломок и вместе с ней решить множество увлекательных задач.
В книге развита теория квантового оптоэлектронного генератора (ОЭГ). Предложена модель ОЭГ на базе полуклассических уравнений лазера. При анализе доказано, что главным источником шума в ОЭГ является спонтанный шум лазера, обусловленный квантовой природой. Приводятся схемы и экспериментальные результаты исследования малошумящего ОЭГ, предназначенного для применения в различных областях военно-космической сферы.
Любую задачу можно решить разными способами, однако в учебниках чаще всего предлагают только один вариант решения. Настоящее умение заключается не в том, чтобы из раза в раз использовать стандартный метод, а в том, чтобы находить наиболее подходящий, пусть даже и необычный, способ решения.В этой книге рассказывается о десяти различных стратегиях решения задач. Каждая глава начинается с описания конкретной стратегии и того, как ее можно использовать в бытовых ситуациях, а затем приводятся примеры применения такой стратегии в математике.
Давид Гильберт намеревался привести математику из методологического хаоса, в который она погрузилась в конце XIX века, к порядку посредством аксиомы, обосновавшей ее непротиворечиво и полно. В итоге этот эпохальный проект провалился, но сама попытка навсегда изменила облик всей дисциплины. Чтобы избавить математику от противоречий, сделать ее «идеальной», Гильберт исследовал ее вдоль и поперек, даже углубился в физику, чтобы предоставить квантовой механике структуру, названную позже его именем, — гильбертово пространство.
Саймон Сингх рассказывает о самых интересных эпизодах мультсериала, в которых фигурируют важнейшие математические идеи – от числа π и бесконечности до происхождения чисел и самых сложных проблем, над которыми работают современные математики.Книга будет интересна поклонникам сериала «Симпсоны» и всем, кто увлекается математикой.На русском языке публикуется впервые.
На протяжении многих веков симметрия оставалась ключевым понятием для художников, архитекторов и музыкантов, однако в XX веке ее глубинный смысл оценили также физики и математики. Именно симметрия сегодня лежит в основе таких фундаментальных физических и космологических теорий, как теория относительности, квантовая механика и теория струн. Начиная с древнего Вавилона и заканчивая самыми передовыми рубежами современной науки Иэн Стюарт, британский математик с мировым именем, прослеживает пути изучения симметрии и открытия ее основополагающих законов.
Сколько имеется простых чисел, не превышающих 20? Их восемь: 2, 3, 5, 7, 11, 13, 17 и 19. А сколько простых чисел, не превышающих миллиона? Миллиарда? Существует ли общая формула, которая могла бы избавить нас от прямого пересчета? Догадка, выдвинутая по этому поводу немецким математиком Бернхардом Риманом в 1859 году, для многих поколений ученых стала навязчивой идеей: изящная, интуитивно понятная и при этом совершенно недоказуемая, она остается одной из величайших нерешенных задач в современной математике.
Произведения Э. Эбботта и Д. Бюргера едины по своей тематике. Авторы в увлекательной форме с неизменным юмором вводят читателя в русло важных геометрических идей, таких, как размерность, связность, кривизна, демонстрируя абстрактные объекты в различных «житейских» ситуациях. Книга дополнена научно-популярными статьями о четвертом измерении. Ее с интересом и пользой прочтут все любители занимательной математики.
Книга известного американского популяризатора науки М. Гарднера содержит множество занимательных задач и головоломок из самых различных областей математики. Благодаря удачному подбору материла, необычной форме его подачи и тонкому юмору автора она не только доставит удовольствие любителям математики, желающим с пользой провести свой досуг, но и может быть полезной преподавателям математики школ и колледжей в их работе.