Introduzione euristica degli insiemi - mi.imati.cnr.italberto/mnB19rTINS.pdf · Al precedente...

MATeXp – Nozioni di base

Capitolo B19:

Introduzione euristica degli insiemi

Contenuti delle sezioni

a. Oltre gli insiemi procedurali p.2 b. Insiemi definiti da proprieta p.4 c. Operazioni sugli insiemi

p.8 d. Relazioni sugli insiemi p.13 e. Funzioni p.16 f. Cardinalita degli insiemi p.19 g. Numeri

transfiniti p.23 h. Composizioni su famiglie di insiemi p.29

B19:0.01 Questo capitolo e dedicato ad una descrizione del ruolo che ha in generale in matematica

la nozione di insieme e ad una panoramica espressa con lo stile chiamato “naif” delle nozioni basilari

della teoria degli insiemi.

Per dare fondamenti formalmente robusti a gran parte della matematica si rivela necessaria una qualche

impostazione assiomatica della teoria degli insiemi, ma una tale formalizzazione, in questo stadio

dell’esposizione e giudicato troppo impegnativa. La presentazione formale della teoria degli insiemi

sara affrontata con l’adeguato rigore nel cap. B65: . Questo richiedera che siano discusse anche alcune

ineludibili questioni sui fondamenti.

Nelle pagine che seguono si adotta invece un tono piu intuitivo.

All’inizio si sostiene l’opportunita di essere in grado di disporre una nozione molto versatile di insieme,

in modo che si possa utilizzare il linguaggio di queste entita per trattare una vasta gamma di situazioni.

Si vogliono prendere in considerazione entita che chiamiamo “insiemi definiti su proprieta”, entita che

possano essere individuate come aggregati costituiti da tutti e soli gli oggetti (membri) che godono di

proprieta specifiche.

Quali possano essere queste proprieta si rinuncia a specificarlo in modo preciso e comprensivo; ci

si limita a chiedere che le proprieta dei membri di un insieme si possano tenere sotto controllo in

modo sufficientemente chiaro e condivisibile. Tra gli insiemi definiti su proprieta, chiaramente, vanno

annoverati insiemi espliciti e gli insiemi procedurali.

Per altri insiemi e per le relative proprieta ci si limita a fornire degli esempi.

Successivamente vengono introdotte le operazioni su questi insiemi definendole mediante opportune

composizioni delle corrispondenti proprieta. Si passa poi a trattare le relazioni e le funzioni tra insiemi

e, mediante la nozione di famiglia di insiemi, si introducono le generalizzazioni infinitistiche delle

operazioni e delle relazioni.

Vengono inoltre presentati i principali risultati sopra la cardinalita degli insiemi e da ultimo vengono

introdotti i numeri transfiniti.

2014-02-07 B19: Introduzione euristica degli insiemi 1

Alberto Marini

B19:a. Oltre gli insiemi procedurali

B19:a.01 Dopo aver definiti e trattati costruttivamente gli insiemi finiti (B11: etc.) ed i procedurali

(B18: etc.), si sente la necessita di ampliare la gamma degli insiemi, nella convinzione, derivata dalla

storia, che tali entita possano costituire strumenti di primaria utilita per lo sviluppo della matematica e

di tutte le sue applicazioni. In effetti si individuano entita che presentano alcune caratteristiche posse-

dute anche dagli insiemi finiti e dai procedurali le quali risultano palesemente utili per il perseguimento

degli obiettivi delle attivita matematiche. Si dimostra tuttavia che molte di queste entita specifiche

non possono essere generati da una MSPG.

Molteplici problemi richiedono che la matematica sviluppi strumenti teorici e computazionali che su-

perino le limitazioni associate agli insiemi finiti e procedurali. Per trattare questi temi nel modo piu

aderente alle richieste di rigore e di consequenzialita logica della matematica e necessario dare a questa

disciplina delle basi logicamente solide.

Serve un apparato formale che oggi puo essere scelto tra vari disponibili; il primo proposto all’inizio

del 1900 e piu frequentemente adottato viene chiamato “teoria assiomatica degli insiemi”.

Questi apparati formali risultano piuttosto impegnativi in quanto richiedono nozioni afferenti alla

logica matematica o a campi limitrofi che si devono affrontare ad un rilevante livello di generalita e

di astrazione; molti, soprattutto se interessati principalmente a determinate applicazioni, potrebbero

giudicare questi formalismi insufficientemente motivati e troppo distanti dai loro scopi ultimi.

Riteniamo dunque piu conveniente posticipare (v. B65:) l’esposizione dell’apparato formale piu chiam-

ato, in quanto richiede nozioni di logica matematica tutt’altro che banali e che riteniamo piu conve-

niente esporre in modo dettagliato.

Qui invece ci proponiamo di ampliare la nozione di insieme ad un livello piu discorsivo e in via fiducia-

ria, cioe utilizzando argomentazioni piuttosto intuitive che possono essere ragionevolmente condivise,

garantendo che piu oltre, quando ci saremo impadroniti delle tecniche opportune potranno essere

sviluppate in modo soddisfacente.

Con questo modo di procedere si vogliono rendere subito disponibili termini, notazioni, risultati e

schemi mentali non ancora compiutamente giustificati, ma in grado di far procedere l’esposizione con

un linguaggio sufficientemente comprensibile. In tal modo viene anticipata la trattazione di varie

nozioni che rivestono ampio interesse, in quanto strumenti concettuali, operativi e lessicali in grado di

ampliare la visione della matematica e del suo potenziale applicativo.

B19:a.02 La caratteristica cruciale degli insiemi usati in matematica consiste nella relazione fra gli

elementi che costituiscono un insieme e l’insieme stesso; questa relazione viene chiamata appartenenza.

Nella teoria assiomatica degli insiemi essa viene considerata esclusivamente sul piano formale. Per

essa sono avanzate richieste formali che devono risultare non contradditorie e in grado di condurre

a tutta una serie di risultati sui quali si possano fondare gran parte degli sviluppi della matematica

consolidata nel passato. Questi pregi della teoria assiomatica, come vedremo, sono tutt’altro che facili

da riconoscere.

In presentazioni piu discorsive l’appartenenza viene introdotta con una metafora intitiva e fornendo

una varieta di esempi che vogliono essere condivisibili sul piano delle argomentazioni colloquiali e che

vogliono fornire idee sulla utilita di questa relazione

B19:a.03 Una metafora di insieme molto intuitiva ed ampiamente utilizzata nelle esposizioni degli

insiemi che rinunciano di affrontare la teoria assiomatica ricorre alla nozione materiale di contenitore.

2 B19: Introduzione euristica degli insiemi 2014-02-07


Si presenta come insieme ogni entita che si possa assimilare ad un contenitore idealizzato il quale ha lo

scopo di raccogliere degli oggetti formali che si sono definiti secondo modalita proposte che intendono

risultare condivisibili.

Ogni oggetto x che puo servire per argomentazioni per fini matematici o per elaborazioni, eventual-

mente assieme ad altri oggetti tendenzialmente simili, puo considerarsi “contenuto” in una entita S

cui descrittivamente si attribuisce il ruolo del “contenitore S”.

In tal caso x viene chiamato elemento di S e questa situazione si esprime dicendo che che x appartiene

ad S e scrivendo simbolicamente x ∈ S . Equivalentemente si dice che x appartiene ad S e che S

contiene x; quest’ultima affermazione puo essere rappresentata concisamente dalla formula S ∋ x . Va

dichiarato che ogni contenitore S si intende distinto da ogni suo possibile contenuto x.

Al precedente schema si possono ricondurre gli insiemi finiti e gli insiemi procedurali. Per un insieme

finito S l’enunciato x ∈ S traduce la possibilita di trovare l’oggetto x in una lista finita che rappresenta

S, possibilita garantita dalla disponibilita effettiva di un elenco o da una regola che consenta (almeno

in linea di principio) di costruire un tale elenco.

Se S e un insieme procedurale, x ∈ S corrisponde alla possibilita di trovare x in una lista illimitata

generata da una MSPG. Questa possibilita nel caso S sia ricorsivo e garantita da un algoritmo gen-

erativo o da un algoritmo in grado di decidere l’appartenenza ad S di un dato x. Il caso di insieme

ricorsivamente enumerabile non ricorsivo viene invece tacitamente considerato trascurabile.

Come vedremo, si incontra una grande varieta di insiemi che non possono essere generati da alcuna

MSPG i quali, ma che vengono intesi come contenitori e risultano di grande utilita per gli sviluppi

della matematica e delle elaborazioni. Sara anche evidente che la possibilita di argomentare sopra tali

insiemi nelle esposizioni consente di avere discorsi piu semplicemente formulabili e leggibili.

B19:a.04 Qualche altra considerazione sugli ”insiemi in generale”, non costruibili, cioe tanto capienti

da contenere piu elementi di quanti possono essere messi in biiezione con gli elementi di un insieme

procedurale, ovvero di quanti possono essere rappresentati da una lista illimitata.

Un cruciale esempio di queste entita e l’insieme dei punti della retta reale (B42:); andando piu oltre si

individuano insiemi contenenti piu elementi di quanti possono essere messi in biiezione con i punti di

una retta: in particolare l’insieme dei sottoinsiemi della retta reale.

Vedremo anche che questo processo di ampliamento della esemplificazione degli insiemi puo essere

proseguito illimitatamente.

Per questi insiemi in generale non si puo proporre alcun tipo di costruzione effettiva (finita o potenzial-

mente ottenibile con l’uso di risorse illimitate) dei suoi singoli elementi: una tale costruzione, secondo

la cosiddetta congettura di Church-Turing (C21:) si puo ottenere solo con qualche genere di procedura.

Lo studio degli insiemi in generale ha per fine la determinazione di loro proprieta e, come vedremo, si

serve di attivita deduttive consistenti nella dichiarazione di enunciati rappresentati da stringhe finite

la cui consistenza si presume condivisibile e in successive trasformazioni degli enunciati disponibili,

trasformazioni consentite da regole di inferenza anch’esse esprimibili finitamente.

A questo punto si intravvede un conflitto fra l’uso degli insiemi in generale e la esigenza di costruibilita

degli insiemi degli oggetti sui quali si basano le elaborazioni effettive e con i quali si eseguono calcoli

effettivi. Questo conflitto merita di essere approfondito da parte degli studiosi che non siano assorbiti

da esigenze applicative non dilazionabili.

A coloro che sono interessati primariamente ai calcoli effettivi e alle loro applicazioni va segnalato

che le proprieta trovate attraverso deduzioni formali per gli insiemi astrattamente intesi, come dice la

storia della scienza e della tecnologia, ampliano in misura determinante la possibilita di prospettare e


Alberto Marini

precisare una grande varieta di procedimenti effettivi in grado di fornire soluzioni costruibili di problemi

concreti; queste soluzioni sono ottenibili e descrivibili con relativa semplicita solo ricorrendo a quelli

che abbiamo chiamati insiemi in generale.

B19:b. Insiemi definiti da proprieta

B19:b.01 Trattiamo dunque entita che possono estendere la casistica degli insiemi forniti dalla metafora

dei contenitori di :a.03. Si tratta di entita alle quali si possono far appartenere oggetti introdotti con

definizioni rigorose o almeno ampiamente accettate, ove l’appartenenza corrisponde al fatto che questi

oggetti soddisfano proprieta definite anch’esse in modo rigoroso o almeno ampiamente accettato, ove

il suddetto soddisfacimento viene assicurato da argomentazioni solide per coerenza e consequenzialita

logica o almeno tali da essere ampiamente accettate.

Queste entita le chiamiamo insiemi definiti su proprieta; nelle prossime pagine per essi useremo anche

l’abbreviazione insiemi -Propr.

Qui chiediamo che un insieme -Propr S trovi collocazione entro un insieme ambiente U introdotto in

modo rigoroso o almeno attraverso argomenti ampiamente accettati e che sia caratterizzata da una

proprieta P che riguarda elementi di U e che a sua volta deve essere definita in modo ben fondato o

almeno ampiamente accettato. La collocabilita di S in U consiste nella richiesta che per ciascuno degli

oggetti che possono considerarsi elementi di U sia sensato chiedersi se soddisfa o meno la proprieta P.

B19:b.02 Le proprieta che definiscono insiemi sono chiamate anche relazioni.

Come vedremo le entita che si possono considerare insiemi -Propr consentono di soddisfare la quasi

totalita delle esigenze di sviluppo della matematica. Inoltre l’impostazione assiomatica degli insiemi

consente di dare una base rigorosa anche a tutti gli insiemi -Propr introdotti in precedenza mediante

esigenze espresse intuitivamente o ampiamente accettate. Quindi e lecito prospettare che i risultati

che qui attribuiremo agli insiemi -Propr possono essere considerati validi per gli insiemi in generale.

Questo consente che nelle pagine nelle quali cade l’interesse a puntualizzare la concezione degli interi

in esame, si parli semplicemente di insiemi, tacendo la limitazione “definiti su proprieta”.

Conviene introdurre qui anche il termine insieme astratto. Questo nome viene utilizzato per insiemi

definiti da proprieta o trattati assiomaticamente che sono individuati senza attribuire loro alcuna

caratteristica individuale: le relazioni trovate per tali insiemi possono essere dichiarate “proprieta

degli insiemi astratti” .

B19:b.03 Premettiamo una introduzione del termine formule ben formate, abbreviato con la sigla wff

acronimo del termine inglese well formed formulas.

Va subito detto che questo termine lo definiremo precisamente in C14: avvalendoci delle tecniche sui

linguaggi formali.

In effetti qui non vogliamo limitare la definizione con delimitazioni precise e tendenzialmente esauri-

