I've got an interesting task from my friend and didn't understand, how to prove that:
The family $\text{CF} \cup \left\lbrace \omega \right\rbrace$ is not computable.
$\text{CF}$ is the family of all graphs of computable functions.
$\left\lbrace \omega \right\rbrace$ - Ordinal number.
The family is computable if it's characteristic function $\chi$ is computable.
Let $A \subseteq \omega^n$ - set of tuples from natural numbers. Then it's characteristic function $\chi A : \omega^n \to \omega$ defined like $\chi A(k_1, . . . , k_n) = 0$, if $(k_1, . . . , k_n) \in A$ and $1$, if $(k_1, . . . , k_n) \in \omega^n \setminus A$.
$A \subseteq \omega^n$ is computably enumerable set if $A(x_1, x_2, . . . , x_n) \iff φ(x_1, x_2, . . . , x_n) \downarrow$ for some partial computable function.
- Also, I have the theorem about graphs:
Let $\psi(x_1, x_2, . . . , x_k )$ - Partial function, then $\psi$ - partial computable function, if and only if it's set of graphs $Γψ = { '\langle'x_1, x_2, . . . , x_k, y'\rangle' | ψ(x_1, x_2, . . . , x_k ) = y}$ - is computably enumerable sets.