I MANUALI

Eraldo NicotraGiulio Vidotto

Loredana Bottazzi

STRUTTURE DISCRETEE MISURAZIONEIN PSICOLOGIA

UNA INTRODUZIONE

Stampa: Arti Grafiche Bianca & Volta

ISBN 978-88-7916-336-1 Copyright 2006 Via Cervignano 4 - 20137 Milano Catalogo: www.lededizioni.com - E-mail: led@lededizioni.com I diritti di traduzione, di memorizzazione elettronica e pubblicazione con qualsiasi mezzo analogico o digitale (comprese le copie fotostatiche e linserimento in banche dati) sono riservati per tutti i paesi.

Indice

1 Logica 191.1 Gli oggetti della logica . . . . . . . . . . . . . . . . . . 191.2 La verifica vero-funzionale . . . . . . . . . . . . . . . . 211.3 Operatori logici e tavole di verità . . . . . . . . . . . . 221.4 Forme proposizionali . . . . . . . . . . . . . . . . . . . 441.5 Validità degli enunciati . . . . . . . . . . . . . . . . . . 511.6 Formule ben formate e predicati . . . . . . . . . . . . 55

2 Insiemi 672.1 Un insieme . . . . . . . . . . . . . . . . . . . . . . . . 672.2 I diagrammi di Eulero-Venn . . . . . . . . . . . . . . . 752.3 Relazioni tra insiemi . . . . . . . . . . . . . . . . . . . 772.4 Operazioni tra insiemi . . . . . . . . . . . . . . . . . . 94

3 Teoria delle Relazioni 1273.1 Prodotti Cartesiani . . . . . . . . . . . . . . . . . . . . 1283.2 Sottoinsiemi di un prodotto cartesiano . . . . . . . . . 1393.3 Proprietà delle relazioni . . . . . . . . . . . . . . . . . 1733.4 Tipi di relazioni . . . . . . . . . . . . . . . . . . . . . . 196

4 Le funzioni 2134.1 Restrizione di una relazione . . . . . . . . . . . . . . . 2134.2 Tipologie Funzionali . . . . . . . . . . . . . . . . . . . 2224.3 Funzioni d’insiemi . . . . . . . . . . . . . . . . . . . . 2484.4 Funzioni numeriche notevoli . . . . . . . . . . . . . . . 256

Bibliografia 270

Presentazione

Ambivalente, per certi versi contraddittorio, sembra essere il rap-porto tra il campo delle scienze psicologiche e l’ambito del saperematematico, generalmente inteso.

Per quanto riguarda la scienza costituita, e la ricerca scientifi-ca in atto, si può constatare che parti significative della modernapsicologia traggono beneficio sostanziale dall’utilizzo di metodi e ri-sultati provenienti da alcuni settori della matematica. Accanto allaconsolidata psicometria, orientata prevalentemente al problema dellamisurazione di caratteristiche psicologiche, e allo sviluppo di metodispeciali per l’analisi statistica di dati da esperimenti psicologici, siè venuta sviluppando una psicologia matematica, in quanto sistemaarticolato di teorie e modelli formali riguardanti ambiti notevoli dellafenomenologia cognitiva e comportamentale - percezione e psicofisica,processi di scelta individuale e collettiva, apprendimento, pensiero elinguaggio, strutture e dinamiche sociali, eccetera. In tempi recentiè rapidamente cresciuta, inoltre, la modellistica computazionale as-sociata a specifici oggetti della ricerca psicologica - in particolare,quelli riguardanti i processi di conoscenza, ed i processi di interesseneuropsicologico - e ciò attraverso un vivace e fertile interscambiocon il campo della intelligenza artificiale, e della scienza matematicadell’informazione nel suo complesso.

A fronte di ciò, coloro che (come il sottoscritto) sono da tempoimpegnati nell’insegnamento di materie collegate alla statistica e allamatematica in corsi di laurea in psicologia - in generale, a quanto èdato sapere, non solo nel contesto universitario italiano - hanno ri-scontrato e continuano a riscontrare difficoltà di ascolto o accettazionedei contenuti e modi caratteristici delle loro discipline, da parte delpubblico cui sono destinati - ossia, gli studenti di psicologia. Un pub-

16 Presentazione

blico che, per altro verso, appare genuinamente interessato al campodelle scienze psicologiche e, per gran parte, seriamente impegnato nelcorso di studi prescelto. Si possono ipotizzare varie ragioni alla basedi questo singolare stato di cose. Ad esempio, una marcata discor-danza tra l’immagine della psicologia nella cultura diffusa, e la realtàeffettiva della psicologia come scienza costituita. Probabilmente, di-sponendo di quella sola immagine, lo studente che inizia gli studi inpsicologia non si aspetta di incontrare in essi parti non secondarie cherisentono dell’interazione con le scienze esatte, ed è quindi indotto aconsiderare quelle parti come qualcosa di estraneo, di non psicologicorelativamente ad una psicologia in quanto sapere umanistico. Può an-che essere che, quanto si riscontra nell’ambito circoscritto degli studipsicologici, sia per la verità il riflesso di un fenomeno di portata piùgenerale, nella presente fase storica dei rapporti tra sapere scienti-fico e società. Un fenomeno che si esprime in una certa resistenza,per una buona percentuale di giovani, ad investire tempo ed energienello studio di discipline con i caratteri dell’astrattezza e del rigo-re formale - paradossalmente, si potrebbe aggiungere, considerandoche appunto discipline di tale tipo hanno svolto e svolgono un ruo-lo determinante nel consentire il progresso scientifico e lo sviluppotecnologico caratteristici del nostro momento storico.

Il presente volume prende forma dall’esperienza degli autori nel-l’insegnamento universitario di psicometria e di metodologia statisti-ca per la ricerca psicologica, e si propone come strumento didatticocapace di confrontarsi con le difficoltà di cui ora si è detto. Gli argo-menti svolti nel volume sono piuttosto elementari, se riferiti al quadrogenerale della moderna matematica: si tratta dei primi concetti di lo-gica formale, di nozioni essenziali di teoria degli insiemi, di elementidella teoria generale delle relazioni e delle funzioni (in chiave insie-mistica), di cenni alla teoria dei grafi e alle strutture combinatoriefinite. Sono però argomenti scelti e disposti con cura e giusto equi-librio, trattandosi di nozioni indispensabili di ingresso non solo perla psicometria, ma anche per parti importanti della psicologia ma-tematica (in particolare, i modelli di tipo discreto), per un primoaccostamento ai modelli computazionali nella ricerca psicologica, eper qualsiasi altro settore della psicologia nel quale sia fatto uso delsistema espressivo e del metodo argomentativo di tipo formale. So-prattutto, sono argomenti esposti, nel volume, con attenzione espertae puntuale alle peculiarità del pubblico al quale il volume stesso è de-

Presentazione 17

stinato, che si esprime nell’impegno costante a stimolare l’interessedello studente-lettore, ad agevolare la comprensione dei concetti pro-posti e l’apprendimento del corrispondente linguaggio simbolico, adillustrare con immediatezza (quando possibile) l’utilità applicativa diquei concetti.

Nel volume sono presentati oltre 100 esempi e più di 90 esercizicon relativo svolgimento, gli uni e gli altri coerentemente inseriti neltesto espositivo. Entro il volume si susseguono inoltre 35 tabelle epiù di 140 figure, che conferiscono visibilità immediata ai principa-li concetti esposti, e danno al lavoro un pregevole aspetto pittorico.Queste caratteristiche sono espressione concreta delle finalità speci-fiche dell’opera, e costituiscono buone premesse per il suo successoin quanto strumento di una didattica introduttiva alle parti formalidella psicologia.

Padova, 14 ottobre 2006

Luigi Burigana

Docente di Psicometria

2.

Insiemi

In questa sezione esporremo brevemente le principali affinità cheesistono tra operatori logici ed operatori insiemistici. Come avre-mo modo di verificare, in maniera analoga al comportamento deglioperatori logici, i quali permettono di generare enunciati complessi apartire da enunciati elementari, gli operatori insiemistici ci mettonoin grado di generare insiemi a partire da altri insiemi precostituiti,utilizzando una o più delle operazioni insiemistiche interne alla teoriaassiomatica degli insiemi. Constateremo, inoltre, che, in base all’as-sioma di specificazione, la stessa identificazione di un insieme puòessere realizzata impiegando variabili individuali ed operatori logici.

