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