Relazioni

Definizioni:

• Una proposizione è una frase della quale si può dire se è vera oppure falsa.

• Una proposizione è formata almeno da un predicato e da uno o più argomenti.

• Una relazione binaria è un predicato con due argomenti che appartengono allo stesso insieme.

• Un grafo è uno schema formato da punti, detti nodi e da archi o frecce che li collegano.

• Prodotto cartesiano A x B: insieme delle coppie ordinate (a;b) con a € B e b € B.

• Un insieme ha un ordinamento discreto quando ogni suo elemento ha un successivo

• L' insieme N è infinito, totalmente ordinato e discreto

• Cardinalità di un insieme: numero di elementi di un insieme

• L' insieme Z è infinito, totalmente ordinato e discreto, ma non ha un primo elemento

• Numero razionale :classe di frazioni equivalenti

• L' insieme Q è un insieme infinito, totalmente ordinato, denso e non ha un primo elemento

• L' insieme I é un insieme totalmente ordinato e discreto

• Proprietà riflessiva : per ogni x € A, x R x

• Proprietà simmetrica : per ogni x, y € A, x R y => y rel x

• Proprietà antisimmetrica : per ogni x, y € A (con x = y), x R y => y rel x

• Proprietà transitiva : per ogni x, y, z € A, (x R y e y R z) => x R z

• Relazione d'ordine o ordinamento : R antisimmetrica e transitiva

• Relazione di equivalenza : R riflessiva, simmetrica e transitiva

• Ogni classe di equivalenza è un insieme contenente tutti e soli gli elementi tra loro equivalenti

Esempi:

x R y <=> x mod 2 = y mod 2

• Riflessiva : x R x <=> x mod 2 = x mod 2

• Simmetrica : x R y <=> x mod 2 = y mod 2 <=>y mod 2 = x mod 2

• Transitiva : x R y e y R x <=> x mod 2 = y mod 2 e y mod 2 = z mod 2 <=> x mod 2 = z mod 2

 

a/b R c/d <=> a + d = b + c

• Riflessiva : a/b R a/b <=> a+b = a+b

• Simmetrica : a/b R c/d <=> a+d = b+c <=> c+b = d+a <=> x/d R a/b

• Transitiva : a/b R c/d e c/d R e/f <=> a+d = b+c e s+f = d+e <=> a+d+c+f = b+c+d+e <=> a+f = b+e <=>a/b R e/f