Abbiamo osservato nel precedente capitolo come le operazioni lo-giche abbiano la capacità di derivare tutti i valori di verità degli enun-ciati composti a partire da tutti i possibili abbinamenti di valori diverità degli enunciati elementari. È importante notare che le formu-le enunciative ottenute tramite l’impiego di connettivi ci mettono ingrado di definire insiemi di struttura complessa. Sotto questo profilole operazioni insiemistiche sono simili a quelle logiche. L’obbietti-vo di un operatore insiemistico è quello di rintracciare la collezionecompleta di tutti gli esemplari (o elementi) per i quali una specificaformula logica semplice o complessa sia risultata vera. Come verràesposto alla fine del presente capitolo, è possibile mettere in corri-spondenza gli operatori logici con quelli insiemistici in funzione delleloro specifiche azioni.

2.1. Un insieme

Un insieme è un aggregato di entità o di oggetti che vengono rag-gruppati a costituire un complesso unitario. Non esiste una defini-zione in senso formale del concetto di insieme, poiché questo termine

68 2. Insiemi

individua un principio fondamentale dell’intuizione. Possiamo cioèdire che il concetto di insieme non è ricavabile per deduzione da nes-sun’altra entità formale della teoria in base all’applicazione di regolededuttive di natura logica. In tal senso dobbiamo considerare l’insie-me come un oggetto primario. All’interno della teoria degli insiemiviene postulato un primo fondamentale assioma detto di esistenza.

Assioma 2.1.1. Esiste almeno un insieme M . Quest’oggetto for-male viene rappresentato con due parentesi graffe che racchiudono lacollezione di elementi, sicché: M = a, b, c, . . ..

George Cantor (1845-1918), al quale si deve la prima presentazio-ne assiomatica della teoria degli insiemi, in una prima formulazionedel concetto di insieme, afferma: Per molteplicità o insieme intendoogni Molti che si può pensare come Uno. Successivamente, egli reseancora più chiaro il suo pensiero affermando: Per molteplicità o in-sieme intendiamo la riunione in un tutto M di oggetti m determinatie distinti della nostra intuizione o del nostro pensiero che sono dettielementi di M .

Dalla formulazione di Cantor possiamo renderci conto che l’og-getto insiemistico M viene considerato come un aggregato di altreentità dette elementi ed indicati con m. È importante notare che idue oggetti insiemistici (insiemi ed elementi) non vengono posti suun medesimo piano o livello gerarchico: l’insieme conterrà l’elementoe l’elemento non potrà mai contenere l’insieme. Il carattere generaledella teoria permette comunque di considerare un insieme come unpossibile elemento di qualche altro insieme; quindi, sarà sempre pos-sibile generare insiemi che contengano a loro volta insiemi, o elementied insiemi al contempo. Dalla stessa definizione cantoriana di insie-me, all’identità, o unicità degli oggetti insiemistici fa riferimento ilseguente assioma di uguaglianza.

Assioma 2.1.2. Due insiemi M e N sono tra loro identici o ugualise ogni oggetto che appartiene ad M appartiene anche ad N e se ogni

oggetto che appartiene ad N appartiene anche ad M .L’assioma introduce una relazione di ordine gerarchico tra l’ele-

mento e l’insieme e tale relazione viene detta di appartenenza. Unavolta che l’insieme sia stato costituito si dirà che i suoi elementi ap-partengono all’insieme e l’appartenenza verrà indicata con il simbolo∈, mentre la non appartenenza verrà indicata con 6∈. L’appartenenzarappresenta una relazione tra un generico elemento m ed un costrutto

2.1. Un insieme 69

teorico di ordine superiore quale è l’insieme M . La notazione

a ∈ A

stabilisce quindi un legame tra il più piccolo dei termini insiemistici,cioè il singolo elemento, ed un aggregato di oggetti del quale essoè parte costitutiva. Questo assioma ci permette di riconoscere ladiversità tra gli oggetti M ed M. Tale diversità viene resa esplicitatramite l’impiego della notazione:

M 6= M. (2.1)

Si può quindi generalizzare affermando che: m rappresenta in simboliun generico elemento, mentre la notazione m vuole indicare l’esi-stenza di un insieme che abbia come suo unico elemento l’oggetto m.Alla stessa maniera, possiamo generare l’insieme m ed in questacircostanza la notazione ci informerà sul fatto che l’insieme contieneun unico elemento che è m: il quale è esso stesso un insieme cheraccoglie al suo interno esclusivamente l’elemento m. Il procedimentopuò ricorrere indefinitamente indicando in sostanza che l’appartenen-za è una relazione tra elementi da un lato ed insiemi dall’altro lato,ma un elemento che appartenga ad un insieme può essere esso stessoun insieme.

Un insieme può essere identificato in due diverse maniere. La pri-ma maniera viene detta per elencazione, o per estensione, e consistenel disporre all’interno dei simboli costituiti dalle parentesi graffe (orotonde) i nomi o i simboli che identificano gli elementi componentil’insieme; i quali, a loro volta, vengono convenzionalmente separatida virgole.

Esempio 2.1.1. Un insieme di individui sarà rappresentato nellaseguente maniera:

Marco, Francesca, Luigi,Matteo,Roberta,

ove l’ordine degli elementi dell’insieme non riveste alcuna rilevanza.L’insieme

Francesca, Luigi,Marco,Roberta,Matteo

non viene distinto del precedente e i due insiemi vengono quindiconsiderati identici.

70 2. Insiemi

Esempio 2.1.2. Qualora l’ordine fosse invece rilevante, per qualcheopportuna ragione, la notazione insiemistica varierebbe leggermente,e in luogo delle parentesi graffe verrebbero impiegate le parentesirotonde; come indicato nel seguente ordine di atterraggio di alcuniaerei sulla pista di un generico aeroporto:

(Milano,Bari, Palermo, V enezia,Roma).

L’insieme

(Bari, Palermo,Milano,Roma, V enezia)

viene distinto del precedente e i due insiemi rappresentano differentiordini di arrivo degli aerei.

La seconda maniera di indicare un insieme viene detta per re-golarità o per intenzione. Essa stabilisce una formula caratteristicaadeguata all’individuazione degli elementi che portano alla costitu-zione dell’insieme. La formula opera su uno o più degli attributio delle proprietà individuali degli elementi che si vogliono aggrega-re all’interno di un insieme. L’idea di formulare l’appartenenza deglielementi all’insieme in funzione delle loro specifiche proprietà fu origi-nariamente introdotta da Gottlob Frege (1848-1925) al quale si devel’introduzione nella teoria del seguente assioma di specificazione oprincipio di composizione.

Assioma 2.1.3. Per ogni insieme M e per ogni condizione P , esistel’insieme N costituito da tutti e soli gli elementi di M che soddisfinola condizione P .

La genericità con la quale il principio di composizione fu introdot-to generò in passato notevoli difficoltà riguardo alla generalità e allaconsistenza dell’intera teoria insiemistica. Un esempio di possibilecontraddizione in termini della teoria fu offerto da Bertrand Russell(1872-1979) con il noto paradosso che porta il suo nome. Russell siinterrogava sulla possibilità di trattare in seno alla teoria insiemi checontenessero essi stessi come elementi e che potessero essere definitiproprio in base all’impiego del principio di composizione. Egli dimo-strò che insiemi del tipo: X = x | x 6∈ x conducono a contraddizionidella forma: X ∈ X ⇐⇒ X 6∈ X .

Esempio 2.1.3. Il problema viene lucidamente inquadrato dalla no-ta esemplificazione riguardante l’attività del barbiere di un piccolo

2.1. Un insieme 71

paese. L’unico barbiere presente nel paese fa la barba a tutti coloroi quali non la fanno a se stessi. Ci si può allora interrogare su chidebba essere la persona deputata a fare la barba allo stesso barbiere!Nel prendere una decisione ci si accorge facilmente di entrare in con-traddizione poichè: se da un lato si è deciso che lui faccia la barbasolo a coloro i quali non la facciano a se stessi, egli non dovrebbe far-si la barba perchè contravverrebbe al suo ruolo; ma, dall’altro lato,non facendosi la barba ricadrebbe proprio all’interno della categoriadi individui per i quali egli dovrebbe fare la barba, e cioè: coloro chenon la fanno a se stessi. In una simile circostanza, per evitare il pro-blema, sembrerebbe opportuno rinunciare all’esistenza di un barbiereche abbia un tale ruolo!

