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

Question

В главе 8 Дугласа Хофстадера «Годель, Эшер, Бах» читателю предлагается перевести эти два утверждения в ТНТ:

"b - это сила 2"

и

"b - это сила 10"

Правильны ли следующие ответы?:

(при условии, что '& # x2203;' означает 'существует число'):

& # x2203; x: (x.x = b)

т.е. «существует такое число« x », что x умноженное на x равно b»

Если это правильно, то следующий в равной степени тривиален:

& # x2203; x: (x.x.x.x.x.x.x.x.x.x = b)

Я в замешательстве, потому что автор указывает, что они хитры и что второй должен занять часы, чтобы решить; Должно быть, я что-то упустил здесь очевидное, но не вижу этого!

Answer 1

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

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

РЕДАКТИРОВАТЬ: Это не работает в течение 10 (спасибо за комментарии). Но, по крайней мере, это работает для всех простых чисел. Сожалею. Я думаю, что вы должны использовать какие-то последовательности кодирования в конце концов. Я предлагаю «Теоремы Гёделя о неполноте» Раймона Смулляна, если вы хотите подробный и более общий подход к этому.

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

Попробуйте это:

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 "

Answer 2

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

Answer 3

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

Answer 4

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

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

2. Если 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 & экв .; 1 (мод с-1), затем.

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

4. Мы можем сформулировать формулу, выражающую «b - это степень 10» (для лучшей читаемости мы опускаем символы & lang; и & rang; и пишем 2 и 5 вместо SS0 и SSSSS0):
   & Существуют; a: & Существуют; C: & Существуют; d: (EXP (2, a) ∧ EXP (5, c) ∧ EXP (5, d) ∧ d> b ∧ a & sdot; c = b ∧ & 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 может быть простым числом). Тогда «наименьшее е ...» равно (5 ^z ) ^y = d ^y & экв .; 2 ^y (мод 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 → i = j.

Answer 5

как насчет:

& forall; x: & forall; y: (SSx & # x2219; y = b & rarr; & Существовать; z: z & # x2219; SS0 = SSx)

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

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

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

Answer 6

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

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

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

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

Или

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

Или

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

Или

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

Или

b - это степень 2

Answer 7

мое решение для b - это степень двойки: ∀x: ∃y x.y = b (isprime (x) => x = SS0)

isprime () писать не должно быть сложно.

Answer 8

Для открытого выражения, означающего, что 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.

Я все еще работаю над проблемой степени 10.

Answer 9

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

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

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

Answer 10

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

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

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