Algebra 1/Insiemi Logica Relazioni/Relazioni: differenze tra le versioni

 
== Relazioni di equivalenza ==
 
Completa la seguente tabella segnando le proprietà di cui gode (R=riflessiva, S=simmetrica, T=transitiva, AS=antisimmetrica, AR=antiriflessiva) ciascuna relazione.
{| style="border-top:1px solid black; border-bottom:1px solid black;text-align:left; background:white;" align="center" width="90%" border="0" cellspacing="0"
|- style="border-bottom:1px solid black;"
! style="border-bottom:1px solid black;" |Relazione
! style="border-bottom:1px solid black;" align="center"|Insieme
! style="border-bottom:1px solid black;" align="center"|Proprietà
|-
|Avere lo stesso perimetro
|align="center"|poligoni
|align="center"|[R] [S] [T] [AS] [AR]
|-
|Essere fratello di
|align="center"|persone
|align="center"|[R] [S] [T] [AS] [AR]
|-
|Essere figlio di
|align="center"|persone
|align="center"|[R] [S] [T] [AS] [AR]
|-
|Essere più alto di
|align="center"|persone
|align="center"|[R] [S] [T] [AS] [AR]
|-
|Avere gli angoli rispettivamente congruenti
|align="center"|triangoli
|align="center"|[R] [S] [T] [AS] [AR]
|-
|Iniziare con la stessa lettera
|align="center"|parole
|align="center"|[R] [S] [T] [AS] [AR]
|-
|Giocare nella stessa squadra
|align="center"|calciatori
|align="center"|[R] [S] [T] [AS] [AR]
|-
|<math>a \,\mathfrak{R}\, b</math> se e solo se <math>a</math> è nato nello stesso anno di <math>b</math>
|align="center"|persone
|align="center"|[R] [S] [T] [AS] [AR]
|-
|<math>x \,\mathfrak{R}\, y</math> se e solo se <math>x</math> ha lo stesso numero di cifre di <math>y</math>
|align="center"|<math>\mathbb{N} \times \mathbb{N} </math>
|align="center"|[R] [S] [T] [AS] [AR]
|-
|<math>x \,\mathfrak{R}\, y</math> se e solo se <math>x</math> ha la stessa ultima cifra di <math>y</math>
|align="center"|<math>\mathbb{N} \times \mathbb{N} </math>
|align="center"|[R] [S] [T] [AS] [AR]
|-
|<math>x \,\mathfrak{R}\, y</math> se e solo se <math>x</math> è multiplo di <math>y</math>
|align="center"|<math>\mathbb{N} \times \mathbb{N} </math>
|align="center"|[R] [S] [T] [AS] [AR]
|-
|<math>x \,\mathfrak{R}\, y</math> se e solo se <math>x+y</math> è pari
|align="center"|<math>\mathbb{N} \times \mathbb{N} </math>
|align="center"|[R] [S] [T] [AS] [AR]
|-
|Avere lo stesso segno zodiacale
|align="center"|persone
|align="center"|[R] [S] [T] [AS] [AR]
|-
|<math>(a;b) \,\mathfrak{R}\, (x;y)</math> se e solo se <math>a+b=x+y</math>
|align="center"|<math>\mathbb{N} \times \mathbb{N}</math>
|align="center"|[R] [S] [T] [AS] [AR]
|}
 
''Svolgimento'': La prima relazione gode delle tre proprietà riflessiva, simmetrica e transitiva; infatti:
 
* “il poligono <math>P</math> ha lo stesso perimetro di se stesso” è vera per qualunque poligono (''proprietà riflessiva'');
* “il poligono <math>P_1</math> ha lo stesso perimetro del poligono <math>P_2</math>” implica la verità della proposizione “il poligono <math>P_2</math> ha lo stesso perimetro di <math>P_1</math>”, qualunque siano i due poligoni <math>P_1</math> e <math>P_2</math> (''proprietà simmetrica'');
* se “il poligono <math>P_1</math> ha lo stesso perimetro di <math>P_2</math>” e “<math>P_2</math> ha lo stesso perimetro di <math>P_3</math>” allora si ha anche che “<math>P_1</math> ha lo stesso perimetro di <math>P_3</math>”, qualunque siano i poligoni <math>P_1</math>, <math>P_2</math>, <math>P_3</math> (''proprietà transitiva'').
 
Verifica tu se anche le altre relazioni godono delle tre proprietà riflessiva, simmetrica, transitiva, come “essere fratello di”, “avere gli angoli rispettivamente uguali”, “iniziare con la stessa lettera”.
 
{{Algebra1/Definizione| Chiamiamo ''relazione d’equivalenza'' una relazione che gode delle tre proprietà riflessiva, simmetrica e transitiva.}}
 
Premettiamo le definizioni:
 
{{Algebra1/Definizione| Dato un insieme <math>A</math>, suddividiamolo in un numero di sottoinsiemi <math>A_1</math>, <math>A_2</math>, …, <math>A_n</math>, detti ''classi'', tali che
 
# nessun sottoinsieme è vuoto;
# a due a due sono disgiunti (non hanno tra loro alcun elemento in comune);
# la loro unione è l’insieme <math>A</math>.
 
{{Testo centrato|L’insieme <math>P(A) = \{A_1</math>, <math>A_2</math>, …, <math>A_n\}</math> è detto ''partizione'' di <math>A</math>.}} }}
 
