задача на вычислимо-перечислимость множества

[Lex3939]

Множество Х является рекурсивным подмножеством $N^2$, а множество У является наименьшим отношением эквивалентности на $N$,которое содержит Х. Доказать,что множество У является Вычислимо-перечислимым. под множество $N$ понимается, естественно, множество натуральных чисел.

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

Ну... Смотря что Вы понимаете под "доказательством".

Если по простому, то перечисляем все конечные последовательности $\{ (x_0, \ldots, x_k) : k \in \mathbb{N} \}$ натуральных чисел, для каждой проверяем, верно ли, что $(x_i, x_{i+1}) \in X$ или $(x_{i+1}, x_i) \in X$ при каждом $i < k$ и, если верно, перечисляем пару $(x_0,x_k)$ в множество $Y$.

Если же требуется что-то более формальное, то разворачивайте определения! В первую очередь определения вычислимого и вычислимо перечислимого подмножеств $\mathbb{N}^2$.