relazioni binarie in generale

(1)

Capitolo B53:

relazioni binarie in generale

Contenuti delle sezioni

a. relazioni binarie p.2

b. operazioni su relazioni binarie p.8 c. digrafi e relazioni binarie p.10

d. caratterizzazioni principali delle relazioni p.12 e. strutture dotate di ordinamento p.17

f. relazioni ternarie e di ariet`a superiore p.18

18 pagine

B53:0.01 Il capitolo è dedicato alle proprietà generali delle relazioni binarie e a qualche considerazione sulle relazioni ternarie e di arietà superiore.

Alcune delle definizioni e delle segnalazioni nelle prossime pagine sono gi`a comparse in precedenza e saranno ripresentate pi`u oltre. In effetti il capitolo vuole servire per raccordare i molti risultati sopra le relazioni che devono essere tenute presenti in gran parte dei passaggi dell’esposizione.

Si inizia con l’inquadramento delle relazioni binarie tra le relazioni di generica ariet`a e con alcune loro caratterizzazioni generali.

Si prosegue con la presentazione delle svariate operazioni che risulta opportuno definire sulle relazioni e di alcune notazioni specifiche che riescono a prescindere dagli ambienti nei quali le relazioni sono collocate.

Successivamente per le relazioni finite e numerabili si riprendono le raffigurazioni mediante grafi e le relative terminologie.

Si espongono poi le loro molteplici caratterizzazioni, entrando in un buon numero di dettagli della casistica.

In seguito si accenna alle strutture che presentano relazioni d’ordine compatibili con importanti operazioni algebriche e con basilari propriet`a topologiche.

Infine si aggiungono alcune considerazioni sulle relazioni ternarie e di ariet`a superiore fornendo alcuni esempi e discutendo come si pu`o cercare di ricondurle a relazioni binarie.

(2)

B53:a. relazioni binarie

B53:a.01 Consideriamo l’intero k ≥ 2, gli insiemi non vuoti A1, A2,... e Ak (non necessariamente diversi e non necessariamente omogenei o con lo stesso cardinale) e il prodotto cartesiano di questi ultimi C := A1× A2× ... × Ak.

Si dice relazione k-aria tra A1, A2, ... e Ak, oppure relazione k-aria entro C, ogni sottoinsieme R ⊆ C.

Il prodotto cartesiano C viene detto terreno della relazione e l’intero k ariet`a della relazione R.

Per riuscire a disporre di locuzioni pi`u versatili che consentano di proporre definizioni ed enunciati di ampia portata e tendenzialmente concisi e uniformi `e opportuno ammettere che sia k = 1.

Diciamo quindi che ogni sottoinsieme di un dato ambiente E pu`o assumere il ruolo di relazione unaria entro il terreno costituito dallo stesso insieme E.

Tra le relazioni di arietà superiore a 2 si distinguono le relazioni associate a equazioni o disequazioni studiate nell’ambito della analisi infinitesimale e della geometria senza porre in rilievo il fatto che ciascuna di esse è una relazione k-aria con k ≥ 3, cioè un sottoinsieme di un prodotto cartesiano di k fattori.

Tra questi ultimi vanno segnalate relazioni che si incontrano in alcuni settori dell’elaborazione dei dati, ed in particolare nel settore delle basi di dati [Relational database (wi)].

Per la maggior parte delle tematiche più tipiche della matematica le relazioni più importanti sono invece le binarie, cioè i sottoinsiemi di un prodotto cartesiano della forma A₁× A2.

Nel seguito del capitolo, a esclusione dell’ultimo paragrafo dedicato alle relazioni di ariet`a superiore a 2, e in molti altri contesti la accennata prevalente importanza delle relazioni binarie, induce a chiamarle relazioni tout court.

Questa abbreviazione viene adottata in molti altri contesti senza rischiare serie l’ambiguit`a.

Ricordiamo che una relazione tra A1 ed A2 viene chiamata anche corrispondenza tra A1 ed A2. B53:a.02 Numerose relazioni binarie sono ben note e in particolare sono state incontrate in pagine precedenti. Alcune sono insiemi di coppie finite, altre insiemi costruibili, altre ancora sono state introdotte prescindendo dalla possibilit`a di esaminarle o di elaborarle concretamente.

Ricordiamone alcune.

- le relazioni = e 6= applicabili entro ogni insieme;

- le relazioni tra stringhe essere prefisso, essere suffisso, essere infisso, essere sottostringa;

- le relazioni entro insiemi individuate dai simboli ⊂, ⊆, ⊃, ⊇, ♦, , e ⊃⊂;

- le relazioni tra numeri naturali, interi qulsiasi, numeri razionali o numeri reali individuate dai segni

<, ≤, > e ≥;

- le relazioni tra numeri interi collegate alla divisibilità come _:, cioè “essere divisore di”, ⊥, cioè

“essere mutuamente primo con”;

- relazioni tra enti geometrici tra le quali il parallelismo // e la perpendicolarit`a ⊥ tra rette, segmenti, piani e sottospazi;

- le relazioni di incidenza tra vertici e spigoli di un grafo nonorientato;

- le relazioni di incidenza tra vertici, spigoli e facce di un poligono o di un poliedro.

