1 Insiemi, proposizioni e relazioni Il sottoinsieme di A A formato da tutte e sole le coppie (x ; y) per le quali è vera la relazione «essere la metà è: {(0 ; 0), (1 ; 2), (2 ; 4), (3 ; 6), (4 ; 8)} L insieme di tutte le coppie ordinate di elementi di A è il prodotto cartesiano A A. Quelle per le quali la relazione è vera costituiscono perciò un sottoinsieme di A A. Ciò è vero in generale: una relazione in un insieme A individua un sottoinsieme di A A: quello a cui appartengono le coppie di elementi tra loro in relazione. esempio O Considera il seguente insieme di numeri naturali: A = {2, 3, 4, 5, 6, 7, 8, 9, 10} L insieme A A è formato da tutte le coppie ordinate di elementi di A: (2 ; 2), (2 ; 3), (2 ; 4), (3 ; 2), (3 ; 3), (3 ; 4) (10 ; 10). Poiché A ha 9 elementi, l insieme A A è formato dalle 81 coppie ordinate dei suoi elementi. Per alcune di esse la relazione è vera, mentre per altre è falsa: «2 è divisore di 2 è vera e quindi (2 ; 2) appartiene al sottoinsieme; «2 è divisore di 3 è falsa e quindi (2 ; 3) non appartiene al sottoinsieme; «2 è divisore di 4 è vera e quindi (2 ; 4) appartiene al sottoinsieme; «5 è divisore di 3 è falsa e quindi (5 ; 3) non appartiene al sottoinsieme; «5 è divisore di 10 è vera e quindi (5 ; 10) appartiene al sottoinsieme; Il sottoinsieme di A A definito dalla relazione «essere divisore è: {(2 ; 2), (2 ; 4), (2 ; 6), (2 ; 8), (2 ; 10), (3 ; 3); (3 ; 6), (3 ; 9), (4 ; 4), (4 ; 8), (5 ; 5), (5 ; 10), (6 ; 6), (7 ; 7), (8 ; 8), (9 ; 9), (10 ; 10)} Per le altre coppie la relazione è falsa. ATTENZIONE! A S un numero a è divisibile Se per un altro numero b, allora b è un divisore di a: 6:3=2 6 è divisibile per 3 perché 3 è divisore di 6 Un modo efficace di rappresentare una relazione definita in un insieme consiste nel disegnare gli elementi dell insieme come punti e collegare tra loro quelli per i quali la relazione è vera. Questo collegamento: a b indica che l elemento rappresentato da a è in relazione con l elemento rappresentato da b. Nell insieme A = {2, 3, 4, 5, 6, 7, 8, 9, 10} dell esempio precedente, la relazione «essere divisore si può rappresentare con il seguente schema: 5 4 10 8 7 2 6 3 ATTENZIONE! A S un numero a è divisibile per Se un altro numero b, allora b è un divisore di a. Q Poiché ogni numero è divisore di sé stesso, nello schema compaiono collegamenti circolari, quali per esempio: Q 9 2 Uno schema come il precedente si chiama grafo della relazione: sono detti nodi i punti che rappresentano gli elementi e archi i collegamenti tra i nodi. In un grafo, non conta il modo in cui sono disposti i nodi, ma la rete dei loro collegamenti. 23