enti per i possibili ambienti U e per le possibili proprieta P. Vogliamo semplicemente proporre una

definizione che possa essere ampiamente condivisa in quanto ragionevolmente accettabile. Anche

l’ambiente U si chiede sia un insieme definito mediante una proprieta la cui formulazione sia ampia-

mente accettabile; in particolare sono da accettare ambienti procedurali, mentre in mancanza di una

procedura generatrice sono auspicabili insiemi ambiente definiti da proprieta accettate senza riserve.



Si tratta di stringhe che soddisfano regole lessicali e sintattiche definite con precisione e che sono

interpretabili mediante regole semantiche anch’esse sostanzialmente precise.

Esempi di wff sono le formule utilizzate nell’algebra elementare, nella combinatorica e nell’algoritmica

delle configurazioni discrete, nella trigonometria, nell’analisi infinitesimale, nella geometria analitica,

nella fisica matematica, nelle tecnologie, nell’economia e nei molteplici modelli matematici delle scienze

naturali, sociali e comportamentali.

B19:b.04 Alcuni esempi di insieme -Propr.

Si possono definire insiemi di numeri interi naturali che soddisfano un’equazione della forma P (x) = 0

con x variabile in N e P (x) espressione ben formata nella quale compaiono la variabile incognita x,

costanti intere, operazioni aritmetiche e coppie di parentesi coniugate aventi il ruolo di delimitatori di

sottoespressioni.

Altre proprieta concernenti incognite variabili in N possono essere espresse con algoritmi o con MSPG.

Quindi gli insiemi procedurali, cioe tutti gli insiemi che sono stati definiti costruttivamente, si possono

considerare insiemi definiti su proprieta.

La gamma delle proprieta che consentono di individuare gli insiemi -Propr dovrebbe essere individuata

da un linguaggio di espressioni ciascuna delle quali in grado di formulare una proprieta. A questo

punto dell’esposizione ci limitiamo a rinviare questa questione (v. B65:) ed a procedere euristicamente

considerando insiemi -Propr caratterizzati da proprieta ragionevolmente condivisibili. In tal modo si

rinuncia a delineare precisi confini della gamma delle proprieta utilizzabili in matematica e ci si limita

ad esempi per i quali si invoca l’ampia condivisibilita.

B19:b.05 Sul piano pratico e ragionevole rivolgere maggiore attenzione agli insiemi -Propr che fanno

meglio intravvedere sviluppi ricchi di risultati.

La individuazione di molti insiemi -Propr interessanti, naturalmente, si basa spesso sopra la conoscenza

di un sistema di risultati coerenti della tradizione matematica, sistema che in particolare sia esente dal

peggiore dei sospetti in matematica, cioe che possa condurre a una situazione di contradditorieta.

Nella individuazione di un insieme -Propr potrebbero essere utili anche delle congetture supportate da

dimostrazioni incomplete o da risultati ottenuti con sperimentazioni e simulazioni condotte mediante

apparecchiature per l’elaborazione automatica dei dati. Ovviamente sara richiesto di essersi accertati

con cura della fondatezza delle congetture e dell’attendibilita dei risultati sperimentali. Quest’ultima

dovrebbe essere assicurata da una attenta critica dei procedimenti utilizzati. Particolarmente delicata

e l’attendibilita di risultati ottenuti mediante calcoli approssimati o attraverso elaborazioni statistiche.

B19:b.06 L’insieme ottenuto con la selezione potenziale derivabile dalla proprieta P applicabile agli

elementi dell’ambiente U si denota con:

(1) {x ∈ U P(x)} ;

questa espressione va letta “insieme degli oggetti x appartenenti all’insieme U tali da verificare la

proprieta P(x)” , oppure “insieme degli oggetti di U tali da rendere vero l’enunciato P(x)”. In parti-

colare P(x) puo costituire un’equazione in una variabile x o un sistema di equazioni in una sequenza

di variabili x.

Piu avanti incontreremo altri schemi di formule atte ad individuare insiemi in generale.

Un’altra variante della formulazione (1) riguarda la individuazione degli oggetti ottenibili dai diversi

elementi v di un insieme (-Propr) V con una trasformazione T che a partire da ciascuno di tali v

individua un elemento x che si denota con T(v). Questi elementi di U, e solo questi, sono caratterizzati


Alberto Marini

dalla proprieta di essere ottenibili come risultati della trasformazione T a partire da un elemento di

V. Questa proprieta svolge il ruolo della P(x) vista in precedenza e quindi gli oggetti T(v) al variare

di v costituiscono un insieme -Propr. Questa entita si denota con

(2) {x ∈ V :| T(x)} ,

formula da leggere “insieme ottenuto con la trasformazione T operata sopra gli elementi di un insieme

precedentemente definito V” . Per un’espressione della forma precedente, mentre viene definito V,

potrebbe costituire un problema una conveniente individuazione dell’ambiente nel quale si collocano i

risultati della trasformazione T.

Le espressioni insiemistiche dei tipi precedenti sono largamente usate. In particolare molti insiemi

procedurali che rivestono un interesse specifico, sostanzialmente molti insiemi ricorsivi, si esprimono

piu significativamente con una formula che ricorre a proprieta secondo uno degli schemi precedenti,

piuttosto che mediante una MSPG.

B19:b.07 Naturalmente si dovrebbe porre il problema della precisa individuazione delle proprieta

ammissibili.

Questo problema ha condotto alla piu cruciale discussione sui fondamenti della matematica tra il 1980

e 1l 1910. Si e giunti a concludere che ci si deve basare su teoria puramente simbolica. .......

E lecito utilizzare un insieme -Propr fin tanto che si abbia un buon accordo sulla sua definizione,

ovvero sulla definizione della proprieta che lo caratterizza, ovvero sulla argomentazione che consente

di stabilire se un elemento z ∈ U soddisfa o meno la proprieta.

Quando questi accordi mancano il procedimento entra in crisi e cresce la preoccupazione che l’utilizzo

di questi insiemi -Propr possa condurre a situazioni di contradditorieta.

Delle incertezze e delle difficolta si incontrano soprattutto quando occorre individuare oggetti che non

appartengono ad un insieme proposto come -Propr.

Di fronte a queste questioni si impone il ricorso a strumenti logici piu cogenti, cioe ad una cosiddetta

teoria assiomatica degli insiemi. Anche per una tale teoria si pongono questioni di fondatezza da

affrontare e possibilmente risolvere con strumenti formali, anch’essi afferenti alla logica matematica.

Qui procediamo solo ad un livello intuitivo, ma otterremo risultati uguali a quelli ottenibili con il

rigore della teoria assionmatica degli insiemi. Le asserzioni che otterremo valgono quindi anche per gli

insiemi in generale. In effetti le asserzioni che seguono possono essere lette come enunciati riguardanti

gli insiemi in generale.

B19:b.08 Nella teoria degli insiemi si considerano entita (matematiche) rappresentate da identificatori

o da espressioni simboliche. Gli identificatori sono lettere eventualmente dotate di deponenti, esponenti

o segni diacritici. Le espressioni sono stringhe costituite da identificatori e da segni specifici che devono

costituire delle formule ben formate.

Possono essere enunciate proprieta concernenti singole entita dell’ambiente (cioe loro caratterizzazioni)

o sequenze di entita (cioe relazioni che stabiliscono dei loro vincoli). Anche queste proprieta sono

rappresentate da espressioni che contengono simboli riguardanti entita coinvolte e altre caratterizzazioni

e relazioni richiamate, oltre a segni loro peculiari e che hanno una forma opportuna, cioe sono opportune

wff.

In una espressione che definisce un oggetto matematico, un insieme, una caratterizzazione o una

relazione, o altre entita piu articolate possono comparire lettere di diversi alfabeti il cui complesso

consentiamo possa crescere illimitatamente e costrutti simbolici ottenuti con opportune combinazioni

di lettere, segni delimitatori e segni connettivi adeguatamente introdotti.



Se E ed F sono espressioni opportune, che sul piano lessicale e sintatico soddisfano determinate regole

formali (wff) e che sul piano semantico sono in grado di individuare entita significative, l’enunciato

della forma (E = F) e da ritenersi espressione ben formata e significa che ogni entita rappresentata

dalla espressione E puo essere rappresentata anche dall’espressione F e viceversa.

La negazione del precedente enunciato e espressa dalla scrittura (E = F) .L’enunciato espresso dalla relazione (E = F) viene letto anche affermando che “coincidono l’insieme

degli oggetti che soddisfano E e l’insieme degli oggetti che soddisfano F” .

In una tale affermazione per insieme si intende una entita, che qui genericamente identifichiamo con

la lettera S, suscettibile di comparire in una relazione della forma (x ∈ S) o nella sua negazione

(x ∈ S), dove x e una wff in grado di identificare un oggetto che abbia senso trattare come oggetto di

indagine matematica.

La formula (x ∈ S) si legge “x appartiene ad S”, o equivalentemente “x e elemento di S”, oppure

anche “S contiene x” .

B19:b.09 Alla precedente nozione essenzialmente formale di insieme si possono ricondurre sia la nozione

di insieme finito esprimibile con un elenco di elementi (B11:), sia la nozione di insieme procedurale,

entita determinata da una procedura generatrice, ovvero da una MSPG, che puo operare servendosi di

risorse illimitate (B18:).

In questa definizione di insieme non si e invece posto alcun limite a quella che in termini metaforici

si puo chiamare ”capienza del contenitore”, termine che va riferito all’insieme stesso. Vedremo che la

precedente definizione puo riguardare molte importanti entita che non sono oggetti o insiemi effettiva-

mente costruibili.

B19:b.10 Le proprieta che definiscono gli insiemi sono individuate con wff che, relativamente all’ambito

della teoria in sviluppo, devono potersi valutare come vere o false. Anche sulla loro forma rinviamo al

capitolo B65: e per ora ci limitiamo a chiedere che la loro interpretazione sia condivisibile.

Le lettere che compaiono in una relazione P possono individuare elementi determinati, cio‘e entita

definite in precedenza, oppure possono avere il ruolo di elementi variabili, cioe di elementi le cui caratter-

istiche specifiche restano da determinare. Ogni elemento variabile x nella P potrebbe assumere come

valore un qualsiasi elemento di U: quindi deve “avere senso” proporre la P consentendo che la x possa

assumere tutti gli elementi di U; gli sviluppi della teoria potranno stabilire per quali valori della x la

R e vera e per quali falsa.

Gli elementi variabili di una relazione e le lettere che li denotano, secondo tradizione, sono chiamate

anche elementi arbitrari, elementi generici e argomenti della relazione.

Per segnalare che in una relazione P compaiono le variabili x, y e z usiamo la scrittura P x, y, z .

B19:b.11 Una relazione nella quale compaiono argomenti variabili si dice identita sse essa risulta vera

per tutti i valori che il contesto rende sensato attribuire a tali variabili.

Se P e Q denotano due proprieta, si dice che P implica Q sse Q risulta vera per tutte le scelte di

valori per le variabili che rendono vera la P. L’implicazione della Q da parte della P si esprime con la

formula

(1) P =⇒ Q .

Si dice che P e Q sono proprieta equivalenti sse la P implica la Q e viceversa la Q implica la P. Questa

situazione si caratterizza con la scrittura

(2) P ⇐⇒ Q .


Alberto Marini

Si dice negazione della proprieta P x, y, z la relazione che risulta vera per le terne ⟨x, y, x⟩ per le

quali P x, y, z risulta falsa. Essa si denota con ¬P x, y, z .

B19:b.12 Data una relazione P x, y, z , l’enunciato “per ogni x si ha P x, y, z ” lo consideriamo

la relazione concernente le variabili y e z che risulta vera per tutte e sole le coppie ⟨y, z⟩ tali cheP x, y, z risulta vera per ogni x.

Inoltre l’enunciato “esiste x tale che P x, y, z ” lo consideriamo la relazione concernente le variabili

y e z che risulta vera per tutte e sole le coppie ⟨y, z⟩ tali che esiste almeno un x per il quale P x, y, z

risulta vera.

Ciascuna delle suddette relazioni si potrebbe individuare con una scrittura della forma P ′ y, z .

La negazione dell’enunciato “quale che sia x si ha P” e “esiste x tale che ¬P” . La negazione

dell’enunciato “esiste x tale che si ha P” e “per ogni x si ha ¬P” .

Conviene osservare esplicitamente che alla nozione di esistenza di una entita E x qui richiamata va

attribuita una validita formale che va chiaramente distinta da una validita che puo essere attribuita

ad una realta fisica o spirituale.

B19:b.13 Consideriamo due proprieta P e Q.Conveniamo che l’enunciato “P e Q” sia la proprieta che risulta vera sse lo sono sia la P che la Q.Tale proprieta viene denotata anche con P ∧Q e viene chiamata congiunzione P e Q.Conveniamo invece che l’enunciato “P o Q” sia la proprieta che risulta vera sse lo sono o la P o la Q(o entrambe). Tale proprieta viene denotata anche con P ∨Q. e viene chiamata disgiunzione di P e Q;il connettivo “o” corrisponde al connettivo latino “vel” .

Si osserva che l’enunciato “P ∨Q” equivale a “¬(¬P ∧ ¬Q)”.L’enunciato ¬P ∨Q si abbrevia scrivendo P =⇒ Q ; il segno =⇒ e detto simbolo dell’implicazione.

Questa relazione tra proprieta si trova essere una relazione d’ordine: infatti se si considerano tre

proprieta P, Q ed R si ha

((P =⇒ Q) ∧ (Q =⇒R)) =⇒ (P =⇒R) .

B19:c. Operazioni sugli insiemi

