Теория Чисел Научная Фантастика

” Бог создал натуральные числа, все остальное-дело рук человека",
- гласит знаменитое изречение Кронекера. Но сколько из них он создал? Конечно, достаточно для
повседневных целей. У паука есть восемь ног, и эта восьмеричность является особенностью паука,
независимой от всех математических теорий. В этом смысле натуральные числа выглядят как
данность, почти как физические объекты. Однако физические теории описывают вселенную
как конечную и дискретную: инфляционная космология дает явную оценку числа
барионов во Вселенной из первых принципов: 10

87

. Дискретность пространства и
времени особенно поразительна в современной теории петлевой квантовой гравитации, см. например,
[4]. Так что вполне вероятно, что числа, как 2

2

10

не имеют никакого физического проявления. Мы

должны быть получены формальные свойства2

2

10

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

* 12 = 2076 по счету.

1

Эдвард Нельсон проводит различие между генетическим и a

формальное понятие числа:

Дело в том, что для рассмотрения 2

⇑ 5 как обозначение генетического числа влечет
за собой философскую приверженность некоему идеальному понятию существования. К
номиналисту, 2

⇑ 4 обозначает число, 65536, на которое можно рассчитывать,

но 2

⇑ 5-это пара арабских цифр с двойной стрелкой между ними,
и нет ни малейшего доказательства того, что это означает генетическое число.
([3]: 75)

1

Можем ли мы проверить, подсчитав, что 181 является простым? Это пограничный случай, потому что нам нужны неограниченные возможности

монотонность умножения, которая предполагает этап размышления над процессом счета.

182

T. Hürter

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

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

Если существование числа чисто формально, то мы должны быть в состоянии выразить
утверждение этого существования в адекватной и непротиворечивой формальной теории чисел.
Но вторая теорема Геделя о неполноте напоминает нам о возможности того, что наши
обычные системы аксиом теории чисел несовместимы. Линия, за которой такое
несоответствие заставило бы нас отступить, лежит где-то между генетическим и
формальным понятиями. Это не изменило бы количество ног паука, но это нарушило бы
наше представление об истине некоторых из них.

1

предложения—и если все пойдет действительно плохо, это может быть

заставьте нас пересмотреть существование 2

⇑ 5. Здесь я хочу более подробно рассмотреть этот
наихудший сценарий. Поскольку у нас нет никаких положительных доказательств несогласованности в
арифметике Пеано, аргумент должен быть в высшей степени гипотетическим.

На первый взгляд, неясно, может ли вообще возникнуть такая ситуация. Можно себе представить
, что генетическое понятие числа не имеет протяженности в бесконечность, без каких-либо
доступных доказательств. Я хочу возразить, что это не так: мы можем понять идею
о том, что снизу мы видим границу для натуральных чисел далеко вверх. Для этого мы
начнем со слабой теории чисел

Т

0

предназначен для захвата силы (не обязательно

дух) генетической концепции. В частности,

Т

0

безразлично к самому существованию

бесконечно много чисел. Мы строим a

0

формула

ϕ (x) и числовой термин t такой

тот

Т

0

подразумевает

∃x ϕ (x), мы не можем опровергнуть непротиворечивостьт

0

+ ∃x

элементарные средства, но...

Т

0

+∃x < t ϕ (x) имеет модели только до конечной границы, потому
что t не может получить свою стандартную интерпретацию. Ключевым моментом конструкции является то, что
мы можем организовать это для данного

n, ϕ (n) может быть решено внутри начального сегмента хорошо

ниже аномалии.

ϕ-ограниченный вариант неподвижной точки Геделя. Мой счет
сильно зависит от [5].

Теория

Т

0

Позволь

Л

Один

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

<, +, ·, 0, 1.

Непоследовательность в реальном мире

183

Это и есть язык арифметики. Позволь

Т

0

будьте теория в

Л

Один