Dalla formulazione dell’assioma 2.1.3 l’insiemeM deve allora esse-re di generalità maggiore rispetto all’insieme N in quanto gli elementiche compongono N provengono da M ; quindi, gli elementi che con-corrono alla creazione di un insieme debbono comunque provenire daqualche altro insieme: e ciò deve valere al fine di evitare inconvenienticome quelli scoperti da Bertrand Russell.

Esempio 2.1.4. Qualora si fosse interessati all’identificazione degliinsiemi costituiti dai soli numeri naturali pari o dai soli numeri na-turali dispari, il metodo per elencazione risulterebbe inapplicabile:poiché entrambi gli insiemi sono costituiti da elementi infinitamen-te contabili. Bisogna perciò identificare una regola che, basandosisu qualche specifica regolarità, rintracci tutti gli elementi che possie-dono tale caratteristica. Le due espressioni qui sotto riportate per-mettono di individuare gli elementi appartenenti ai due insiemi, Pe D, impiegando esclusivamente operazioni aritmetiche tra i membridell’insieme R dei numeri reali:

P = x ∈ R | x = 2n, n ∈ N; (2.2)

D = x ∈ R | x = 2n+ 1, n ∈ N. (2.3)

Per l’insieme P l’espressione 2n rappresenta un generico numero pari,mentre per l’insieme D l’espressione 2n+1 individua un generico nu-mero dispari. N rappresenta l’insieme dei numeri naturali, R quellodei numeri reali ed il simbolo | rappresenta l’espressione linguisti-ca "tale che" . Nelle due precedenti definizioni degli insiemi P e Dviene impiegata una variabile individuale x ed una formula predica-tiva mono-argomentale che stabilisce l’appartenenza dei numeri pari

72 2. Insiemi

o dei numeri dispari alle loro rispettive collezioni. Dalla definizione2.3.3 fornita a pagina 81 potrà apparire chiaro come gli insiemi N edR siano legati tra loro da una relazione di inclusione. La relazionedi inclusione che riguarda (congiuntamente) le diverse famiglie nu-meriche verrà invece presentata a pagina 122 nella sezione ad essadedicata.

Esercizio 2.1.1. Si identifichi una tra le possibili regole di specifi-cazione per ciascuno dei seguenti insiemi:

a) X1 = a, e, i, o, u;

b) X2 = 2, 4, 6, 8, 10, 12;

c) X3 = 2, 3, 5, 7, 11, 13, 17, 19, 23, . . .;

d) X4 = 1, 1, 2, 3, 5, 8, 13, . . .;

e) X5 = 1, 2, 4, 8, 16, 32, 64, 128.

Soluzioni:

a) X1 = x | x è vocale dell’alfabeto italiano;

b) X2 = x | x è numero pari compreso fra 2 e 12;

c) X3 = x | x è numero primo;

d) In questo esercizio bisogna tenere presente che gli elementi del-l’insieme vanno considerati nell’ordine dato e costituiscono unasequenza ordinata di numeri naturali. Diversamente, non sa-rebbe possibile identificare una regola che ricorsivamente rin-tracci un elemento che occupi una particolare posizione all’in-terno dell’insieme in funzione di uno o più dei suoi predeces-sori. Quindi, in questa circostanza si tratta di identificare unaparticolare serie numerica piuttosto che un insieme numericoqualsiasi. Questa serie di valori numerici viene denominata se-

rie di Fibonacci, dal nome del matematico che la formalizzò. Laregola generatrice della serie è la seguente: x1 = x2 = 1;Xn =Xn−1 +Xn−2;n = 3, 4, . . .;

e) X5 = x | x = 2n; 0 ≤ n ≤ 7, n ∈ N.

2.1. Un insieme 73

Un ruolo speciale, all’interno della teoria degli insiemi, viene as-segnato all’insieme vuoto; il quale, come constateremo più avanti, èsottoinsieme di qualsiasi altro insieme. Il simbolo impiegato per in-dicarlo è ∅. Un insieme vuoto è generabile mediante l’impiego di unaqualsiasi forma proposizionale che conduca ad una contraddizione,quale ad esempio: ∅ = z | z 6= z. Oppure, in termini concreti, conuna espressione del tipo: l’insieme dei mesi dell’anno di 40 giorni. Laproprietà dell’insieme vuoto di essere incluso in qualsiasi altro insiemeverrà trattata dopo che avremo avuto modo di presentare la defini-zione relativa all’inclusione tra insiemi. Un altro importante insiemeè quello che raccoglie al suo interno la gamma di tutti gli oggetti per iquali è rilevante stabilire una rappresentazione insiemistica. Tale in-sieme viene detto insieme universale e noi lo indicheremo con il sim-bolo U. L’insieme universale è generabile mediante l’impiego di unaqualsiasi forma proposizionale che conduca ad una tautologia la qualeè, ad esempio utilizzata per descrivere la collezione: U = z | z = zdegli oggetti identici a se stessi.

In generale, un insieme A può venire idealmente costituito identi-ficando un’espressione del tipo ϕ(·) (si veda, a proposito, il capitolo1) che abbia lo scopo di caratterizzare gli elementi interni ad A conqualche formula predicativa: così come viene auspicato dall’assioma2.1.3. L’espressione ϕ(·) rappresenta quindi una funzione enunciati-va che ha come argomento una variabile enunciativa per la quale siapossibile rilevare un dato numero di elementi che la rendano vera.Sotto tale profilo, tutti gli oggetti, o le entità, per i quali sia pos-sibile verificare il possesso dell’attributo o della proprietà espressada ϕ(·) vengono idealmente raggruppati e identificati con un nuovosimbolo: nella nostra notazione il simbolo impiegato è A. Seguendoquindi l’indicazione di Cantor alla lettera maiuscola A corrisponderàun collettivo di oggetti, mentre alla lettera minuscola corrisponderàil singolo elemento a. Per rappresentare formalmente l’insieme A sipotrà allora ricorrere all’espressione: A = a | ϕ(a) = 1 oppure, inmaniera alternativa, a ∈ A⇐⇒ ϕ(a) = 1.

Esercizio 2.1.2. Si rappresenti in forma estesa la composizione in-terna dei seguenti insiemi:

a) X1 = x ∈ N | 2 ≤ x ≤ 8;

b) X2 = x | x è una sigla automobilistica veneta;

74 2. Insiemi

c) X3 = x ∈ N | x = n× 4;n = 1, 2, 3, 4;

d) X4 = x ∈ Q | (x ≥ 0) ∧ ((2x+ 3)(3x− 2) = 0);

e) X5 = x ∈ N | 5 ≤ x ≤ 12;

f) X6 = x ∈ N | 3 < x ≤ 14;

g) X7 = x ∈ N | 7 ≤ x < 11;

h) X8 = x ∈ Z− | 5 < x < 16;

i) X9 = x ∈ Z− | −4 < x < 12;

j) X10 = x ∈ Z∗ | −2 < x < 2;

k) X11 = x ∈ R− | x < 16;

l) X12 = x ∈ R+ | x ≥ 10.Soluzioni:

a) X1 = 2, 3, 4, 5, 6, 7, 8;

b) X2 = BL, PD, RO, TV, VE, VR, VI;

c) X3 = 4, 8, 12, 16;

d) In questo esercizio l’insieme viene indicato dalla forma proposi-zionale (x ≥ 0) ∧ ((2x+3)(3x−2) = 0) la quale stabilisce che lavariabile individuale deve essere un numero razionale maggioreo uguale a 0 e che il prodotto (2x+3)(3x-2) si deve annullare.Questa forma proposizionale individua lo spazio della soluzionecostituito dagli elementi interni a Q che rendono vera l’equa-zione polinomiale. I valori ottenuti dalla soluzione trasformanoquindi la forma proposizionale in una proposizione vera ed in-dividuano, con ciò, un sottoinsieme di Q. La soluzione propriaè allora: X4 = 2

3;

e) X5 = 5, 6, 7, 8, 9, 10, 11, 12;

f) X6 = 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14;

g) X7 = 7, 8, 9, 10;

h) X8 = = ∅;

2.2. I diagrammi di Eulero-Venn 75

i) X9 = −3,−2,−1;

j) X10 = −1, 1;

