Rekurencyjność zbiorów i relacji

[primax]

Witam. Proszę o pomoc z zadaniem polegającym do udowodnieniu rekurencyjności:
następującego zbioru \(\displaystyle{ \lbrace5k+3, k\in \mathbb{N}\rbrace}\),
relacji \(\displaystyle{ \neq:x\sim y\leftrightarrow x\neq y\subset \mathbb{N}^2}\)
oraz rekurencyjności przeliczalnej zbioru
\(\displaystyle{ \lbrace p_0^{x_0}, p_1^{x_1},\ldots,p_n^{x_n}, x_0\ge x_1 \ge \ldots \ge x_n, n \in \mathbb{N} \rbrace}\), gdzie \(\displaystyle{ p_0,\ldots,p_n}\) są kolejnymi liczbami pierwszymi.

[Kartezjusz]

Co wiesz? Jakie znasz i rozumiesz definicje?