Задача по математической логике

[Nt.Mag1steR]

Число является двойкой в степени Х

y=2(в сепени Х)

Показать, что его можно выразить в стандартной интерпритации арифметики:
тоесть носитель интерпритации - множество натуральных чисел, есть одна константа НОЛЬ, определена одна унарная операция S - увеличение на единицу и две бинарных: плюс и умножение.

Помогите кто знает.

При этом такой вариант:
Существует такое Z0=s(0), Существует такое Z1...Zn=s(s(0)) что y=z0*z1*...*zN

Такой вариант не подходит, так как троеточия в станартной итерпритации нет

перемещаю // нг

[luitzen]

Основная идея: любой делитель либо чётен, либо является единицей.

Верещагин, Шень, с. 102

[Dandan]

luitzen писал(а):

Основная идея: любой делитель либо чётен, либо является единицей.

Верещагин, Шень, с. 102

это если бы нужно было выразить, что y - какая-то степень двойки. А нам дано конкретное x. В этом случае делается так - вводим одноместный предикат f:

f(0)=s(0), f(z+s(0))=f(z)\cdot s(s(0))

и тогда y=f(x)

[Nt.Mag1steR]

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

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

Правильное решение (сорри за кривое оформление)

A(y): (Для всех)z (существует такое)k (y=kz) => ( z=s(0) ) v ( z=s(s(0)) )

Тоесть истина, что число игрек разлагается на k делителей, каждый из которых равен 2 или 1. При наличие других делитей формула ложна, а значит y не = 2 (в степени х)

[Dandan]

Мда, так получается конкретного X нам не дано и luitzen был прав. Только так, как вы записали вроде не правильно.
А если все же пробовать выразить A(y,x): y=2^x, то у меня без дополнительного функционального символа не получилось (возможно это вообще нельзя сделать). Тут надо подумать.

[Nt.Mag1steR]

да, как я понял от преподавателя, здесь можно сказать "у есть степенью двойки", вот как

[neo66]

Nt.Mag1steR писал(а):

Правильное решение (сорри за кривое оформление)

A(y): (Для всех)z (существует такое)k (y=kz) => ( z=s(0) ) v ( z=s(s(0)) )

Вы, наверное, хотели сказать следующее:
$A(y)= \{ (y=kz) \Rightarrow (\exists t: (k=s(s(0))t;) \vee (k=s(0);) \}$

[Nt.Mag1steR]

Нет, я хотел сказть так, как я сказал, и никак иначе. У вас в варианте z - свободная переменная вообще

[Dandan]

Nt.Mag1steR писал(а):

Нет, я хотел сказть так, как я сказал, и никак иначе. У вас в варианте z - свободная переменная вообще

Ну так поставте перед формулой $\forall z \forall k$. А в вашей формуле получается $\forall y \neq 0 ~ A(y) = true$ потому, что $\forall z \exists k=2y ~ \{ (y=kz) = false \} $