Разрешимость множества

[ugo]

Доброй ночи.

Пусть $S$ - разрешимое множество натуральных чисел. $D$ - множество простых, встречающихся в разложении чисел из $S$. Нужно доказать или опровергнуть, что $D$ - разрешимо.

Насколько я понимаю, $D$ вообще говоря неразрешимо, но вот что бы такого свести к разрешению $D$ - не могу придумать.

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

ugo в сообщении #516002 писал(а):

Насколько я понимаю, $D$ вообще говоря неразрешимо

Правильно понимаете.

Берёте перечислимое,но не разрешимое множество простых $D = \{ p_0, p_1, p_2,\ldots \}$ (числа даны в порядке эффективного перечисления). А теперь для каждого $i$ подбираете натуральное $n_i$ так, чтобы $S = \{ p_0^{n_0} < p_1^{n_1} < p_2^{n_2} < \ldots \}$.