Годель, Эшер, Бах Типографские теории чисел (ТНТ) и решения

Ответ 1

Ваши выражения эквивалентны утверждениям "b - квадратное число", а "b - 10-я степень числа" соответственно. Преобразование "полномочий" в TNT значительно сложнее.

Ответ 2

В общем, я бы сказал, что "b - степень 2" эквивалентно "каждому делителю b, кроме 1, кратно 2". То есть:

∀x ((∃y (y * x = b и ¬ (x = S0))) → ∃z (SS0 * z = x))

EDIT: Это не работает на 10 (спасибо за комментарии). Но, по крайней мере, это работает для всех простых чисел. Сожалею. Я думаю, что вы должны использовать какие-то кодирующие последовательности. Я предлагаю "теоремы о неполноте Гёделя" Раймонда Смуллиана, если вы хотите получить подробный и более общий подход к этому.

Или вы можете кодировать последовательности чисел, используя теорему китайского остатка, а затем кодировать рекурсивные определения, чтобы вы могли определить степень возведения в степень. Фактически, это в основном то, как вы можете доказать, что арифметика Peano завершена.

Попробуйте следующее:

D(x,y)=∃a(a*x=y)
Prime(x)=¬x=1&∀yD(y,x)→y=x|y=1
a=b mod c = ∃k a=c*k+b

Тогда

∃y ∃k(
 ∀x(D(x,y)&Prime(x)→¬D(x*x,y)) &
 ∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z<x→¬D(z,y))→(k=1 mod x)) &
 ∀x∀z(D(x,y)&Prime(x)&D(z,y)&Prime(z)&z<x&∀t(z<t<x→¬(Prime(t)&D(t,y)))→
  ∀a<x ∀c<z ((k=a mod x)&(k=c mod z)-> a=c*10))&
 ∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z>x→¬D(z,y))→(b<x & (k=b mod x))))

должно указывать "b - мощность 10", на самом деле говоря "существует число y и число k такое, что y является произведением различных простых чисел, а последовательность, закодированная с помощью k, пропуская эти простые числа, начинается с 1, обладает свойством что следующий элемент c из a равен 10 * a и заканчивается b"

Ответ 3

Там есть решение проблемы "b - это проблема 10" за кнопкой спойлера в скептическом ученом post post здесь. Это зависит от теоремы о китайском остатке от теории чисел и существования произвольно длинных арифметических последовательностей простых чисел. Как указал Хофстадтер, его нелегко придумать, даже если вы знаете соответствующие теоремы.

Ответ 4

как насчет:

∀x: ∀y: (SSx∙y = b → ∃z: z∙SS0 = SSx)

(на английском языке: любой коэффициент b, который является & ge; 2, должен быть делит на 2, буквально: для всех натуральных чисел x и y, если (2 + x) * y = b, то это означает, что существует естественный число z такое, что z * 2 = (2 + x).)

Я не уверен на 100%, что это разрешено в синтаксисе TNT и пропозициональное исчисление, прошло некоторое время с тех пор, как я просмотрел GEB.

(edit: для задачи b = 2 ⁿ я могу понять, почему 10 ⁿ будет более сложным, поскольку 10 не является простым, но 11 ⁿ будет одним и тем же, кроме замены одного термина "SS0" на "SSSSSSSSSSS0".)

Ответ 5

При выражении "b - сила 10" вам фактически не нужна теорема китайского остатка и/или кодирование конечных последовательностей. Вы также можете работать следующим образом (мы используем обычные символы как |, > , c-d, как ярлыки для формул/терминов с очевидным значением):

• Для простого числа p обозначим EXP (p, a) некоторую формулу в TNT, говорящую, что "p - простое число, a a - степень p". Мы уже знаем, как его построить. (По техническим причинам мы не считаем, что S0 является степенью p, поэтому ~ EXP (p, S0).)

• Если p - простое число, мы определяем EXP _p (c, a) ≖ & lang; EXP (p, a) ∧ (c-1) | (a-1) & rang;. Здесь символ | является ярлыком для "делений", который может быть легко определен в TNT с использованием одного квантора существования и умножения; то же самое имеет место для c-1 (a-1, соответственно), что означает "d, что Sd = c" (Sd = a, соответственно). Если выполняется EXP (p, c) (т.е. C - степень p), то формула EXP _p (c, a) гласит, что "a является степенью c", так как a & equiv; 1 (mod c-1), затем.

