Algebra e Geometria - Appunti

Teoria Algebra e Geometria

Relazione: corrispondenza tra gli elementi di due insiemi. Una relazione tra A e B è un

sottoinsieme di AxB.

Relazione binaria: è una relazione tra un insieme A e se stesso.

Relazioni d’equivalenza: una relazione binaria su un insieme S si chiama relazione

d’equivalenza se è: ∀ ∈

x A siha che xRx

• Riflessiva: cioè se ;

∀ ∈

x , y A si ha che xRy e yRx

• Simmetrica: cioè se ;

∀ ∈

x , y , z A si ha che xRy yRz e xRz

• Transitiva: cioè se .

Classe d’equivalenza: sottoinsieme di A nel quale vengono raggruppati gli elementi

che hanno caratteristiche comuni in base alla relazione d’equivalenza (possono esserci

più classi d’equivalenza ma un elemento può appartenere ad una sola di esse).

A R

/

Insieme quoziente: data una relazione d’equivalenza, l’insieme quoziente è

l’insieme delle classi di equivalenza di A.

Partizione: una partizione F di un insieme A è una famiglia di sottoinsiemi di A se

(B=parte):

Bi è contenuto∈ A

• ;

Bi ≠ ∅

• ;

Bi ∩Bj=∅

• ;

U A

=

• Bi

Teorema fondamentale delle relazioni d’equivalenza:

• Se Rf è una relazione d’equivalenza su A, l’insieme quoziente è una partizione di

A;

• Se F è una partizione di A, allora la relazione Rf su A definita da

Rf x , y , y appartengono allo stesso blocco di F

={( )∨x } è una relazione

A Rf

/ =F

d’equivalenza tale che .

Relazioni d’ordine: una relazione binaria su in insieme S si chiama relazione d’ordine

se è: ∀ ∈

x A siha che xRx

• Riflessiva: cioè se ;

∀ ∈

x , y A si ha che xRy e yRx solo se x= y

• Asimmetrica: cioè se ;

∀ ∈

x , y , z A si ha che xRy yRz e xRz

• Transitiva: cioè se .

P( A)={0,{a , b

}, {b }, {a }}

Relazione di Inclusione: dato un insieme l’insieme vuoto

è contenuto in ogni insieme, il singleton {a} è contenuto in se stesso e in {a,b} ecc

ecc.

Prefissi: data R la relazione di “prefisso”, ogni parola è prefisso di se stessa

uRv vRu uRv , vRw e uRw

(riflessiva), asimmetrica se e e transitiva se .

ab è prefisso di abcdab

ba è prefisso di babac

acb è prefisso di acba

Minimo e Massimo: per rappresentare gli elementi minimo e massimo si usano i

diagrammi di Hasse, possono esserci anche elementi minimali al post del minimo e

massimali al posto del massimo: ∈

m∈ A è il minimo se per ognia A mRa

• L’elemento ;

∈ ∈

M A è il massimo se per ognia A aRM ;

• L’elemento

• L’estremo inferiore è il massimo dei minoranti e l’estremo superiore è il minimo

dei maggioranti. ∈ ∀

Insieme dei minoranti di A b B b ≤ a per a∈ A ;

∣

{ }

∈B=

• ∈ ∀ ∈

Insieme deimaggioranti di A b B b ≥ a per a A .

∣

{ }

∈B=

•

Funzione: una funzione da un insieme A a un insieme B è una legge che a ogni

∈ ∈

a A b B f : A→B

elemento di si associa uno e un solo ele