Successioni con 0 e 1 periodiche

[40rob]

Volevo porre un quesito, non ci ho ragionato tantissimo su, però il quesito è questo.
Indichiamo con $P$ l'insieme delle successioni formate con $0$ e $1$ periodiche, cioé che da un certo punto in poi ripetono una stessa sequenza finita di cifre.
Ad esempio

$001011110101010101010101010101...$
$1101011101001001001001001001001...$
ecc.

Questo insieme è ovviamente numerabile quindi è possibile piazzare ogni elemento di $P$ in un elenco numerabile in modo esaustivo.
Ora se dato un elenco di $P$ diagonalizziamo (estraiamo la successione formata dalla diagonale dell'elenco cambiando $0$ in $1$ e $1$ in $0$) otteniamo una successione che non è presente nell'insieme $P$ di partenza.
Se indichiamo con $I$ l'insieme delle successioni ottenute per diagonalizzazione di ogni elenco (esaustivo) possibile di $P$, l'insieme $I \cup P$ contiene tutte le successioni possibili di $0$ e $1$?
O ce n'è qualcuna che di sicuro non c'è?
Se qualcuna non c'è, quale non c'è e perché non c'è?

[40rob]

Risolto, le contiene tutte.

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$.

[vict85]

Non ho letto tutto, ma ho l'impressione che tu stia dando per scontato che "diagonalizzando" tu ottenga necessariamente un elemento dell'insieme di partenza. Ma questo è falso.

[40rob]

"vict85":Non ho letto tutto, ma ho l'impressione che tu stia dando per scontato che "diagonalizzando" tu ottenga necessariamente un elemento dell'insieme di partenza. Ma questo è falso.

"bub":Ora se dato un elenco di $P$ diagonalizziamo (estraiamo la successione formata dalla diagonale dell'elenco cambiando $0$ in $1$ e $1$ in $0$) otteniamo una successione che non è presente nell'insieme $P$ di partenza.

Ho scritto non. Ho scritto l'esatto contrario.

[vict85]

Hai ragione, ho letto male.

[40rob]

Ma sono riuscito a spiegarmi? O non s è capito nulla?

[vict85]

Avevo letto velocemente io e pensavi volessi mostrare che \(P\) contenesse tutte le successioni. Mi sembra che in generale sia corretto, anche se forse un po' contorto.

Poteva essere fatto in maniera, secondo me, più semplice osservando che la proprietà che cerchi di dimostrare vale per \(P\) se e solo se vale per l'insieme delle successioni finite (infatti puoi sempre supporre di prendere una successione di elementi in \(P\) tali per cui l'antiperiodo sia più lungo dell'indice nella successione ).

[40rob]

Comunque le liste di elementi di $P$ per formare $I$ (con la diagonalizzazione) devono contenere tutti gli elementi di $P$, devono essere insomma esaustive.
Nessuna di queste liste può avere ogni elemento (estratto da $P$) con antiperiodo maggiore della posizione che occupa nella lista. In $P$ ce ne sono infiniti di elementi con lo stesso antiperiodo, devono starci tutti quanti poi nella lista da diagonalizzare, non ne puoi escludere alcuni.

Ho scritto più volte che questi elenchi devono essere esaustivi, cioé contenere tutti gli elementi di $P$. Nessun elenco che si prende per diagonalizzarlo e formare $I$ possiede la proprietà che dici perché conterrà necessariamente infinite successioni con antiperiodo di lunghezza $0$, infinite successioni con antiperiodo di lunghezza $1$, infinite successioni con antiperiodo di lunghezza $2$ e così via.

In questi elenchi devono andarci a finire tutti gli elementi di $P$, se si potevano eliminare degli elementi di $P$ l'avrei dimostrato anche io più semplicemente.
E' un vincolo del problema questo che non può essere violato, le liste per formare poi $I$ per diagonalizzazione devono contenere tutti gli elementi di $P$.

Ma può essere anche che non ho capito bene, puoi spiegarti meglio?

[vict85]

Non vedo queste cose da molti anni, e comunque non è una cosa che abbia molto approfondito. Ora ho capito ora quello che indendi dire, non stavo mettendo tutti gli elementi di \(P\). Mi sembra evidente che sia troppo arrugginito in queste cose per esserti davvero di aiuto .