с аксиомами для
нерефлексивного транзитивного порядка рекурсивные определения сложения и умножения,
т. е. E., универсальные замыкания

x,

x < y ∧ y < z → x,

x + 0 = x,

x + (y + 1) = (x + y) + 1,

x * 0 = 0,

x · (y + 1) = x * y + x,

а также универсальные затворы

x + 1 = y + 1 → x = y,

x,

x,

и

0

индукционная схема:

ϕ (0) ∧ ∀х (ϕ (х) → ϕ (х + 1)) → ∀х ϕ (х)

для каждого

0

формула

ϕ.

Т

0

имеет сколь угодно большие конечные модели, наименьшие с областью видимости

{0}. Это не так

докажите монотонность арифметических операций относительно

<. Добавление

x + 1 = 0

Для

Т

0

привести

Я

0

.

2

Лемма 1. Пусть...

М

= M, <, +, ·, 0, 1 быть моделью T

0

. Затем

М

является конечным iff

M,+, 0

является циклической группой, порожденной 1.

Определим каноническое число

n для каждого натурального числа n путем рекурсии. То

цифрой для 0 является символ "0". Если

n = 2k + 1, пусть N-строка

(1 + 1) · k + 1.

Если

n = 2k + 2, пусть N-строка

(1 + 1) · k + 1 + 1.

2

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

Т

0

не
претендует на то, чтобы быть концептуально точной кодификацией некоторого претеоретического понятия числа. Выбор
T

0

это был скорее вопрос математического вкуса. (Однако, как заметил Богослов Линк, в истории культуры может быть некоторое
оправдание для проведения элементарного подсчета в терминах остаточных классов.) Альтернативами
было бы рассматривать арифметические операции как тернарные предикаты, представляющие, возможно, частичные функции,
или допускать наибольшее число “много”, которое поглощает каждый ненулевой сопутствующий аргумент в сложении
и умножении. Но будьте осторожны: эти три подхода не эквивалентны.

184

T. Hürter

Длина:

n растет пропорционально логу

2

(северный).

Нам нужна более эффективная нотация для больших чисел вида 2

2

н

. Набор

т

0

≡ (1 + 1),

т

n+1

≡ (t

н

· t

н

).

Так

т

н

представляет собой 2

2

н

. Длина:

т

н

растет пропорционально к

n · 2

н

. Обратите внимание, что

Лима

северный→∞

n · 2

н

2

2

н

= 0.

Определение предложений

σ

н

Автор:

σ

0

≡ 1 < 1 + 1,

σ

n+1

≡ σ

н

∧ ∀ x (1

н

→ t

н

< Т

н

· икс).

σ

н

утверждает, что Вселенная имеет размер не менее 2

2

н

+ 1. Длина σ

н

ограничивается по

(скажем) 30

· (n + 30)

2

· 2

н

. Обратите внимание, что

Лима

северный→∞

30

· (n + 30)

2

· 2

н

2

2

н

= 0.

Для каждого

Л

Один

-срок

s (x) определить формулу ε

с

(x) (”s (x) существует") путем индукции на

сложность проведения

с:

ε

0

≡ ε

икс

я

≡

,

ε

1

≡ 0 < 1,

ε

с

0

+с

1

≡ ε

с

0

∧ ε

с

1

∧ (с

0

+ с

1

≥ max (s

0

, с

1

)),

ε

с

0

·с

1

≡ ε

с

0

∧ ε

с

1

∧ ∀г < с

1

(с

0

· (y + 1) ≥ s

0

).

Обратите внимание, что

Т

0

ε

т

н

↔ σ

н

.

Теперь для каждого ограниченно

Л

Один

-формула

ϕ (x) определить ϕ

∗

x) с помощью другой индукции: для

атомный

ϕ, set

(t

0

(x) = t

1

(икс))

∗

≡ ε

т

0

∧ ε

т

1

→ t

0

(x) = t

1

(икс),

(t

0

(x)

1

(икс))

∗

≡ ε

т

