Hola,
Para el primero hay varias formas de hacerlo. La estándar es la siguiente. Supongamos (por reducción al absurdo) que existe una biyección \( f: \mathbb{N} \longrightarrow P(\mathbb{N}) \). Considera el conjunto \( X= \{ n \in \mathbb{N} : n \not\in f(n) \} \). X es un subconjunto de naturales y como f es biyectiva, existe un natural m tal que X=f(m). Trata de llegar a una contradicción a partir de aquí (el argumento es una adaptación de la paradoja de Russell).
Para el segundo, hay dos nociones de primalidad y de irreducibilidad en retículos : meet y join. Hago el de join y te dejo el otro. Recordemos que x es join-irreducible si \( x = a \vee b \) implica \( x=a \) o \( x=b \). Y x es join-primo si \( x \leq a \vee b \) implica \( x \leq a \) o \( x \leq b \).
Supongamos que x es join-primo. Sea \( x= a \vee b \). Entonces, en particular, \( x \leq a \vee b \), luego por join-primalidad, \( x \leq a \) o \( x \leq b \). Si \( x \leq a \) demuestra que \( x = a \) y si \( x \leq b \) demuestra que \( x = b \), lo que implica que x es join-irreducible (no pierdas de vista el hecho de que \( x = a \vee b \)).
Para el tercero, nota que \( \{0,1\}^* = \bigcup_{n \in \mathbb{N}} \{0,1 \}^n \). Usando que \( \{0,1 \}^n \) es numerable (de hecho finito) para todo n natural y que la unión numerable de conjuntos numerables es numerable, se sigue el resultado.
Saludos
