---

Разделы На главную История денег и экономики История экономических знаний Формы безналичных денег Международные финансы Экономические концепции Экономические теории Экономика в реальной жизни Экономический анализ и интеграция Макроэкономика Экономика и социальное общество Социальная экономика Социология Кризисная экономика Инфляция в экономике Экономика зарубежных стран Иностранные деньги Государственное регулирование Бюджетная система Политическая экономия Политология Законы денег Налогообложение Аудит Банкротство Теория рынка Конкуренция Международная торговля Товарная биржа Нефть и газ на бирже Логистика Банки - услуги и операции Банки в России Банковский кредит Недвижимость Ипотека в банке Инвестирование Стратегии инвестирования Инвестиционные фонды Ценные бумаги Акции Вексель Облигации Опционы Фьючерсы Биржевая торговля Биржа Forex Фондовый рынок Фондовый рынок России Волны Эллиотта Теория фракталов Торговая теория Ганна Фибоначчи на бирже Графический анализ на бирже Паттерны Биржевой анализ "Крестики-нолики" Японские свечи Технический анализ Математика на бирже Фундаментальный анализ Биржевая торговля Стратегии торговли Механические торговые системы Программирование МТС Управление торговым капиталом Управление портфелем Управление риском Страхование Профессия трейдер Практический трейдинг Технологии инфосистем Информационный рынок Безопасность информации Криптология и криптография Реклама PR - Public Relations Маркетинг Финансовая система Начало бизнеса Предпринимательство Малый бизнес Микроэкономика Торговля Ценообразование Работа в Интернете Сайты, софт, дизайн Управление качеством Управление предприятием Производство продукции Стратегический менеджмент Учебники по менеджменту Системы и организации Теория систем Планирование Статистика финансов Управление персоналом Трудовые отношения Бухгалтерия «1С:Бухгалтерия» Управленческий учет Делопроизводство и офис Автоматизация делопроизводства Рынок труда Карьера Менеджер Лидерство и бизнес карьера Лидерство и карьера Общение и переговоры Общение в бизнесе Бизнес переговоры Инновации в моделировании Экономическое моделирование Нейронные сети Нейролингвистика Логика нейросетей Программирование Пакет Excel Технологии программирования Языки программирования Практическая психология Психологические тренинги Психология в медицине Возрастная психология Ваши скрытые резервы Здоровье и долголетие Работа с эмоциями Пикап Управление временем Гипнотерапия Подсознание Трансовые техники Магия Здоровье советы Спорт для здоровья Йога Религии Эзотерика Мистицизм

---

Выразимость в арифметике

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

Выразимые с помощью формул этой сигнатуры предикаты называются арифметическими и играют в математической логике важную роль. Соответствующие множества также называются арифметическими. О них подробно рассказано в другой нашей книжке [5]; оказывается, что почти всякое множество, которое можно описать словами, является арифметическим.

58. Докажите, что существует множество натуральных чисел, не являющееся арифметическим. (Указание: семейство всех подмножеств множества несчетно, а арифметических множеств счетное число.)

Для начала мы установим арифметичность довольно простых предикатов.