• Имея свойство P чисел (т.е. неотрицательные целые числа), существует способ, как передать в TNT наименьшее число с этим свойством: & lang; P (a) ∧ & forall; c: & lang; a > c → ~ P (a) & rang; & rang;.

• Мы можем указать формулу, выражающую "b - степень 10" (для лучшей читаемости мы опускаем символы & lang и & rang;, и мы пишем 2 и 5 вместо SS0 и SSSSS0):
  & exist; a: & exist; c: & exist; d: (EXP (2, a) ∧ EXP (5, c) ∧ EXP (5, d) ∧ d > b ∧ a & sdot; c = b ∧ & forall; e: (e > 5 ∧ e | c ∧ EXP ₅ (e, c) → ~ EXP ₅ (e, d)) ∧ & forall; e:( "e является наименьшим таким что EXP ₅ (c, e) ∧ EXP ₅ (d, e)" → (d-2) | (ea))).

Объяснение: Напишем b = a & sdot; c = 2 ^x & sdot; 5 ^y (x, y > 0) и выбрать d = 5 ^z > b таким образом, что z и y взаимно просты (например, z может быть простым). Тогда "наименьшее e..." равно (5 ^z) ^y= d ^y & equiv; 2 ^y (mod d-2) и (d-2) | (ea) влечет a = 2 ^x= e mod (d-2) = 2 ^y (мы также имеем d-2 > 2 ^y 'и' d-2 > a '), и поэтому x = y.

Примечание. Этот подход легко адаптируется для определения "b - степень n" для любого числа n с фиксированным разложением a ₁ a ₂... a _k, где каждый a _i является степенью простого p _i и p _i= p _j → я = j.

Ответ 6

Вот что я придумал:

∀c: ∃d: < (с * д = б) → < (с = SO) v∃e: (д = е * ССО) →

Что означает:

Для всех чисел c существует число d, такое, что если c раз d равно b, то либо c равно 1, либо существует число e такое, что d равно e раз 2.

или

Для всех чисел c существует число d, такое, что если b является коэффициентом c и d, то либо c равно 1, либо d является фактором 2

или

Если произведение двух чисел равно b, то один из них равен 1 или один из них делится на 2

или

Все делители b являются либо 1, либо делятся на 2

или

b - степень 2

Ответ 7

Я думаю, что большинство из приведенных выше показало, что b должно быть кратным 4. Как насчет этого: ∃b: ∀c: < < ∀e: (c ∙ e) = b и ~ ∃c ': ∃c' ':( ssc' ∙ ssc '') = c > → c = 2 >

Я не думаю, что форматирование прекрасное, но оно гласит:

Существует такое b, что для всех c, если c является коэффициентом b и c простым, то c равно 2.

Ответ 8

Вот что я придумал для утверждения "b - сила 2"

∃b: ∀a: ~ ∃c: ((a * ss0) + sss0) * c = b

Я думаю, что это говорит: "Существует число b, такое, что для всех чисел a не существует числа c такого, что (a * 2) + 3 (другими словами, нечетное число больше 2) умножается на c, дает вам b." Итак, если b существует и не может быть нулем и не имеет нечетных делителей больше 2, то не обязательно будет b, 1, 2 или другой степенью 2?

Ответ 9

Для открытого выражения, означающего, что b является степенью 2, у меня есть ∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = b

Это эффективно говорит, что для всех a S (Sa ∙ SS0) не является фактором b. Но в нормальных условиях S (Sa ∙ SS0) 1 + ((a + 1) * 2) или 3 + 2a. Теперь мы можем изменить формулировку как "нечетное число, которое не менее 3 является фактором b". Это верно тогда и только тогда, когда b является степенью 2.

Я все еще работаю над b, это проблема в 10 проблемах.

Ответ 10

Мое решение для b является степенью двух: ∀x: ∃y x.y = b (isprime (x) = > x = SS0)

isprime() не должно быть трудным для записи.