Ejercicio 1. Demostrar que las funciones \(h_1 : \mathbb{N} \rightarrow \mathbb{N}\) y \(h_2 : \mathbb{N} \rightarrow \mathbb{N}\) se encuentran en toda clase PRC.
Ejercicio 2. Decidir si el siguiente conjunto es i) p.r., ii) c.e. y co-c.e., iii) sólo c.e., iv) sólo co-c.e., v) ni c.e. ni co-c.e.
Ejercicio 3. Decidir si cada una de las siguientes afirmaciones es verdadera o falsa y justificar.
i) Si \(A\) y \(B\) son dos conjuntos no computables tal que \(A \subset B\), entonces existe \(C\) no computable tal que \(A \subset C \subset B\).
ii) Si \(A\) es un conjunto de índices no trivial, entonces existe un conjunto de índices no trivial \(B\) tal que \(B \subset A\).
Ejercicio 4. Decidir si el siguiente conjunto es i) p.r., ii) c.e. y co-c.e., iii) sólo c.e., iv) sólo co-c.e., v) ni c.e. ni co-c.e.