B19:c.01 Procediamo ora ad estendere agli insiemi definiti su proprieta e, fiduciariamente, agli insiemi

tout court le operazioni e le relazioni che sono state introdotte per gli insiemi finiti (B11:d) e per i

procedurali (B18:d). Per l’ampliamento di queste nozioni conviene servirsi delle stesse notazioni usate

in precedenza; in effetti queste notazioni saranno utilizzate anche per la teoria assiomatica e sono da

considerare notazioni standard: in effetti esse sono utilizzate per una grande varieta di sviluppi, anche

in vari ambiti applicativi.

Cessiamo quindi di distinguere fra insiemi definiti su proprieta ed insiemi introdotti assiomaticamente.

In effetti manterremo qualche inciso (-Prprt) per sottolineare che le nozioni consolidate ci consentireb-

bero solo di parlare di insiemi definiti su proprieta.

Nel seguito avremo a che fare con insiemi che denoteremo con lettere cone S, T , U , ... e con le proprieta

atte a caratterizzarli che denoteremo, risp., con PS , PT , PU . Quando servira collocare gli elementi

degli insiemi in ben determinati insiemi ambiente, per questi ultimi useremo identificatori come U e V.



Inoltre useremo una scrittura della forma S ∈ Set per enunciare che con S si denota un insieme.

Discorsivamente si puo essere indotti a dire che con Set si denota l’insieme degli insiemi. Vedremo pero

che se si considera Set come tutti gli altri insiemi si ha l’enunciato Set ∈ Set e che questo porta a

pericolose contraddizioni.

Si puo invece dire che Set costituisce una “classe”, ove tale termine (come vedremo in B65:d) viene

usato per denotare entita piu generali degli insiemi che possono considerarsi contenitori ai quali e

consentito di contenere se stessi.

B19:c.02 Consideriamo due insiemi S e T caratterizzati, risp., dalle proprieta PS e PT .

Si dice che S e sottoinsieme di T sse dalla proprieta PS segue la proprieta PT . Questo equivale ad

affermare che ogni elemento di S e anche elemento di T . cioe che “a ∈ A =⇒ a ∈ B”.

Per enunciare questa situazione scriviamo S ⊆ T .

Con il segno ⊆ abbiamo denotata una entita del genere delle relazioni fra insiemi (v. :d.01). Piu

precisamente la relazione che si denota con ⊆ viene chiamata inclusione tra insiemi.

L’enunciato S ⊆ T si legge anche “S e parte di T” .

Come per gli insiemi procedurali si introduce la relazione essere sottoinsieme proprio e la corrispondente

notazione S ⊂ T ; questa equivale all’enunciato “S ⊆ T ∧ S = T” .

Si dimostra facilmente che il segno “⊆” rappresenta una relazione d’ordine, cioe che valgono le seguenti

proprieta:

∀S ∈ Set S ⊆ S (riflessivita) ;

∀S, T ∈ Set S ⊆ T ∧ T ⊆ S =⇒ S = T (antisimmetria) ;

∀S, T, U ∈ Set S ⊆ T ∧ T ⊆ U =⇒ S ⊆ U (transitivita) .

Come per le altre relazioni d’ordine conviene introdurre la relazione trasposta (o riflessa, o reciproca)

della ⊆ che si denota con ⊇ e la riflessa della ⊂ denotata con ⊃. Se T ⊇ S esprime il fatto che S e

sovrainsieme di S e se T ⊃ S si dice che T e sovrainsieme proprio di S.

Sono utili anche le negazioni delle relazioni precedenti per le quali si usano le notazioni ⊆, ⊂, ⊇ e ⊃.Si dice inoltre che due insiemi diversi S e T sono non confrontabili sse S ⊂ T ∧ T ⊂ S. Tale relazione

tra insiemi si enuncia con la scrittura S T .

Evidentemente la relazione ⊆ e una relazione d’ordine parziale non totale: sono facilmente individuabili

duetti di insiemi non confrontabili come:

{1, 2, 3} e {1, 2, 4} , insiemi finiti;

N e 2Z, insiemi ricorsivi;

gli intervalli [0, 2] e [1, 3] , insiemi con la cardinalita del continuo.

B19:c.03 Siano dati due insiemi S, caratterizzato dalla proprieta PS e T definito mediante la proprieta

PT , collocabili in un insieme ambiente U. Si dice unione di S e T l’insieme degli elementi di U che

soddisfano o la proprieta PS o la PT (senza escludere che le soddisfino entrambe).

Per tale entita useremo la notazione

(1) S ∪ T := {x x ∈ S ∨ x ∈ T} .

Chiaramente si tratta dell’insieme caratterizzato dalla proprieta “PS o PT ” .

Dunque l’unione e un’operazione binaria tra insiemi (-Propr).

Per questa operazione si dimostrano facilmente le seguenti proprieta:

∀S, T ∈ Set S ∪ T = T ∪ S (commutativita);


Alberto Marini

∀S, T, V ∈ Set (S ∪ T ) ∪ V = S ∪ (T ∪ V ) (associativita);

∀S ∈ Set S ∪ S = S (idempotenza).

L’associativita dell’unione consente la scrittura semplificata

∀S, T, V ∈ Set S ∪ T ∪ V := (S ∪ T ) ∪ V = S ∪ (T ∪ V ).

e scritture ottenute per iterazione come la S1 ∪ S2 ∪ S3 ∪ S4 ∪ S5 .

Anche per gli insiemi in generale e utile la scrittura S ∪T per denotare l’unione di S e T e per segnalare

che i due insiemi sono disgiunti.

B19:c.04 Dati due insiemi S, caratterizzato dalla proprieta PS e T definito mediante la proprieta PT ,

si dice intersezione di tali insiemi caratterizzato dalla proprieta “PS e PT ”. Tale entita e dunque un

insieme e si denota con

(1) S ∩ T := {x x ∈ S ∧ x ∈ T} .

Dunque l’intersezione puo considerarsi un’operazione binaria tra insiemi -Propr.


∀S, T ∈ Set S ∩ T = T ∩ S (commutativita);

∀S, T, V ∈ Set (S ∩ T ) ∩ V = S ∩ (T ∩ V ) (associativita);

∀S ∈ Set S ∩ S = S (idempotenza).

L’associativita dell’intersezione consente la scritture semplificata

∀S, T, V ∈ Set S ∩ T ∩ V := (S ∩ T ) ∩ V = S ∩ (T ∩ V )

e scritture ottenute per iterazione come S1 ∩ S2 ∩ ... ∩ Sn .

B19:c.05 Per unione ed intersezione di insiemi si dimostrano facilmente anche le proprieta che seguono.

(1) ∀S, T ⊆ U S ⊆ S ∪ T , S ∩ T ⊆ S

(2) ∀S, T, V ⊆ U S ⊆ T =⇒ S ∪ V ⊆ T ∪ V ∧ S ∩ V ⊆ T ∩ V

(3) ∀S, T, V ⊆ U V ⊆ S ∧ V ⊆ T ⇐⇒ V ⊆ S ∩ T

(4) ∀S, T, V ⊆ U S ⊆ V ∧ T ⊆ V ⇐⇒ S ∪ T ⊆ V

(5) ∀S, T, V ∈ Set (S ∪ T ) ∩ V = (S ∩ V ) ∪ (T ∩ V )

(6) ∀S, T, V ∈ Set (S ∩ T ) ∪ V = (S ∪ V ) ∩ (T ∪ V )

Le due precedenti uguaglianze esprimono le proprieta di distributivita per unione ed intersezione.

B19:c.06 Dati due insiemi S, caratterizzato dalla proprieta PS e T dalla proprieta PT , si dice eliminazione

di T da S l’insieme definito dalla proprieta

“PS e non PT ” .

Tale entita e dunque di un insieme (-Propr) e per essa si usa la notazione

S \ T := {x x ∈ S ∧ x ∈ T} .Anche l’eliminazione puo considerarsi un’operazione binaria tra insiemi (-Propr) e si denota con

(1) S \ T := {x x ∈ S ∧ x ∈ T} .



Puo essere significativo leggere l’espressione S \ T come “insieme S senza T .


∀S, T, V ∈ Set (S \ T ) \ V = (S \ V ) \ T ;

∀S, T, V ∈ Set (S \ T ) \ V = S \ (T ∪ V ) ;

∀S, T, V ∈ Set S \ (T ∩ V ) = (S \ T ) ∪ (S \ V ) .

B19:c.07 Dati due insiemi S, caratterizzato dalla proprieta PS e T dalla proprieta PT , si dice differenza

simmetrica di T da S l’insieme definito dalla proprieta

“PS e non PT oppure PT e non PS”.

Anche tale entita e dunque di un insieme e e per essa si usa la notazione

(1) S ⊖ T := {x x ∈ S ∧ x ∈ T ∨ (x ∈ T ∧ x ∈ S)} .

Anche la differenza simmetrica puo considerarsi un’operazione binaria tra insiemi (-Propr).

Per questa operazione binaria di insiemi si dimostrano le seguenti proprieta:

∀S ∈ Set S ⊖ S = ∅ (nilpotenza);

∀S, T ∈ Set S ⊖ T = T ⊖ S (commutativita);

∀S, T, V ∈ Set (S ⊖ T )⊖ V = (S \ (T ∪V )) ∪ (T \ (V ∪S)) ∪ (V \ (S ∪T )) (associativita).

Nella terza relazione abbiamo fatto uso della notazione ∪ introdotta in :c.03 . La terza relazione

implica anche

∀S, T, V ∈ Set (S ⊖ T )⊖ V = S ⊖ (T ⊖ V ) ,

cioe l’associativita della differenza simmetrica. Da questa proprieta e dalla commutativita della dif-

ferenza simmetrica deriva la possibilita di semplificare le espressioni precedenti scrivendo

∀S, T, V ∈ Set S ⊖ T ⊖ V := S ⊖ (T ⊖ V ) = S(⊖T )⊖ V .

B19:c.08 Si dice insieme delle parti di un insieme S l’insieme i cui elementi sono i sottoinsiemi di S. Esso

viene denotato con P(S) , con SP o anche con 2S . Termini equivalenti ad insieme delle parti di S

sono collezione dei sottoimsiemi di S, booleano di S e potenza di S.

Si incontrano spesso sottocollezioni dell’insieme delle parti di un insieme S. Per la collezione dei sot-

toinsiemi finiti di S useremo le scritture PF (S) o l’equivalente SPF . Per la collezione dei sottoinsiemi

cofiniti di S, cioe dei sottoinsiemi con complementare finito useremo le scritture Pcof (S) e SPcof .

B19:c.09 Dato un insieme ed un ambiente U nel quale si possono collocare gli elementi di S, si dice

insieme complementare di S entro U l’insieme caratterizzato dalla proprieta “inclusione in U e non PS”.

Anche questa entita e un insieme e per essa si usano le notazioni

(1) U(S) := S U := {x ∈ U x ∈ S} .

Fissato l’ambiente U, la trasformazione da S al suo complementare puo considerarsi un’operazione

unaria per i sottoinsiemi (-Propr) di U.

Per la complementazione entro l’ambiente U si dimostrano le seguenti proprieta.

(2) Prop.: ∀S ⊆ U (S U) U = S (la complementazione e una involuzione)

(3) Prop.: ∅ U = U , U U = ∅(4) Prop.: ∀S, T ⊆ U (S ∪ T ) U = S U ∩ T U , (S ∩ T ) U = S U ∪ T U (leggi di De Morgan)

(5) Prop.: ∀S, T ⊆ U T (S) = U(S) ∩ T

(6) Prop.: ∀S, T ⊆ U S ⊆ T ⇐⇒ U(S) ⊇ U(T ) ⇐⇒ S ∪ T = T ⇐⇒ S ∩ T = S


Alberto Marini

(7) Prop.: ∀S, T ⊆ U S ∩ T = ∅ ⇐⇒ S ⊆ U(T )⇐⇒ T ⊆ U(S)

(8) Prop.: ∀S, T ⊆ U S ∪ T = U⇐⇒ U(S) ⊆ T ⇐⇒ U(T ) ⊆ S

Nei brani espositivi nei quali l’ambiente puo essere sottinteso risulta comodo sostituire notazioni come

U(S) ed S U con le ben piu semplici (S) ed S .

Le operazioni di unione, intersezione, eliminazione, differenza simmetrica e complementazione di insiemi

fanno parte delle cosiddette operazioni booleane sugli insiemi.

B19:c.10 Agli insiemi in generale si estende la regola di dualita vista per gli insiemi costruibili.

Si consideri un’espressione ben formata avente come operandi alcuni sottoinsiemi X1, X2, ..., Xn di

un ambiente U, e come operatori ∩, ∪ e U, espressione che individuiamo con la scrittura

(1) E ∩,∪, X1, ..., Xn

e che chiamiamo espressione insiemistica booleana.

Diciamo espressione duale in U di tale E l’espressione ottenibile sostituendo in questa ogni Xi con il suo

complementare in U e scambiando ∩ e ∪; per essa scriviamo, sottintendendo l’ambiente,

(2) E ∩,∪, X1, ..., Xn := E ∪,∩, U(X1), ..., U(Xn)

(3) Prop.: Il complementare in U del sottoinsieme di U fornito da una qualsiasi espressione insiemistica

booleana Y := E ∩,∪, X1, ..., Xn si ottiene come

U(Y ) = E ∩,∪, X1, ..., Xn .

(4) Prop.: Consideriamo due espressioni insiemistiche booleane

E ∩,∪, X1, ..., Xn e F ∩,∪, X1, ..., Xn .

Se esse undividuano lo stesso insieme Y ⊆ U, allora le rispettive espressioni duali forniscono il comple-