• Предикат является арифметическим. В самом деле, его можно записать как .
• Предикаты и являются арифметическими. В самом деле, тогда и только тогда, когда для любого (а также когда ). А тогда и только тогда, когда представляет собой наименьшее число, отличное от нуля. (Можно также воспользоваться тем, что при любом .)
• Вообще для любого фиксированного числа предикат является арифметическим. (Например, можно написать сумму из большого числа единиц.)
• Полезно такое общее наблюдение: если мы уже установили, что какой-то предикат является арифметическим, то в дальнейшей его можно использовать в формулах, как если бы он входил в сигнатуру, поскольку его всегда можно заменить на выражающую его формулу.
• Предикат (число является делителем числа ), очевидно, арифметичен (формула ).
• Предикат " — простое число" арифметичен. В самом деле, число просто, если оно отлично от и любой его делитель равен или самому числу. Это сразу же записывается в виде формулы.
• Операции частного и остатка арифметичны (в том смысле, что трехместные предикаты " есть частное при делении на " и " есть остаток при делении на " арифметичны.
  Например, первый из них записывается формулой
  
  ( как мы уже говорили, использование арифметического предиката не создает проблем).
• Этот список можно продолжать: для многих предикатов их определение по существу уже является нужной формулой. Например, свойства "быть наибольшим общим делителем", "быть наименьшим общим кратным", "быть взаимно простыми" все относятся к этой категории.
• Предикат "быть степенью двойки" является арифметическим (хотя это и не столь очевидно, как в предыдущих примерах). В самом деле, это свойство можно переформулировать так: любой делитель либо равен единице, либо четен.

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

Два наиболее известных способа доказывать арифметичность основаны на возможности "кодирования" конечных множеств и последовательностей. Один восходит к Геделю (так называемая -функция Геделя), второй изложен в книге "Теория формальных систем" [24]. Ее написал Р.Смаллиан, известный также как автор популярных сборников "логических задач" и анекдотов. (Один из таких сборников имеет парадоксальное название "Как же называется эта книга?" [23].)

В некоторых отношениях метод Геделя предпочтительней, и мы рассказываем о нем в книжке о вычислимых функциях [5], но сейчас для разнообразия рассмотрим другой способ. Зафиксируем взаимно однозначное соответствие между натуральными числами и двоичными словами: Это соответствие задается так: чтобы получить слово, соответствующее числу , надо записать в двоичной системе и удалить первую единицу. Например, нулю соответствует пустое слово , числу — слово и т. д. Теперь можно говорить об арифметичности предикатов, определенных на двоичных словах, имея в виду арифметичность соответствующих предикатов на .

• Предикат "слово состоит из одних нулей" арифметичен.
  
  
  В самом деле, при переходе к числам ему соответствует предикат " есть степень двойки", который (как мы видели) арифметичен.
• Предикат "слова и имеют одинаковую длину" арифметичен. В самом деле, это означает, что найдется степень двойки , для которой (именно такой промежуток заполняют числа, которым соответствуют слова одной длины).
• Предикат "слово является конкатенацией слов и " (проще говоря, получается приписыванием справа к слову ) арифметичен. В самом деле, его можно выразить так: найдется слово из одних нулей, имеющее ту же длину, что и слово , при этом (умножение на соответствует дописыванию нулей, а добавление заменяет нули на буквы слова ).
• Предикат "слово является началом слова " арифметичен. В самом деле, это означает, что существует слово , при котором есть конкатенация и .
• То же самое верно для предикатов " есть конец слова ", " есть подслово слова " (последнее означает, что найдутся слова и , для которых
  
  есть конкатенация , и ; конкатенация трех слов выразима через конкатенацию двух).
• 
  
  Существует арифметический трехместный предикат с такими свойствами: (а) для любых и
  
  множество
  
  конечно; (б) среди множеств при различных парах встречаются все конечные множества. Например, в качестве такого предиката можно взять " есть подслово слова " (здесь есть конкатенация трех слов: , и снова ).
  
  В самом деле, ясно, что слово не длиннее слова , и потому множество всегда конечно. С другой стороны, пусть имеется некоторое конечное множество слов . Положим , где число нулей больше длины любого из слов , и .
  
  

Последнее утверждение не упоминает явно о словах, и больше они нам не понадобятся: достаточно знать, что конечные множества натуральных чисел можно кодировать парами натуральных чисел в описанном смысле.

Теперь мы можем выразить, что число является степенью числа , следующим образом: существует конечное множество , которое содержит число и обладает таким свойством: всякий элемент либо равен , либо делится на и



также принадлежит . Теперь надо везде заменить множество на его код , а утверждение на , где — построенный нами кодирующий предикат.

Немного сложнее выразить двуместный предикат . Здесь нам хотелось бы сказать так: существует последовательность , для которой , каждый следующий член вчетверо больше предыдущего () и . Как научиться говорить о последовательностях, если мы умеем говорить о множествах? Вспомним, что в терминах теории множеств последовательность есть функция, определенная на начальном отрезке натурального ряда, то есть конечное множество пар . Пары можно кодировать числами. Например, можно считать кодом пары число , поскольку по нему арифметически восстанавливается (как наибольшее число, квадрат которого не превосходит ), а затем и . Теперь конечное множество пар можно заменить конечным множеством их кодов, которое в свою очередь можно закодировать парой чисел.

59. Проведите это рассуждение подробно.

60. Покажите, что двуместный предикат " есть -ое по порядку простое число" арифметичен.

---