Agli ordini!

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Agli ordini!

Messaggio da edriv » 29 ago 2008, 08:53

Sia A un insieme. Ora faccio un po' di definizioni che chi le sa già ovviamente può comodamente saltare..

Un ordine su A è una relazione $ ~ R \subset A \times A $ tale che:
- ogni elemento è in relazione con se stesso: $ (a,a) \in R $
- soddisfa la proprietà antisimmetrica: se $ (a,b) \in R $ e $ (b,a) \in R $ allora $ a=b $
- è transitiva: $ (a,b) \in R $ e $ (b,c) \in R $ allora $ (a,c) \in R $.
Ma piuttosto che scrivere $ (a,b) \in R $ si preferisce $ a \le b $.

Esempi di ordine sono (divertitevi a dimostrare che lo sono):
- a divide b nei naturali
- a è sottoinsieme di b, tra i sottoinsiemi di un dato insieme
- esiste una funzione non decrescente f tale che f(a(x)) = b(x), tra tutte le funzioni da un insieme ordinato in se stesso.

Due elementi a,b si dicono confrontabili se $ (a,b) \in R $ oppure $ (b,a) \in R $.
Un ordine in cui gli elementi sono a due a due confrontabile si dice totale.
Esempi di ordine totale:
- l'ordine dei naturali, interi, razionali, reali e tutti i loro sottoinsiemi.

Infatti se ho un ordine su A, prendendo un sottoinsieme di A posso restringere la relazione su di esso, ottenendo un nuovo ordine (che si chiama sottoordine).
Un sottoinsieme di A in cui questo ordine indotto è totale si chiama catena
Invece, un sottoinsieme in cui gli elementi sono a due a due non confrontabili, si dice anticatena.
Ad esempio, nei naturali con la divisibilità, le potenze di 2 formano una catena, i primi un'anticatena.

Ora siamo pronti per il problema:
dimostrare che un insieme ordinato infinito ha una catena infinita o un'anticatena infinita

fph
Site Admin
Messaggi: 3613
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 29 ago 2008, 17:56

Mi sto perdendo qualcosa o l'insieme $ \mathbb N $ con l'ordinamento "$ a \leq b $ se e solo se a=b" soddisfa l'ipotesi ma non la tesi?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 29 ago 2008, 19:49

A me quello sembra il più semplice esempio di anticatena infinita, uhm..

eli9o
Messaggi: 106
Iscritto il: 14 mag 2008, 19:43

Messaggio da eli9o » 29 ago 2008, 22:49

Intanto grazie ad edriv per averci fatto questo mini-corso (in effetti era un po' che ero curioso di sapere cosa c'era scritto nella firma di salva90, sempre che sia questo eh). Posso chiedere se e dove posso trovare una dispensa o qualcosa di simile che tratta queste cose?

