Вычисление характеристической функции

[Dandan]

Тут есть другой "философский" вопрос

Вот давайте построим функцию g:N->N так:
в качестве g(1) возьмем любое число из $\{1\}$
в качестве g(2) возьмем любое число из $\{1,2\}$
...
в качестве g(k) возьмем любое число из $\{1,...,k\}$
...

Будет ли g вычислима? Мы ж на каждом шаге получили значение g(k), значит будет наверное ?

[Профессор Снэйп]

Dandan писал(а):

Что нужно показать? Что в этом множестве любое A вычислимо или что найдется некоторое A, которое вычислимо? Или нам по условию дано, что существует ровно одно такое A?

Нужно показать, что любое $A$ будет вычислимо.

Господа! Давайте решать конкретную задачу, а не забалтывать тему обсуждением "философских" вопросов. Если Русту охота быть конструктивистом --- его право, вот только пусть он пишет об этом в другой теме. Эта задача предназначена для тех, кто мыслит в рамках классической логики. К обсуждаемой задаче нежелание Руста понять её условие не имеет никакого отношения! А если охота очередной раз пофлудить по поводу топика --- заводите тему в дискуссионном разделе и вперёд.

Ещё раз повторю условие. Даны какие-то конкретные $f$ и $A$, связанные отношением $f(x_1, \ldots, x_m) \neq A(x_1) + \ldots + A(x_m)$. Известно, что $f$ вычислима. Надо доказать, что $A$ также вычислимо.

Вот тривиальная задача для пятого класса, в которой можно усмотреть похожую "проблему". Даны целые числа $a,b > 1$, причём $a$ делится на $2b$ . Известно, что $a$ не делится на $4$. Надо доказать, что $b$ не делится на $2$. При некоторых $a$ может существовать несколько различных $b$, для которых выполнено условие задачи. Ну и что? Ведь при любых допустимых $b$ это число всегда будет нечётным. Если следовать логике Руста, то задача некорректно задана и не имеет решения, ибо $b$ неоднозначно зависит от $a$. Но я думаю, что любой разумный человек согласится с корректностью этой задачи и с тем, что она имеет нормальное решение. А ежели так, то что может в исходной задаче не понравиться?

[Dandan]

Как будут выглядеть для f подходящие A приблизительно понятно.

Пусть m=2 и пусть есть некоторая $f$ для которой существует хоть одно подходящее A.

Для доказательства утверждения (или для построения контрпримера) можно считать, что $f(x_1,x_2)=f(x_2,x_1), f(x_2,x_1)=1$. Почему: если $f$ не такая, то можно просто построить "исправленную" симметричную $f^\prime$, такую, что если A подходит для $f$, то A подходит и для $f^\prime$. Т.е. симметричное исправление не уменьшает множества подходящих A.

Далее, если $f(x_1,x_2)=1$, то $x_1, x_2$ одновременно либо принадлежат подходящему A либо не принадлежат. Значит все числа можно разбить на классы эквивалентности : $f(x_1,x_2)=1 ~=>~ x_1 \sim x_2 $ (+ транзитивное замыкание). Каждый класс целиком либо принадлежит A либо не принадлежит.
Также для понимая подходящих A можно использовать следующие утверждения:
если $x,y,z$ из разных классов, то
1. $f(x,y)=0,f(x,z)=0,f(y,z)=2 ~~=>~~ x \in A$
2. $f(x,y)=2,f(x,z)=2,f(y,z)=0 ~~=>~~ x \not\in A$

Почему подходящие A будут вычислимы пока не понятно.

[Профессор Снэйп]

Ну да, непонятно. Ввели некоторое отношение эквивалентности, оно перечислимо и если два числа эквивалентны,то $A(x)$ принимает на них одинаковое значение. Ну и что?

[Dandan]

ну и какое предполагаемое решение?