Pagina 1 di 1

Zermelo e gli Insiemi

MessaggioInviato: 20/09/2005, 12:41
da Bemipefe
...visto che nella sezione generale nessuno sapeva rispondermi....vediamo se in campo universitario qualcuno ne sà qualcosa.

Dato un insieme A x A con A = {1 , 2 , 3 , 4}....
Quante Relazioni di Transitività si possono individuare in tale insieme?

Il numero di queste è anche il numero di Relazioni Transitive che si deve raggiungere per affermare che C = AxA gode della proprietà transitiva?


In altre parole per dire che esistono ad esempio 2 relazioni di transitività in V devono essere tutte diverse le coppie di ognuna delle due prorpietà individuate ?

Se è così allora il numero di proprietà individuabili in C (C = A x A) è prorpio il numero di Proprietà che Dovrebbero ipoteticamente stare in C per affermare che esso gode di proprietà transitiva?


Aiutatemi ! Please! :)

<b><u>Bemipefe</u></b>

MessaggioInviato: 20/09/2005, 15:10
da Piera
Dato un insieme A x A con A = {1 , 2 , 3 , 4}....
Quante Relazioni di Transitività si possono individuare in tale insieme?

il problema da te posto è di difficile risoluzione, attualmente non esistono formule semplici per risolvere problemi di questo tipo,
in questo articolo www.cs.uwaterloo.ca/journals/JIS/VOL7/P ... iffer6.pdf
(se non trovi l'articolo digita su google counting transitive relations
e guarda un link simile a quello scritto)
si trova una formula , inoltre nelle ultime pagine c'è una tabella dove puoi vedere quante relazioni transitive ci sono con 4 elementi

se proprio ti vuoi esercitare con problemi di questo tipo,
ti consiglio di provare a risolvere problemi MOLTO più semplici
tipo:
Dato un insieme A x A con A = {1 , 2 , 3 , 4}
quante relazioni si possono definire?
quante sono riflessive?
quante simmetriche?
quante riflessive e simmetriche?
quante antisimmetriche?
quante riflessive simmetriche e transitive (cioè di equivalenza)?
sempre nell'articolo trovi una tabella con il risultato di questi
quesiti

MessaggioInviato: 20/09/2005, 16:22
da Bemipefe
Io vorrei caro "Piera" che tu rispondessi alle tue stesse domande...perchè è prorpio questo che vorrei sapere.

Con la proprietà transitiva è più complicato ok e poi ti viene il dubbi quando hai una coppia che già hai usato per individuare una terna transitiva e la vuoi utilizzare per un altra tera in cui però come ho detto c'è un elemento che appartiene ad un altra terna transitiva....questo non sò quanto sia corretto.

Vorrei sapere ad esempio quante ce ne sono riflessive oppure semplicemente quante ce ne sono o si possono definire.

Il mio problema è che non ho capito e se un insieme tipo A x A ad esempio può avere al massimo 12 coppie di coppie cioè (a;b) e (b;a) che egodono della propietà simmetrica.

Secondo al massimo ne puoi individuare 12 in quanto ci sono esattamente 12 coppie che hanno tutte la loro inversa, quindi si escludono ovviamente le coppie riflessive.

<b><u>Bemipefe</u></b>

MessaggioInviato: 20/09/2005, 18:38
da Piera
se un insieme ha n elementi, l’insieme della parti , cioè l’insieme di
tutti i sottoinsiemi ha 2^n elementi
1) quante relazioni si possono costruire
una relazione è per definizione un sottoinsieme dell’insieme AxA
ora, il prodotto cartesiano ha 4*4=16 coppie, quindi le relazioni sono
2^16

2)quante sono riflessive
traccia su un sistema cartesiano le 16 coppie,
una relazione per essere riflessiva deve avere TUTTE le coppie sulla
diagonale, (1,1) (2,2), (3,3) (4,4)
ad esempio R: (2,1) (4,2) (1,1) (2,2), (3,3) (4,4) è riflessiva
per costruire una relazione riflessiva le coppie (1,1) (2,2), (3,3) (4,4)
ci devono essere sempre, poi posso aggiungere a mio piacere altre coppie tra quelle
rimanenti che sono 16 – 4 = 12, allora i modi in cui posso aggiungere le 12 coppie rimanenti
sono tanti quanti i sottoinsiemi da un insieme di 12 elementi cioè 2^12
quindi le relazioni riflessive sono 2^12

3) quante sono simmetriche
per essere simmetrica occorre che se , ad esempio, c’è la coppia (1,2) ci deve essere
anche la coppia (2,1)
ad esempio R: (1,1) (1,2) (2,1) è simmetrica, questo significa che per costruire una relazione simmetrica si possono considerare tutte le coppie simmetriche tipo (1,2) e (2,1) come un unico elemento, quindi per costruire queste relazioni utilizzo le coppie sulla diagonale
(1,1) (2,2), (3,3) (4,4) che sono 4 e le coppie simmetriche prese come un solo elemento
che sono in tutto quante le coppie che stanno sotto la diagonale (oppure sopra tanto il numero è lo stesso),in totale posso utilizzare 4 + 6 =10 coppie formando 2^10 relazioni simmetriche