k) X11 =]−∞, 0[ è un intervallo aperto;

l) X12 = [10,+∞[ è un intervallo chiuso sul numero reale 10.

2.2. I diagrammi di Eulero-Venn

Un insieme può essere rappresentato tramite una figura geome-trica regolare, quale ad esempio un cerchio oppure un rettangolo; o,in altra maniera, facendo uso di una qualsiasi figura geometrica chiu-sa. Gli elementi dell’insieme vengono disposti all’interno dell’area

Figura 2.1: Rappresentazione di un insieme.

individuata dalla figura. Come è già stato indicato, agli insiemi ven-gono assegnate lettere maiuscole, a riprova del loro più elevato ruologerarchico rispetto agli elementi; mentre per questi ultimi vengonogeneralmente riservate le lettere minuscole.

Come abbiamo precedentemente rilevato, un insiemeA viene iden-tificato all’interno di una classe più ampia di oggetti che può essereanche indicata col termine dominio o classe di appartenenza di A. Unqualsiasi insieme viene conseguentemente ricavato circoscrivendo gli

76 2. Insiemi

elementi ad esso interni e, contemporaneamente isolando quelli estra-nei, che comunque rimangono membri della classe più estesa. Nelcaso più generale, la classe di appartenenza di A può essere defini-ta nel modo più esteso possibile identificandosi quindi con l’insiemeuniversale U. Per rendere visibile la dominanza di un insieme univer-sale nei riguardi di un insieme generico vengono utilizzate due figuregeometriche chiuse: la prima delle quali indica l’insieme universale edelimita l’area più estesa; mentre la seconda racchiude alcuni elementidell’insieme universale U che possano essere isolati sulla base di alcuneloro peculiarità (o proprietà) e in maniera tale che l’area delimitatasia interna a quella tracciata dal confine più esterno. Il diagrammadi Venn relativo a questa ultima circostanza viene presentato nellasottostante figura 2.2. Quando un insieme viene generato tramite

Figura 2.2: Rappresentazione di un insieme A in U.

un’espressione che è falsa per tutti gli elementi dell’insieme univer-sale si ottiene l’insieme vuoto. Tale insieme può comunque venireidealmente tracciato all’interno dell’area relativa all’insieme univer-sale, ma al suo interno non potrà apparire alcun oggetto o elementodi quello stesso dominio universale.

2.3. Relazioni tra insiemi 77

Figura 2.3: L’insieme vuoto: un insieme che non contiene elementi.

2.3. Relazioni tra insiemi

Uguaglianza tra insiemi

Definizione 2.3.1. Siano dati due insiemi A e B. Diremo che A èidentico a B e scriveremo A = B quando, per qualsiasi elemento xvenga scelto, x è presente in A se e solamente se x è presente anchein B.

Figura 2.4: Uguaglianza tra due insiemi.

78 2. Insiemi

Possiamo allora indicare in maniera formale che:

A = B sse (∀x)(x ∈ A⇐⇒ x ∈ B). (2.4)

Esempio 2.3.1.A = a, b, d, h, w, e, i,B = a, d, b, h, e, w, i,

(A = B) = a, b, d, e, h, i, w.

Nell’esempio proposto è possibile osservare che la differenza nellacollocazione interna degli elementi dei due insiemi A e B è del tuttoirrilevante al fine della valutazione della relazione di uguaglianza trai due insiemi non ordinati. Le etichette A e B risultano quindi inter-scambiabili, poiché individuano la stessa collezione di oggetti. Cosìle scritture:y, y,y, e y,y,y sono da considerare tra loro tutteequivalenti. In base alla definizione 2.3.1, un insieme non ordinatocostituisce quindi una collezione di tipi piuttosto che una disposizio-

ne di elementi ad esso interni. Si tenga però presente che le duenotazioni y e y rappresentano oggetti diversi e quindi:

y 6= y 6= y. (2.5)

Il simbolo y viene impiegato per connotare un elemento generico men-tre il simbolo y rappresenta un insieme che contiene al suo internosolo l’elemento y; inoltre, la notazione y indica un insieme checontiene come elemento un altro insieme che possiede al suo internol’unico elemento y.

Esempio 2.3.2. L’uguaglianza tra due insiemi A e B viene formal-mente dimostrata verificando la validità di due opposte implicazioni,le quali congiuntamente rappresentano un’equivalenza logica. Le dueimplicazioni provano l’appartenenza di un elemento variabile x ad en-trambi gli insiemi A e B; ma operano in direzioni opposte muovendola prima a partire da A e la seconda a partire da B come mostratodalle due seguenti espressioni:

x ∈ A =⇒ x ∈ B;

x ∈ B =⇒ x ∈ A.

2.3. Relazioni tra insiemi 79

Riprendendo l’esempio 2.1.4 presentato a pagina 71 e richiamando ledefinizioni 2.2 e 2.3, possiamo provare come l’insieme P+ dei numerinaturali pari, e diversi da zero, sia uguale all’insieme dei numeri na-turali K ottenuti sommando due numeri dispari in D. Vogliamo cioèverificare che sebbene gli insiemi P+ e K abbiano definizioni diver-se essi portano alla costituzione dello stesso insieme. Inizialmente,assumiamo che x ∈ P+ e deduciamo quindi che dovrà valere anchex ∈ K. Se x è un numero pari, se cioè è membro di P+, allorapossiamo individuarlo utilizzando la regola di identificazione dell’in-sieme P+ dei numeri pari corrispondente a x = 2(n + 1). Questaespressione è però uguale ad un’altra espressione che fa invece rife-rimento alla regola di composizione dell’insieme dei numeri dispariD. In particolare, possiamo scrivere x = (2n + 1) + 1 e constatareche tale numero appartiene a K essendo x somma dei due numeridispari 2n + 1 ed 1. Risulta quindi provato che: se x appartiene aP+ allora deve appartenere anche a K. Nel verificare la seconda im-plicazione si assume invece che x ∈ K; da cui, essendo x definito inK come un numero ottenuto dalla la somma di due numeri dispari,potrà, in alternativa, essere scritto come x = (2m+1)+(2n+1), con-formemente alla regola di definizione dell’insieme dei numeri dispariD. Quest’ultima espressione è chiaramente riconducibile alla seguen-te uguaglianza: x = 2(m + n + 1), dove i numeri 2 ed 1 sono dellecostanti ed m ed n delle variabili individuali. Possiamo osservare chesostituendo ad (m+n+1) la lettera d, indicante un qualsiasi numero,ricaviamo l’espressione x = 2d dalla quale è chiaramente visibile chex non può che essere un numero pari. Risulta così verificata anche laseconda implicazione, la quale asseriva che se x fosse appartenuto aK allora sarebbe appartenuto anche a P . Essendo le due implicazionivalide congiuntamente, possiamo concludere che l’insieme P+ dei nu-meri pari e diversi da zero può venire identificato anche della regoladi composizione x = (2n + 1) + 1, la quale genera lo stesso insiemedella regola x = 2(n+ 1); pertanto, gli insiemi P+ e K coincidono esi potrà allora scrivere P+ = K.

La relazione di uguaglianza tra insiemi gode di alcune importantiproprietà che verranno adesso brevemente indicate. Per qualsiasigenerica collezione di insiemi M,N,O si ha che:

M = M ;

N = N ;

80 2. Insiemi

O = O;

(M = N) =⇒ (N = M);

(M = N) ∧ (N = O) =⇒ (M = O).

Qualora due insiemi A e B non dovessero possedere la medesimacollezione di elementi, essi dovranno essere considerati diversi e talemancata uguaglianza verrebbe indicata con la notazione A 6= B.

Definizione 2.3.2. Due insiemi A e B sono tra loro differenti seesiste almeno un elemento che appartiene esclusivamente ad uno deidue insiemi, come indica la seguente espressione:

A 6= B sse (∃y)((y ∈ A ∧ y 6∈ B) ∨ (y ∈ B ∧ y 6∈ A)). (2.6)

Figura 2.5: Insiemi differenti.

Esempio 2.3.3.A = a, b, d, e, f, i, w,B = a, b, d, e, h, i, w,

(A 6= B).

In questo esempio si può facilmente riscontrare come la composizioneinterna dei due insiemi sia differente e in conseguenza di ciò le eti-chette formali A e B non sono più interscambiabili ma delineano dueoggetti chiaramente distinti. In questa circostanza gli elementi sonogli stessi in entrambi gli insiemi ad eccezione di f che appartiene soload A e di h che appartiene solo a B.

2.3. Relazioni tra insiemi 81

Inclusione e sottoinsiemi

Definizione 2.3.3. Siano A e B due generici insiemi, diremo che Aè un sottoinsieme di B, o che A è incluso in B, se e solamente se perogni generico elemento x, se x è presente in A, allora x apparterràanche a B. Formalmente:

A ⊆ B sse (∀x)(x ∈ A =⇒ x ∈ B). (2.7)

Esempio 2.3.4.A = b, g, f, h, u, w,

B = a, b, d, e, f, g, h, i, j, k, u, s, w,A ⊆ B.

Figura 2.6: Inclusione tra gli insiemi A e B.

L’uguaglianza presentata nella definizione 2.3.1 può venire rifor-mulata nei termini di inclusione tra insiemi osservando che per poteressere valida devono valere congiuntamente le due inclusioni:

A = B sse A ⊆ B e B ⊆ A. (2.8)

Dall’uguaglianza tra insiemi e dalla relazione di inclusione deriva laseguente proprietà:

A ⊆ B sse A ∪B = B. (2.9)

82 2. Insiemi

Questa proprietà può essere estesa alla relazione di inclusione diun insieme con se stesso, in quanto può sempre venire verificata lacondizione:

B ⊆ B sse B ∪B = B. (2.10)

Definizione 2.3.4. Diremo che un insieme A è sottoinsieme proprio

di B e scriveremo A ⊂ B quando:

(∀x)((x ∈ A =⇒ x ∈ B) ∧ (∃x)(x ∈ B ∧ x 6∈ A)); (2.11)

o analogamente

A ⊂ B sse (A ⊆ B ∧B 6= A). (2.12)

Esercizio 2.3.1. Si verifichi in quali circostanze risultano vere leseguenti espressioni:

a) (A ∩B) = A;

b) (A ∪B) ∩ (A ∩B) = A.