0

∧ ε

т

1

→ t

0

(x)

1

(икс).

Для

ϕ более высокой сложности, мы можем предположить, что ϕ задано в безотрицательном пренексе

форма, потому что закончилась

Т

0

, каждая формула имеет канонический эквивалент этой формы. Набор

(ϕ ∧ ψ)

∗

≡ ϕ

∗

∧ ψ

∗

,

(ϕ ∨ ψ)

∗

≡ ϕ

∗

∨ ψ

∗

,

Непоследовательность в реальном мире

185

и

(∃y)

∗

≡ ε

т

→ ∃y

∗

,

(∀y)

∗

≡ ∀г < т (х) ϕ

∗

.

для

y /

∈ {икс}. В достаточно богатой метатеории мы имеем:

Лемма 2. Если бы...

Я

0

доказывает ограниченную формулу

ϕ, затем T

0

доказывает

ϕ

∗

.

Идея доказательства. Пусть...

ϕ быть дано, а также модель

М

от

Т

0

. Мы покажем, что

М

удовлетворяет

ϕ

∗

. Мы можем предположить, что

М

имеет по крайней мере два элемента. Развернуть

Л

Один

Для

Л

М
А

путем добавления констант для всех элементов домена

M of

М

. Эти константы имеют

их каноническое толкование в

М

. (Мы не различаем между константами и

их назначение.) Развиваться

М

путем связывать с каждым

Л

М
А

- термин конечная последовательность из

элементы:

M следующим образом: a присваивается каждому a ∈ M. для молекулярного t,
рассматривайте последовательности как цифры с обобщенными цифрами и упорядочивайте их соответственно—
так последовательности равной длины упорядочиваются лексикографически. Например, пусть

t быть

(t

0

+ t

1

) и предположим, что t

я

была назначена

один

я

. Чтобы получить последовательность для

t, добавить a

0

и

один

1

так же, как вы научились складывать десятичные цифры в начальной школе. Если

полученная последовательность имеет вид (скажем)

б

0

, б

1

, затем

б

0

является

т

М

, и

б

1

подсчитывает, как часто

вы должны пройти над 0

М

в расчете на то, что:

М

. Аналогично, умножение является

выполняется по алгоритму начальной школы.

3

Таким образом, мы приходим к модели термина

М

для

Л

М
А

. Каждый термин интерпретируется соответствующей последовательностью.

М

Модели

Я

0

.

Инъекция

е:

М

→

М

, a → a

имеет свойство

М

ψ e (a) ⇒

М

ψ

∗

(ля)

для всего ограниченного

ψ (x) в L

Один

и все же...

ля ∈

М

. (

М

отображается на начальный сегмент объекта

М

.) В частности,

М

ϕ.

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

Лемма 2 индуктивно поворачивая свободные от среза производные в

Я

0

в отвлечения внутри

Т

0

.

Метаматематика внутри

Т

0

Теперь мы хотим арифметизировать синтаксис в

Т

0

. В общем случае это может быть сделано адекватно только
до определенного предела, потому что конечная модель не может иметь коды для всех конечных последовательностей.

Мы действуем в соответствии с разделом V. 3 из [2]. Многие конструкции сделаны там для

Я

0

смогите быть перенесено к

Т

0

с помощью леммы 2. С оглядкой на вещи, чтобы

3

Эта идея взята из доказательства [2]: Теорема IV. 2. 2.

186

T. Hürter

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

0

формула