mentare di Y , ovvero

(5) E ∩,∪, X1, ..., Xn = F ∩,∪, X1, ..., Xn =⇒ E ∩,∪, X1, ..., Xn = F ∩,∪, X1, ..., Xn .

B19:c.11 Consideriamo alcuni oggetti matematici ai ed alcuni insiemi Si per gli interi i = 1, 2, ...n.

Si dice coppia (ordinata) costituita da a1 ed a2 la sequenza

(1) ⟨a1, a2⟩ := {a1, {a1, a2}} .

Evidentemente questo oggetto e diverso da ⟨a2, a1⟩ sse a1 = a2, dato che ⟨a2, a1⟩ := {a2, {a1, a2}}; siosserva anche che, ovviamente, ciascuna di queste coppie e diversa dal doppietto {a1, a2}.Si definisce prodotto cartesiano di S1 ed S2 l’insieme delle coppie la cui prima componente appartiene

ad S1 e la seconda ad S2:

(2) S1 × S2 := {⟨a1, a2⟩ a1 ∈ S1 ∧ a2 ∈ S2} .

Anche il prodotto cartesiano e un’operazione binaria tra insiemi -Propr.

La composizione prodotto cartesiano si puo estendere a sequenze costituite da piu di due componenti.

Sia n ∈ N; introduciamo ⟨a1, ..., an⟩ n-upla (ordinata) o sequenza costituita accostando secondo un’ordineben definito gli oggetti a1, a2, ..., an.

S1 × ...× Sn := {⟨a1, ..., an⟩ ai ∈ Si ∀i ∈ {, n}} .

Se S1 = ... = Sn si ha la potenza cartesiana n-esima di S1 che si puo indicare con S1×n o piu semplicemente

con S1n.



B19:c.12 Sono particolarmente importanti i prodotti cartesiani, ed ancor pou importanti le potenze

cartesiane, di insiemi di base come l’insieme dei naturali N, l’insieme degli interi Z, l’insiem dei razionali

Q e l’insieme dei numeri reali R e l’insieme A∗ delle stringhe sopra un alfabeto A.

B19:d. Relazioni sugli insiemi

B19:d.01 Una relazione R su n variabili x1, x2,...,xn le quali si possono ritenere correre, risp., sugli

insiemi X1, X2,...,Xn si puo considerare un sottoinsieme del prodotto cartesiano X1 ×X2 × · · · ×Xn.

Si puo dunque scrivere

(1) R x1, x2, ..., xn ⊆ X1 ×X2 × · · · ×Xn .

Una relazione della forma precedente viene chiamata relazione n-aria.

La negazione della precedente relazione R e data da

(2) ¬R = X1 ×X2 × ...×Xn \ R ;

anch’essa e una relazione n-aria.

Per descrivere la situazione espressa dall’enunciato ⟨x1, x2, ..., xn⟩ ∈ R si dice che per in corrispon-

denza della la n-upla ⟨x1, x2, ..., xn⟩ la relazione R e vera, oppure che la relazione R e resa valida dalla

la n-upla ⟨x1, x2, ..., xn⟩ .

B19:d.02 La gran parte delle considerazioni generali sopra le relazioni riguardano quelle su due argo-

menti, cioe le relazioni binarie.

Infatti si consideri, ad esempio, una relazione ternaria R x, y, z . La proprieta “quale che sia x :

R x, y, z ” definisce la relazione binaria entro y e z vera sse R x, y, z e vera per ogni valore di x.

Inoltre la proprieta “esiste x tale che R x, y, z ” definisce la relazione binaria entro y e z vera sse

R x, y, z e vera per almeno un valore di x.

Useremo la notazione Rel per denotare la classe delle relazioni binarie.

Osserviamo anche che potremmo concentrarci sulle relazioni entro un unico insieme. Infatti una

relazione R contenuta in un prodotto cartesiano X × Y si puo considerare sottoinsieme di

(X ∪ Y )× (X ∪ Y ) . Ovviamente questo secondo punto di vista puo risultare svantaggioso rispetto al

primo in quanto meno focalizzato.

Viceversa talora puo esserci qualche vantaggio a sostituire lo studio di una R ⊆ X × Y con X e Y

comprendenti elementi comuni attraverso l’introduzione di un insieme Y ′ privo di elementi in comune

con X, cioe tale che Y ′♢X e tale che esista una biiezione β ∈ {Y ▹−−◃Y ′}, procedendo all’esame della

relazione R′ := { ⟨x, y⟩ ∈ X × Y :| ⟨x, β(y)⟩ } .Si dice identita o relazione ovvia su X la relazione

(1) IdX := {x ∈ X :| ⟨x, x⟩ } .

Questa relazione viene detta anche diagonale di X × X e conseguentemente viene denotata con ∆X .

Quando si puo considerare sottinteso che si parla dell’ambiente X essa viene spesso individuata con il

segno di uguaglianza “=”.

Chiamiamo diversita su X la negazione della relazione precedente

(2) X ×X \ IdX = { ⟨x, y⟩ ∈ X ×X x = y } .


Alberto Marini

Quando si puo sottintendere che ci si trova nell’ambiente X, la diversita viene individuata anche con

il segno di disuguaglianza “ =”.

B19:d.03 Consideriamo una relazione binaria R x, y . Si dice prima proiezione o dominio della R

l’insieme

(1) dom(R) := Prj 1(R) :={x ∃yt.c.R x, y

}.

Si dice seconda proiezione o codominio della R l’insieme

(2) cod(R) := Prj 2(R) :={y ∃xt.c.R x, y

}.

Dunque ogni relazione binaria R si puo considerare un sottoinsieme del prodotto cartesiano delle sue

due proiezioni:

(3) R ⊆ Prj 1(R)×Prj 2(R) .

Si possono estendere alle relazioni fra arbitrari insiemi (definiti da proprieta) le considerazioni che

avevamo svolte per le relazioni entro insiemi finiti ed entro insiemi procedurali.

Diciamo invece prima garanzia della R l’insieme

(4) Wrnty1(R) :={x ∀y R x, y

}.

Simmetricamente diciamo seconda garanzia della R l’insieme

(5) Wrnty2(R) :={y ∀x R x, y

}.