{{Algebra1/Definizione| In un insieme <math>A</math> dove sia stata definita una relazione d’equivalenza <math>\mathfrak{R}</math>, si chiama ''classe d’equivalenza'' ogni sottoinsieme di <math>A</math> contenente tutti e soli gli elementi tra loro in relazione secondo <math>\mathfrak{R}</math>. }}
 
Si viene così a determinare una partizione dell’insieme <math>A</math> in classi d’equivalenza, ognuna delle quali è indicata racchiudendo tra parentesi quadrate uno degli elementi della classe considerata.
 
{{Algebra1/Definizione| Si chiama ''insieme quoziente'' di un insieme <math>A</math> rispetto alla relazione di equivalenza <math>\mathfrak{R}</math> in esso definita, l’insieme i cui elementi sono le classi d’equivalenza determinate dalla relazione <math>\mathfrak{R}</math>, ovvero la partizione di <math>A</math> definita da <math>\mathfrak{R}</math>. L’insieme quoziente si indica con il simbolo <math>A/\mathfrak{R}</math>. }}
 
{{Algebra1/Osservazione| Ogni volta che si ha una relazione d’equivalenza <math>\mathfrak{R}</math> in un insieme <math>A</math>, possiamo stabilire la seguente catena di passaggi:
{{Testo centrato|<math>\text{insieme }A\rightarrow\mathfrak{R}\rightarrow\text{ partizione }\wp(A)=\text{ insieme quoziente }A/\mathfrak{R}.</math>}}}}
 
{{Algebra1/Esempio1| Nell’insieme <math>A = \{x \in \mathbb{N} \mid 0\le x\le 20\}</math> è data la relazione <math>\mathfrak{R}=</math> “avere lo stesso resto nella divisione per 5”. Vediamo alcuni numeri che sono in relazione: {{Div col}} 0 : 5 quoziente 0 resto 0;
 
1 : 5 quoziente 0 resto 1;
 
2 : 5 quoziente 0 resto 2;
 
3 : 5 quoziente 0 resto 3;
 
4 : 5 quoziente 0 resto 4;
 
5 : 5 quoziente 1 resto 0;
 
6 : 5 quoziente 1 resto 1;
 
7 : 5 quoziente 1 resto 2;
 
8 : 5 quoziente 1 resto 3;
 
9 : 5 quoziente 1 resto 4;
 
10 : 5 quoziente 2 resto 0;
 
11 : 5 quoziente 2 resto 1;
 
12 : 5 quoziente 2 resto 2;
 
……{{Div col end}} Sono quindi in relazione:
 
* <math>0 \, \mathfrak{R} \,5</math>, <math>5 \, \mathfrak{R} \,10</math>, <math>10 \, \mathfrak{R} \,15</math>, <math>15 \, \mathfrak{R} \,20 \ldots</math>;
* <math>1 \, \mathfrak{R} \,6</math>, <math>6 \, \mathfrak{R} \,11</math>, <math>11 \, \mathfrak{R} \,16</math>, <math>21 \, \mathfrak{R} \,26 \ldots</math>;
* <math>2 \, \mathfrak{R} \,7</math>, <math>7 \, \mathfrak{R} \,12</math>, <math>12 \, \mathfrak{R} \,17</math>, <math>27 \, \mathfrak{R} \,32 \ldots</math>
* <math>\ldots\ldots\ldots\ldots\ldots</math>
 
Vediamo quali proprietà verifica la relazione <math>\mathfrak{R}</math>:
 
* ''Riflessiva'': perché ogni numero ha lo stesso resto di se stesso nella divisione per 5. <math>0 \, \mathfrak{R} 0</math>, <math>1 \, \mathfrak{R} 1</math>, <math>2 \, \mathfrak{R} 2</math>, …;
* ''Simmetrica'': Se <math>m \,\mathfrak{R} \, n </math> significa che <math>{resto}(m:5)={resto}(n:5)</math> allora vale anche <math>{resto}(n:5)={resto}(m:5)</math> e quindi <math>n \,\mathfrak{R} \, m</math>;
* ''Transitiva'': Se <math>m \,\mathfrak{R} \, n </math> e <math>n \,\mathfrak{R} \, p </math> significa che <math>{resto}(m:5)={resto}(n:5)={resto}(p:5)</math> e quindi <math>m \,\mathfrak{R} \, p</math>.
 
Possiamo concludere che <math>\mathfrak{R}</math> è una relazione di equivalenza.
 
Rappresentiamo la partizione dell’insieme <math>A</math> secondo la relazione <math>\mathfrak{R}</math>.
 
<span>./lbr/chap07/fig033_part.pgf</span>
 
Le classi di equivalenza sono:
 
* <math> [0]=\{0\text{, }5\text{, }10\text{, }15\text{, }20\} </math>;
* <math> [1]=\{1\text{, }6\text{, }11\text{, }16\} </math>;
* <math> [2]=\{2\text{, }7\text{, }12\text{, }17\} </math>;
* <math> [3]=\{3\text{, }8\text{, }13\text{, }18\} </math>;
* <math> [4]=\{4\text{, }9\text{, }14\text{, }19\} </math>.
}}
 
== Relazioni di ordine ==
848

contributi