Пусть $%A,B$% - множества, чья симметрическая разность конечна. Докажите, что $%A\le_m B$% и $%B\le_m A$%

задан 19 Окт '19 4:39

Тут вроде что-то простое: на конечном A \ B полагаем f(x)=b (фиксированный элемент из B), на остальных элементах f(x)=x. Ясно, что f вычислима, и x in A iff f(x) in B.

(19 Окт '19 5:21) falcao

Тогда в условие надо добавить, что А и В непусты?

(19 Окт '19 5:46) logic

@logic: это само собой -- мелкие оговорки тут нужны. Из непустого нет отображений в пустое.

(19 Окт '19 12:26) falcao

А зачем дано то, что симметрическая разность конечна? Это как-то используется для доказательства вычислимости f? Я думал вычислимость следует из https://i89.fastpic.ru/big/2019/1021/78/350e4b14330ec2ab55865be949f09078.png

(21 Окт '19 8:38) logic

@logic: если бы A \ B было бесконечно, у нас не было бы способа определить f на этом множестве "как попало", то есть пропала бы вычислимость. А здесь функция "почти" равна тождественной, и потому вычислима. Тот факт, на который Вы сослались, здесь в принципе используется.

(21 Окт '19 9:47) falcao

А как это на более формальном уровне выразить? Если используется этот факт при доказательстве A <= B, то отношение R в данном случае (рассматриваемое как подмножество N) - это A. Но почему оно примитивно рекурсивно? Само А вроде может быть бесконечно. Наверное, тут как-то используется конечность симметрической разности.

(21 Окт '19 9:57) logic

@logic: множества тут могут быть какими угодно. Обосновать нужно только один факт: вычислимость функции, которая равна f(x)=x для всех x кроме конечного множества значений. Формально это делается при помощи "развилки", то есть той формулы, где функция по-разному себя ведёт на множестве и его дополнении. Этот факт того же уровня, что и разрешимость конечного множества. То есть алгоритм там такой: получаем x на вход, и сравниваем с элементами конечного списка. Если x попадает в список, то значение равно y по "шпаргалке". Если в списке числа нет, то выдаём x как результат.

(21 Окт '19 10:45) falcao

Если алгоритм принимает х и проверяет, лежит ли х в А, то откуда "конечный список"? Само А же может не быть конечным?

(21 Окт '19 18:24) logic

@logic: алгоритм проверяет, принадлежит ли число конечному множеству A \ B.

(21 Окт '19 19:01) falcao

Понятно. Получается, для A<=B требуется только конечность A-B; для доказательства B<=A требуется конечность B-A, а для доказательства А=В требуется оба условия, и эти два условия вместе эквивалентны конечности симметрической разности. А в условии надо помимо непустоты А и В потребовать, чтобы ни А, ни В не были равны N (натуральным числам)? В некоторых источниках требуют почему-то.

(21 Окт '19 20:38) logic

@logic: конечность симметрической разности взята как достаточное условие m-эквивалентности. В принципе, оно не необходимо.

Случаи типа A=N, B=N, скорее всего, ведут к чему-то малосодержательному. Я не знаю, надо ли этот случай специально запрещать. Здесь вроде как всё и так работает. Но лучше ориентироваться на определения из изучаемого курса, так как могут быть мелкие разночтения.

(21 Окт '19 22:00) falcao
показано 5 из 11 показать еще 6
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×32

задан
19 Окт '19 4:39

показан
269 раз

обновлен
21 Окт '19 22:00

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru