В арифметике Пеано доказать бесконечность простых чисел

[mathematician123]

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

Простоту числа можно определить так:

$$P(x) \Leftrightarrow \forall a \forall b (x = ab \rightarrow a = 1 \lor b = 1)$$

Утверждение о бесконечности множества простых:

$$\forall n \exists p(p > n \land P(p))$$

Если следовать доказательству Евклида, то нужно рассмотреть число $p_1p_2 \ldots p_k + 1$. Проблема в том, чтобы определить число $p_1p_2 \ldots p_k$. Я не знаю как определить это число средствами арифметики Пеано. Ещё есть вариант попробовать определить число $n!$. Обычно факториал определяется рекурсивно: $0! = 0$, $n! = n (n-1)!$. Можно ли такое определение формализовать в арифметике Пеано?

[zykov]

mathematician123 в сообщении #1590047 писал(а):

Я не знаю как определить это число средствами арифметики Пеано

Да так и определить.
Предикат простоты числа есть же?
Вот и перемножте все числа, для которых предикат верен.

[mihaild]

zykov в сообщении #1590049 писал(а):

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

Это не так-то просто. Я сходу не могу придумать, как определить произведение набора чисел, заданного предикатом, без общих заморочек с кодированием произвольных вычислений.

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

[mathematician123]

mihaild в сообщении #1590051 писал(а):

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

То есть, определить факториал возможно?

[mihaild]

mathematician123 в сообщении #1590052 писал(а):

То есть, определить факториал возможно?

Для произвольной вычислимой частичной функции $f$ от $n$ переменных существует $\Sigma_1$-формула $F$ от $n + 1$ переменной, такая что $F(x, y_1, \ldots, y_n) \leftrightarrow x = f(y_1, \ldots, y_n)$. Но это технически довольно сложный результат.

[mathematician123]

Кажется, придумал. Нам достаточно доказать, что существует число, делящееся на все числа меньшие $n$

$$\forall n \exists x \forall m \exists y(m < n \rightarrow x = my) $$

Если обозначить

$$P(n) \Leftrightarrow \exists x \forall m \exists y(m < n \rightarrow x = my) $$

Тогда по индукции доказаваем, что $\forall n P(n)$. Для доказательства $P(n+1)$ берём $x = nz$, где $z$ делится на все числа меньшие $n$.

[zykov]

mihaild в сообщении #1590051 писал(а):

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

$f(1)=1$
для $n>1$, если $n$ - простое, то $f(n)=n f(n-1)$, иначе $f(n)=f(n-1)$.

[mihaild]

zykov в сообщении #1590076 писал(а):

для $n>1$, если $n$ - простое, то $f(n)=n f(n-1)$, иначе $f(n)=f(n-1)$.

Что за $f$? Никакого $f$ в сигнатуре арифметики Пеано нет.
Я имел в виду - по формуле $F(x)$ с одной свободной переменной написать формулу $G(n, m)$ с двумя свободными переменными, которая в стандартной модели означает $n = \prod\limits_{x \leq m, F(x)} x$.

[zykov]

mihaild в сообщении #1590097 писал(а):

Что за $f$?

Функция из натуральных чисел в натуральные.