Soluzioni:

a) La verifica è semplice: è sufficiente richiamare le definizione2.3.3 di inclusione e l’espressione 2.9 la quale ci informa sulfatto che B è un insieme che raccoglie tutti gli elementi di A ene aggiunge alcuni specificamente suoi. È vero cioè che: A ⊆ B.

b Anche in questa circostanza è utile fare riferimento alle formule2.7 e 2.9 dalle quali possiamo dedurre che:

(A ∪B) ∩ (A ∩B)

= B ∩ (A ∩B) [dalla 2.7]

= (B ∩A) [dalla 2.9]

= (A ∩B)

= A.

Anche in questo caso è vero che: A ⊆ B.

2.3. Relazioni tra insiemi 83

Se un insieme C non è un sottoinsieme di un insieme D la nota-zione C 6⊂ D indicherebbe l’assenza della relazione tra i due insiemimessi a confronto.

La relazione di inclusione tra insiemi gode anche della proprietàtransitiva: secondo la quale, se A ⊆ B, B ⊆ C, C ⊆ D allora A ⊆ C,A ⊆ D e B ⊆ D.

A

=

⊆

⊆ ⊆

B

=

⊆⊆

D

=

C

=

⊆

Figura 2.7: Proprietà transitiva della relazione di inclusione.

Insieme potenza Come avremo modo di approfondire nel capi-tolo dedicato alla probabilità, lo sviluppo dell’insieme potenza rivesteun ruolo fondamentale nel potere assegnare dei valori di probabilitàagli eventi. Per adesso è sufficiente comprendere come l’insieme po-tenza, indicato con la lettera P, rappresenti la più ampia collezionedi sottoinsiemi di un insieme già costituito.

Definizione 2.3.5. Sia dato l’insieme Ω. Diremo che P(Ω) è l’insie-me potenza di Ω se valgono le tre seguenti condizioni:

1. Ω ∈ P(Ω);

2. ∅ ∈ P(Ω);

3. P(Ω) = A | A ⊆ Ω.

3.

Teoria delle Relazioni

In molteplici circostanze è necessario mettere in corrispondenzagli elementi di un insieme con quelli di un altro insieme. Così, adesempio, nel condurre una ricerca sui rapporti familiari tra genitorie figli è opportuno registrare per ogni coppia di genitori quali siano ilori figli e rilevare, in riferimento al dato accoppiamento genitori-figli,le variabili sperimentali ritenute rilevanti nel valutare il rapporto.

Figura 3.1: La corrispondenza associa a ciascun genitore i propri figli.

Tali corrispondenze debbono però essere eseguite in modo da assi-curare alcune regolarità insiemistiche. In tal senso, qualsiasi elemen-to venga associato ad un altro elemento dello stesso insieme, o di uninsieme diverso, dovrà fornire informazione riguardo alla collezioneinsiemistica di provenienza (di quale tipo di oggetto si tratta) e allaposizione ordinale che esso occupa all’interno della concatenazionedi elementi generata dalla corrispondenza che di volta in volta vienerealizzata.

128 3. Teoria delle Relazioni

3.1. Prodotti Cartesiani

L’operazione che permette di stabilire lo spazio fondamentale al-l’interno del quale realizzare un insieme di concatenazioni tra elementiinsiemistici prende il nome di prodotto cartesiano. All’interno di unprodotto cartesiano vengono realizzati tutti i possibili abbinamentitra gli elementi di volta in volta coinvolti. Il numero totale di abbi-namenti generati dall’operazione insiemistica dipende dal numero dielementi presenti in ciascuno degli insiemi generatori. Naturalmente,nulla esclude la possibilità di concatenare tra loro un numero fini-to oppure infinito di insiemi o di ripetere l’operazione su un unicoinsieme.

Esempio 3.1.1. In una indagine sul clima lavorativo esistente trai dipendenti di una grossa industria potrebbe essere utile svolgereun’indagine che accerti quale sia lo stato della comunicazione all’in-terno del luogo di lavoro, e, al fine di raggiungere un tale obbiettivo,si potrà procedere alla valutazione dell’intensità e della natura dellecomunicazioni tra il personale dirigente e quello tecnico, oppure traquello tecnico e quello amministrativo, e così via. Per poter studiareal meglio le modalità di comunicazione bisognerà individuare tuttii possibili circuiti di comunicazione esistenti tra tutte le categorielavorative implicate. Così, ad esempio, se il sistema produttivo del-l’industria, di cui si è già accennato, fosse ripartito in un’area delladirigenza (D), un’area tecnica (T), un’area amministrativa (A) ed, inultimo, un’area produttiva (P), si dovrà rappresentare l’intera rete dicomunicazione nella seguente maniera:

D T

A P

Figura 3.2: Schema della rete di comunicazione all’internodell’azienda.

3.1. Prodotti Cartesiani 129

Quando vengono stabilite delle connessioni tra entità appartenen-ti ad insiemi distinti, o anche tra elementi di uno stesso insieme, sigenera un nuovo aggregato di oggetti: in questo caso, gli elementi ap-partenenti al nuovo insieme saranno delle coppie, oppure delle terne,o più in generale delle file, o catene ordinate, di elementi chiamaten-uple.

Posizioni

1 2 3 4

a ∈ A b ∈ B c ∈ C d ∈ D

(a, b, c, d)

Figura 3.3: Generazione di una 4-upla ordinata.

Le n-uple, come già indicato, debbono essere generate in modotale che le posizioni occupate dai singoli elementi forniscano informa-zione riguardo all’ordine di successione degli insiemi generatori.

Come abbiamo avuto modo di osservare nel capitolo preceden-te, un insieme costituisce un aggregato di oggetti non ordinati. Unacoppia di elementi viene fornita di un ordine se presi due qualsiasioggetti x, y di un insieme X si considera la relazione di inclusionepresente nell’insieme x, x, y. Essendo x ⊆ x, y si assumeche l’insieme x, x, y ordinato per inclusione trasferisca l’ordi-ne alla coppia x, y, la cui notazione viene modificata con la scrit-tura (x, y) e resa diversa dall’ordinamento y, x, y legato allascrittura (y, x).

Come avremo modo di notare nelle prossime pagine, fornire un or-dine agli elementi di un insieme costituisce il primo passo per stabilireuna relazione (o associazione) tra due (o più) insiemi. Un’importantepropriatà delle coppie ordinate è la seguente:

∀(xi, xj ∈ X)(xi, xj) = (x′i, x′j)⇔ xi = x′i ∧ xj = x′j .

Questa proprietà ci permette di mantenere distinti due insiemi com-posti dagli stessi elementi ma presentati in ordine inverso. Se difatti

130 3. Teoria delle Relazioni

dovessimo valutare le due coppie (xi, xj) e (xj , xi) in base alla pro-prietà più sopra menzionata noteremmo che essa viene falsificata nelcaso in cui (xi 6= xj), in quanto, per l’equivalenza stabilita, si ricaval’espressione (xi = xj) ∧ (xj = xi), la quale è vera se e solo se en-trambe sono vere; pertanto se (xi 6= xj) è vero che (xi, xj) 6= (xj , xi).L’ordine è quindi discriminativo quando gli elementi sono tra lorodifferenti, mentre non lo è nel caso in cui sussiste uguaglianza. Lapropriatà appena indicata può naturalmente essere estesa a qualsiasin-upla ordinata ricorrendo alla formula:

