Risolto, le contiene tutte.
Testo nascosto, fai click qui per vederlo
Basta notare che:
1) Per ogni $n$, $P$ contiene infinite successioni che all'$n$-esimo posto assumono come valore $0$
2) Per ogni $n$, $P$ contiene infinite successioni che all'$n$-esimo posto assumono come valore $1$
e che $P$ è chiuso rispetto all'operazione di "complementazione", cioé l'operazione che trasforma una successione nella sua complementare...
$c(0100010100100000101010101...) = 1011101011011111010101010...$
e all'operazione di sostituzione iniziale di sequenza finita
$s(011110, 0100010100100000101010101...) = 0111100100100000101010101...$
3) $forall x (x in P -> c(x) in P)$
4) $forall x (x in P -> forall y( y$ è una sequenza finita $ -> (s(y,x) in P))$
Grazie a queste quattro proprietà si può mostrare che data una successione $a !in P$, $a$ si può ottenere lungo la diagonale di un elenco esaustivo di elementi di $P$.
Sia $a !in P$, e supponiamo che gli elementi di $P$ stiano in un elenco $e$ numerabile qualsiasi.
Disponiamo $a$ su una diagonale di un elenco "vuoto" e prediamo il primo elemento (chiamiamolo $b$) dell'elenco $e$ e facciamo scorrere orizzontalmente $b$ sull'elenco vuoto dove giace la diagonale $a$ fino a che non otteniamo che il valore di questa linea $b$ non coincide con un qualche valore della diagonale $a$. A questo punto lasciamo in questa posizione dell'elenco $b$, e continuiamo analogamente col secondo, il terzo, il quarto elemento di $e$ e così via cercando di posizionarli nei posti della lista rimasti liberi.
Dovrà capitare per forza questa cosa, che $b$ coinciderà con qualche valore facendolo scendere giù.
Se per assurdo non capitasse vorrebbe dire che da un certo punto in poi i valori di $b$ risultano tutti invertiti rispetto a quelli di $a$ e potremmo perciò ottenere $a$ tramite le due operazioni 3) e 4) a partire da $b$ e quindi $a$ apparterrebbe a $P$, ma questo non può essere perché abbiamo supposto che $a !in P$.
Continuando ad estrarre elementi dall'elenco $e$ ragionando in modo analogo si mostra che prima o poi troveranno un valore comune con la diagonale e quindi un posto nell'elenco (che costruiamo un po' alla volta) che genera $a$.
Grazie infine poi alle proprietà 1) e 2) dovranno essere esauriti tutti i posti dell'elenco inizialmente vuoto dove giace la diagonale $a$.
Da questo segue che $a$ si può ottenere anche per diagonalizzazione perché il "complemento" di $a$ (la successione con valori $0$ e $1$ invertiti rispetto ad $a$) lo stesso non appartiene a $P$.