B19:d.04 Per ogni x ∈ dom(R si dice taglio verticale della relazione R relativo alla prima coordinata x

l’insieme

(1) R|x∗ := {y ∈ cod(R) ⟨x, y⟩ ∈ R} .

Simmetricamente per ogni y ∈ cod(R si dice taglio orizzontale della relazione R relativo alla seconda

coordinata y l’insieme

(2) R|∗y := {x ∈ dom(R) ⟨x, y⟩ ∈ R} .

Si hanno dunque le due applicazioni

(3) x ∈ dom(R) R|x∗ ∈ {dom(R)▹−→ P(C)} e

(4) y ∈ cod(R) R|∗y ∈ {cod(R)▹−→ P(D)} .

Chiaramente ciascuna di queste due applicazioni dipende dall’altra.

Viceversa ad ogni applicazione x ∈ D K(x) ∈ {D▹−→ C} risulta associata la relazione binaria

{⟨x, y⟩ ∈ D×C y ∈ K(x)} e ad ogni applicazione y ∈ C H(x) ∈ {C▹−→ D} risulta associata

la relazione binaria {⟨x, y⟩ ∈ D × C x ∈ K(y)} .

B19:d.05 Si dice trasposta, riflessa o reciproca di una relazione binaria R la relazione

(1) R :={⟨y, x⟩ ∈ Prj 2(R)× Prj1(R) ST R x, y

}.

Chiaramente la trasposizione e un’involuzione, cioe

(2) ∀R ∈ Rel (R ) = R .



Applicando la trasposizione al prodotto di due relazioni R ed S si ottiene

(3) (R ◦lr S) = (S ) ◦lr (R ) .

B19:d.05 Consideriamo due relazioni binarie R e S. Si dice prodotto di composizione o prodotto di Peirce

di R ed S la relazione

(1) R ◦lr S :={⟨x, z⟩ ∃y R x, y ∧ S y, z

}.

Chiaramente

(2) Prj 1(R ◦lr S) ⊆ Prj 1(R) , Prj 2(R ◦lr S) ⊆ Prj 2(S) .

B19:d.06 Riprendiamo le principali classi di relazioni binarie trattate in B14:b e in B18:d (v.a. B53:).

Una relazione binaria R si dice riflessiva sse

(1) Prj 1(R) = Prj 2(R) e ∀x ∈ Prj 1(R) R x, x .

L’identita e la relazione assurda su qualsiasi ambiente sono relazioni riflessive.

Una relazione binaria R si dice antiriflessiva sse

(2) Prj 1(R) = Prj 2(R) e ∀x ∈ Prj 1(R) ¬R x, x .

Una relazione binaria R si dice simmetrica sse

(3) Prj 1(R) = Prj 2(R) e R = R .

ovvero sse

(4) Prj 1(R) = Prj 2(R) e ∀x, y ∈ Prj 1(R) R x, y ∧R x, y =⇒ x = y .

L’identita e la diversita su X sono particolari relazioni simmetriche.

Una relazione binaria R si dice antisimmetrica sse

(5) R ∩R ⊆ IdPrj1(R) .

ovvero sse

(6) ∀⟨x, y⟩ ∈ Prj 1(R)×Prj 2(R) R x, y ∧R x, y =⇒ x = y .

La relazione fra insiemi ⊆ e una particolare relazione antisimmetrica.

B19:d.07 Una relazione binaria R si dice transitiva sse

(1) R x, y ∧R y, z =⇒ R x, z .

La relazione fra insiemi ⊆ e anche una relazione transitiva.

B19:d.08 Una relazione binaria R si dice equivalenza sse e riflessiva, simmetrica e transitiva.

Esempi di relazioni di equivalenza entro insiemi non costruibili sono: il differire per un addendo intero

dei nmeri reali, la conguenza fra triangoli del piano o fra figure solide, la similarita fra coniche aventi

la stessa eccentricita.

Le relazioni in generale saranno esaminate con una certa ampiezza insieme alle partizioni, entita loro

strettamente associate, in B54:b.


Alberto Marini

Conviene osservare che la relazione di equivalenza e stata introdotta per coppie di entita ⟨α, β⟩ che si

collocano in uno stesso ambiente U e che la constatazione di una equivalenza tra una α e una β viene

utilizzata spesso per giustificare la sostituzione in determinati contesti della α con la β. Conviene

anche confrontare la nozione di equivalenza con la relazione chiamate criptomorfismo, relazione che

associa due entita di natura diversa, cioe collocate in due ambienti diversi, le quali sono logicamente

intercambiabili. In particolare individueremo un criptomorfismo fra relazioni di equivalenza e partizioni

di insiemi (v. B54:b.02).

B19:d.09 Una relazione binaria R si dice relazione d’ordine sse e riflessiva, antisimmetrica e transitiva.

La relazione fra insiemi ⊆ e anche una relazione transitiva.

Esempi di relazioni d’ordine sono la relazione ≤ tra numeri reali, la relazione di ordine lessicografico

tra i punti del piano reale o dello spazio suoi reali e la relazione di di dominanza fra funzioni reali.

Le relazioni d’ordine in generale saranno esaminate con una certa ampiezza in B55: .

Si osserva che, mentre le relazioni di equivalenza presentano una struttura generale molto semplice,

viceversa si incontra una grande varieta di relazioni d’ordine. In particolare si distinguono le relazioni

d’ordine totale, tali che tra due diversi elementi dell’insieme ordinato accade che aut il primo precedeil

secondo aut viceversa (cioe due elementi diversi sono sempre confrontabili), dalle relazioni per le quali

si hanno duetti di elementi non confrontabili. Tra gli esempi dati in precedenza solo l’ordinamento dei

numeri reali e totale.

B19:e. Funzioni

B19:e.01 Per relazione funzionale dall’insieme D nell’insieme C si intende una relazione f con Prj 1(f) ⊆D e Prj 2(f) ⊆ C tale che ad un elemento di D puo associare al piu un elemento di C.

Questo insieme di coppie di D × C si dice anche funzione da D in C.

Denotiamo con {D −→ C} l’insieme delle funzioni da D in C.

Una f ∈ {D −→ C} viene anche chiamata applicazione, mappa o trasformazione da D in C.

Si dice dominio della f l’insieme dom(f) := Prj 1(f), mentre si dice codominio o immagine della f

l’insieme cod(f) := Img(f) := Prj 2(f).

In molti contesti una funzione f viene individuata da una scrittura del tipo f(x) nella quale il campo

di variabilita dell’argomento e stabilito in anticipo o puo essere sottinteso.

Talora al termine funzione attribuisce il significato di operazione, di meccanismo, determinato da una

relazione funzionale che ad alcuni elementi di D associa un elemento di C.

B19:e.02 Similmente a quanto e stato fatto per le funzioni finite in B13:b, si definiscono i vari generi

di funzioni ed i corrispondenti insiemi.

Sia dunque f ∈ {D −→ C}.Se dom(f) = D la f si dice funzione di D, ovvero dall’intero d, in C. L’insieme delle funzioni di D in

C si denota con {D 7−→ C}.La f si dice funzione suriettiva o suriezione da D su C sse Prj 2(f) = C.

L’insieme delle funzioni suriettive da D su C si denota con {D−−◃C}.A sua volta l’insieme delle funzioni suriettive di D (cioe dall’intero D) su C si denota con {D ◃C}.



La f si dice funzione iniettiva o iniezione da D in C sse ∀x1, x2 ∈ dom(f) f(x1) = f(x2) =⇒ x1 = x2 .

L’insieme delle funzioni iniettive da D su C si denota con {D ←→ C}.La f e iniettiva sse la relazione trasposta della f , cioe la f = {x ∈ dom(f) :| ⟨f(x), x⟩} e funzionale.

Per tale motivo le funzioni iniettive sono chiamate anche invertibili e la funzione f viene chiamata

anche funzione inversa della f e viene denotata con f−1.

L’insieme delle funzione iniettive di D (cioe dall’intero D) in C si denota con {D▹−→ C}.L’insieme delle funzioni iniettive da D su C (ossia iniettive e suriettive da D su C) si denota con

{D ←−◃C}.La f si dice funzione biiettiva o biiezione di D su C sse e iniettiva dall’intero D e suriettiva sull’intero C.

L’insieme delle biiezioni di D su C si denota con {D ▹−−◃C} .Per enunciare che una f appartiene ad un insieme {D −→ C} diremo anche che f e una funzione di

genere {D −→ C}. Similmente parleremo di funzioni del genere {D 7−→ C}, del genere {D−−◃C}, delgenere {D ◃C}, del genere {D ←→ C}, del genere {D▹−→ C}, del genere {D ←−◃C} e del genere

{D ▹−−◃C}.

B19:e.03 Consideriamo una funzione f ∈ {D −→ C}.Si dice estensione booleana della f la funzione

(1) f be := X ⊆ D {x ∈ D :| f(x)} .

Chiaramente f be ∈ {P(D) −→ P(C)}.Spesso il contesto consente di identificare la f be con la f stessa. Questa semplificazione l’adottiamo

qui di seguito.

(2) Prop.: ∀S ⊆ T ⊆ D f(S) ⊆ f(T )

(3) Prop.: S ⊆ D ∧ S = ∅ ⇐⇒ f(S) = ∅(4) Prop.: f(S ∪ T ) = f(S) ∪ f(T )

(5) Prop.: f(S ∩ T ) ⊆ f(S) ∩ f(T )

B19:e.04 Consideriamo ancora la generica f ∈ {D −→ C} e un Y ⊆ C. consideriamo inoltre la

cosiddetta immagine reciproca di Y ottenibile dalla f considerata come una relazione tra D e C.

f (Y ) := {x ∈ D ST f(x) ∈ Y } .

Questa relazione puo essere considerata una applicazione da P(C) in P(D) e puo chiamarsi estensione

reciproca della f agli insiemi booleani del codominio e del dominio.

Consideriamo un insieme f ({y}) ricavato da qualche elemento di cod(f), ossia l’insieme degli x ∈dom(f) tali che f(x) = y. In genere la sua espressione si semplifica nella f (y).

Consideriamo un S ⊆ D; si dice applicazione canonica di S in D la funzione s ∈ S s ; essa

chiaramente e una iniezione di S in D.

Per traccia di un X ⊆ D su A si intende l’immagine reciproca della X per l’applicazione canonica di S

in D.

B19:e.05 Consideriamo ancora la generica f ∈ {D −→ C}.(1) Prop.: ∀Y1, Y2 ⊆ C Y1 ⊆ Y2 =⇒ f (Y1) ⊆ f (Y2)

(2) Prop.: ∀Y1, Y2 ⊆ C f (Y1 ∪ Y2) = f (Y1) ∪ f (Y2)

(3) Prop.: ∀Y1, Y2 ⊆ C f (Y1 ∩ Y2) = f (Y1) ∩ f (Y2)


Alberto Marini

(4) Prop.: ∀Y ⊆ C f ( (Y )) = (f (Y )

(5) Prop.: Se f ∈ {D 7−→ C}, allora ∀X1, X2 ⊆ D f(X1 ∩X2) = f(X1) ⊆ f(X2)

(6) Prop.: Se f ∈ {D ▹−−◃C}, alloray = f(x) e x = f (x) sono relazioni equivalenti ;

∀X ⊆ D f( D(X)) = Cf(X) ;

f be ∈ {P(D) ▹−−◃P(C)} svq

Diciamo quaterna di biunivocita un sistema ⟨D,C, f, g⟩, dove D e C sono insiemi, f ∈ {D ▹−−◃C} e

g = f ∈ {C ▹−−◃D} .

B19:e.06 (1) Prop.: Consideriamo f ∈ {D −→ C}, X ⊆ D e Y ⊆ C.

f (Y ) = f (U ∩ f(D)) ;

D ⊆ f (f(X)) ;

f(f (Y ) ⊆ Y

(2) Prop.: Sono equivalenti le proprieta ∀Y ⊆ C f(f (Y ) = Y e f ∈ {D−−◃C}(3) Prop.: Sono equivalenti le proprieta ∀X ⊆ D f (f(X)) = X e f ∈ {D ←→ C}(4) Prop.: Sono equivalenti le proprieta ∀X ⊆ D ,Y ⊆ C f (f(X)) = X ∧ f(f (U) = Y e

f ∈ {D ←−◃C}

B19:e.07 Consideriamo quattro insiemi (non necessariamente diversi) D, C, B ed A e le funzioni

f ∈ {D −→ C} , g ∈ {C −→ B} ed h ∈ {B −→ A}.Si dice applicazione composta o prodotto di Peirce della f e della g:

(1) p := f ◦lr g := x ∈ D f(g(x)) ∈ {D −→ B} .

Questo operazione binaria e associativa e in genere non commutativa.

B19:e.08 Le funzioni di {D 7−→ D} si dicono endofunzioni entro D. Il loro insieme {D 7−→ D} si denotaanche con EndoD.

In particolare si hanno le endofunzioni entro D iniettive, cioe le funzioni costituenti {D 7−→ D} e le

endofunzioni entro D suriettive, cioe le funzioni costituenti {D ◃D}Una endofunzione iniettiva non suriettiva: n ∈ Z 2n .

Una endofunzione suriettiva non iniettiva: n = 6m+ k ∈ N 3m+ k#3

=

y 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 · · ·0 1 2 0 1 2 3 4 5 3 4 5 6 7 8 6 · · ·

y .

Ancor piu particolari sono le endofunzioni entro D biiettive, ossia le endofunzioni entro D iniettive e

suriettive, cioe le funzioni costituenti a {D ▹−−◃D}. Esse si dicono anche permutazioni di D e il loro

insieme si denota anche con PermD.

Esempi x ∈ R+ :| 1/x , x ∈ R× R :| 2x+ ⟨3, 4⟩ , n = 4m+ k ∈ N 5m− k#4− 1 .

=

y 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 · · ·3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 19 · · ·

y .

Si osservi che abbiamo segnalate endofunzioni appartenenti a {D▹−→ D}\{D▹−−◃D} ed endofunzioni

appartenenti a {D ◃D} \ {D ▹−−◃D} .

B19:e.09 Una endofunzione f ∈ {D 7−→ D} si dice involuzione sse e una biiezione e f = f−1, ovvero

In geometria si incontrano varie involuzioni: riflessioni rispetto a rette o rispetto a piani, simmetrie

centrali.



Una endofunzione f ∈ {D 7−→ D} si dice idempotente sse f ◦lr f = f . Esempi di funzioni idempotenti

in geometria sono i vari tipi di proiezioni ortogonali su rette o su piani.

Se f ∈ {D 7−→ D, il sottoinsieme S del suo dominio S si dice stabile per l’endofunzione sse f(S) ⊆ S.

Per esempio consideriamo l’endofunzione suriettiva non biiettiva n ∈ N ⌊n/e⌋ ∈ {N ◃ N} .

La collezione degli insiemi stabili per questa endofunzione e costituita dagli intervalli [0 : n] per tutti

gli n ∈ N.

B19:e.10 Consideriamo una funzione f ∈ {D 7−→ C} e una parte E ⊆ D. Si dice restrizione ad E della

f la funzione

(1) f|A := a ∈ A f(a) = f ∩ E × C .

Equivalentemente la funzione f si puo chiamare il prolungamento o l’estensione della f|A.

Si osserva che la restrizione f|A si puo considerare la composizione della applicazione canonica di A in

E con la f .

(2) f|A = a ∈ A a ◦lr f .

B19:e.11 In alcune circostanze una funzione f ∈ {D ←−◃C} viene chiamata rappresentazione parametrica

di C medianteD. In tal caso si dice cheD e l’insieme dei parametri della rappresentazione e gli elementi

di D sono chiamati parametri.

B19:f. Cardinalita degli insiemi

B19:f.01 Due insiemi S e T si dicono avere la stessa cardinalita o la stessa numerosita sse esiste una

biiezione di S su T , ossia sse {S ▹−−◃T} = ∅. In questa situazione si dice anche che tra i due insiemi

S e T sussiste la relazione di equicardinalita.

L’equicardinalita e una relazione di equivalenza: infatti e evidente che sia una relazione riflessiva e

simmetrica e per la transitivita basta osservare che se S, T e V sono insiemi per i quali esistono le

biiezioni β ∈ {S ▹−−◃T} e γ ∈ {T ▹−−◃V }, allora β ◦lr γ ∈ {S ▹−−◃V }.Consideriamo un insieme S e la collezione di tutti gli insiemi aventi la sua stessa cardinalita; questa

collezione e una classe della equivalenza equicardinalita. Essa si dice cardinalita di S e si denota con

card(S), con |S|, con S# o con #(S).

Evidentemente le definizioni di equicardinalita e di cardinalita estendono le nozioni con tali nomi per

definite per gli insiemi finiti ed i procedurali.

Affermare che due insiemi S e T hanno la stessa cardinalita, ovvero che si possono porre in biiezione,

si esprime con l’uguaglianza card(S) = card(T ) o con una scrittura equivalente come |S| = |T | ,come S# = T# o come #(S) = #(T ) .

Si osserva anche che la relazione di equicardinalita e l’equivalenza canonica della card, funzione in-

trodotta per associare ad ogni insieme la collezione degli insiemi che con esso si possono porre in

biiezione.

Conveniamo anche di denotare con Card l’insieme dei numeri cardinali, cioe l’insieme delle classi di

equicardinalita costituite dagli insiemi. Chiaramente N ⊂ Card .


Alberto Marini

B19:f.02 Un insieme finito con un certo numero n di elementi individuato da una lista priva di ripetizioni

di identificatori dei suoi membri, ha la stessa cardinalita dell’insieme numerico {1, 2, ..., n}.Ogni sottoinsieme proprio S′ di un insieme finito S con almeno un elemento ha cardinalita strettamente

inferiore a quella dell’insieme: si puo quindi affermare ∀S ∈ SetF, S′ ⊂ S |S′| < |S| .

Abbiamo invece visto che si trovano insiemi numerabili che hanno la stessa cardinalita di loro sottoin-

siemi propri: ad esempio |P| = |N| = |Z| = |Q| = |RC| e |N| = |Even| = |Odd|.

Anche molti altri insiemi si possono porre in corrispondenza biunivoca con propri sottoinsiemi.

Esaminiamo il caso dell’insieme R dei numeri reali (alla la cui definizione e dedicato il cap. B42:)

e dei suoi intervalli.

(1) Prop.: L’insieme dei numeri reali R ha la stessa cardinalita di ciascuno dei suoi intervalli, finiti o

illimitati, aperti, chiusi o simili.

Dim.: (non ricorre a funzioni trascendenti) I due intervalli reali chiusi [0 : 1] e [a : b] sono posti in

biiezione dalla funzione x ∈ [0 : 1] a+b x . Quindi tutti gli intervalli finiti chiusi hanno la stessa

cardinalita.

E evidente il seguente complesso di disuguaglianze

[0 : 1]#= [0.1 : 0.9]

# ≤ (0 : 1)# ≤ (0 : 1]

#, [0 : 1)

# ≤ [0 : 1]#

.

Quindi tutti gli intervalli reali limitati hanno la stessa cardinalita.

Consideriamo la poligonale illimitata avente come vertici i punti

P0 − ⟨0, 0⟩, P1 = ⟨1/2, 1⟩, P2 = ⟨2/3, 2⟩, ..., Pn = ⟨1− 1/n+ 1, n⟩, ...e la poligonale ottenuta prolungando la precedente nei vertici P−n := −Pn.

Esse individuano due funzioni crescenti; la prima pone in corrispondenza biunivoca [0 : 1) e (0 : +∞),

mentre la seconda pone in biiezione (− 1 : 1) con l’intero R. Infine si osserva che gli intervalli illimitati

si possono porre in biiezione mediante semplici traslazioni.

Quindi R si puo porre in biiezione con ciascuno dei suoi intervalli illimitati e con ciascuno dei suoi

intervalli finiti

La cardinalita di R e dei suoi intervalli viene detta cardinalita del continuo.

B19:f.03 Il precedente risultato conduce a distinguere gli insiemi finiti, insiemi che non possono porsi in

biiezione con loro sottoinsiemi propri, dagli insiemi infiniti, definiti come insiemi che si possono porre in

biiezioni con loro sottoinsiemi propri. L’insieme degli insiemi infiniti lo denotiamo con SetI.

Le cardinalita degli insiemi finiti si possono identificare con i numeri interi naturali e l’insieme dei

numeri cardinali, che conveniamo di denotare con Card, si puo considerare un’estensione di N.

I numeri cardinali che, come ℵ0, non fanno parte di N vengono chiamati numeri transfiniti; la loro

collezione la denotiamo con Transf. Si puo quindi scrivere

Card = N ∪Transf .

Il numero transfinito che rappresenta la cardinalita di N e di insiemi come Z e Q viene denotato con

ℵ0 e chiamato “alef con 0”. Gli insiemi (infiniti) con la cardinalita ℵ0 sono detti insiemi contabilmente

infiniti. Si usa il termine insiemi contabili per denotare collettivamente gli insiemi finiti e gli insiemi

contabilmente infiniti.

Il numero transfinito che rappresenta la cardinalita di R e di insiemi come gli intervalli reali viene

denotato con ℵ1 e chiamato “alef con 1”.



B19:f.04 Ora ci proponiamo di introdurre tra i numeri cardinali un ordinamento totale che estende

l’ordine dei numeri naturali e per il quale useremo ancora il segno “≤” ed i segni associati <, ≥, >,

<, ... .

Dati due insiemi S e T poniamo |S| ≤ |T | sse esiste una funzione iniettiva in {S▹−→ T}. Chiaramente

questa relazione tra cardinalita e una relazione riflessiva e transitiva.

La sua antisimmetria e garantita dal seguente teorema che dimostriamo seguendo Halmos (1960).

B19:f.05 Teorema di Schroder-Bernstein Dati due insiemi S e T , vale l’implicazione

|S| ≤ |T | ∧ |T | ≤ |S| =⇒ |S| = |T | .Dim.: Per ipotesi esistono σ ∈ {S▹−→ T} e τ ∈ {T▹−→ S}; a partire da tali funzioni individuiamo una

biiezione fra S e T . Diciamo discendenti di un s ∈ S gli elementi di U := S ∪ T s σ, s σ τ, s σ τ σ, ...

e diciamo discendenti di un t ∈ T gli elementi di S ∪ T t τ, t τ σ, t τ σ τ.... Se v ∈ U e discendente di

u ∈ U diciamo che u e predecessore di v. Per la iniettivita di σ e τ per ogni elemento di U sono definiti

i suoi predecessori. Vanno distinti gli elementi di U che hanno un predecessore privo di predecessori

dagli elementi di U per i quali la risalita ai predecessori non ha termine ma conduce ad una successione

illimitata di elementi.

Quindi esiste una tripartizione S = SS ∪ST ∪S∞, ove SS denota l’insieme degli elementi di S che

hanno come predecessore senza predecessori un elemento di S, ST denota l’insieme degli elementi di S

che hanno come predecessore senza predecessori un elemento di T e S∞ denota l’insieme degli elementi

di S che non hanno un predecessore senza predecessori.

Simmetricamente esiste una tripartizione T = TT ∪TS ∪T∞.

A questo punto puo essere utile riferirsi al seguente schema visivo delle due tripartizioni e delle funzioni

menzionate.

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

....

.........

.........

.........

.........

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

....

.........

.........

.........

.........

SS

ST

S∞

TS

TT

T∞...............................................................................................................................................................................................................................

.....

......

..............................................................................................................................................................................................................................

.........................................................

..................................................................

.......................................

......

..........................................................................................................................................

..............................................................

......

..............................................................................

............................................................................

..............................................

......

...............................................................................................

.............................................................

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

....

.........

.........

.........

.........

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

....

.........

.........

.........

.........

SS

ST

S∞

TS

TT

T∞................................................. .................................................

................................................. .................................................

..................................................................................................

..................................................................................................

σ

τ

..................................................................................................

..................................................................................................

Chiaramente SS σ = TS , TS τ = SS , TT τ = ST , ST σ = TT , S∞ σ = T∞ e T∞ τ = S∞.

Di conseguenza σ|SS∈ {SS ▹−−◃TS}, σ|ST

∈ {ST ▹−−◃TT } e σ|S∞ ∈ {S∞ ▹−−◃T∞}.L’unione delle tre precedenti biiezioni costituisce la biiezione di {S ▹−−◃T} cercata

B19:f.06 Dunque la relazione tra cardinalita e una relazione d’ordine totale ed evidentemente e

un’estensione dell’ordinamento fra numeri naturali.

Consideriamo due insiemi S e T tali che |S| ≤ |T |; se inoltre |S| = |T | scriviamo |S| < |T |.Si noti che la condizione |S| = |T | e necessaria per garantire la disuguaglianza forte |S| < |T |; ad

esempio Z ⊂ Q implica |Z| ≤ |Q|, ma si e visto che |Z| < |Q| e piu precisamente, che |Q| = |Z|.Per quanto si e visto abbiamo che ∀n ∈ N n < ℵ0.

B19:f.07 Cerchiamo ora di individuare numeri transfiniti superiori ad ℵ0.(1) Teorema di Cantor Ogni insieme S ha cardinalita inferiore al proprio booleano: |S| < P(S)| .Dim.: Definiamo come funzione di inclusione per l’insieme S la funzione inclS := x ∈ S {x} . Dato

che inclS ∈ {S 7−→ P(S)}, si ha |S| ≤ |P(S)|.


Alberto Marini

Dimostriamo che ogni funzione iniettiva del genere I ∈ {S▹−→ P(S)} non puo essere suriettiva. Per

questo consideriamo l’insieme XI := {x ∈ S x ∈ I(x)}, sottoinsieme che appartiene a P(S)

Supponiamo che sia Xf ∈ I(S); in tal caso esisterebbe un x ∈ S tale che I(x) = XI ; se questo x

appartenesse ad XI la definizione di tale insieme implicherebbe x ∈ XI ; se viceversa fosse x ∈ XI la

stessa definizione implicherebbe x ∈ XI . Queste contraddizioni implicano che sia XI ∈ I(S)

A questo punto risulta individuata una successione di classi di equicardinalita di insiemi via via piu

estese, ovvero una successione crescente di numeri transfiniti:

ℵ0 := |N| < ℵ1 := |P(N)| < ℵ2 := |P(P(N))| < ... < ℵk < ℵk+1 < ...

B19:f.08 Eserc. Se si denota con PF (S) l’insieme dei sottoinsiemi finiti dell’insieme S, dimostrare che

per ogni insieme infinito |S| = |PF (S)|.

B19:f.09 Eserc. Dimostrare che |R| = |P(N)|.

B19:f.10 Introduciamo operazioni sui numeri cardinali che estendono le operazioni di somma, prodotto e

potenza fra numeri naturali, operazioni che presentano alcune proprieta uguali a quelle delle operazioni

su N ed altre proprieta nettamente diverse. Questo giustifica l’adozione del sostantivo numero per i

numeri cardinali.

Siano µ e ν due numeri cardinali; ricordiamo inoltre che l’insieme delle funzioni da un insieme T ad

un insieme S si puo denotare con ST , cioe si ha l’omonimia ST := {T 7−→ T} .Si definisce come somma µ+ν la cardinalita di un insieme S ∪T ottenuto unendo due insiemi disgiunti

S di cardinalita µ e T con |T | = ν.

Si definisce come prodotto µ · ν la cardinalita di un insieme S × T prodotto cartesiano di due insiemi

S di cardinalita µ e T con |T | = ν.

Si definisce come potenza µν la cardinalita di un insieme ST dove S e T sono due insiemi aventi, risp.,

cardinalita µ e ν.

Va rilevato che queste definizioni richiedono che si dimostri che le composizioni di due numeri cardinali

non dipendano dai due insiemi rappresentativi delle classi di equicardinalita.

B19:f.11 Per le tre operazioni sopra i numeri cardinali si dimostrano le seguenti proprieta espresse da

formule uguali a quelle riguardanti elementi di N, cioe concernenti le cardinalita degli insiemi finiti.

(1) Prop.: Somma e prodotto di numeri cardinali sono operazioni commutative:

∀µ, ν ∈ Card µ+ ν = ν + µ , µ · ν = ν · µ .

(2) Prop.: Somma e prodotto di numeri cardinali sono operazioni associative:

∀µ, ν, ρ ∈ Card (µ+ ν) + ρ = µ+ (ν + ρ) , (µ · ν) · ρ = µ · (ν · ρ) .

(3) Prop.: Si ha distributivita della somma rispetto al prodotto di numeri cardinali sono operazioni

associative:

∀µ, ν, ρ ∈ Card µ · (ν + ρ) = µ · ν + µ · ρ) .

(4) Prop.: Valgono le seguenti uguaglianze per le potenze fra numeri cardinali:

∀µ, ν, ρ ∈ Card µν+ρ = µν · µρ , (µν)ρ = µν·ρ , (µ · ν)ρ = µρ · µρ .



B19:f.12 Enunciamo ora due proprieta dei numeri transfiniti ben diverse dalle omologhe per le cardi-

nalita degli insiemi finiti.

(1) Prop.: ∀µ, ν ∈ Transf µ+ ν = max(µ, ν) .

(2) Prop.: ∀µ, ν ∈ Transf µ · ν = max(µ, ν) .

B19:g. Numeri transfiniti

B19:g.01 Abbiamo visto che rivestono interesse sia i sottoinsiemi di un insieme procedurale E, sia le

funzioni che hanno come dominio un tale insieme. Inoltre ci si convince facilmente che risulterebbe

comodo fare riferimento all’insieme dei sottoinsiemi di E e all’insieme delle funzioni di E in un insieme

procedurale o finito F ; queste entita converrebbe denotarle, risp., con P(E) e con {E 7−→ F}, cioe connotazioni coerenti con quelle che si usano quando in luogo di E si ha un insieme finito.

Questi insiemi risultano comodi anche per collocare in essi sottoinsiemi come l’insieme dei sottoinsiemi

finiti di E, da denotare con PF (E), l’insieme delle endofunzioni di E da denotare con EndoE =

{E −→ E}, e l’insieme delle funzioni binarie da denotare con {E −→ {0, 1}}.

Se si tratta di insiemi, questi devono essere infiniti. Infatti tra i sottoinsiemi di E si trovano i singoletti

e questi costituiscono un insieme procedurale, mentre tra le funzioni con dominio in E si trovano le

funzioni caratteristiche dei singoletti, in corrispondenza biunivoca l’insieme dei singoletti.

Ci si chiede allora se queste entita possono considerarsi insiemi procedurali, trattabili come liste di

MSPG, oppure come entita di nuovo genere che possono essere trattate solo con strumenti di nuovo

genere.

Vediamo ora che, quale che sia E procedurale, si possono individuare MSPG che permettono di gener-

are PF (E), mentre questo risulta impossibile per P(E) e questa entita puo essere trattata solo con

strumenti di altro genere i quali non consentono di ottenere da essa quello che la disponibilita di pro-

cedure consente per gli insiemi procedurali. Anche le classi {E −→ E′} non possono essere generate

da MSPG: in effetti la particolare classe {E 7−→ {0, 1}} si puo porre in una sorta di corrispondenza

biunivoca con P(E) e se fosse un insieme procedurale lo sarebbe anche P(E).

B19:g.02 Prop. Se E e un insieme procedurale, allora e tale anche PF (E).

Dim.: Per l’ipotesi E e ottenibile dalla lista generata da una MSPG che denotiamo conM. Procederemo

a dimostrare che si puo costruire una seconda MSPGN in grado di generarePF (ML), che quindi risulta

anch’esso un insieme procedurale.

Cominciamo con il supporre che M sia non ripetitiva e denotiamo la successione delle stringhe generate

successivamente dalla M con S := MG =: ⟨e1, e2, ..., en, ...⟩. Si tratta di individuare una MSPG N che

si serve della M per generare gli elementi PF (E) secondo un ordine derivato da quello della MG .

La N organizza la sua attivita generativa in fasi successive; in ciascuna di queste attende che la M

le fornisca una nuova componente ej della S e, ottenutala, procede ad accodare su un nastro TN gli

insiemi costituenti PF (E) contenenti ej ed eventualmente elementi ei con 1 ≤ i < j.

Nella fase 0 N emette su TN l’insieme vuoto.

Nella fase 1 M fornisce e1 ed N accoda {e1} su TN .

Nella fase 2 M genera e2 ed N accoda su TN {e2} ed {e1, e2}.


Alberto Marini

Nella fase 3 M fornisce e3 ed N scorre TN dall’inizio e procede ad emettere su nuove caselle di T2

{e3}, {e1, e3}, e {e2, e3} e {e1, e2, e3}, cioe gli insiemi ottenuti aggiungendo e3 a ciascuno degli insiemi

a generati precedentemente.

. . . . .

Nella fase j, raccolto ej da M, N procede ad accodare su TN i 2j−1 sottoinsiemi ottenuti aggiungendo

ej ai 2j−1 gia generati e registrati su TN , in modo che alla fine di questa fase su TN siano elencati tutti

i 2j sottoinsiemi di {e1, e2, ..., ej}.. . . . .

L’esecuzione di queste fasi da parte di N puo procedere illimitatamente o meno.

Se M e ripetitiva basta prevedere che essa tenga registrate senza ripetizioni sopra un proprio nastro

TM tutte le stringhe generate e che ad ogni nuova eh generata dalla M si controlli che non sia gia

presente su tale nastro

Si osserva che gli insiemi generati dalla macchina non ripetitiva nella fase j si possono far corrispondere

biunivocamente alle sequenze binarie di lunghezza j che nell’ultima posizione presentano il bit 1;

dunque anche l’insieme delle sequenze binarie finite e procedurale.

B19:g.03 Prop. Se E e un insieme ricorsivo, anche PF (E) lo e.

Dim.: Sia M una macchina che genera E, cioe tale che ML = E, sia A l’alfabeto del suo nastro di uscita

e sia U := A∗; si puo dunque asserire che ML ⊆ U. Sia inoltre D un algoritmo in grado di decidere

per ogni x ∈ U se appartiene o meno ad E.

Un algoritmo in grado di decidere se un qualsiasi sottoinsieme finito di U {y1, y2, ..., yj} appartiene a

PF (E) organizza lo scorrimento degli elementi yi per i = 1, 2, ..., j ed applica A a ciascuno di essi per

stabilire che tutti appartengono ad E

Questo risultato consente di ampliare significativamente il repertorio disponibile degli insiemi ricorsivi

e degli insiemi numerabili.

(1) Eserc. Descrivere procedure progressive che generano l’insieme delle sequenze binarie, l’insieme

dei linguaggi finiti su un dato alfabeto, l’insieme dei linguaggi finiti sopra un alfabeto numerabile

⟨a1, a2, ..., an, ...⟩.

B19:g.04 Dimostriamo ora due fondamentali teoremi dovuti a [[Georg Cantor]] che negano la possibilita

di servirsi di procedure per generare gli elementi di classi come P(E) ed EndoE .

(1) Teorema Un insieme non vuoto qualsiasi E non si puo porre in biiezione con il proprio booleano

P(E).

Dim.: Supponiamo che si abbia una biiezione β fra E e P(E) e consideriamo il sottoinsieme di E

E := {x ∈ E x ∈ β(x)} [*] .Questo elemento di P(E) dovrebbe esprimersi come β(x) per un qualche x ∈ E.

Si constata pero che x non puo trovarsi ne in E ne in E \ E. Infatti se fosse x ∈ E per la [*] sarebbe

x ∈ β(x) = E, mentre se fosse x ∈ E per la [*] sarebbe x ∈ β(x) = E. Questa situazione e assurda e

di conseguenza non puo esistere la funzione β ipotizzata

B19:g.05 Teorema Un insieme E non si puo porre in biiezione con l’insieme delle proprie endofunzioni

EndoE .

Dim.: Supponiamo che si abbia una biiezione β fra E ed EndoE ; consideriamo una endofunzione σ che

scambia tra di loro due elementi diversi di E e la endofunzione associata definita come

(1) ησ := e ∈ E σ[(β(e))(e)] .



Questa dovrebbe essere esprimibile come β(e) per un qualche e ∈ E, ma questo non e possibile per

alcun e; infatti ησ = β(e) implica

ησ(e) = (β(e))(e) ,

mentre (1) comporta ησ(e) = σ[(β(e))(e)], in conflitto con la precedente uguaglianza

Osserviamo che le due precedenti affermazioni con le relative rgomentazioni sono strettamente collegate;

il secondo teorema puo riformularsi per le funzioni da E in {0, 1} pur di definireη := e ∈ E 1− (β(e))(e) .

Inoltre l’insieme delle funzioni suddette e in corrispondenza biunivoca con la collezione dei sottoinsiemi

dell’insieme E.

B19:g.06 Le argomentazioni sviluppate in :g.04(1) ed in :g.05 costituiscono tipiche dimostrazioni per

assurdo. Le dimostrazioni esposte in precedenza erano invece dimostrazioni costruttive, cioe si basavano

sulla possibilita di realizzare costruzioni formali effettive concluse dopo un numero finito di passi (sopra

insiemi finiti) o costruzioni sviluppabili illimitatamente, cioe in grado di condurre ad insiemi con numeri

di elementi grandi quanto si vuole.

In effetti quando si va oltre l’ambito degli insiemi procedurali la costruibilita viene necessariamente a

mancare: essa ha senso solo in ambiti finiti o illimitatamente generabili: si possono trattare costrut-

tivamente, mediante meccanismi descrivibili finitamente, solo informazioni finite o illimitatamente

ampliabili.

Per riuscire a trattare entita come le collezioni dei sottoinsiemi di un insieme procedurale e le collezioni

delle funzioni aventi come dominio un insieme procedurale o una entita ottenibile con costruzioni

formali ancor piu elaborate, servono altre nozioni e altri procedimenti dimostrativi, quelli basati su

una teoria assiomatica degli insiemi (v. cap. B65:). Anche queste nuove entita e le dimostrazioni che

li riguardano, devono essere introdotte, sviluppate e comunicate mediante stringhe finite, ma in modo

meno diretto delle precedenti, attraverso costruzioni formali sostanzialmente piu complesse di quelle

presentate finora, riconducibili direttamente a procedure.

Va anche osservato che i teoremi :g.04(1) e :g.05 riguardano insiemi non bene identificati: infatti fino a

questo punto sono stati definiti solo insiemi finiti e insiemi procedurali e le due affermazioni dovrebbero

riguardare gli insiemi procedurali, risultando esse banali per insiemi finiti. I teoremi sono stati enunciati

in forma generale perche le loro dimostrazioni prescindono dalle caratteristiche costruttive degli insiemi;

esse hanno piena validita per gli insiemi definiti con una teoria assiomatica.

B19:g.07 Dato che puo essere utile poter trattare come insiemi i booleani di insiemi non finiti e le

collezioni di funzioni fra insiemi non finiti, ad esempio per fare riferimento ai risultati di operazioni

insiemistiche su queste collezioni di insiemi, emerge l’opportunita di considerare altri insiemi oltre ai

finiti ed ai numerabili, cioe insiemi non trattabili costruttivamente.

Questi insiemi, come vedremo, risultano indispensabili gia per poter trattare i numeri reali

dell’intervallo [0, 1) e a fortiori sono necessari per introdurre la totalita dei numeri reali, tutti gli

enti della geometria del continuo, le grandezze ed i processi studiati nella fisica, nella tecnologia, nelle

scienze naturali e in ogni altra disciplina quantitativa.

Entita come numeri reali, funzioni continue, figure geometriche etc. sono state studiate anche in assenza

di una impostazione rigorosa, impostazione in parte adottata dai grandi matematici dell’epoca greco-

ellenistica (Euclide, Archimede, ...) in seguito quasi dimenticata e recuperata pienamente solo nella

seconda meta del XIX secolo ([[Dedekind]], [[Weierstrass]], [[Cantor]], [[Peano]], [[Hilbert]], [[Godel]],

[[Turing]], ...). Esse richiedono una impostazione assiomatica, cioe una teoria formale che si basa su as-

siomi e procedimenti dimostrativi che risultino non contradditori e sufficientemente fecondi. Qui, senza


Alberto Marini

entrare nei dettagli e procedendo solo su un piano descrittivo, ricordiamo che in questa impostazione

gioca un ruolo importante una teoria degli insiemi che trae avvio dalla introduzione contemporanea

delle nozioni di elemento, insieme ed appartenenza. Questa teoria consente di trattare anche gli insiemi

procedurali e di esprimersi su costruzioni come quella dell’insieme di tutte le funzioni da un insieme

dato in un altro insieme dato e quella del booleano di un insieme dato.

B19:g.08 Quando si vogliono evitare al lettore le questioni che abbiamo messo in rilievo, spesso si

espongono i risultati della teoria generale degli insiemi che servono partendo da alcune nozioni assunte

come “primitive”: quelle di insieme, di appartenenza di un elemento ad un insieme e quella di proprieta

che caratterizza tutti e soli gli elementi di un insieme. Questo funzione grazie alla sorprendente efficacia

della semplicissima metafora degli insiemi come sacchetti riempiti di palline. Accenniamo all’inizio della

narrazione.

Una proprieta puo esprimersi con una proposizione piu o meno formalizzata, nella quale oltre a segni

o espressioni di significato noto, interviene un segno o una espressione, denotiamola a, che rappresenta

il generico oggetto che la soddisfa. Se rappresentiamo una tale proposizione con P[a], l’insieme degli

oggetti che soddisfano questa proprieta si denota {a P[a]} e P si dice proprieta caratteristica di questo

insieme. Dato che il segno a esaurisce la sua funzione nella precedente scrittura (si dice (v. cap. B61:)

che e saturato), si puo sostituire con ogni altro segno x: {a P[a]} = {x P[x]}.Un oggetto che soddisfa la proprieta espressa da P[a] e elemento di {a P[a]}, questo si esprime

scrivendo b ∈ {a P[a]} utilizzando il segno della relazione di appartenenza ∈. Per un oggetto c che

non soddisfa P[a] si scrive c /∈ {a P[a]}.

B19:g.09 Con Set denotiamo la classe degli insiemi, cioe una entita che permette di usare scritture come

A,B,C :∈ Set per dichiarare che con le lettere A, B e C denotiamo tre insiemi. Scriviamo inoltre

x :∈ A per convenire che x denoti un elemento dell’insieme A. Scriviamo B :⊆ A per introdurre un

sottoinsieme di A da indicare con B. Con C :⊂ B si dichiara che l’insieme C e un simbolo usato per

denotare un sottoinsieme proprio di B.

Altri insiemi si introducono con scritture del tipo

S = {a ∈ A P[a]} ;qui P individua una proprieta che puo essere soddisfatta o meno da ciascuno degli elementi dell’insieme

A in qualche misura noto; l’insieme individuato dalla precedente scrittura e costituito da tutti e soli

gli elementi di A che godono della proprieta P.Per poter dare indicazioni precise sulle analisi che garantiscono che si possono utilizzare espressioni

come la S = {a ∈ A P[a]} o la precedente {a1, ..., an} o altre che incontreremo tra breve, si dovrebbero

dare indicazioni precise su cosa si intenda per “regola”, “proprieta”, “meccanismo costruttivo”.

Una semplice variante della forma precedente e una espressione del tipo

S = {B ⊆ A P[B]} ,per l’insieme dei sottoinsiemi di A che godono della proprieta P.Se a e P indicano, risp., un oggetto e una proprieta ben definita, la scrittura

{a sse a soddisfa P}fornisce il singoletto {a} nel caso in cui a soddisfi effettivamente P e ∅ nel caso opposto.

Un’altro tipo di espressione insiemistica spesso utile ha la forma

S = {x ∈ X :| C[x]} :qui C denota una costruzione dipendente da un oggetto x che puo scegliersi arbitrariamente nell’insieme

X, ovvero un meccanismo che puo operare sopra questi x in modo da associare una entita a ciascun x.



La formula precedente individua l’insieme degli oggetti che si ottengono considerando i diversi elementi

di X e attuando per ciascuno di essi la costruzione espressa.

Osserviamo che le espressioni della forma S = {a0, a1, ..., an, ...}, usate spesso per gli insiemi numerabili,

sono riconducibili alla forma precedente scrivendo

S = {n ∈ N :| an} ,dove an si suppone denoti il risultato di una costruzione operante sul generico intero positivo n.

Questo e un caso particolare del seguente piu generale in cui gli oggetti di un insieme A = {a P[a]}sono individuati riferendoli agli oggetti di un’altro insieme I = {i Q[i]} caratterizzato da una proprietaQ che ci aspettiamo piu semplice della P. In questo caso si individua A come {i ∈ I :| αi}, ovverocome {αi Q(i)} ove αi e una espressione che individua un oggetto a partire da un generico elemento

di I. In questo caso si dice che {i ∈ I :| αi} e una famiglia di oggetti avente I come insieme degli

indici.

B19:g.10 Una cardinalita, o numerosita, si attribuisce a tutti gli insiemi chiedendo che abbiano la stessa

cardinalita due insiemi che si possano porre in corrispondenza biunivoca. La cardinalita di ogni insieme

A viene indicata con A#, con #(A) o con |A|. Denotiamo con Card l’insieme delle cardinalita.

Se un insieme A si trova in corrispondenza biunivoca con una parte di un insieme B e se B si trova in

biiezione con una parte di un insieme C, evidentemente A si trova in biiezione con una parte di C. Se

A e in biiezione con una parte di B, un insieme A′ e in biiezione con A ed un insieme B′ si trova in

biiezione con B, allora A′ si trova in biiezione con una parte di B′.

Questo rende lecito stabilire una relazione d’ordine totale fra le cardinalita degli insiemi e descrivere

le situazioni precedenti con le relazioni: |A| = |A′| ≤ |B| = |B′| ≤ |C|.

B19:g.11 Se si riesamina la dimostrazione del teorema di Cantor si vede che essa consente di enunciare

la disuguaglianza generale.

(1) Teorema Per ogni insieme E diverso dal vuoto si ha |E| < |P(E)|

Si individua quindi una successione illimitata di cardinalita non finite: ℵ0 := |N|, la cardinalita del

numerabile; ℵ1 := |P(N)|, detta cardinalita del continuo; ℵ2 := |P(P(N))|, detta cardinalita delle funzioni;

etc.

Le classi di equivalenza ℵα di questa successione si dicono numeri transfiniti; scriviamo

(1) Transf := {α ∈ N :| ℵα} .

Segnaliamo che occorre cautela nel considerare l’insieme delle cardinalita, in quanto non e noto se

esistano cardinalita comprese tra ℵ0 e ℵ1 e tanto meno cardinalita comprese tra altri due transfiniti

caratterizzati da deponenti successivi.

Chiamiamo allora N ∪Transf insieme delle cardinalita definibili mediante la costruzione P.

B19:g.12 In seguito per n ∈ N denoteremo con Setn la classe degli insiemi con n elementi (Set0 = {∅}),con SetF, con Setφ o con SetN la classe degli insiemi finiti, cioe costituiti da un numero finito di

elementi. Piu in generale per ogni insieme di interi naturali N, con SetN si denota la classe degli

insiemi con un numero di elementi appartenente ad N.

Con SetI o con Set∞ si denota la classe degli insiemi infiniti; va osservato che abbiamo trovato un primo

ruolo per il simbolo ∞, quello di caratterizzare gli insiemi infiniti.

scriveremo involtre Setcof (S) per denotare la classe dei sottoinsiemi dell’insieme S cofiniti, cioe otteni-

bili da S per eliminazione di sottoinsiemi finiti.


Alberto Marini

Va segnalato che la collezione di tutti gli insiemi, che puo denotarsi con Set, non puo considerarsi

un insieme: infatti questo consentirebbe di affermare Set ∈ Set , e da questo enunciato seguirebbero

situazioni logicamente insostenibili in quanto contradditorie chiamate [[paradossi]]. La scoperta dei

paradossi verso la fine del XIX secolo ha condotto ad un attento esame dei fondamenti della matematica

ed a formulazioni molto accurate di sistemi di assiomi da porre alla base della teoria degli insiemi.

Se k :∈ Card⊣, si individua la collezione dei sottoinsiemi di A aventi cardinalita k scrivendo

APk := {B ∈ AP B# = k} .Gli insiemi di cardinalita n con n intero naturale spesso sono chiamati anche k-insiemi. Se K :⊆ Card⊣

scriviamo APK := {B ∈ AP B# ∈ K}. Scriviamo poi, risp., Setk e SetK la classe degli insiemi

aventi cardinalita uguale a k e cardinalita in K.

Si vede che la cardinalita del continuo ℵ1, cioe (NP)#, coincide con la cardinalita dell’insieme [0, 1)

dei numeri reali compresi tra 0 ed 1, quest’ultimo escluso. Questi sono definibili attraverso le loro

notazioni binarie come successioni 0.b1b2...bn... con bi ∈ {0, 1}, ad esclusione delle sequenze della

forma 0.b1b2...br111...1... . Quindi introdotto l’insieme dei numeri reali, ad esempio con la definizione

R := {z ∈ Z, r ∈ [0, 1)) :| z + r} ,

si trova che anche questo insieme ha cardinalita ℵ1: infatti i due insiemi numerici sono posti in

corrispondenza biunivova dalla trasformazione

x ∈ [0, 1) :| 1

2loge

x

1− x.

Dunque l’insieme dei reali non puo essere posto in corrispondenza biunivoca con N e quindi non e

costruibile.

B19:g.13 Ricordiamo che A ∈ Setn =⇒ (AP)♯ = 2n.

Si dimostra inoltre A ∈ Setℵi =⇒ (AP)♯ = ℵi+1 .

Piu limitatamente se ν ∈ N ∪ {i ∈ N :| ℵi} ∪ {N0 ∪ {i ∈ N0 :| ℵi}}P , segue che

APν := {B B ⊆ A, B♯ = ν} = AP ∩ Setν in particolare per n ∈ N APn := AP ∩ Setn ;

APφ := AP ∩ Setφ, AP∞ := AP ∩ Set∞ .

B19:g.14 Sugli insiemi si definiscono le seguenti relazioni:

A ⊂φ B sse A ⊆ B e A ∈ Setφ ;

A ⊂∞ B sse A ⊆ B e A ∈ Set∞ .

Con A♢B abbreviamo la relazione di disgiunzione tra i due insiemi A e B tali che A ∩ B = ∅. Per la

sua negazione scriviamo A B.

Diciamo che B e C sono insiemi non confrontabili [rispetto alla inclusione] sse B ⊂ C ∧ C ⊂ B, ovvero sse

B \ C = ∅ ∧ C \B = ∅ . Denoteremo questa relazione B C.

Scriveremo piu specificamente A ⊃⊂ B sse A B e A ∩ B = ∅ , cioe sse i due insiemi sono non

confrontabili e non disgiunti.

Scriviamo A ∪B per esprimere sia la affermazione preliminare che gli insiemi A e B sono disgiunti, sia

il risultato della composizione A ∪B.



B19:h. Composizioni su famiglie di insiemi

B19:h.01 Procediamo ora ad introdurre la famiglia, costrutto che si riconduce a quella di funzione, ma

che fornisce uno strumento lessicale che facilita la definizione di varie costruzioni di ampia portata. In

particolare composizioni di insiemi viste in precedenza possono estese in misura rilevante servendosi

della nozione di famiglia di insiemi.

Una terna della forma⟨L, U, Φ

⟩, dove L ed U denotano due insiemi e Φ una funzione del genere

Φ ∈ {L 7−→ U}. si dice famiglia di elementi di U. L viene detto insieme degli indici o insieme delle etichette

della famiglia.

Spesso non si incontrano difficolta usando la semplificazione che identifica una famiglia⟨L, U, Φ

⟩con

la corrispondente funzione Φ.

Se per ogni λ ∈ L si pone Aλ := Φ(λ), la famiglia F viene individuata piu mnemonicamente dalle due

espressioni equivalenti ⟨λ ∈ L :| Aλ

⟩e λ ∈ L Aλ

⟩.

Generi particolari di famiglie di elementi sono le sequenze della forma⟨i = 1, 2, ..., n :| Ai

⟩per n intero

positivo e le successioni di elementi⟨i = 1, 2, ... :| Ai

⟩.

Se M ⊆ L la famiglia⟨M, U, Φ|M

⟩viene detta sottofamiglia della famiglia

⟨L, U, Φ

⟩.

B19:h.02 Si dice famiglia di insiemi una terna della forma⟨M, A, F

⟩, dove M ed A denotano due insiemi

ed F una funzione del genere F ∈ {M 7−→ P(A)}. U viene detto terreno della famiglia e laM si dice

famiglia su U.

Chiaramente la famiglia di insiemi⟨M, A, F

⟩si puo considerare come una famiglia di elementi della

forma⟨M, P(A), F

⟩.

Nel seguito denotiamo con FamSet la classe delle famiglie di insiemi; piu in particolare con FamSetF

denotiamo la classe delle famiglie di insiemi finiti.

Si dice collezione di insiemi associata alla famiglia di insiemiM =⟨M, A, F

⟩sul terreno U l’insieme di

insiemi

(1) sets(M) := cod(F ) = {µ ∈M :| Sµ} .

B19:h.03 Le operazioni di unione e intersezione si estendono a tutte le famiglie di insiemi, senza

restrizioni per gli insiemi indice.

Consideriamo una generica famiglia di insiemi indicizzata da una variabile, µ, che corre in un insieme

M , M = µ ∈M Sµ .

Si dice unione della famiglia di insiemiM l’insieme definito come

(1)∪

µ∈M

Sµ := {x ∃ν ∈M t.c. x ∈ Sν} .

B19:h.04 Si dice intersezione della famiglia di insiemiM l’insieme definito come

(1)∩

µ∈M

Sµ := {x ∀µ ∈M x ∈ Sµ} .

Va rilevato che sia l’unione che l’intersezione di una famiglia M dipende solo dalla corrispondente

collezione di insiemi sets(M). In altri termini se due famiglieM edM′ sopra U riguardano la stessa


Alberto Marini

collezione di insiemi, sottocollezione di P(U), le rispettive unioni coincidono e le rispettive intersezioni

coincidono.

Talune composizioni si possono effettuare servendosi di collezioni di insiemi, sistemi un poco piu sem-

plici delle famiglie di insiemi. Infatti per una famiglia a due valori diversi dell’indice possono corrispon-

dere insiemi coincidenti; se queste coincidenze mancano si possono utilizzare quelle che chiamiamo

collezioni di insiemi, sistemi che possiamo individuare con espressioni della forma {λ ∈ L :| Aλ} .L’idempotenza dell’unione e dell’intersezione inducono ad applicare queste costruzioni a collezioni di

insiemi.

B19:h.05 La proprieta di mutua disgiunzione introdotta per le famiglie discrete di insiemi si puo estendere

a collezioni di insiemi

(1) ♢{λ ∈ L :| Aλ} sse λ, µ ∈= L =⇒ Aλ♢Aµ .

Similmente si puo estendere a collezioni di insiemi la proprieta di mutua non confrontabilita

(2) {λ ∈ L :| Aλ} sse λ, µ ∈= L =⇒ Aλ Aµ .

Inoltre puo essere vantaggioso adottare una scrittura della forma

·∪{λ ∈ L :| Ai}

per individuare l’insieme∪{λ ∈ L :| Ai} e per asserire la mutua disgiunzione degli insiemi che vengono

uniti, cioe il fatto che ♢{λ ∈ L :| Ai}.

B19:h.06 Le proprieta di distributivita per unione ed intersezione si estendono alle seguenti proprieta

di distributivita generalizzate per intersezioni e unioni di famiglie di insiemi -Profdef.

(3) ∀U,M ∈ Set , µ ∈M Sµ ∈ FamSet (∪

µ∈M

Sµ) ∩ U =∪

µ∈M

(Sµ ∩ U) ;

(4) ∀U,M ∈ Set , µ ∈M Sµ ∈ FamSet (∩

µ∈M

Sµ) ∪ U =∩

µ∈M

(Sµ ∪ U) .

B19:h.07 Altre proprieta per le operazioni booleane generalizzate

B19:h.08 Per una arbitraria famiglia di insiemi ⟨λ ∈ L :| Aλ⟩ si introduce anche il prodotto cartesiano

generale

(1) X{λ ∈ L :| Aλ} = {⟨λ ∈ L :| aλ⟩ ∀λ ∈ L aλ ∈ Aλ} .

In particolare si hanno le sequenze delle forme ⟨i ∈ (n] :| ai⟩ e ⟨i ∈ [n) :| ai⟩ , le successioni delle

forme ⟨i ∈ P :| ai⟩ e ⟨i ∈ N :| ai⟩ e le successioni bilatere della forma ⟨i ∈ Z :| ai⟩ .

E anche evidente che la n-upla ⟨a1, ..., an⟩ e diversa dall’n-upletto {a1, ..., an}, che la successione

⟨i ∈ N :| ai⟩ = ⟨a0, a1, ..., an, ...⟩ e diversa dall’insieme procedurale {a0, a1, ..., an, ...} e la famiglia

⟨λ ∈ L :| aλ⟩ dall’insieme {λ ∈ L :| aλ}.

B19:h.09 Accade spesso di considerare insiemi C i cui elementi sono insiemi; per queste entita in

genere useremo il termine di collezione di insiemi. La loro classe la denotiamo StCll. Talora e opportuno



considerare esplicitamente un insieme U del quale tutti gli elementi della collezione sono sottoinsiemi:

C ⊆ AP. Questo si puo chiamare ambiente o universo per C.Diciamo ipergrafo o spazio di blocchi sul terreno U ogni coppia ⟨U, C⟩ con U ∈ Set e C ⊆ UP.

Con HygrfU denotiamo la collezione degli ipergrafi aventi come terreno U.

Se C e una collezione di insiemi ed N ⊆ Card, C ∈N C indica concisamente che C ∈ C e |C| ∈ N .

In particolare C ∈φ C indica che C e un sottoinsieme finito di C e C ∈∞ C che C e un sottoinsieme

infinito di C.

Non e raro neppure considerare insiemi di insiemi di sottoinsiemi di un universo U, cioe elementi di un

insieme della forma (UP)P. Potrebbe essere opportuno chiamare tale insieme aggregato di collezioni

di insiemi, in modo da distinguere . Osserviamo che (UP)P = HygrfU e che le succitate collezioni di

insiemi corrispondono a particolari tipi di ipergrafi.

B19:h.10 Definiamo ora altre due operazioni che riguardano famiglie di insiemi o collezioni di insiemi.

Consideriamo la famiglia di sottoinsiemi di A F := {λ ∈ L :| Aλ} ⊆ AP.

Si dice maggiorazione booleana o chiusura per unione di F

(1) {λ ∈ L :| Aλ}((∪)) := {M ⊆ L :| ∪µ∈M Aµ} .

Si dice minorazione booleana o chiusura per intersezione di F

(2) {λ ∈ L :| Aλ}((∩)) := {M ⊆ L :| ∩µ∈M Aµ} .

La collezione di insiemi C si dice chiusa rispetto all’unione sse C((∪)) = C; con Stabs(∪) denotiamo

l’aggregato delle collezioni chiuse rispetto all’unione.

La collezione di insiemi C si dice chiusa rispetto all’intersezione sse C((∩)) = C. Con Stabs(∩) denotiamo

l’aggregato delle collezioni chiuse rispetto all’intersezione.

La collezione di insiemi C si dice discendente sse A ∈ C, A ⊇ B =⇒ B ∈ C. Con Stabs(⊇) denotiamo

la classe delle collezioni discendenti. Queste collezioni sono anche chiamate complessi simpliciali e la loro

collezione si denota anche con Simplcmp.

La collezione di insiemi C si dice ascendente sse A ∈ C, A ⊆ B =⇒ B ∈ C. Con Stabs(⊆) denotiamo

la classe delle collezioni ascendenti. Queste vengono dette anche filtri e la loro collezione si denota

anche Fltr.

Osserviamo che: Stabs(⊆) ⊂ Stabs(∪), Stabs(⊇) ⊂ Stabs(∩).

B19:h.11 Sia C una collezione di insiemi. Un suo membro C si dice insieme minimale in C sse

C ′ ⊆ C =⇒ C ′ ∈ C .

Con CMnl denotiamo la collezione degli insiemi minimali di C.L’insieme D ∈ C si dice insieme massimale in C sse

D ⊂ D′ =⇒ D′ ∈ C .

Con CMxl denotiamo la collezione degli insiemi massimali in C.Una collezione di insiemi C ⊆ UP si dice copertura di A ⊆ U sse∪

{C ∈ C :| C} ⊇ A .

Una copertura C dell’insieme A ⊆ U si dice non debordante sse ∪C∈CC = A , ovvero sse ∀C ∈ C : C ⊆ A

.

Una copertura C di A ⊆ U non debordante si dice partizione sse ∀C,D ∈= C : C♢C ′ .


Alberto Marini

Talora interessa la collezione delle collezioni di insiemi di A mutuamente nonconfrontabili: per essa usiamo

la notazione:

ANCSS := {N ⊆ AP N1,N2 ∈= N =⇒ N1 N2} .

Le varie componenti di questo testo sono accessibili in http://www.mi.imati.cnr.it/∼alberto


Introduzione euristica degli insiemi - mi.imati.cnr.italberto/mnB19rTINS.pdf · Al precedente...

Documents

Transcript of Introduzione euristica degli insiemi - mi.imati.cnr.italberto/mnB19rTINS.pdf · Al precedente...