(x1, . . . , xn) = (x′1, . . . , x′n)⇔ x1 = x′1, . . . , xn = x′n.

Prima di potere esporre formalmente il concetto di relazione sarà ne-cessario introdurre la definizione di una nuova operazione insiemisticache renda possibile generare degli insiemi i cui elementi siano propriole dette n-uple ordinate. Questa nuova operazione prende il nome diprodotto cartesiano. Presenteremo, di seguito, le principali proprietàche caratterizzano alcuni tipi notevoli di relazioni e l’insieme delleregole che permettono di generare nuove relazioni a partire da altrerelazioni tramite l’operazione di composizione. In ultimo, presentere-mo due importanti famiglie di relazioni: le relazioni di equivalenza ele relazioni d’ordine.

Sia il primo tipo che il secondo tipo di relazioni assumono un ruolonotevole all’interno della teoria della misurazione e, in specifico, sonofondamentali nel determinare le differenze esistenti tra tipi diversi discale di misura. Illustreremo, infine, le loro principali caratteristichee le loro specifiche proprietà.

Prodotto cartesiano tra due insiemi Un’operazione fon-damentale tra insiemi riguarda la formazione di coppie, di terne, o,più in generale, di qualsiasi n-upla si voglia costituire al fine di iden-tificare una relazione tra due o più elementi appartenenti ad insiemidi diversa o di identica natura.

Definizione 3.1.1. Dati gli insiemi A e B, non vuoti, tra loro distintio coincidenti, chiameremo prodotto cartesiano tra A e B, e lo indiche-remo con A × B, oppure con #A,B, l’insieme ottenuto accoppiandoogni elemento di A con ciascuno degli elementi di B, in modo tale chel’elemento di A occupi sempre il primo posto della coppia e l’elementodi B occupi sempre il secondo posto della medesima coppia.

3.1. Prodotti Cartesiani 131

Utilizzando la notazione simbolica possiamo allora scrivere:

A×B = (ai, bj) | ai ∈ A∧bj ∈ B : i = 1, . . . , n; j = 1, . . . ,m. (3.1)

con |A| = n e |B| = m. Dalla 3.1 appare chiaramente che il prodottocartesiano tra insiemi è un insieme non ordinato al cui interno com-paiono elementi che sono essi stessi insiemi ma con elementi ordinati.Dall’ordinamento imposto al prodotto cartesiano deriva la seguenteproprietà:

A×B 6= B ×A.Questa proprietà ci informa sul fatto che il prodotto cartesiano nongode, in generale, della proprietà commutativa, tranne nella circo-stanza in cui si abbia A = B. In quest’ultimo caso risulterà vera ladoppia implicazione:

A×B = B ×A⇔ A = B.

Una prima modalità di rappresentazione di un prodotto cartesianotra due insiemi può essere ottenuta facendo uso di una tabella adoppia entrata dove le n righe, ordinate in senso verticale, allineanogli elementi appartenenti all’insieme A; mentre le m colonne, ordinatein senso orizzontale, allineano gli elementi appartenenti all’insieme B.

A×B b1 b2 · · · bma1 (a1, b1) (a1, b2) · · · (a1, bm)a2 (a2, b1) (a2, b2) · · · (a2, bm)...

......

. . ....

an (an, b1) (an, b2) · · · (an, bm)

Tabella 3.1: Prodotto cartesiano A×B.

In ciascuna delle n×m celle, interne alla tabella, vengono succes-sivamente collocate le coppie ordinate costituenti l’insieme prodottoA×B. È convenzione adottare gli elementi di riga come primi mem-bri delle coppie e gli elementi di colonna come secondi membri. Ilmodello generale viene esposto nella tabella 3.1.

Esempio 3.1.2. In uno studio sugli effetti arrecati dal fumo sulsistema cardiaco si potrà procedere alla valutazione dello stato disofferenza cardiaca secondo due modalità di indagine: relate, da un

132 3. Teoria delle Relazioni

lato, alla quantità di sigarette fumate giornalmente; A = a1 ≤5, 6 ≤ a2 ≤ 15, 16 ≤ a3 ≤ 30, a4 ≥ 31; e, dall’altro la-to, alla valutazione della gravità del disturbo cardiaco riscontrato:B = b1 = non presente, b2 = lieve, b3 = medio, b4 =grave, b5 = gravissimo. In questa circostanza, al fine di stu-diare la relazione intercorrente tra le due modalità di indagine, sarànecessario individuare tutti i possibili accoppiamenti tra le diversequantità di sigarette fumate giornalmente e i diversi gradi di gravi-

tà del disturbo cardiaco stabiliti. L’insieme totale degli abbinamentipotrà essere ottenuto per mezzo del prodotto cartesiano tra i due in-siemi A e B, impiegando i valori numerici associati alle due variabilisperimentali.

Sicchè:

A×B =

= (a1, b1), (a1, b2), (a1, b3), (a1, b4), (a1, b5)

= (a2, b1), (a2, b2), (a2, b3), (a2, b4), (a2, b5)

= (a3, b1), (a3, b2), (a3, b3), (a3, b4), (a3, b5)

= (a4, b1), (a4, b2), (a4, b3), (a4, b4), (a4, b5).

Esempio 3.1.3. In un esperimento in cui il compito dei parteci-panti consiste nel denominare oggetti con basso, medio e alto valored’immagine, si vuole studiare l’effetto provocato dalla durata dellapresentazione dello stimolo visivo sul tempo di risposta. Vengonoadottati per l’esperimento i seguenti tempi di presentazione degli sti-moli: 100, 200 e 500 millisecondi. Al fine di ottenere una valutazionedei legami esistenti tra la natura iconica degli stimoli e le modalità dipresentazione degli stessi, il ricercatore dovrà valutare tutte le pos-sibili circostanze d’osservazione del fenomeno: dovrà, cioè, procederealla verifica di tutti i possibili abbinamenti tra i valori d’immaginedegli oggetti e i diversi tempi di presentazione degli stimoli. È que-sto il caso in cui il piano dell’esperimento viene stabilito realizzandoil prodotto cartesiano tra i due insiemi A = basso, medio, alto eB = 100, 200, 500 secondo lo schema presentato nella tabella 3.2

Il prodotto cartesiano tra due insiemi può essere utilizzato an-che per rappresentare un sistema di misurazione secondo il quale,all’interno delle celle del prodotto, vengono registrati i valori ricavatidall’osservazione congiunta di una data regolarità funzionale esisten-

3.1. Prodotti Cartesiani 133

A×B 100 200 500basso (basso, 100) (basso, 200) (basso, 500)medio (medio, 100) (medio, 200) (medio, 500)alto (alto, 100) (alto, 200) (alto, 500)

Tabella 3.2: Prodotto cartesiano dell’esempio 3.1.3.

te tra gli elementi di un insieme A e quelli presenti in un insieme Bdiverso da A.

Esempio 3.1.4. Se indichiamo conM l’insieme dei valori della massadei corpi e con F l’insieme delle forze applicabili agli stessi corpi,possiamo ricavare la misura delle diverse accelerazioni a ∈ A ottenutedai corpi con masse m ∈M ai quali sia stata applicata una forza f ∈F . Sappiamo che la relazione fisica che lega i due insiemi F ed M , neiconfronti delle accelerazioni, è esprimibile con la relazione funzionaleg(M,F ) = A, la quale è legata alla relazione numerica a = f/m.La tabella 3.3 presenta gli abbinamenti tra i valori dell’insieme M equelli dell’insieme F ; mentre i simboli che rappresentano il risultatodel rapporto f/m della funzione g(M,F ) sono stati inseriti all’internodelle celle della tabella 3.4.

M × F f1 f2 · · · fK

m1 (m1, f1) (m1, f2) · · · (m1, fK)m2 (m2, f1) (m2, f2) · · · (m2, fK)...

......

. . ....

mN (mN , f1) (mN , f2) · · · (mN , fK)

Tabella 3.3: Rappresentazione tabellare della funzione g(M,F ).

g(M,F ) f1 f2 · · · fK

m1 a11 a12 · · · a1K

m2 a21 a22 · · · a2K

......

.... . .

...mN aN1 aN2 · · · aNK

