OliForum Matematico

1 - Dimostrare che se un albero non ha foglie (cioè nodi senza figli), esiste un ramo infinito.
2 - Dimostrare che se in un albero ogni nodo ha un numero finito di figli, e in totale c'è un numero infinito di nodi, esiste un ramo infinito


La 1) è equivalente al fatto che in un gioco finito, un giocatore ha una strategia vincente.
La 2) è equivalente... a un bel problema irrisolto del forum

Ah, visto che i problemi sono abbastanza intuitivi... inviterei a formalizzare bene le vostre dimostrazioni.

edriv ha scritto:Ah, visto che i problemi sono abbastanza intuitivi... inviterei a formalizzare bene le vostre dimostrazioni.

Questa richiesta rende i problemi non elementari. Sposto...

edriv ha scritto:2 - Dimostrare che se in un albero ogni nodo ha un numero finito di figli, e in totale c'è un numero infinito di nodi, esiste un ramo infinito

Mi lancio:

Ora e in seguito considero ramo un insieme di nodi tali che:

-la radice appartiene al ramo;

-il padre di ogni nodo diverso dalla radice e appartenente al ramo, appartiene al ramo;

-per ogni nodo appartenente al ramo, al piu' un figlio di quel nodo appartiene al ramo.

ALLORA:

Dato un nodo, esiste uno e un solo ramo tale che quel nodo appartiene al ramo ma suo figlio no.

Quindi esistono infiniti rami.

Dato un nodo appartenente a n rami, esiste per il pigeonhole un figlio appartenente a almeno, detto k il numero dei figli, $ \lceil\frac{n-1}{k}\rceil $ rami.

Dato un nodo x, sia f(x) il figlio di x appartenente a piu' rami (rispetto agli altri figli di x); se ce n'e' piu' d'uno a parimerito, ne scelgo uno qualunque (assioma di scelta).

Chiamiamo r la radice.

Sia F l'insieme dei nodi esprimibili come f(f...f(r)..))

F e' un ramo.

Ogni elemento di F e' contenuto in infiniti rami.

Ora supponiamo per assurdo che la cardinalita' di F sia finita.

Prendiamo il nodo che richiede il maggior numero di f per essere scritto. Questo nodo non ha figli, quindi appartiene a un solo ramo. Assurdo.

Rilancio: trovare il problema nel forum che si risolve utilizzando esclusivamente questo fatto.

Ok, il punto 2 si poteva scrivere più concisamente così: "Consideriamo il sottoalbero di tutti i nodi che hanno infiniti discendenti. Per ipotesi non è vuoto (c'è la radice), e ovviamente non ha foglie. Quindi, per il punto 1, ha un ramo infinito."

Poi per dimostrare il punto 1 devi appunto per forza usare l'assioma della scelta. Però nella tua dimostrazione il punto debole è appunto definire l'insieme dei nodi "che si possono scrivere come f(f(....))", una volta definito questo è chiaro che hai ottenuto il tuo bel ramo infinito.

Un modo di definirlo sarebbe: un insieme tale che la radice appartiene all'insieme, il padre di ogni nodo che non sia la radice appartiene all'insieme, ogni nodo è la f del padre.
Questo (in particolare in base alla definizione di piever) è un ramo, ed è infinito perchè la funzione f(nodo) è iniettiva e il suo codominio è un sottoinsieme proprio del dominio.

Quanto al "rilancio", quel problema ha un bel topic tutto per sè, quindi chi ha voglia di risolverlo lo risolva là!!