Matematica Discreta
Lezione del giorno 12 aprile 2010
Dopo che nel 1901 Tarry aveva dimostrato la non esistenza di 2 quadrati latini ortogonali di ordine n=6 (dando così una risposta negativa al problema dei 36 ufficiali di Eulero) rimaneva ancora aperta la congettura di Eulero, nella quale si affermava la non esistenza di 2 quadrati latini ortogonali di ordine n per tutti i numeri naturali n della forma n=4k+2=6,10,14,18,22,……
Finalmente nel 1959 Bose e Shrikhande riuscirono a costruire una coppia di quadrati latini ortogonali di ordine 22, dimostrando che la congettura di Eulero era falsa. Inoltre, sempre nel 1959, Parker riuscì a costruire una coppia di quadrati latini ortogonali di ordine 10, utilizzando un computer UNIVAC dell’epoca.
Ecco un esempio di 2 quadrati latini ortogonali di ordine 10 (per semplicità gli elementi dei quadrati sono i numeri 0,1,2,,,,,9):
Infine, unendo i loro sforzi, congiuntamente Bose, Shrikhande e Parker dimostrarono che per ogni n>6 esiste una coppia di quadrati latini ortogonali di ordine n, chiudendo definitivamente la questione.
Dunque solo per n=2 (caso banale) ed n=6 (Tarry) non è possibile costruire una coppia di quadrati latini ortogonali di ordine n (ossia un quadrato greco-latino di ordine 6) ed Eulero si sbagliava di molto nel formulare la sua congettura.
Parallelamente procedevano le ricerche nella teoria dei piani proiettivi: servendosi della cosiddetta teoria dei campi finiti i matematici erano riusciti a dimostrare che un piano proiettivo di ordine n esiste certamente se n è potenza di un numero primo.
Dunque per valori di n come 2=21,3=31,4=22,5=51,7=71,8=23,9=32,11=111 etc… è possibile costruire un piano proiettivo di ordine n (e perciò per tali valori di n, per il Teorema di Bose, è possibile costruire (n-1) quadrati latini di ordine n ortogonali a 2 a 2).
Restava aperto il problema dei valori di n che non erano potenza di un numero primo, per esempio n=6,10,12,14,15,18….
Come già detto, per ognuno tali valori n costruire un piano proiettivo di ordine n era equivalente, per il Teorema di Bose, a costruire (n-1) quadrati latini di ordine n a 2 a 2 ortogonali.
Abbiamo già visto che ciò era impossibile per n=6.
Il successivo caso non risolto era il numero n=10: é possibile costruire un piano proiettivo di ordine 10 (oppure equivalentemente costruire 9 quadrati latini di ordine 10 a 2 a 2 ortogonali) ?
Il fatto che Parker nel 1959 avesse costruito 2 quadrati latini ortogonali di ordine 10 poteva essere incoraggiante nei tentativi di costruire un piano proiettivo di ordine 10.
Con l’avvento dei mezzi informatici, la ricerca ebbe nuovo impulso finché, nel 1989, dopo parecchi mesi di calcoli su un computer VAX, Lam riuscì a dimostrare che un piano proiettivo di ordine 10 non esiste (il racconto di tale scoperta si può trovare nell’articolo “The search for a finite projective plane of oder 10” all’indirizzo http://www.cecm.sfu.ca/organics/papers/lam/paper/html/paper.html).
Resta a tutt’oggi aperto il problema dell’esistenza di un piano proiettivo di ordine n=12: esso dovrebbe contenere n2+n+1=144+12+1=157 punti (ed altrettante rette); su ogni retta dovrebbe esservi n+1=13 punti; per ogni punto dovrebbero passare n+1=13 rette; inoltre per 2 punti dovrebbe passare una sola retta e 2 rette dovrebbero incontrarsi solo in un punto.
In modo equivalente si dovrebbero costruire 11 quadrati latini di ordine 12 a 2 a 2 ortogonali.
Fino ad ora nessuno dei 2 approcci ha avuto successo.
Relazioni di equivalenza in un insieme.
Supponiamo che A sia un insieme non vuoto e che sia definita una relazione R dall’insieme A all’insieme A (si dice anche che R è una relazione definita in A): quindi la relazione R associa elementi di A con elementi di A (spesso mediante un predicato P(x,y) in 2 variabili). Ricordiamo che con il simbolo aRb (dove a,b sono elementi di A) si intende indicare che l’elemento a è associato all’elemento b nella relazione R (quindi i valori x=a, y=b rendono vera la proposizione P(a,b)).
Diremo che R è una relazione di equivalenza se R soddisfa le seguenti 3 proprietà:
1) riflessiva: per ogni aA si ha aRa (quindi ogni elemento a di A è associato a sé stesso)
2) simmetrica: per ogni a,bA, se aRb allora bRa (quindi se un elemento a di A è associato ad un elemento b di A, allora l’elemento b è associato all’elemento a)
3) transitiva: per ogni a,b,cA, se aRb e bRc allora aRc (quindi se un elemento a di A è associato ad un elemento b di A, e se l’elemento b è associato ad un elemento c di A, allora l’elemento a è associato all’elemento c).
Esempio: definiamo la relazione R nell’insieme dei numeri naturali N mediante il predicato “x+y è pari”, e verifichiamo se è una relazione di equivalenza.
Proprietà riflessiva: per ogni aA si ha aRa, perché a+a=2a è pari. Proprietà simmetrica: per ogni a,bA, se aRb allora bRa, perché se a+b è pari anche b+a=a+b lo è (per la proprietà commutativa della somma). Proprietà transitiva: per ogni a,b,cA, se aRb e bRc allora aRc, perché se a+b, b+c sono pari, allora è pari la loro somma a+c+2b, dunque, sottraendo il pari 2b, anche a+c è pari.
Si conclude che R è un esempio di relazione di equivalenza definita nell’insieme N dei numeri naturali.
Classi di equivalenza
Sia definita nell’insieme A una relazione di equivalenza R.
Fissato un aA, possiamo costruire il sottoinsieme di A formato dagli elementi x che sono associati ad a nella relazione R :
{ xA / aRx } (notiamo che è equivalente scrivere aRx oppure xRa per la proprietà simmetrica) Tale sottoinsieme contiene almeno l’elemento a stesso (infatti per la proprietà riflessiva si ha aRa) dunque non è vuoto: esso è chiamato classe di equivalenza rappresentata dall’elemento a ed è indicato con il simbolo [a]:
[a] = { xA / aRx }
(l’elemento a è detto rappresentante della classe [a] ).
Esempio: nella relazione R dell’esempio precedente, costruiamo alcune classi di equivalenza fissando vari rappresentanti:
[3] = { xN / 3Rx } = { xN / 3+x è pari }= {1,3,5,7,….} = {numeri naturali dispari}
[8] = { xN / 8Rx } = { xN / 8+x è pari }= {2,4,6,8,….} = {numeri naturali pari}
[5] = { xN / 5Rx } = { xN / 5+x è pari }= {1,3,5,7,….} = {numeri naturali dispari}
In generale, ricordando che la somma di 2 numeri naturali è pari solo quando sono entrambi pari o dispari, si ottiene che per un generico rappresentante aN la classe [a] da esso rappresentata coincide con l’insieme dei numeri naturali dispari (se a è dispari) o con l’insieme dei numeri naturali pari (se a è pari): dunque in questo esempio le diverse classi di equivalenza sono in tutto 2 sottoinsiemi di N: {numeri naturali dispari}, {numeri naturali pari}.
Come visto nell’ultimo esempio, elementi diversi dell’insieme possono essere rappresentanti di classi di equivalenza uguali: il numero 3 e il numero 5 sono rappresentanti della stessa classe di equivalenza [3]=[5]={numeri naturali dispari}. Il criterio per stabilire quando due elementi sono rappresentanti della stessa classe di equivalenza è il seguente:
Teorema. Sia definita nell’insieme A una relazione di equivalenza R.
Allora dati a,bA si ha:
[a ] = [b] aRb Dimostrazione:
(): per ipotesi [a] = [b]; l’elemento a [a] (per la proprietà riflessiva), e dunque a[b] (essendo per ipotesi [a] = [b]), ossia aRb (tesi).
(): per ipotesi aRb; la tesi [a]=[b] richiede la dimostrazione di una doppia inclusione insiemistica [a] [b] e [a] [b].
Dimostriamo che [a] [b] : preso un generico elemento x[a] si ha xRa; da xRa e dall’ipotesi aRb si ha bRx (per la proprietà transitiva), dunque x [b], e si può concludere che [a] [b].
Viceversa dimostriamo che [b] [a]: preso un generico elemento x[b] si ha xRb; dall’ipotesi aRb segue bRa (per la proprietà simmetrica); da xRb e da bRa si ha xRa (per la proprietà transitiva), dunque x [a], e si può concludere che [b] [a].
Nota: nella dimostrazione precedente, tutte e 3 le proprietà simmetrica, riflessiva e transitiva sono utilizzate.
Le classi di equivalenza hanno una importante proprietà:
Teorema. Sia definita nell’insieme A una relazione di equivalenza R.
Allora le diverse classi di equivalenza formano una partizione dell’insieme A.
Dimostrazione:
Dimostriamo le proprietà che caratterizzano una partizione di A
1) Le classi di equivalenza sono sottoinsiemi non vuoti di A: questo è già stato notato prima, sfruttando la proprietà riflessiva (la classe rappresentata da a contiene almeno l’elemento a)
2) Date 2 generiche classi diverse [a]≠[b], esse sono disgiunte, ossia hanno intersezione vuota: per assurdo supponiamo che abbiano un elemento in comune x; dunque xRa (perché x[a]) e anche xRb (perché x[b]). Ma allora da aRx segue xRa (per la simmetrica) e da aRx e xRb segue aRb (per la transitiva). Infine da aRb segue, per il teorema precedente, l’eguaglianza [a]=[b], contraddizione.
3) L’unione di tutte le classi di equivalenza è uguale all’insieme A: ciò è ovvio, perché preso un generico elemento aA, tale elemento appartiene ad almeno una classe di equivalenza (per esempio alla classe [a], sempre per la proprietà riflessiva).
Esempio: nell’esempio precedente si sono ottenute 2 diverse classi di equivalenza {numeri naturali pari} e {numeri naturali dispari}, e in effetti esse costituiscono una partizione di N, come affermato dal Teorema.