Tabella 3.4: Rappresentazione tabellare dei valori a = f/m.

4.

Le funzioni

Nel precedente capitolo, abbiamo mostrato come una relazionestabilisca legami di qualche natura tra alcuni o tra tutti gli elementiappartenenti ad almeno due insiemi tra loro diversi o identici. Questilegami, come abbiamo avuto modo di verificare, sono regolati da pro-prietà formali ben definite. L’argomento che ci apprestiamo a trattarein questo capitolo riguarda il modo di rendere una relazione ancorapiù fine sotto il profilo formale; e, come avremo modo di osservare,anche più regolare dal punto di vista operazionale.

Imponendo sulle relazioni alcuni vincoli, l’ambito di validità diqueste risulterà ridotto ed il numero di n-uple conformi alle distinteregole di generazione sarà di conseguenza minore rispetto al numerodi n-uple che appartengono ad una qualsiasi relazione. Tali relazionicon vincoli vengono identificate con il nome di applicazioni o funzioni.

4.1. Restrizione di una relazione

Abbiamo osservato fino ad adesso come sia possibile associare glielementi di un insieme agli elementi di un altro insieme sfruttandol’operazione di prodotto cartesiano (si veda, a tal fine, la definizio-ne 3.1.1 oppure l’espressione 3.1). Abbiamo anche avuto modo diconstatare come più di un elemento del codominio della relazionepossa essere associato ad uno stesso elemento del dominio, ed inoltreabbiamo verificato come non sia necessariamente dato che tutti glielementi del dominio debbano entrare a comporre l’insieme delle cop-pie appartenenti alla relazione (si veda, ad esempio, la figura 3.1). Visono però situazioni nelle quali le relazioni assumono una forma spe-ciale: quella in cui ad ogni elemento del dominio viene a corrispondereun unico oggetto, o elemento, del codominio della relazione. Questotipo speciale di relazioni possono essere formalizzate applicando due

214 4. Le funzioni

condizioni restrittive alla definizione di relazione già presentata in3.2.1. La prima restrizione consiste nel vincolare gli elementi del do-minio relazionale a tracciare un unico percorso di collegamento conuno qualsiasi degli elementi del codominio. Questo vincolo imponequindi l’univocità del legame esistente tra un elemento del dominioed uno del codominio.

Il vincolo di univocità può essere definito nel modo seguente.

Definizione 4.1.1. Dati gli insiemi X e Y ed una relazione f ⊆X × Y , diremo che f è univoca se accade che per ogni elemento diX esiste uno ed uno solo tra gli elementi di Y con il quale x sia inrelazione. In altri termini, non può mai accadere che un elementox sia presente come primo termine in due differenti coppie (x, y1) e(x, y2) senza che si abbia y1 = y2. In simboli:

∀x ∈ X ∀y1, y2 ∈ Y xfy1 ∧ xfy2 ⇔ y1 = y2. (4.1)

Per ottenere un’applicazione (o funzione) è necessario però intro-durre una seconda restrizione nei confronti del dominio della relazio-ne, e cioè quello che stabilisce l’esaustività della relazione. L’esausti-vità della relazione vincola ogni elemento del dominio a stabilire unlegame con qualche elemento del codominio, indipendentemente dalfatto che diversi elementi del dominio possano comunque mandarecollegamenti allo stesso elemento del codominio dell’applicazione.

Il vincolo di esaustività può essere definito nel modo seguente.

Definizione 4.1.2. Dati gli insiemi X e Y ed una relazione f ⊆X × Y , diremo che f è esaustiva se accade che per ogni elemento diX esiste un qualche elemento di Y con il quale x sia in relazione. Insimboli:

∀x ∈ X ∃y ∈ Y | xfy. (4.2)

I due vincoli su indicati ci permettono, congiuntamente, di fornirela definizione più generale di un’applicazione.

Definizione 4.1.3. Si indica con il termine applicazione (o funzione)una relazione che sia al contempo esaustiva ed univoca. In simboli:

∀x ∈ X ∃! y ∈ Y | xfy. (4.3)

4.1. Restrizione di una relazione 215

Il simbolo ∃! rappresenta l’univocità della funzione e va letto come:"esiste un solo...".

Esempio 4.1.1. Consideriamo un insieme universo Ω e la collezioneP(Ω) dei suoi sottoinsiemi. Chiaramente, l’operazione che associa adogni sottoinsieme ω ⊆ Ω il suo complemento ωc ⊆ Ω rappresenta unafunzione dall’insieme P(Ω) delle parti di Ω in se stesso, in quantoil complemento di ogni sottoinsieme di Ω esiste ed è unico in P(Ω).Consideriamo ad esempio l’insieme P(Ω) già utilizzato nell’esercizio2.3.5.

a,b,c a,b,c

a,b a,c b,c a,b a,c b,c

a b c a b c

∅ ∅

f : ω⊆Ω ωc⊆Ω

Figura 4.1: Funzione di complementazione insiemistica.

Se adesso associamo a ciascun sottoinsieme il proprio complemen-to in P(Ω) possiamo verificare che tale associazione genera una fun-zione che indichiamo generalmente con il termine complementazione.

Nella figura 4.1 viene rappresentato il processo che porta alla co-stituzione della funzione di complementazione insiemistica all’internodell’insieme potenza P(Ω).

Dalle precedenti definizioni 4.1.1 e 4.1.2 discende la definizioneche segue.

216 4. Le funzioni

Definizione 4.1.4. Sia R ⊆ X × Y una relazione binaria; diremoche R è un’applicazione in X × Y se, e solo se,

R R−1 ⊆ Y ∧ R−1 R ⊇ X . (4.4)

Esercizio 4.1.1. Sia data la seguente rappresentazione booleanadella relazione R ⊆ X × Y :

‖rij‖ =

∥∥∥∥∥∥∥∥

0 0 1 00 1 0 00 1 0 01 0 0 0

∥∥∥∥∥∥∥∥

.

Si verifichi se la relazione sia oppure no un’applicazione.Soluzione:

Affinché la relazione sia conforme con ciò che è stato esposto nelladefinizione 4.4 è necessario che ciascuna riga della matrice abbia al piùun solo valore 1, in quanto ogni elemento del dominio non può esserein relazione con più di un elemento del codominio. Inoltre, poichétutti gli elementi del dominio debbono essere in corrispondenza conqualche elemento del codominio non potranno mai essere presentirighe composte da soli zeri. Osservando la matrice della relazione sipuò notare come tutti i vincoli siano stati rispettati e, pertanto, larelazione possiede tutte le caratteristiche per poter essere consideratauna funzione f dall’insieme X all’insieme Y .

Esempio 4.1.2. L’espressione "essere il genitore di x" non è unarelazione che dimostri di possedere le proprietà necessarie a caratte-rizzarla come una relazione funzionale. Se però prendessimo in con-siderazione la relazione che associa ad ogni individuo la propria ma-dre naturale ci accorgeremmo che, in questa circostanza, la relazionepossiede tutti i requisiti per essere di fatto una funzione, poiché tutti

gli individui posseggono una madre naturale (esaustività), e nessun

individuo possiede più di una madre naturale (univocità).

Definizione 4.1.5. Siano dati gli insiemi X e Y ed una funzione f .Chiameremo dominio di f , e lo indicheremo con Dom(f), l’insiemedi elementi di X a partire dai quali ha origine la funzione f . Questadefinizione ricalca quella fornita per l’insieme di definizione di una

4.1. Restrizione di una relazione 217

relazione. Va però tenuto presente che le funzioni sono soggette alvincolo di esaustività, dal quale si deduce che deve essere sempre verala relazione:

X = Dom(f).

Definizione 4.1.6. Siano dati gli insiemi X e Y ed una funzione f .Chiameremo codominio di f , e lo indicheremo con Cod(f), l’insiemedi tutti gli elementi di Y , alcuni dei quali siano in corrispondenza congli elementi di X .

Il codominio di una funzione non è quindi differente, in terminiformali, dal codominio di una generica relazione.

Così come abbiamo avuto già modo di verificare nel capitolo pre-cedente dedicato alle relazioni, anche per le funzioni possiamo operarela distinzione tra codominio della funzione e immagine della stessa.Noi sappiamo già dalle relazioni che questi insiemi non coincidononecessariamente. Possiamo adesso presentare la definizione formaledi ciò che viene indicato come immagine di una funzione.