Ho provato ad immaginarmelo con i grafi (anche se il mio tentativo mi sembra un po' incompleto): i vertici corrispondono agli elementi dell'insieme e i lati sono tutte e sole le relazioni tra 2 elementi.
Allora ricadremo sicuramente in almeno una di queste 2 possibilità:
(1) avremo infiniti sottografi disgiunti (si dice così?) e in questo caso basterebbe prendere un vertice da ciascun sottografo per avere un'anticatena infinita
(2) avremo almeno un sottografo connesso con infiniti vertici (proviamo a dimostrare che ne esiste uno infinito completo): la proprietà transitiva ci garantisce che data una terna di vertici, se abbiamo 2 lati allora c'è anche il terzo. Se c'è un terna con i 3 lati (un triangolo) all'interno di questo grafo infinito ci dev'essere un'altro vertice in relazione con almeno 1 di questi 3. Ma allora, considerando la terna costituita da il vertice esterno al triangolo di partenza, quello del triangolo collegato ad esso ed un'altro a caso dei 3 iniziali avremo almeno 2 lati e quindi anche il terzo, poi consideriamo l'altra terna analoga e otteniamo un grafo completo con 4 vertici. Vediamo che se il grafo con n vertici è completo, solo per il fatto della proprietà transitiva lo deve essere anche quello con n+1 che si forma aggiungendo un vertice. Questo vertice dev'essere in relazione con almeno uno del sottografo completo di ordine n, quindi consideriamo tutte le terne di vertici composte da questi 2 e al variare tutti gli altri. Queste hanno tutte almeno 2 lati quindi ne avranno tutte 3... Così abbiamo il grafo completo. Quindi possiamo iterare questo passaggio infinite volte ed avere un grafo infinito completo che costituisce quindi una catena infinita.
Rimane da controllare il caso in cui il grafo infinito è connesso e tutti i suoi vertici hanno un solo lato. Questo è evidentemente impossibile... Quando hai legato i primi 2 non puoi più "attaccargli" nemmeno un vertice, figuriamoci infiniti!



Considerando il fatto che ultimamente scrivo più strafalcioni che cose esatte, linciatemi pure

Edit: ho scritto un po' meglio una delle molte cose che potevano essere poco chiare...

carlop
Messaggi: 13
Iscritto il: 16 gen 2008, 06:45
Località: Pisa

Messaggio da carlop » 30 ago 2008, 10:27

L'idea di usare i grafi è buona, anche se mi sa che c'è qualche errore...

Se $ B \le A $ e $ C \le A $ non è detto che $ B \le C $ oppure $ C \le B $, quindi il passo induttivo non funziona.

Ci provo io usando i grafi..

Come prima cosa eliminiamo i "doppioni": se esistono due elementi $ $A $ e $ $B $ tali che $ A \le B $ e $ B \le A $, eliminiamo uno dei due elementi.

O esistono infiniti equivalenti di un determinato elemento oppure anche dopo aver eliminato tutte le "copie" l'insieme è composto da infiniti elementi. Nel primo caso, prendiamo tutte le copie di un certo elemento e formano una catena infinita. Continuiamo ora con l'insieme infinito senza ripetizioni.

Aggiungiamo all'insieme di partenza un elemento fittizio, il "minimo" $ $M $, tale che per ogni elemento $ $x $ $ M \le x $.

Creiamo ora un grafo con un nodo per ogni elemento dell'insieme (minimo compreso) e con un arco tra due nodi $ $A $ e $ $B $ se $ A \le B $ ma non esiste nessun altro elemento tale che $ A \le C \le B $ (oppure $ B \le A $ ma non esiste nessun $ $C $ tale che $ B \le C \le A $).

Il grafo ottenuto è aciclico, cioè non si può trovare un percorso chiuso muovendosi lungo gli archi, per costruzione.

Un grafo aciclico è anche detto albero, se l'albero ha infinite foglie (nodi con un unico arco uscente) l'insieme delle foglie costituisce una anticatena (dovendo essere collegate, tramite un qualche percorso al "minimo" è impedito che due foglie possano essere connesse tra loro). Se l'albero ha un numero finito di foglie, consideriamo il numero di nodi in ciascun percorso tra "minimo" e foglie, la somma delle distanze tra "minimo" e foglie è maggiore o uguale al numero di nodi totali, quindi infinita, quindi almeno uno dei percorsi ha infiniti nodi ed è la catena infinita cercata.

Spero di non essere stato troppo confuso nella spiegazione (e che non ci siano troppi errori) , al solito ottima proposta da parte di edriv.

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 30 ago 2008, 12:09

Per ora però tutte le soluzioni sono sbagliate...

A eli90 è già stato spiegato perchè (iconducendoti solo a un grafo perdi troppa struttura del tuo originale ordine...).

Per carlop, a parte la strana idea di eliminare i doppioni (sembra che non hai letto molto attentamente la proprietà antiriflessiva) ci sono davvero un sacco di errori. Quindi ti invito a cercarli da solo... ad esempio, come si comporta la tua dimostrazione con Q? Com'è il grafo che tu definisci, in questo caso? E c'è davvero un'anticatena infinita?
Posso chiedere se e dove posso trovare una dispensa o qualcosa di simile che tratta queste cose?
Mah, queste cose sono cultura generale che dopo un po' impari... non ho mai letto una dispensa di teoria degli ordini.

ciao a tutti!

fph
Site Admin
Messaggi: 3613
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 30 ago 2008, 15:47

edriv ha scritto:A me quello sembra il più semplice esempio di anticatena infinita, uhm..
Ok, mi sto perdendo qualcosa (o non sono più capace di leggere un testo :D). Scusa per la perdita di tempo.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 30 ago 2008, 16:43

edriv ha scritto:Per carlop, a parte la strana idea di eliminare i doppioni (sembra che non hai letto molto attentamente la proprietà antiriflessiva)
Secondo me è un errore di interpretazione comprensibile, perché come ti riferisci ad una relazione d'ordine generica con <=, potresti riferirti ad una relazione d'equivalenza generica con = (il che è proibito, ma magari qualcuno non lo sa...). Quindi, nella definizione d'ordine, per maggior chiarezza, andrebbe specificato che l'= che usi è proprio l'UGUALE standard: a=b se e solo se a e b sono lo stesso elemento di A.

carlop
Messaggi: 13
Iscritto il: 16 gen 2008, 06:45
Località: Pisa

Messaggio da carlop » 30 ago 2008, 18:13

Cerchiamo di sistemare un po' di cose del mio primo, goffo, tentativo....
me medesimo ha scritto: Aggiungiamo all'insieme di partenza un elemento fittizio, il "minimo" $ $M $, tale che per ogni elemento $ $x $ $ M \le x $.

Creiamo ora un grafo con un nodo per ogni elemento dell'insieme (minimo compreso) e con un arco tra due nodi $ $A $ e $ $B $ se $ A \le B $ ma non esiste nessun altro elemento tale che $ A \le C \le B $ (oppure $ B \le A $ ma non esiste nessun $ $C $ tale che $ B \le C \le A $).
Gli archi introdotti sopra li prendiamo orientati nel verso indicato dall'ordine.

L'insieme dato dai nodi "destinazione" degli archi uscenti da un determinato nodo è un anticatena, perchè non possono esservi elementi confrontabili, se vi fossero allora ci sarebbe una contraddizione con la scelta degli archi da inserire.

Se un determinato nodo ha infiniti archi uscenti possiamo ottenere una anticatena infinita, ora basta affrontare il problema di nodi con numero finito di archi uscenti.

Costruiamo ora i seguenti insiemi:
$ $a_0 $ contenente il nodo "minimo"
$ $a_n $ contenente tutti i nodi destinazione di archi che partano in $ $a_{n-1} $ non ancora assegnati ad un qualche insieme

Se in numero massimo di archi uscenti da un qualsiasi nodo è $ $K $, ogni insieme $ $a_i $ può contenere al massimo $ $K^i $ elementi, ma comunque un numero finito di elementi.

Gli $ $a_i $ sono tutti disgiunti e la loro unione deve contenere tutti gli elementi dell'insieme di partenza, che sono infiniti, quindi devono esistenere un numero infinito di tali insiemi.

Per costruire una catena di lunghezza $ $L $ possiamo prendere un elemento qualsiasi in $ $a_L $, poi prendere un elemento di $ $a_{L-1} $ che sia origine di un arco che arrivi all'elemento prescelto in $ $a_L $ e così via, passando man mano da un insieme all'altro, l'unione del primo elemento scelto e di tutti i suoi "predecessori" è una catena.
Questa procedura la possiamo attuare anche con infiniti insiemi, ottenendo quindi la catena infinita cercata.

Spero di aver capito qualcosa di più del problema, questa mattina mi era sfuggito più di qualcosa...

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 30 ago 2008, 21:35

Sì ma se non leggi quello che scrivo io... non è che la tua dimostrazione sia migliorata di molto.
Prova a partire da Q e fare la tua costruzione.
Ottieni un grafo in cui due punti distinti non sono mai connessi (perchè tra due razionali c'è sempre un altro razionale).
Ora mi spieghi come fai a tirare fuori da un grafo di questo genere una catena infinita??

Poi stai attento che se con la tua costruzione riesci a tirar fuori catene di lunghezza n per ogni n, non è detto che tu ne prenda una infinita...
$ \mbox{grande quanto vuoi} \neq \mbox{infinito} $

Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein » 01 set 2008, 12:40

Premetto di non aver letto le risposte altrui(non lo faccio mai quando provo a risolvere un problema qui,ovviamente): se dovessi aver fatto gli stessi errori,basta che mi dite vedi su :) .
Allora io cercherò in tutti i modi di evitare la tesi per doverci inevitabilmente cascare su(poi magari casco io nel frattempo), quindi: non può esistere un insieme infinito di elementi confrontabile solo con un numero finito di elementi, altrimenti esisterebbe un anticatena infinita presto fatta tra gli elementi di un opportuno sottoinsieme infinito di questo insieme. Ora prendiamo uno di questi elementi, a, confrontabile con infiniti altri, chiamando l'insieme degli infiniti altri $ A $ ora questo insieme degli infiniti altri è davvero infinito: riapplico il lemma, ovvero ci sono infiniti elementi di A confrontabili con infiniti altri di A, ma io ne prendo di nuovo uno solo, b. Ma ora gli infiniti altri di b generano un insieme infinito $ B $ sottoinsieme di A a cui possiamo applicare il lemma proprio come ad A: la cosa curiosa è che a e b sono confrontabili, e anche il c che ne verrà fuori(lo tiro fuori da B come ho tirato fuori a dall'insieme generale e b da A )è confrontabile sia con a che con b. Ora posso continuare questa operazione infinite volte( e sempre con elementi nuovi, perchè essendo infiniti i possibili, ed essendo finiti i precedenti, ho sempre modo di tirarne fuori nuovi)...e tutti gli elementi che io prendo così sono confrontabili con tutti i precedenti...ovvero formano una catena infinita...solo una cosa io ho pensato e scritto, perchè l'idea non mi sembrava malaccio, però potrebbero esserci seri errori, poichè non l'ho proprio passata al vaglio critico...quindi non vi innervosite troppo in tal caso...e prendetela più come uno spunto per la soluzione(probabilmente errato) che la soluzione stessa....faccio tutto ciò(ovvero non sistemo per bene) perchè non ho tantissimo tempo in questo periodo...mi scuso
Ultima modifica di Carlein il 01 set 2008, 16:35, modificato 3 volte in totale.
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 01 set 2008, 13:07