Osserviamo anche che tutte le curve speciali piane (ad esempio quelle elencate in G70 o quelle presentate nella Encyclop´edie des Formes Math´ematiques Remarquables [http://www.mathcurve.com/],

(3)

in quanto insiemi di coppie di numeri reali o complessi si possono considerare relazioni entro R × R o entro C × C.

Segnaliamo inoltre che a ogni curva speciale piana nonintrecciata chiusa (ad esempio una ellisse, una tricuspoide o una quartica piriforme) sono associati l’insieme dei suoi punti interni e quello dei suoi punti esterni in modo da determinare una relazione di equivalenza entro R × R.

Di queste equivalenze nella sezione :f saranno accennate le generalizzazioni relative alle figure di tre 4 e pi`u dimensioni.

B53:a.03 Sia R una relazione binaria; in luogo di ha, bi ∈ R spesso conviene usare la notazione equivalente a R b; questa si dice notazione infissa della relazione inoltre in genere, se non si rischia l’ambiguit`a, a questa viene preferita l’abbreviazione a R b .

Una notazione come 4 ≤ 6 si pu`o considerare la notazione infissa equivalente alla h4, 6i ∈≤, notazione nella quale ≤ `e chiaramente visto come un insieme di coppie di numeri.

Pi`u precisamente, in relazione alle esigenze del contesto, accade di considerare ≤ come sottoinsieme di N × N, di Z × Z, di Q × Q, di R × R o di un quadrato cartesiano di qualche altro qualche altro insieme totalmente odinato.

Dal complesso degli esempi precedenti emerge il carattere multivalente e versatile della nozione di relazione.

Ricordiamo inoltre la decisione [B19d02] di denotare con Rel la classe di tutte le relazioni binarie.

B53:a.04 Per una qualsiasi relazione R ⊆ A × B si introducono:

il dominio di R: R^` :=: dom(R) := { a ∈ A (B 3 b a R b) } = Prj₁(R);

il codominio di R: R^a :=: cod(R) := { b ∈ B (A 3 a aRb) } = Prj₂(R).

Il codominio di una relazione R si dice anche immagine della R e si denota anche con img(R).

Per ciascuna relazione R si riscontra una e una sola delle seguenti situazioni:

- R^` = R^a; questo `e il caso della uguaglianza, della differenza e delle svariate relazioni di equivalenza;

le relazioni con questa propriet`a sono chiamate relazioni presimmetriche);

- R^` ⊂ R^a, come la relazione > sugli interi naturali e su ogni insieme totalmente ordinato inferiormente limitato (e in particolare finito), osservando in particolare che entro N 0 ∈≥^a \ >^`);

- R^` ⊃ R^a, come la relazione < sugli interi non positivi e su ogni insieme totalmente ordinato superiormente limitato (e in particolare finito), osservando in particolare che entro Z−0 0 ∈≤^a\,^`);

- R^`♦R^a, come accade per la incidenza tra vertici e spigoli dei grafi nonorientati e caratterizza i nodi dei digrafi bipartiti;

- R^` R^a, come accade per la funzione a ∈ {1, 2, 3} a + 1 e per tutte le biiezioni fra insiemi diversi.

B53:a.05 Per taluni sviluppi riguardanti una relazione R ⊆ A × B si pone la questione della distinzione tra l’insieme di coppie R e la coppia hA × B, Ri.

Quando occorre evidenziare questa distinzione per la coppia della forma hA × B, Ri ci serviremo del termine relazione collocata in A × B; per una tale coppia diremo che il rettangolo cartesiano A × B costituisce una collocazione della R.

Inoltre useremo la scrittura Rel_A,B per denotare l’insieme delle relazioni collocate entro A × B.

(4)

Evidentemente l’insieme delle relazioni collocabili in A × B `e P(A × B); per questo insieme talora, si usa anche la notazione {A−−−B}, notazione che si avvicina alle notazioni per i generi delle funzioni come {A −→ B} e {A . B} [B15b10].

Consideriamo in particolare le relazioni collocate in quadrati cartesiani, cio`e insiemi di coppie della forma R ⊆ A × A per qualche insieme A; queste entit`a le chiamiamo relazioni collocate sopra l’insieme A e per il loro insieme usiamo la notazione Rel_A:= Rel_A,A.

L’insieme delle relazioni che si possono collocare su A `e dunque P(A^×2), ovvero {A−−−A}.

B53:a.06 Consideriamo una relazione collocata hA × B, Ri ∈ RelA,B.

Per ogni hA⁰⁰, B⁰⁰i con A⁰⁰ ⊇ A e ogni B⁰⁰ ⊇ B `e evidentemente lecito prendere in considerazione la relazione collocata hA⁰⁰× B⁰⁰, Ri.

Inoltre la relazione R si pu`o collocare senza perdita di sue coppie sopra uno qualsiasi dei rettangoli cartesiani A⁰× B⁰ che contengono R^`× R^a.

Si osserva anche che per ogni hA, Bi con A ⊆ A e B ⊆ B `e lecito prendere in considerazione le relazione collocate hA × B, R ∩ A × Bi , hA × B, R ∩ A × Bi e hA × B, R ∩ A × Bi .

Occorre segnalare che vi sono propriet`a delle relazioni sulle quali la collocazione non ha alcuna influenza, mentre per altre essa conta; questo accade soprattutto per relazioni da considerate sottoinsiemi di quadrati cartesiani di interesse applicativo.

Pu`o accadere che si introduca una relazione R come relazione tra due insiemi, R ⊂ A × B, ma che per taluni sviluppi risulti opportuno considerare una sua variante definita tra un sottoinsieme o un sovrainsieme di A e un sottoinsieme o un sovrainsieme di B.

Per esempio relazioni numeriche come ≤ e > nell’analisi infinitesimale spesso si intendono collocate sopra l’insieme dei numeri reali R, ma in talune circostanze pu`o essere opportuno limitarsi a considerarle relazioni sopra un sottoinsieme di R come un suo intervallo, Rc, RA, Q, Z o il pi`u circoscritto insieme dei numeri primi.

Spesso risulta comodo chiedere che una relazione sia collocata sopra un unico insieme, cio`e che si consideri sottoinsieme di un quadrato cartesiano.

In effetti per ogni relazione si ha

R ⊆ (R^`× Râ) ⊆ (R^`∪ Râ) × (R^`∪ Râ) .

Quindi in considerazioni che non si curano di esigenze elaborative, ogni relazione R si può collocare sopra un unico ben determinato insieme; la scelta di questo insieme andrebbe effettuata tenendo conto anche di esigenze espositive; talora può essere opportuno scegliere questo insieme come il minimale, cioè R^`∪ Râ, talaltra potrebbe essere preferibile un sovrainsieme del minimale avente limiti più evidentemente definibili.

B53:a.07 Consideriamo dunque una relazione collocata sopra un insieme hA × A, Ri.

Si dice relazione trasposta o relazione inversa di R: R = R^← := {ha, bi ∈ R :| hb, ai}.

Evidentemente anche hA × A, R i `e una relazione collocata sopra A.

Chiaramente per ogni relazione R si ha (R ) = R. In altre parole la trasposizione `e una involuzione entro ciascuna classe Rel_A.

Si osserva che affermare R ⊆ A × B equivale a enunciare R ⊆ B × A .

Inoltre sono evidenti ed equivalenti gli enunciati dom(R ) = cod(R) e cod(R ) = dom(R) . Per esempio per le relazioni numeriche si ha

(5)

≤ = ≥ , < = > , mentre per le relazioni insiemistiche

⊆ = ⊇ , ⊂ = ⊃ .

Inoltre la trasposta della relazione essere divisore di `e la relazione essere multiplo di . B53:a.08 Le relazioni invarianti per la trasposizione di relazioni collocate, cio`e le relazioni coincidenti con la propria trasposta, sono dette relazioni simmetriche.

Sono evidentemente simmetriche l’uguaglianza e la diversità. E ragionevole ritenere che in genere` risulti più semplice considerare una relazione simmetrica collocata sopra un quadrato cartesiano, cioè che abbia dominio e codominio coincidenti, cosa sempre ottenibile.

Evidentemente la trasposta di una relazione simmetrica `e simmetrica: possiamo considerare che

R = R ⇐⇒ R = (R ) = R .

Osserviamo esplicitamente che vi sono relazioni presimmetriche, cio`e relazioni aventi dominio e codominio coincidenti, che non sono simmetriche: per esempio la relazione ≤ sopra insiemi come Z, Q o R

`e presimmetrica ma non simmetrica.

B53:a.09 Quando si deve esaminare una sola relazione spesso la sua collocazione è poco importante e spesso tale collocazione può non essere esplicitata senza che questo comporti serie ambiguità.

Talora il prodotto cartesiano A × B nel quale risulta opportuno collocare una relazione R si impone con una certa evidenza e quindi in molti di questi casi viene sottinteso senza conseguenze.

In particolare molte relazioni R presimmetriche si intendono implicitamente collocate entro il rispettivo quadrato cartesiano minimale R^`× R^`.

Talvolta invece si rende necessario essere circostanziati sulla collocazione di una relazione; questo accade quando la relazione riguarda entit`a in corso di indagine, ad esempio quando viene ottenuta componendone altre o quando `e interessante confrontarla con altre [:b].

Vi sono inoltre molti sviluppi nei quali non ha sostanziale importanza definire la collocazione e risulta possibile senza rischiare ambiguit`a lasciarla inespressa e anche non distinguere tra le possibili relazioni collocate di uno stesso insieme di coppie.

La non precisazione della collocazione pu`o semplificare sensibilmente alcune presentazioni e si giustifica nella confidenza che il lettore sia in grado di giungere a precisare le collocazioni nelle circostanze che lo richiedano (circostanze in genere considerate remote).

B53:a.10 Vediamo ora alcune situazioni nelle quali pu`o essere opportuno esplicitare la collocazione di una relazione.

Quali che siano gli insiemi A e B, l’insieme vuoto collocato entro A×B si pu`o chiamare relazione assurda tra A e B, mentre A × B collocato entro A × B si pu`o chiamare relazione ovvia tra A e B.

Quale che sia l’insieme A, si dice relazione identica o identit`a su A l’insieme di tutte le coppie aventi i due membri identici e appartenenti ad A:

Id_A := {a ∈ A :| ha, ai} .

Essa si denota anche con AId e viene anche chiamata diagonale di A × A.

B53:a.11 Si dice relazione opposta della relazione collocata hA × B, Ri la relazione collocata hA × B, (A × B) \ R .

(6)

Essa viene anche detta negazione della relazione e se si `e convenuto di collocare R in A × B, si pu`o denotare con la semplice notazione ¬R.

Questa dizione, insieme alle dizioni relazione ovvia e relazione assurda, costituiscono termini adottati per il calcolo proposizionale [B60]. Questa teoria formale si applica in modo piuttosto semplice alle affermazioni riguardanti relazioni chiaramente collocate o facilmente collocabili.

Le proposizioni della forma ha, bi ∈ R forniscono esempi significativi per propriet`a del calcolo proposizionale.

Il termine negazione di una relazione pu`o essere chiarito dalla seguente equivalenza tra enunciati

∀ha, bi ∈ A × B ha, bi ∈ (A × B) \ R ⇐⇒ ha, bi 6∈ R .

B53:a.12 Vediamo situazioni nelle quali `e ammissibile parlare di passaggio alla relazione opposta senza precisare la sua collocazione entro un rettangolo cartesiano A × B.

Si pu`o asserire senza collocazioni esplicite che l’opposta della relazione numerica < `e la relazione ≥.

Similmente si pu`o affermare che l’opposta della relazione insiemistica ⊃ `e la ⊆.

In molti di questi casi interessano conclusioni per le quali la precisa collocazione delle relazioni `e ininfluente, oppure che risultano valide per tutte le collocazioni ragionevoli.

Per questi casi si possono citare le relazioni di parallelismo e di ortogonalit`a che possono riguardare vettori, rette e piani segmenti

In altre situazioni accade che il contesto e la finalit`a del discorso corrente conducono “naturalmente”

a ritenere che, per esempio, < e ≥ riguardino numeri reali, oppure numeri razionali positivi, oppure numeri interi, oppure ... .

Il lettore di altri contesti a sua volta pu`o venire indotto a pensare che ⊃ e ⊆ riguardino insiemi del tutto generici, oppure insiemi di vettori, oppure insiemi di figure piane, oppure ... .

B53:a.13 Consideriamo ancora R ∈ RelA,B.

Per ogni a ∈ A si dice immagine di a per R a R := {b ∈ B a R b}.

Per ogni b ∈ B si dice controimmagine di b per R: R b := {a ∈ A a R b}.

I due segni ora introdotti “ ” e “ ” sono due connettivi riguardanti una relazione e un elemento che essa coinvolge: il primo serve a collegare esplicitamente un elemento o un sottoinsieme dell’insieme nel quale si colloca il dominio della relazione con la relazione stessa; il secondo si inserisce tra la relazione e un elemento o un sottoinsieme dell’insieme nel quale si colloca il codominio della relazione.

In genere questi segni possono essere sottintesi e si semplifica la scrittura a R con la a R e la R b con la R b .

Queste semplici espressioni si possono interpretare come insiemi di oggetti collegati alla relazione R:

(1) a R := {b ∈ cod(R) ha, bi ∈ R} e R b := {a ∈ dom(R) ha, bi ∈ R} . Diamo qualche esempio.

{1, 2, 3} ⊃ = ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3} .

All’interno di un discorso riguardante dichiaratamente l’intervallo [0 : 9], si pu`o affermare

≤ 5 = {0, 1, 2, 3, 4, 5} .

B53:a.14 Dato che le relazioni sono insiemi, si possono applicare ad esse tutte le operazioni insiemistiche.

(7)

Spesso, date due relazioni R ed S `e utile considerare la loro unione, la loro intersezione e l’operazione denotata con ˙∪ consistente nell’unione con segnalazione di disgiunzione degli operandi.

Facciamo alcune altre osservazioni che si collegano al calcolo dei predicati [B61] applicato a relazioni.

L’enunciato a (R ∪ S) b equivale all’affermazione a R b o a S b ; questo enunciato si dice congiunzione degli enunciati a R b e a S b e si scrive anche a R b ∨ a S b . L’enunciato a (R ∩ S) b equivale ad affermare a R b e a S b ; questo enunciato si dice disgiunzione degli enunciati a R b e a S b e si scrive anche a R b ∧ a S b . L’affermazione a (R ˙∪ S) b equivale ad affermare aut a R b, aut a S b ; questo enunciato viene chiamato or esclusivo degli enunciati o xor a R b e a S b e si scrive anche

a R b +2 a S b .

Per completezza ribadiamo che se la relazione viene collocata, implicitamente o meno, in un dato ambiente A × B, l’affermazione a ((A × B) \ R) b equivale alla negazione dell’enunciato a R b e risulta lecito enunciarla anche nella forma “¬(a R b)” .

B53:a.15 Spesso è significativo stabilire per due relazioni R ed S che sia R ⊆ S; in questo caso si dice che R è relazione più stringente in senso lato della S o, equivalentemente, che S è meno stringente in senso lato di R.

Analogamente può essere utile stabilire che sia R ⊂ S, affermazione che si espone dicendo che R è una relazione più stringente in senso stretto della S o, equivalentemente, che S è meno stringente in senso stretto di R.

L’accostamento tra “stringente” e “stretto” fa pensare a un gioco di parole: in effetti abbiamo applicato le due relazioni ⊆ e ⊂ a due relazioni: ma anche per queste due relazioni si può stabilire quale è la più stringente: evidentemente ⊂ è più stringente della ⊆.

A questo punto si potrebbe essere indotti a scrivere “⊂ ⊂ ⊆” .

Una tale scrittura va per`o considerata inopportuna e da evitare, in quanto la mancata esplicitazione delle collocazioni delle relazioni in gioco la rende poco leggibile e a prima vista ambigua: in essa primo e terzo segno esprimono relazioni entro un non meglio identificato A × B, cio`e appartengono a P(A × B), mentre il segno infisso esprime una relazione tra relazioni del precedente insieme e quindi appartiene a P(P(A × B)).

Osserviamo anche che R ⊆ S ⇐⇒ (∀ha, bi ∈ A × B a R b =⇒ a S b ) .

In varie circostanze si incontrano due relazioni R ed S in un contesto che rende utile stabilire se sono disgiunte, cio`e se R♦S, o meno e decidere stabilire se non sono confrontabili, cio`e se R S, o meno.

(8)

B53:b. operazioni su relazioni binarie

B53:b.01 Introduciamo ora alcune operazioni peculiari sulle relazioni. Per questo faremo riferimento agli insiemi generici A, B, C e D e alle relazioni R, S, R⁰, S⁰ e T .

Consideriamo le relazioni R ⊆ A × B ed S ⊆ B × C; si dice prodotto di composizione, prodotto:c o prodotto di Peirce delle relazioni R ed S:

R ◦ S := ha, ci ∈ A × C B 3 b a R b ∧ b S c .

Per questa importante operazione si derivano direttamente dalle definizioni le propriet`a che seguono, nelle quali supponiamo che R, R⁰ ⊆ A × B, S, S⁰⊆ B × C e T ⊆ C × D.

(a) R ◦ S = ∅ ⇐⇒ R^a∩ S^`= ∅ (non componibilit`a delle relazioni).

(b) (R ◦ S)^` ⊆ R^` , (R ◦ S)^a⊆ S^a . (c) (R ◦ S) = S ◦ R .

(d) (R ◦ S) ◦ T = R ◦ (S ◦ T ) (associativit`a del prodotto di composizione).

(e) (R ∪ R⁰) ◦ S = R ◦ S ∪ R⁰◦ S , R ◦ (S ∪ S⁰) = R ◦ S ∪ R ◦ S⁰

(distributivit`a del prodotto di composizione rispetto all’unione).

(f) AId ◦ R = R , R ◦ BId = R .

(g) (R ∩ R⁰) ◦ S ⊆ (R ◦ S) ∩ (R⁰◦ S) , R ◦ (S ∩ S⁰) ⊆ (R ◦ S) ∩ (R ◦ S⁰) . (h) R ⊂ R⁰ =⇒ R ◦ S ⊆ R⁰◦ S , S ⊂ S⁰ =⇒ R ◦ S ⊆ R ◦ S⁰ .

B53:b.02 Una semplice situazione nella quale (R ∩ R⁰) ◦ S ⊂ (R ◦ S) ∩ (R⁰◦ S) si ha con R = {h1, 2i} , R⁰= {h1, 3i} ed S = {h2, 4i, h3, 4i}; in tal caso (R ∩ R⁰) ◦ S = ∅, mentre (R ◦ S) ∩ (R⁰◦ S) = {h1, 4i} . Una semplice situazione nella quale R ◦ (S ∩ S⁰) ⊂ (R ◦ S) ∩ (R ◦ S⁰) si ha con R = {h1, 2i, h1, 3i}, S = {h2, 4i} ed S⁰ = {h3, 4i}; in tal caso R ◦ (S ∩ S⁰) = ∅, mentre (R ◦ S) ∩ (R ◦ S⁰) = {h1, 4i} . Una semplice situazione nella quale R ⊂ R⁰ed R◦S = R⁰◦S si ha con R = {h1, 2i}, R⁰ = {h1, 2i, h1, 3i}, S = {h2, 4i, h3, 4i}; in tal caso R ◦ S = R⁰◦ S = {h1, 4i} .

Una semplice situazione nella quale S ⊂ S⁰ed R ◦S = R ◦S⁰si ha con R = {h1, 2i h1, 3i}, S = {h2, 4i}, S⁰ = {h2, 4i, h3, 4i}; in tal caso R ◦ S = R ◦ S⁰= {h1, 4i} .

B53:b.03 Come per ogni operazione binaria associativa, a partire dal prodotto di composizione si introducono le potenze di composizione o potenze-c di una qualsiasi relazione R.

R¹ := R ; ∀n ∈ P Rⁿ⁺¹ := Rⁿ◦ R ; ∀n ∈ P R⁻ⁿ := (R )ⁿ = (Rⁿ) . Definiamo come potenza zero minima della relazione R la

R⁰ := (R^`∪ R^a)Id = (R^`)Id ∪ (R^a)Id .

Una nozione molto vicina alla precedente è quella di potenza zero della relazione collocata hA × A, Ri per A ⊇ (R^`∪ Râ): essa è definita come AId.

Si dimostrano facilmente i seguenti enunciati.

(a) ∀m, n ∈ N R^m◦ Rⁿ = R^m+n , R^−m◦ R⁻ⁿ = R^−(m+n) ,

(b) ∀m, n ∈ N (R^m)ⁿ = (R^−m)⁻ⁿ = R^{m n} , (R^−m)ⁿ = (R^m)⁻ⁿ = R^{−m n} . (c) ∀n ∈ N dom(Rⁿ) ⊆ dom(R) , cod(Rⁿ) ⊆ cod(R) .

(9)

Per trovare esempi del caso (c) con le relazioni di inclusione forte consideriamo la relazione R = {12, 13, 14, 15, 23, 24, 25, 34, 35, 45}, cio`e la relazione “minore di” entro {1, 2, 3, 4, 5}.

Si constata che R²= {13, 14, 15, 24, 25, 35}, R³= {14, 15, 25}, R⁴ = {15}, R⁵ = ∅; quindi dom(R) = {1, 2, 3, 4} ⊃ dom(R²) = {1, 2, 3} ⊃ dom(R³) = {1, 2} ⊃ dom(R⁴) = {1} ⊃ dom(R⁵) = ∅; inoltre cod(R) = {2, 3, 4, 5} ⊃ cod(R²) = {3, 4, 5} ⊃ dom(R³) = {4, 5} ⊃ dom(R⁴) = {5} ⊃ dom(R⁵) = ∅.

B53:b.04 Introduciamo la chiusura transitiva o chiusura-crossc della relazione R:

R^⊕ := R ∪ R²∪ R³∪ · · · = S{n ∈ P :| Rⁿ} . Introduciamo anche la chiusura riflessivo-transitiva o chiusura-starc della relazione R:

R^⊗ := R⁰∪ R^⊕ = [

{n ∈ N :| Rⁿ} .

Per un insieme N ⊆ N useremo la scrittura: R^N := S{i ∈ N :| Rⁱ} e le sue specializzazioni per casi particolari di N . Si introducono le seguenti scritture:

∀n ∈ P R^<n := R[ⁿ) = R⁰∪ · · · ∪ Rⁿ⁻¹; R^<0 := ∅ ; ∀n ∈ P R^≤n := R[ⁿ] = R^<n+1

;

∀n ∈ N R^≥n := Rⁿ∪ Rⁿ⁺¹∪ · · · ; R^>n := R^≥n+1 . Si trovano senza difficolt`a le seguenti uguaglianze:

(a) R^⊕ = R ◦ R^⊗ = R^⊗◦ R ; ∀n ∈ N R^≥n = Rⁿ◦ R^⊗ = R^⊗◦ Rⁿ ;

(b) ∀n ∈ N R^>n = Rⁿ◦ R^⊕ = R^⊕◦ Rⁿ ; ∀n ∈ N R^<n∪ R^≥n = R^≤n∪ R^>n = R^⊗ . B53:b.05 Introduciamo le seguenti altre operazioni unarie che agiscono sopra ogni relazione R; si tratta di trasformazioni che mandano una relazione in un’altra relazione, ovvero si tratta di endofunzioni di Rel:

chiusura riflessiva minima: R ∪ R⁰ ; chiusura riflessiva sopra A: R ∪ AId ; chiusura simmetrica: R ∪ R ;

chiusura riflessivo-simmetrica: R ∪ R⁰∪ R ; chiusura di equivalenza: R := (R ∪ R )^⊗ . Si trova facilmente la relazione

(a) R ⊇ R^⊗∪ (R )^⊗ .

Consideriamo la relazione numerabile tra numeri interi R = {n ∈ Z :| hn, n + 1i}, cio`e la relazione che si pu`o leggere “essere l’intero immediatamente precedente”.

Per essa si trova che R^⊗ è la relazione ≤ entro Z,. La sua trasposta R è la relazione “essere l’intero immediatamente successivo”, e si trova che (R )^⊗ è la relazione ≥ entro Z.

Consideriamo la relazione R = {13, 23, 34, 35} ; per essa si trova

R^⊗ = {11, 13, 14, 15, 22, 23, 24, 25, 33, 34, 35, 44, 55} , R = {31, 32, 43, 53} ; (R )^⊗ = {11, 22, 31, 32, 33, 41, 41, 43, 44, 51, 52, 53, 55} e R = {1, 2, 3, 4, 5}Id . Per questa relazione la (a) `e una relazione di inclusione stretta:

R^⊗∪ (R )^⊗ = {1, 2, 3, 4, 5}Id \ {12, 21, 45, 54} ⊂ {1, 2, 3, 4, 5}Id .

(10)

B53:c. digrafi e relazioni binarie

B53:c.01 Riprendiamo le nozioni di digrafo e di grafo nonorientato che in B16b abbiamo introdotta a partire dalle matrici binarie e abbiamo associate alle relazioni finite.

Scopo di questa ripresa `e quello di poterli utilizzare per presentare esempi semplici ed efficaci di vari tipi di relazioni finite.

Inoltre allarghiamo la visuale con due generalizzazioni che consentano di parlare di strutture grafiche e di digrafi costruibili.

Con il termine strutture grafiche intendiamo varie specie di strutture discrete, accomunate dal fatto di essere costituite da un numero finito di oggetti tendenzialmente semplici detti nodi o vertici e da collegamenti tra questi nodi, anch’essi in numero finito.

Questo comporta che esse possono essere presentate con raffigurazioni che nei casi meno elaborati sono facilmente comprensibili e aiutano a capire le loro propriet`a.

Come abbiamo visto in B16b vi sono due specie basilari di strutture grafiche finite i grafi orientati o digrafi e i grafi nonorientati che qui vediamo come casi particolari dei digrafi.

Ogni collegamento in un digrafo viene chiamato arco e va da un nodo iniziale ad un nodo finale (che potrebbe ‘o coincidere con il primo); questo fatto si esprime dicendo che gli archi sono collegamenti dotati di una orientazione.

Anche ciascuno dei collegamenti di un grafo nonorientato, chiamati spigoli o lati, riguardano due nodi o un solo nodo; nel primo caso ora non si distinguono il nodo iniziale e il finale.

Dato che uno spigolo di un grafo nonorientato risulta equivalente a una coppia di archi l’uno il riflesso dell’altro, possiamo considerare che i grafi nonorientati sono casi particolari di digrafi.

Una tipica applicazione delle strutture grafiche consiste nella schematizzazione di collegamenti (stradali, ferroviari, aerei, telematici, ...) riguardanti determinate localit`a o postazioni. Se si hanno collegamenti a senso unico, percorribili solo da un nodo all’altro si utilizza un digrafo; se tutti i collegamenti si possono percorrere in entrambi i sensi basta un grafo nonorientato.

B53:c.02 Si studiano anche varie strutture grafiche che costituiscono degli arricchimenti delle due basilari; queste in parte riguardano problemi strettamente matematici, ma se ne incontrano moltissime studiate per soddisfare esigenze applicative.

Studiando un sistema stradale, ferroviario o aereo pu`o rendersi necessario caratterizzare i diversi tratti con distanze o tempi medi di percorrenza; oppure caratterizzare le localit`a con la capienza dei suoi parcheggi delle sue stazioni e delle sue piste di atterraggio.

Per trattare queste situazioni si rende necessario arricchire i grafi che le schematizzano con valori ed etichette distintive ai nodi e agli archi.

B53:c.03 Una relazione finita `e una relazione R ⊆ A × B in cui A e B sono insiemi finiti.

Diciamo digrafo ogni coppia Q, R con Q insieme finito i cui elementi sono detti nodi del digrafo, ed R ⊆ Q × Q cio`e R `e una relazione entro Q (e quindi una relazione finita) i cui elementi sono detti archi del digrafo.

Lo studio dei digrafi quindi si confonde con quello delle relazioni finite.

Un digrafo che non sia costituito da un insieme eccessivo di nodi si pu`o presentare efficacemente attraverso la sua raffigurazione, rappresentazione visiva nella quale a ogni nodo corrisponde un punto

(11)

di una porzione di piano e ogni arco ha, bi viene dato da un segmento che unisce a e b ed `e dotato di un segno di freccia che segnala che a si trova prima di b nella precedente scrittura.

Mediante raffigurazioni di digrafi si possono quindi fornire esempi di relazioni finite. Per esempio la relazione < entro l’insieme {2, 3, 5, 7, 11} viene efficacemente rappresentata dal seguente digrafo:

//input pB53c03

In B16b abbiamo visto come i digrafi (finiti) si possono rappresentare esaurientemente anche mediante le loro cosiddette matrici delle adiacenze. Di un digrafo D = hQ, Ri la matrice delle adiacenze `e la funzione indicatrice del sottoinsieme R dell’insieme ambiente Q × Q; tale matrice si denota con D^adjm. Per esempio le matrici delle adiacenze, risp., delle relazioni < e ≥ entro {1, 2, 3, 4, 5}² sono







0 1 1 1 1

0 0 1 1 1

0 0 0 1 1

0 0 0 0 1

0 0 0 0 0













1 0 0 0 0

1 1 0 0 0

1 1 1 0 0

1 1 1 1 0

1 1 1 1 1





 .

B53:c.04 Sono di grande interesse anche entit`a simili alle strutture digrafiche ma costituite da insiemi costruibili non necessariamente finiti di nodi e di loro collegamenti.

A questo proposito definiamo digrafo:costruibile, in breve digrafo:c, ogni struttura costituita da oggetti che si possono proporre come elementari, chiamati ancora nodi, e da coppie di nodi, chiamate ancora archi, per i quali si chiede la disponibilit`a di una procedura in grado di generare i suddetti nodi e i suddetti archi.

Dopo queste strutture si possono prendere in proporre con formalizzazioni prevedibili i pi`u particolari grafi:costruibili nonorientati e le pi`u ricche strutture grafiche:costruibili.

Tra i digrafi:c si distinguono i digrafi (finiti) e i digrafi:c numerabili, strutture dotate di infiniti nodi che sono generabili progressivamente, come lo sono i suoi archi; in altre parole un digrafo-c si dice numerabile sse si dispone un algoritmo in grado di decidere se un possibile nodo `e effettivamente un suo nodo e si dispone di un algoritmo in grado di decidere sse una coppia di possibili nodi `e effettivamente un suo arco.

Usiamo inoltre il terminedigrafi:c contabili per caratterizzare collettivamente i digrafi:c numerabili e i digrafi (finiti).

A partire dai digrafi:c si possono definire, sostanzialmente come strutture particolari delle precedenti, i grafi nonorientati:c, i grafi nonorientati numerabili e i grafi nonorientati contabili. sono chiamati digrafi contabili.

Le strutture grafiche sono molto importanti per lo studio degli algoritmi, per la programmazione e per varie questioni di teoria dei linguaggi. In seguito svilupperemo con una certa ampiezza varie nozioni che riguardano queste strutture [D26 -D35] e alcune loro applicazioni all’interno della matematica.

(12)

B53:d. caratterizzazioni principali delle relazioni

B53:d.01 Introduciamo ora delle caratterizzazioni generali delle relazioni binarie, cio`e caratterizzazioni indipendenti dalla peculiarit`a della loro costruzione e in particolare indipendenti dal prodotto cartesiano nel quale si collocano.

Consideriamo una relazione R ⊆ A × B.

Ricordiamo [a04] che R si dice relazione presimmetrica sse il suo dominio e il suo codominio coincidono, cio`e sse (R^` = R^a).

R si dice invece relazione riflessiva sse `e una relazione presimmetrica e R⁰ = (R^`)Id ⊆ R , cio`e sse R ⊆ R² .

Si dice più particolarmente che R è una relazione riflessiva su A sse AId ⊆ R . La relazione R si dice relazione antiriflessiva sse R^`♦Râ ossia sse

∀a ∈ (dom(R) ∩ cod(R)) ha, ai 6∈ R . Pi`u particolarmente la R si dice relazione antiriflessiva su A sse AId♦R .

Tra le relazioni numeriche e insiemistiche di uso comune sono riflessive le relazioni associate ai segni

= , ≤ , ≥ , ⊆ e ⊇, mentre sono antiriflessive quelle associate ai simboli 6= , > , < , ⊃ , ⊂ . Evidentemente `e antiriflessiva ogni relazione R con dom(R)♦cod(R). mentre la relazione 6= `e antiriflessiva su ogni insieme sul quale viene collocata.

Le relazioni finite riflessive hanno digrafi nei quali ogni nodo `e dotato di cappio cio`e di un arco che parte da un nodo e arriva allo stesso nodo. All’opposto le relazioni:c antiriflessive hanno digrafi privi di cappi.

B53:d.02 Ricordiamo [a08) che la relazione R si dice relazione simmetrica sse R = R ; evidentemente una tale R `e presimmetrica.

Inoltre una relazione R presimmetrica `e simmetrica sse ∀a, b ∈ R^`(= R^a) a R b =⇒ b R a.

Esempi di relazioni simmetriche sono l’uguaglianza = e la disuguaglianza 6=, quale che sia l’ambiente nel quale si colloca.

Sopra l’insieme degli interi positivi P `e simmetrica la relazione di coprimalit`a ⊥

Le relazioni simmetriche finite hanno digrafi in cui per ogni arco u è presente anche il suo riflesso, cioè un arco in cui il nodo d’arrivo è quello di partenza di u e viceversa il nodo di partenza è quello d’arrivo di u.

In altre parole un arco riflesso di un dato arco `e l’arco che incide negli stessi nodi ma che presenta l’orientazione opposta.

Questo induce a raffigurare le relazioni:c simmetriche mediante grafi nonorientati, oggetti che si possono vedere come semplificazioni di quei digrafi che insieme a ogni arco presentano anche l’arco riflesso.

L’insieme delle relazioni simmetriche entro A sar`a denotato con RelSym_A. B53:d.03 La relazione R si dice relazione antisimmetrica sse

∀ a, b ∈ R^`∩ R^a a R b ∧ b R a =⇒ a = b , ovvero sse

R ∩ R ⊆ (R^`)Id ∩ (R^a)Id = (R^`∩ R^a)Id .

Le relazioni associate ai segni ≤ , ≥ , ⊆ e ⊇ sono esempi di relazioni antisimmetriche.

(13)

Nel caso delle relazioni:c l’antisimmetria implica che gli archi dei digrafi associati che non sono cappi sono privi dei loro riflessi.

In particolare si hanno le relazioni R antisimmetriche e antiriflessive per le quali R ∩ R = ∅ e le relazioni R antisimmetriche e riflessive per le quali R ∩ R = (dom(R) ∩ cod(R))Id .

L’insieme delle relazioni antisimmetriche entro A sar`a denotato con RelAsym_A.

B53:d.04 Ancora pi`u particolari delle antisimmetriche sono le relazioni R con R^`♦R^a; esse sono dette relazioni bipartite.

Alle relazioni finite bipartite sono associati i digrafi bipartiti. In un tale digrafo si hanno solo archi che vanno da un nodo associato al dominio della relazione a un nodo associato al suo codominio.

Da un qualsiasi elenco di stringhe, che per una separazione pi`u netta chiediamo non presentino alcun monogramma, si ricava un grafo bipartito i cui archi corrispondano ai collegamenti tra ciascuna delle stringhe e ciascuno dei caratteri che sia sua occorrenza.

La relazione che collega cognomi e nomi quando si applica a un gruppo ristretto di persone italiane di solito risulta bipartita; se invece si citano personaggi quali Giordano Bruno, Andrea Giordano, Corrado Alvaro e Alvaro Vitali si rischia di far venir meno il carattere bipartito del relativo digrafo.

B53:d.05 La relazione R si dice relazione transitiva sse

∀a ∈ R^` , b ∈ (R^`∩ Râ) , c ∈ Râ a R b ∧ b R c =⇒ a R c . Quindi R è transitiva sse R ◦ R ⊆ R, cioè sse

∀n ∈ N Rⁿ ⊆ R , ossia sse R = R^⊕ .

Sono transitive le relazioni associate ai segni = , ≥ , > , ≤ , < , ⊆ , ⊂ , ⊇ , ⊃ .

I digrafi associati a relazioni finite transitive sono caratterizzati dal fatto che la presenza di due o pi`u archi consecutivi implica l’esistenza di un arco che collega il nodo di partenza del primo degli archi consecutivi e il nodo d’arrivo dell’ultimo di questi archi.

Un esempio di relazione transitiva nonpresimmetrica e antiriflessiva `e quella che nell’insieme N (o in qualsiasi dei numeri naturali `e rappresentata dal segno < .

La relazione ⊥ di coprimalit`a non `e transitiva: mentre 20 ⊥ 21 e 21 ⊥ 55, si riscontra che 20 6⊥ 55 . Sono ben definite varie relazioni simmetriche e transitive: inparticolare le relazioni di parallelismo riguardanti segmenti, semirette, rette e piani nel piano-RR e nello spazio tridimensionale.

B53:d.06 Consideriamo ora tipi di relazioni che contengono nella loro definizione altre combinazioni delle relazioni viste in precedenza.

Molti esempi di queste relazioni nel caso siano costruibili riguardano varie entit`a introdotte in precedenza.

La relazione R si dice equivalenza sse è riflessiva, simmetrica e transitiva, cioè sse R⁰ = (R^`)Id = (Râ)Id ⊆ R = R = R² ,

cio`e sse

∀n ∈ Znz R⁰⊆ R = Rⁿ , cio`e sse

R = (R )^⊕∪ R⁰∪ R^⊕ =: R .

La collezione delle relazioni d’equivalenza che presentano interesse, pur molto estesa e variegata per quanto riguarda gli insiemi nei quali si colloca e le propriet`a che possono caratterizzarle, non presenta

(14)

forti distinzioni che riguardino i comportamentidelle singole relazioni rispetto alla definizione generale dell’essere relazione.

Infatti ciascuna relazione equivale alle partizioni dell’insieme, denotiamolo con A, sul quale `e collocata.

L’insieme delle equivalenze entro A sar`a denotato con Eqv_A.

L’importanza delle relazioni di equivalenza `e anche dovuta al fatto che ogni funzione f avente come dominio l’insieme A induce su di esso una partizione che costituisce una caratteristica importante della stessa funzione f .

B53:d.07 La relazione R si dice preordine sse è riflessiva e transitiva, cioè sse è presimmetrica e R⁰ = (R^`)Id ⊆ R = R², cioè sse

R^` = R^a e ∀n ∈ N R⁰⊆ R = Rⁿ , o equivalentemente sse

R^` = R^a e R = R^⊗ .

Osserviamo esplicitamente che ogni relazione R pu`o ampliarsi fino a diventare un preordine: si tratta di sostituirla con la sua chiusura-star.

La relazione R si dice ordine parziale, o anche semplicemente ordine, sse è riflessiva, antisimmetrica e transitiva , cioè sse è presimmetrica e R ∩ R = R⁰⊆ R = R² , cioè sse

R^` = R^a e ∀n ∈ N R ∩ R ⊆ R⁰⊆ R = Rⁿ , cio`e sse

R^` = R^a ∧ R ∩ R = R⁰ ∧ R = R^⊗ .

Possiamo anticipare che si incontra una ampia variet`a di relazioni d’ordine che svolgono ruoli importanti per la comprensione e la organizzazione di tutti i settori della matematica e delle sue applicazioni, sia per quanto riguarda i possibili terreni e le caratterizzazioni legate ad essi, sia per le caratterizzazioni riguardanti l’essere relazioni d’ordine.

Qui ci limitiamo a segnalare che numerosi ordini:costruibili hanno grande rilevanza pratica e spesso possono essere utilizzati vantaggiosamente attraverso le raffigurazioni dei corrispondenti digrafi ordinati [B55].

L’insieme degli ordini entro l’insieme A sar`a denotato con OrdA.

B53:d.08 La relazione R si dice relazione totale sse `e presimmetrica e R∪R ⊇ (R^`×R^a)\dom(R)Id .

E una relazione totale la disuguaglianza, quale che sia l’insieme nel quale si colloca.

Sugli insiemi di numeri reali come Z, Q, RA, Rc e sullo stesso R, sono totali le relazioni espresse dai segni < e >.

Una coppia ha, bi ∈ R^`× R^a si dice coppia confrontabile per la relazione R, o coppia confrontabile-R, sse accade che a R b oppure accade che b R a (senza escludere che si possano provare entrambi gli enunciati).

Chiaramente una relazione R `e totale sse tutte le coppie di R^`× R^a hanno i membri confrontabili secondo R.

L’insieme degli ordini totali entro A sarà denotato con OrdT_A. La relazione R si dice ordine totale sse è un ordine ed è totale.

(15)

Per esempio le relazioni ≥ e ≤ , sopra R o sopra un qualsivoglia insieme di numeri reali risultano essere ordini totali.

Non sono invece ordini totali la relazione di divisibilit`a tra interi positivi e la relazione di inclusione in senso lato tra gli insiemi di un qualsiasi ambiente.

Questi ordini si dicono relazioni d’ordine strettamente parziale.

Tra le relazioni numeriche quelle caratterizzate dai segni < e > non sono ordini totali, in quanto sono totali ma non sono riflessive.

Un altro esempio di ordine strettamente parziale `e la relazione tra coppie di numeri reali definita da hr, si v ht, ui sse r ≤ t ∧ s ≤ u .

Infatti due coppie come h3, 5i e h6, 1i non sono confrontabili.

Pi`u in generale si individua in modo simile un ordine strettamente parziale su ogni prodotto cartesiano di due o pi`u ordini totali.

B53:d.09 Una relazione R si dice relazione tricotomica sse `e presimmetrica e per ogni coppia di elementi diversi ha, bi ∈ R^`× R^` aut a R b aut b R a. Quindi confrontando due elementi qualsiasi a e b del suo dominio = codominio si possono dare tre possibilit`a mutuamente esclusive: a = b, a R b e b R a.

Sono relazioni tricotomiche le relazioni numeriche < e >.

In generale la relazione trasposta di una tricotomica è anch’essa tricotomica. Più precisamente una relazione R ⊂ A × A è tricotomica se {R, AId, R } costituisce una tripartizione di A × A.

Pi`u in generale interessano insiemi di relazioni mutuamente collegate R1, R2, ..., Rm⊂ A × A, con A insieme non vuoto, le quali costituiscono una partizione in m parti dell’ambiente A × A.

Il semplice caso m = 2 si riduce ai duetti formati da una relazione e dalla sua opposta: per esempio in R² duetti di relazioni come {<, ≥} e {>, ≤}.

Situazioni pi`u complesse si presentano per relazioni tra sottoinsiemi di un dato insieme A. Si hanno partizioni come le seguenti

P(A) × P(A) = =A ∪ ⊂ ˙˙ ∪ ⊃ ˙∪ = ⊃ ˙∪ ⊆ ˙∪ ♦ ˙∪ ⊃⊂ = ⊂ ˙∪ ⊇ ˙∪ ♦ ˙∪ ⊃⊂ . Queste partizioni di un generico quadrato cartesiano possono essere utili per chiarire quali sono le possibili relazioni che intercorrono tra due oggetti omogenei; una partizione del quadrato cartesiano di un insieme delle parti in particolare collocati in uno stesso ambiente.

B53:d.10 Consideriamo una relazione R ⊆ A × B e due insiemi C, D tali che C ⊆ A e D ⊆ B.

Si dice restrizione di R a C × D la relazione R

C×D := R ∩ (C × D).

Per esempio di molte relazioni entro l’insieme R risultano utili le restrizioni a sottoinsiemi come R⁺, Q, Z e N .

I sottodigrafi, cio`e digrafi ottenuti da un certo digrafo eliminando alcuni nodi e archi, forniscono esempi di restrizioni di relazioni finite utili in varie applicazioni, in particolare per vari algoritmi.

Sono particolarmente praticate le restrizioni simmetriche delle relazioni; se R `e una relazione contenuta in un quadrato cartesiano S × S, si chiama sua restrizione simmetrica ogni sua restrizione della forma a R ∩ (C × C) con C ⊂ S.

Si considerano spesso le restrizioni simmetriche di relazioni sopra R ai suoi sottoinsiemi come quelli citati in precedenza.

(16)

Ricordiamo che le restrizioni simmetriche di ≤ e ≥ a un qualsiasi sottoinsieme di R continuano a essere ordini totali.

Pi`u in generale ogni restrizione simmetrica di un ordine totale `e un ordine totale.

(17)

B53:e. strutture dotate di ordinamento

B53:e.01 Vi sono molte strutture matematiche rilevanti per le quali è utile definire relazioni binarie che presentano proprietà di compatibilità con le operazioni e con gli oggetti che caratterizzano le strutture stesse.

Per tali strutture munite di relazioni si possono definire costruzioni e procedimenti utilizzabili profi- cuamente per varie finalit`a, in buona sostanza per definire algoritmi efficaci.

Le relazioni che si rivelano pi`u interessanti per arricchire le strutture algebriche sono le relazioni d’ordine.

In effetti vengono definite convenientemente varie specie di strutture ordinate che `e risultato conveniente studiare con sistematicit`a.

Qui ci limitiamo ad segalare alcune di esse per dare una prima percezione delle possibilit`a offerte da queste strutture “miste”.

B53:e.02 Le prime strutture ordinate che conviene considerare sono talune strutture algebriche e tra queste le pi`u basilari sono i semigruppi ordinati.

Si dice semigruppo ordinato una struttura della forma hS, ·, i , ove hS, ·i `e un semigruppo e una relazione d’ordine entro S tali che valga una legge di compatibilit`a

∀ a, b, c ∈ S a b =⇒ a · c b · c . Un esempio ben evidente `e dato dal semigruppo commutativo

P, +, ≤ .

Strutture pi`u specifiche sono i gruppi ordinati. Esempi elementari sono forniti da gruppi numerici come Z, +, −, 0, ≤

e

R+, ·,⁻¹, 1, ≤ . Questi sono gruppi commutativi e totalmente ordinati.

Molti altri gruppi sono soltanto parzialmente ordinati.

Strutture algebriche ordinate pi`u ricche sono gli anelli ordinati.

Pi`u particolari e utili per i calcoli effettivi sono i campi ordinati. Particolarmente importante `e il campo odinato dei numeri reali costruibili.

B53:e.03 Grande rilievo hanno anche alcune strutture topologiche ordinate. Basilare `e la topologia sulla retta.

Notevole interesse rivestono gli spazi vettoriali ordinati. Tra questi sono particolarmente fecondi gli spazi di polinomi.

Va notato che questi sistemi presentano sia una struttura algebrica che una struttura topologica e che entrambe sono compatibili con la rispettiva relazione d’ordine.

Altre strutture ordinate particolarmente ricche sono talune specie di algebre su campo.

(18)

B53:f. relazioni ternarie e di ariet` a superiore

B53:f.01 Osserviamo preliminarmente che tutte le funzioni multivariate, cio`e le funzioni di un genere {A1× A2× · · · × Ak−→ B} se B non si considera decomponibile come prodotto cartesiano si possono considerare relazioni di ariet`a k + 1.

Se invece il suddetto B viene preso in considerazione come prodotto cartesiano della forma B = {B1× B2× · · · × Bh}, le funzioni di cui sopra si possono considerare relazioni di ariet`a k + h.

Un tipo di relazione ternaria che si incontra spesso `e dato dalle funzioni di un genere {A × B −→ C} con A, B e C insiemi qualsiasi; una tale funzione bivariata F individua l’insieme {ha, bi ∈ dom(F ) :| ha, b, F (a, b)i} , cio`e un sottoinsieme di A × B × C.

In particolare le relazioni ternarie fornite dalle funzioni del genere {R × R −→ R} individuano le superfici appartenenti a R^×3che presentano una sola intersezione con le rette parallele al terzo asse di riferimento, quello riguardante gli elementi di C..

Pi`u in generale a ogni funzione del genere F ∈ {A₁× · · · × A_n−1−→ B} corrisponde la relazione n-aria {ha1, ..., an−1i ∈ dom(F ) :| ha1, ..., an−1, F (a1, ..., an−1)i} .

B53:f.02 Nei fondamenti della geometria euclidea [G25] si incontra la relazione di betweenness, o relazione di interposizionalit`a, tra i punti di ciascuna retta R.

Una terna hp, q, ri di punti di R si trova in tale relazione sse q appartiene al segmento pr.

Si ha anche una sorta di variante ciclica della relazione precedente. Essa si applica alle cironferenze o a qualsiasi curva chiusa nonintrecciata Γ e in particolare su ogni curva piana.

Su tale curva si fissa un verso di percorrenza, ad esempio su una curva piana si fissa il verso positivo, ossian il verso antiorario.

Sui punti di tale Γ risulta definita la relazione ternaria, relazione costituita dalle terne di punti diversi che denotiamo con hp, q, ri tali che un oggetto mobile per andare da p ad r percorrendo con continuit`a la Γ nel verso scelto tocca necessariamente q, che risulta essere il punto interposto fra p ed r.

Ricordiamo che di solito invece che di interposizione si usa il termine “intermediazion”, anche se tale nozione non possiede implicazioni metriche.

B53:f.03 Ad ogni figura geometrica collocata in R^×3si associa un insieme di punti individuati da terne di coordinate reali; quindi anche ciascuna di queste figure si pu`o considerare una relazione ternaria.

Ad esempio vengono studiate con cura le relazioni ternarie costituite dai punti delle superfici di elissoidi, paraboloidi, iperboloidi ? e tori e le relazioni ternarie fornite dai punti interni di tali figure [G52].

Pi`u in generale per qualsiasi d ∈ {2, 3, 4, ...} ad ogni figura geometrica nello spazio R^×d si possono associare relazioni d-arie costituite da insiemi di d-uple di numeri reali hx1, x2, ..., xdi.

Questo genere di relazioni possono essere esaminate utilizzando diversi tipi di coordinate. Ad esempio le superfici nello spazio tridimensionale si possono riferire a terne di coordinate cartesiane, di coordinate sferiche, di coordinate cilindriche e di altre ancora [I49].

B53:f.04 Consideriamo un qualsiasi poliedro [D33, G37] e i tre insiemi V costituito dai suoi vertici, E formato dai suoi spigoli ed F l’insieme delle sue facce.

Una interessante relazione ternaria entro V × E × F `e costituita dalle terne hv, e, f i tali che il vertice v lo spigolo e e la faccia f siano mutuamente incidenti.

(19)

Testi dell’esposizione in http://www.mi.imati.cnr.it/alberto/ e in http://arm.mi.imati.cnr.it/Matexp/