Definizione 4.1.7. Siano dati gli insiemi X e Y ed una funzione f .Chiameremo immagine di f dentro Y , e la indicheremo con Im(f),l’insieme di tutti gli elementi di Y che siano associati secondo f aqualche elemento di X . Formalmente:

f(X) = y ∈ Y | ∃x ∈ X ; y = f(x). (4.5)

L’immagine Im(f) di f è quindi un sottoinsieme del codominio di f ,i cui elementi figurano come seconde componenti delle coppie (x, y)del prodotto cartesiano X×Y . Ciò comporta, in termini insiemistici,che la coppia (x, y) debba appartenere alla funzione f e che y sial’immagine di x. In notazione simbolica:

y = f(x)⇔ (x, y) ∈ f.

Dato un qualsiasi sottoinsieme W ⊆ X , si dirà immagine di Wsecondo f il sottoinsieme Z ⊆ Y tale che sia:

f(W ) = z ∈ Y | ∃w ∈W ; z = f(w).

È importante notare come nella definizione dell’immagine di unafunzione sia necessario fare rimando all’esistenza di un elemento deldominio dal quale la trasformazione f abbia avuto origine.

218 4. Le funzioni

Per rendere evidente la direzione e l’azione di trasformazione ope-rata dalla regola funzionale f sopra l’insieme Y si usa spesso lanotazione:

f : X −→ Y.

Questa notazione indica in maniera implicita che l’applicazione f col-lega gli insiemi X e Y . In letteratura è però riscontrabile un secondotipo di notazione che rende invece più esplicito il ruolo della regoladi trasformazione f nel determinare l’insieme f(X) ⊆ Y a parti-re dagli elementi dell’insieme X . Quanto detto viene rappresentatograficamente nel modo seguente:

Xf(·)−−−→ Y.

In generale noi diciamo che l’elemento y ∈ Y è immagine secon-do f dell’elemento x ∈ X , e indichiamo questa affermazione conl’espressione simbolica:

y = f(x).

Nella ricerca sperimentale l’insieme X viene spesso indicato comevariabile indipendente ed i suoi elementi x come argomenti della fun-zione f . L’insieme Y viene invece indicato come variabile dipendente

ed i suoi elementi y come valori della funzione f .Sulla base delle definizioni fornite, una funzione costituisce una strut-tura insiemistica formata da tre insiemi 〈Dom(f), Cod(f), Im(f)〉 :un insieme X di partenza, un insieme Y di arrivo ed un sottoinsie-me Im(f) ⊆ Cod(f) generato dalla regola di trasformazione f chepermetta di collegare ogni elemento di X ad uno ed uno solo deglielementi di Y. Con il variare degli insiemi Dom(f) e Cod(f) può ac-cadere che l’immagine Im(f) della funzione cambi anche se la regoladi generazione di f non abbia subito alcuna modifica. Rimane inoltreaperta la possibilità che regole di generazione diverse f e g generinoimmagini Im(f) e Im(g) tra loro identiche sotto opportuni insiemiDom(f), Cod(f), Dom(g) e Cod(g).

Esempio 4.1.3. Consideriamo una prima funzione f : N −→ N. Ri-chiamando l’espressione esposta nella 2.3 a pagine 71 otteniamo latrasformazione f(x) = 2x + 1. Noi sappiamo che questa regola ge-nera l’insieme dei numeri naturali dispari contenuti in N. Prendiamoadesso come punto di riferimento una seconda funzione g : N −→ N

4.1. Restrizione di una relazione 219

la cui regola di generazione sia la seguente: g(x) = 4x2−12x−1 . Questa

seconda funzione può essere considerata uguale alla prima. Possia-mo difatti notare che il dominio della funzione f coincide con il do-minio della funzione g, si ha cioè: Dom(f) = Dom(g); allo stessomodo Cod(f) = Cod(g) e l’immagine di f coincide con l’immaginedi g; sicché: Im(f) = Im(g). Solo in questa circostanza le funzio-ni f e g risulteranno indistinguibili e risulterà vera l’uguaglianza:〈N,N, f〉 = 〈N,N, g〉. Ciò che appare evidente è che sebbene le regoledi trasformazione che definiscono f e g siano diverse, le funzioni risul-tano essere identiche. Se sviluppiamo la regola relativa alla funzioneg otteniamo la seguente uguaglianza:

(4x2 − 1)

(2x− 1)=

(2x+ 1)(2x− 1)

(2x− 1)

= (2x+ 1)(2x− 1)

(2x− 1)

= (2x+ 1).

In generale, possiamo affermare che la regola di trasformazione checaratterizza ogni singola funzione non è necessariamente unica. Adesempio, sussiste un’altra regola funzionale che restituisce la stessafunzione delle regole f e g: tale regola è h(x) = 4x2−1

2x+1 + 2.Se prendiamo in considerazione l’insieme X = 0, 1, 2, 3, 4, 5, 6, 7

applicando le regole funzionali f e g otteniamo la corrispondenzapresentata in tabella 4.1.

x 0 1 2 3 4 5 6 7f(x) = 2x+ 1 1 3 5 7 9 11 13 15

g(x) = (4x2−1)(2x−1) 1 3 5 7 9 11 13 15

Tabella 4.1: Tabella relativa alle funzioni f e g dell’esempio 4.1.3.

Verifichiamo adesso la regola f . Quando la variabile x avrà comeargomento il valore 0 la funzione restituirà il valore 2(0) + 1 = 1.Quando invece la variabile x avrà come argomento il valore 1 la fun-zione restituirà il valore 2(1) + 1 = 3 e così via. Allo stesso modo

220 4. Le funzioni

possiamo verificare che la funzione g restituisce la medesima imma-gine di f . Quando la variabile x assumerà come argomento il valore

0 la trasformazione restituira il valore (4(02)−1)(2(0)−1) = 1. Se invece la va-

riabile x avrà come argomento il valore 1 la trasformazione restituirà

il valore (4(12)−1)(2(1)−1) = 3 e così via.

Rappresentazione grafica di un’applicazione Così co-me accade per le relazioni ordinarie, anche per le funzioni si dispone distrumenti in grado di rappresentarle in forma grafica. Naturalmente,sarà sempre possibile trattare una funzione anche in forma tabellare.L’insieme delle coppie (x, f(x)), in analogia con le relazioni, costi-tuisce un sottoinsieme del prodotto cartesiano X × Y , ed anche inquesta circostanza l’insieme delle coppie viene identificato con il ter-mine grafico della funzione f . In notazione simbolica il grafico di unafunzione viene descritto con l’insieme:

Gf = (x, y) ∈#X,Y | x ∈ X, y = f(x).

Esempio 4.1.4. Consideriamo adesso la funzione f = (1,2), (2,3),(3,4), (4,5), (5,6), (6,7). Facilmente si intuisce che la regola associa-ta alla funzione consiste nell’incrementare il valore numerico di unaunità; sicchè: y = x + 1. La regola può essere rappresentata nellaseguente maniera:

Xy=x+1−−−−→ Y.

Se volessimo codificare questa funzione in forma tabellare dovremmoutilizzare una struttura grafica che rappresenti nella prima riga glielementi appartenenti al dominio della funzione ed in seconda riga glielementi che invece appartengono al codominio della funzione, cosìcome viene esposto nella tabella 4.2.

X 1 2 3 4 5 6Y 2 3 4 5 6 7

Tabella 4.2: Tabella relativa alla funzione dell’esempio 4.1.4.

La rappresentazione insiemistica realizza invece una collezione diarchi che collegano gli elementi del dominio a quelli del codominio.In questo tipo di rappresentazioni grafiche appare evidente come a

4.1. Restrizione di una relazione 221

ciascun elemento del dominio sia associato un unico elemento delcodominio.

La funzione f(x) = x+1, ad esempio, avrà come rappresentazioneinsiemistica la struttura grafica delle connessioni presentata in figura4.2.

1 2 3

4 5 6

X

f

2 3 4

5 6 7

Y

Figura 4.2: Funzione tra gli insiemi X e Y dell’esempio 4.1.4.

Una terza maniera di rappresentare le funzioni riguarda l’uso deidigrafi. In questo caso gli elementi appartenenti al dominio dellafunzione verranno disposti nella parte sinistra del digrafo mentre glielementi interni al codominio verranno allineati nella parte destra.Naturalmente dall’insieme dei nodi sinistri potrà partire un solo arcodi collegamento con qualche nodo disposto alla destra del digrafo,come esemplificato nella figura 4.3.

• •• •• •• •• •

X Y

Figura 4.3: Rappresentazione con digrafo di una funzione.