Dammi solo un a capo, una maiuscola, un punto, uno spazio, un paragrafo, ed io sarò salvato!

Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein » 01 set 2008, 13:17

LOL!
chiedo scusa :oops: , l'ho detto che ho scritto di getto :D . vabbeh magari dopo pranzo vado a correggere la forma, nel caso però non mi dovessi accorgere durante il pasto di errori di sostanza. In tal caso cancello. Se comunque qualche temerario(in effetti la sto rileggendo e sembra un post di gpdimonderose :lol: ) la leggesse sarei contento delle eventuali correzioni sulla sostanza(che se totali, mi risparmierebbero la riscrittura :D ).
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 01 set 2008, 13:20

Carlein ha scritto:..quindi non vi innervosite troppo in tal caso...
Ma che Zeus ti fulmini, piuttosto!
Hai avuto una bella idea, l'hai risolto brillantemente nel modo più semplice possibile, ma dovevi per forza nasconderla in un flusso di coscienza dostoevskijano la dimostrazione? :D

Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein » 01 set 2008, 13:42

E' che quando ho scritto l'avevo appena concepita in quell'ordine: lo so che si fa difficoltà a immaginarlo, ma l'ho dovuta ordinare un pò nella mia testa prima di farla arrivare a quella forma indecente.Figurati se scrivevo davvero in flusso di coscienza :shock: :D . Beh forse mi bannavate :lol: :lol:
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"

Rispondi