4) riflessive e simmetriche
se nel ragionamento fatto sopra la relazione deve essere anche riflessiva, le 4 coppie sulla diagonale
ci devono essere SEMPRE, quindi posso usare 10 – 4 = 6 coppie
adesso le relazioni sono 2^6

i punti 5) e 6) li tralascio perché sono più difficili

visto che sicuramente non sono stato molto chiaro, ti dò le seguenti
formule:
sia A un insieme di n elementi e si consideri AxA, allora
1) 2^(n^2) sono le relazioni che si possono costruire
2) 2^(n^2-n) sono quelle riflessive
3) 2^[(n^2+n)/2] sono simmetriche
4) 2^[(n^2-n)/2] sono riflessive e simmetriche

TI RISPONDO DA QUI PERCHé TU POSSA TENERE PRESENTE LE FORMULE SCRITTE SOPRA CHE NON ME LE SONO INVENTATE MA CHE SONO BEN NOTE IN LETTERATURA
ADESSO CERCO DI SPIEGARTI IL PUNTO 1)QUANTE RELAZIONI SI POSSONO DEFINIRE

una relazione è per definizione un sottoinsieme di AxA
se |A|=4 , cioè se A ha 4 elementi, il prodotto cartesiano ne ha 16 e fin qui non ci sono dubbi
dalla definizione segue posso costruire una relazione con una sola coppia
oppure con due coppie
oppure con tre coppie
....
oppure con nessuna coppia
oppure con tutte le coppie
è abbastanza intuitivo che ne posso costruire tantissime
ti invito a provare a costruire alcune relazioni che hanno esattamente 3 coppie

comunque io affronterei questi problemi di carattere combinatorio
(tengo a precisare che sono cose difficili per chiunque)
solo in un corso di matematica discreta o di combinatoria se mai lo farai, adesso ti conviene solo capire le definizioni magari prova a ragionare solo con A=2 elementi e vedere che le relazioni sono in tutto 2^4=16

MessaggioInviato: 22/09/2005, 17:58
da Bemipefe
Scusami "Piera" ma non mi è molto chiara la tua teoria......cioè non mi convince.

Ti dico quello che penso io:

<u>Qunte relazini si possono individuare:</u>

Tu dici che se ne possono individuare 2^16 ???

ma 2 ^16 = 65536 .... e sinceramente non credo che in Pordotto cartesiano con 16 elementi si possano fare così tante relazioni.

relazioni di che tipo poi?

In A x A gli elementi sono coppie di valori e avendo A cardinalita = 4 (#A = 4) ....io al massimo avrò quattro elementi che corrispondono alla coppia del tipo (x ; x).
Quindi posso individuare al massimo n coppie riflessive do n = #A

Quelle simmetriche poi sono invece due coppie a e b in cui a è simmetrica a b, del tipo a = (x;y) e b = (y;x).
Quindi avendo due coppie "a" e "b" in esame posso costruire (16)coppie x (16-1)coppie = s sottoinsiemi contenenti 2 coppie. Il -1 è motivato dal fatto che ogni coppia "a" deve stare in relazione con una delle restanti 15 coppie a cui è stato tolto la coppia "a".

Quindi al massimo ho 240 sottoinsiemi da 2 ma quanti di questi possono soddisfare la simmetria?

Un numero preciso di certo.
In A ci sono 4 elementi , il proddo cartesiano crea 16 coppie, per studiare la simmetricità creo 240 sottoinsiemi da due coppie.

Quindi si escudono subito le coppie riflessive , sapendo che in A x A ci sono 16 elementi tali che ogni coppia a appartenente a A x A e ogni coppia b appartenente a A x A è a diversa da b. cioè ad esempio la coppia (1:1) sarà in relazione con altre 15 coppie senza trovare la simmetrica. E così vale anche per le altre 3 coppie rifelssive che in tutto sono 4.

Quindi in totale si escludono
[1 (coppia) * 15 (coppie)] + [1 (coppia) * 15(coppie)] + [1 (coppia) * 15(coppie)] + [1 (coppia) * 15(coppie)] = 15 x 4 = 60

Rimangono 240 - 60 = 180 sottoinsiemi da 2 coppie da studiare.

Ora però riflettendo sul fatto che ogni coppia in A x A è diversa dall'altra si arriva a dire che al massimo ogni coppia "a" avrà solo una coppia "b" che soddisfa la simmetricità.

Quindi ne risulta che dei 180 sottoinsiemi di due coppie rimasti , solo 12 potranno soddisfare la simmetricità, in quanto ci sono 12 coppie non riflessive con cui è possibile costruire un sottoinsieme avente per elementi le coppie simmetriche a e b.


Per la transitività non saprei .... dovrei raggruppare le coppie di A x A in sottoinsiemi da 3 e sarebbe poi più complicato....

<b><u>Bemipefe</u></b>