π (m, n, p) (”p кодирует упорядоченную пару (m, n)") по

π (m, n, p) ≡ ∃ x ≤ p (ε

(1+1)·x

∧([ε

x·(m+n)+m

∧ (1 + 1) · x = m+n+1∧ p = x · (m + n) + m]

∨[ε

x·(m+n)+m+1

∧(1+1)·x = m+n ∧ p = x ·(m+n+1) + m]).

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

Имея под рукой упорядоченную пару, мы применяем определение V. 3. 5 из [2], чтобы получить эффективный

кодирование конечных последовательностей. Важным свойством данного кодирования является то, что “

s-конечное число

последовательность”, “

m встречается в последовательности s " и " m является i-м элементом последовательности

s " можно определить в T

0

по формулам со всеми кванторами, ограниченными

s. этого достаточно

чтобы разработать синтаксис в

Т

0

как это делается для

Я

0

в [2]: V. 3(g). По стандартным определениям мы
представляем термины, формулы, доказательства и т. д., а также синтаксические операции, такие как
подстановка. В частности, мы приходим к a

0

формула Bew

τ

(x, y) для “x является доказательством y в

теория, определенная с помощью

τ ”. Здесь мы принимаем τ (x), чтобы быть a

0

бинирование формулы

Т

0

в

бесконечные модели из

Т

0

. Мы, конечно, можем требовать этого

Т

0

σ

6

∧ ε

н

→ τ (n) ↔ τ

∗

(¯северный)

для всех

n. Звездные версии обычных условий адекватности могут быть выведены в T

0

.

Например, мы можем выразить непротиворечивость

Т

0

внутри

Т

0

Автор:

∃x Bew

τ

x, 0

∗

,

что, кстати, является теоремой из

Т

0

. (

θ - это число, которое кодирует θ.)

4. “Армагеддон”

А теперь давай

k-натуральное число, большее восьми. Примените лемму о неподвижной точке (для

формулы с только

y бесплатно) в I

0

к формуле:

σ

к

→ ∃x

к

Бью...

τ

(x, y).

Мы приходим к приговору

ϕ

к

эквивалент более

Я

0

Для

σ

к

→ ∃x

к

Бью...

τ

x, ϕ

к

.

Более пристальный взгляд на наше кодирование и доказательство леммы о неподвижной точке показывает, что

ϕ

к

2

2

к

. Следовательно

Т

0

σ

к

→ ε

ϕ

к

.

Непоследовательность в реальном мире

187

Из нашего замечания об ограничениях кванторов в кодировании конечных последовательностей вместе с
нашим требованием на

τ отсюда следует, что

ϕ

к

⇐⇒ ϕ

∗

к

над

Т

0

.

ϕ

к

граничить. По Лемме 2,

ϕ

к

является ли фиксированная точка над

Т

0

. Неофициально,

ϕ

к

утверждает, что если Вселенная имеет размер не менее 2

2

к

+ 1, нет никаких доказательств ϕ

к

ниже

2

2

к

.

Лемма 3. Для каждого натурального числа

к > 8>, т

0

подразумевает

ϕ

к

.

Доказательство. Предположим, что нет. Позволь

М

будьте образцом для подражания

Т

0

+ ϕ

к

.

Тогда Вселенная из

М

имеет размер не менее 2-х

2

к

+ 1, а в

М

, есть доказательство от

Т

0

от

ϕ

к

с кодом

p

2

к

. По правильности предиката доказательства, существует естественное

номер

n такое, что p является n-М преемником 0 в

М

и

n коды a доказательство от T

0

от

ϕ

к

в реальном мире.

4

Но

М

удовлетворяет

Т

0

, и поэтому тоже

ϕ

к

. Противоречие.

Так

Т

0

подразумевает

ϕ

к

. Можем ли мы надеяться найти доказательство для

ϕ

к

в

Т

0

? Будем надеяться, что нет!

Любое доказательство surveyable к человеку или компьютеру конечно должно иметь код под 2

2

9

. (Если

вы не согласны, поднимите

k.) представьте, что мы нашли доказательство с кодом p

2

к

. Затем

P поворотов

выходит быть "свидетелем Армагеддона" (слова Вудина).

Теорема 1. Предположим, что

p

2

к

коды a доказательство

ϕ

к

. Затем

Т

0

не имеет моделей с размером

больше чем 2

2

к

.

Доказательство. Доказательство-это Лемма 3 наоборот. Мы покажем, что

Т

0

подразумевает

σ

к

.

Предположим, что

М

|= T

0

+ σ

к

.

Затем

М

|= ε

т

к

,

т.е.,

т

к

имеет стандартное толкование. То же самое относится и к

¯

p и ϕ

к

. Но теперь это...

следовать за теми

М

|= σ

к

∧ Bew

τ

¯

p, ϕ

к

,

что противоречит

М

|= ϕ

к

.

Так

p заставляет нас заключить, что 2

2

к

не существует.

4

Это решающий шаг от формального к генетическому понятию числа.

188

T. Hürter

Ну И Что С Того?

Давайте вернемся к кошмарному видению, которое мы только что придумали. Мы построили

гипотетическую ситуацию, в которой мы видим снизу (из области генетических
чисел), что термин, предназначенный для обозначения большого натурального числа, не может получить своей
предполагаемой интерпретации. Тогда структура арифметики не может быть расширена за пределы
некоторой конечной точки. Это была бы очень плохая новость для теоретиков чисел, но пастухам,
бухгалтерам и астрономам не нужно было бы беспокоиться. Поскольку мы просто хотели показать
, что такая ситуация мыслима, мы были вольны использовать метатеоретическую бесконечность как-
суммации в нашей конструкции - до тех пор, пока мы их удерживаем вне теории объектов. Поэтому
мы изложили наш сценарий как гипотетический аргумент reductio ad absurdum: мы начали
с нашего полученного представления о бесконечности. Тогда мы вообразили, что находим ужасное

p и are

отброшено назад к

Т

0

.

5

Обратите внимание, что вместо удобного переноса известных результатов из

Я

0

Для

Т

0

по Лемме 2, мы могли бы сделать эту работу непосредственно в

Т

0

.

Естественная реакция на этот сценарий: "ну, это просто окольный аргумент, что

ϕ

к

не имеет короткого доказательства внутри

Т

0

.- Но ведь это означает принимать существование бесконечного множества
чисел как должное. Если вы серьезно отбросите предположение о бесконечности, вы не можете
исключить существование доказательства, закодированного в

p как указано выше. Завтра-блестящий математик

может проснуться и найти его.

Подтверждение. Спасибо Dieter Donder, Stefan Iwan, Godehard Link, Uwe

Люк, Хольгер Штурм и особенно Карл-Георг Нибергал за полезные комментарии и
критику.

Рекомендации

[1]

Hájek, Petr: 1984. О новом понятии частичной консервативности. Теория вычислений и доказательств
(лекционные заметки по математике 1104). Берлин: Спрингер, 217-232.

[2]

Hájek, Petr and Pavel Pudlák: 1993. Метаматематика арифметики первого порядка. Берлин:
Спрингер.

[3]

Nelson, Edward: 1986. Предикативная Арифметика. Принстон: Издательство Принстонского Университета.

[4]

Ровелли, Карло и Ли Смолин: 1995 год. Дискретность площади и объема в квантовой гравитации.
Ядерная Физика B442: 593-622.

5

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

ϕ

к

с

k параметр теории объектов. Тогда
параметризованная версия леммы 3 терпит неудачу. Если мы примем эту аналогию, то сможем экстраполировать ее обратно на
стандартный случай. Например, мы могли бы исследовать возможность доказательства локальной согласованности путем исключения

несоответствия до 2-х

к

или 2

2

к

, основываясь на доказательствах вплоть до нестандартных

k. результаты работы [1] предупреждают о некоторых

подводные камни, которые могут заманить в эту линию аргументации.

Непоследовательность в реальном мире

189

[5]

Woodin, W. Hugh: 1998. Ханойская башня. In: H. G. Dales and G. Oliveri (eds.), Правда

в математике, Оксфорд: издательство Оксфордского университета, 329-351.

Обзор
Технологий Helstorfer Straße 7
30625 Ганновер
Германия

E-mail: [email protected]