Существуют ли такие неразрешимые множества A и B, что множество A+B разрешимо?

задан 30 Май '18 15:33

Если множество A неразрешимо, то его дополнение также неразрешимо. Их объединение -- всё множество натуральных чисел. Оно разрешимо.

(30 Май '18 20:50) falcao

Спасибо, конечно, но речь не об объединении, а о множестве, состоящем из всевозможных сумм элементов из A и B. Иначе никакого вопроса и нет.

(30 Май '18 21:06) kabenyuk

@kabenyuk: вопрос у меня не вызвал подозрений, так как на эту тему бывали задачи ещё более лёгкие, как это ни странно. Для поэлементной суммы вместо объединения, конечно, получается чуточку интереснее. Сейчас изложу.

(30 Май '18 21:32) falcao
10|600 символов нужно символов осталось
0

Если нам дано какое-то неразрешимое подмножество X множества N, то по нему многими способами строятся новые неразрешимые множества, элементы которых встречаются "редко". Например, множество чисел вида 100x, где x принадлежит X. Или множества степеней двойки вида 2^x, где числа неразрешимого множества становятся ещё более "редкими". Поскольку дополнение также неразрешимо, мы располагаем примерами, где элементы неразрешимого множества встречаются "часто".

Каждое натуральное число, начиная с 2, можно представить в виде суммы двух чисел, ни одно из которых не делится на 10 (или даже на 3). Поэтому, если A и B будут дополнениями неразрешимого множества 10X, то A+B станет разрешимым множеством (все числа без 1).

ссылка

отвечен 30 Май '18 21:37

То есть можно взять А=В. Потрясающе. Спасибо. А ведь я понимал, что можно строить такие матрешки неразрешимых множеств. А вот подишь ты.

(31 Май '18 6:44) kabenyuk
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×196
×26

задан
30 Май '18 15:33

показан
127 раз

обновлен
31 Май '18 6:44

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

по почте:

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

по RSS:

Ответы

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

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