Помогите, пожалуйста, доказать: Пусть множества А и В отличаются друг от друга конечным числом элементов. Доказать, что если А вычислимо (вычислимо перечислимо), то множество В вычислимо (вычислимо перечислимо).

задан 26 Июн '17 20:43

10|600 символов нужно символов осталось
1

Для конечного множества можно составить "шпаргалку", какие элементы ему принадлежат. Если некоторое множество A вычислимо (разрешимо), то рассматриваем разрешающий алгоритм. Подаём на вход число n; проверяем принадлежность множеству A. Потом по "шпаргалке" смотрим, принадлежит ли n множеству B. На основании этого можно получить алгоритм проверки произвольного числа как объединению A U B, так и разности A-B. Отсюда ясно, что добавление или изъятие конечного множества не влияет на разрешимость.

С перечислимостью всё аналогично. Если надо напечатать A U B, то сначала печатаем элементы конечного множество B, а потом начинаем печатать A по перечисляющей процедуре. Если же надо напечатать A-B, то начинаем перечислять A, и проверяем принадлежность элемента множеству B перед тем, как выдать его на печать. Если оно у нас записано в "шпаргалке", то не печатаем это число.

ссылка

отвечен 26 Июн '17 21:18

@falcao: А что такое у вас конечное множество? Это элементы на которые они отличаются?

(26 Июн '17 22:37) 12345Ann

Я не понимаю, зачем здесь говориться об объединении и разности. Начало понятно, что запускаем алгоритм для множества А. Не понятно, что такое это "шпаргалка" и как по ней определяется принадлежность. Но понятно, что если все это проходит, то тем самым можем сказать, что множество В вычислимо.И это следует из вычислимости множества А. А с перечислимостью уже не понятно, как из того, что А вычислимо перечислимо, следует, что и В вычислимо перечислимо?

(26 Июн '17 22:46) 12345Ann

@12345Ann: начать надо вот с чего: у нас есть два множества A1 и A2, которые отличаются конечным множеством элементов, то есть их симметрическая разность конечна. Мы хотим превратить A1 в A2; как это сделать? Для начала надо убрать из A1 то, что не принадлежит A2. Это какое-то конечное множество -- скажем, B1. Далее надо добавить то, что принадлежит A2 и не принадлежит A1. Это какое-то конечное множество B2. То есть у нас две операции: добавление конечного множества B (абстрактного), и вычитание какого-то конечного множества, которое я тоже обозначаю B.

"Шапаргалка" -- это конечный список.

(26 Июн '17 23:21) falcao

@falcao: Спасибо, уже лучше понимаю. А как изменится решение, если множества А и В отличаются друг от друга только элементами, не превосходящими некоторого фиксированного числа а?

(26 Июн '17 23:36) 12345Ann

@12345Ann: если числа не превосходят фиксированного a, то они образуют конечное множество. Поэтому получится частный случай того, что уже рассмотрено.

(27 Июн '17 0:14) falcao

@falcao: Понимаю, что это частный случай. Но вопрос в том, что при доказательстве этого частного случая, можно просто сослаться на общее доказательство,ничем его не дополняя?

(27 Июн '17 0:17) 12345Ann

@12345Ann: разумеется, можно. Меня такого рода вопросы, честно говоря, удивляют, потому что я не понимаю причин их возникновения. Ведь это следует из общих правил логики, которые существуют как бы сами по себе. Что-то доказано про всех людей; Сократ -- человек. Можно ли доказанное применить к Сократу? :)

(27 Июн '17 0:20) falcao

@falcao: Знаю, что вопрос глупый) Просто переживаю за то, а примут ли такое доказательство, вдруг скажут, ну и что, что частный случай и то доказано, а вы конкретно для него расскажите. Поэтому хочется заранее разобраться во всех мелочах) И есть еще вопрос. А если дополнения множеств А и В отличаются друг от друга только элементами, не превосходящими некоторого фиксированного числа а, это ведь тоже частный случай?

(27 Июн '17 0:25) 12345Ann

@12345Ann: если Вы при ответе хотите показать, что решали именно частный вариант, а не общий, то можно рассказывать общее доказательство в другом виде -- скрывая факт знакомства с общим фактом. Подставляете туда другие слова, соответствующие своему варианту. Правда, я не уверен, что именно так следует поступать -- можно в начале сказать, что мы будем доказывать более общий факт, частным случаем которого является данный. Это обычный приём рассуждения; его часто используют.

Утверждение о том, что дополнения A, B отличаются только элементами <=a, тождественно такому же утверждению про сами A, B.

(27 Июн '17 4:36) falcao
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×730
×113

задан
26 Июн '17 20:43

показан
517 раз

обновлен
27 Июн '17 4:36

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

по почте:

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

по RSS:

Ответы

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

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