Teoria degli insiemi

Teoria NAIF degli insiemi

La matematica non comprende i cicli viziosi. Un ciclo vizioso è un qualcosa che si contraddice. La definizione

di insieme è un ciclo vizioso, infatti è difficile da dare perché crea contraddizioni e perciò non viene assunta

dalla matematica. Bisogna prima iniziare a definire le nozioni di sintassi e di semantica:

SINTASSI: è la grammatica, che si sceglie di adottare, con cui i linguaggi vengono espressi; fornisce il

• modo in cui scrivere le formule; non attribuisce valore ai simboli.

SEMANTICA: fornisce l’interpretazione che diamo ai simboli o agli oggetti; è ciò che dà il significato.

•

teoria NAIF ingenua degli insiemi

La (G. Cantor, fine ‘800) prova a dare una definizione intuitiva di insieme.

In realtà in questa teoria l’insieme non viene definito, ma viene usato. In questa teoria quindi l’insieme è

elementi.

considerato come una collezione Anche gli elementi non vengono definiti ma in questa teoria

vengono intuitivamente considerati oggetti o unità. Se un insieme è privo di elementi allora viene detto

insieme vuoto, indicato con il simbolo ø. Normalmente un insieme viene indicato con una lettera latina

maiuscola. Un elemento con una lettera latina minuscola. ø

X insieme x elemento insieme vuoto

  

appartenenza.

La teoria degli insiemi e data dal concetto di La relazione di appartenenza esiste tra elementi

e insiemi. ∈ ∉

appartiene non appartiene

 

Esempio: ∈ ∉

La teoria ingenua degli insiemi ha dei limiti e porta a paradossi e contraddizioni: come esempio di

dimostrazione si prende il paradosso di Russell del barbiere, crea un paradosso sintattico. Se si

Problema

dice che lo è allora non lo è. Se si dice che non lo è allora lo è. .

{ }

= | ∉

Non c’è differenza tra logica e matematica perché la logica è una teoria formale e la matematica è un

insieme di logiche (quindi esistono più logiche) e quindi viene definita attraverso le teorie che si usano in

essa. La matematica ha bisogno del concetto di insieme perché questo è fondamentale per definire le cose.

Gli insiemi, le classi e gli oggetti sono concetti equivalenti, e sono dei simboli che sono definiti dalle loro

proprietà.

La teoria NAIF fa uso del metalinguaggio per esprimere dei concetti. Per metalinguaggio si intende l’utilizzo

di due o + linguaggi differenti mischiati. Per esempio: studio il cinese e mi viene spiegato in inglese 

cinese: linguaggio; inglese: metalinguaggio.

La teoria GBN o NBG o di Ghedel è una teoria non ingenua.

sottoinsieme

Si dice che un insieme è un (o parte) di un insieme e si usa la seguente scrittura:

oppure

⊆ ⊇

quando non esiste alcun elemento tale che in tal caso dicesi pure che è contenuto (o

∈ ∉ ;

incluso) in o che contiene (o include) Ad esprimere che non è parte di si scrive:

.

oppure

⊈ ⊉

La qualità ‘sottoinsieme’ è una relazione unaria o una proprietà dell’insieme, in questo caso, .

Le proprietà possono essere:

Relazioni zero-arie.

• Es: “Allo studente Marco è piaciuta la lezione di matematica.”. Frasi della lingua senza

o variabili. Si dice anche sentenza o proposizione.

Relazioni unarie.

• Es: “Allo studente x è piaciuta la lezione di matematica.”. Frasi della lingua con una variabile.

o

Relazioni binarie

• Es: “Allo studente x è piaciuta la lezione y.”. Frasi della lingua con due variabili.

o

…

• prodotto cartesiano

A questo punto, si definisce il prodotto degli insiemi (o costituito dalle

× × )

coppie aventi la prima coordinata in e la seconda in La coppia di coordinate si indica con con

(,

. )

e In simboli:

∈ ∈ . {( }

× : = , ) | ∈ e ∈

2

Il prodotto di un insieme per sé stesso si indica anche con e viene detto quadrato cartesiano di

×

. è una relazione

ℛ:

binaria. ℛ

ℛ

2 ℛ ⊆ ×

ℛ ⊆

diagonale

I sottoinsiemi di hanno un ruolo notevole, in particolare lo ha la di costituita

× Δ ×

dalle coppie tali che Se allora La relazione diagonale è binaria e si

(, ) ∈ × = . Δ = ∅ = ∅.

dice relazione identica o uguaglianza. ∆() {( }

∆(): = , ): ∈

La coppia appartiene alla diagonale per avere una relazione di uguaglianza. Quindi:

(, ) (,

= ⟺ ) ∈ ∆()

ovvero e sono uguali se la loro coppia è presente della diagonale. Queste relazioni sono dei

sottoprodotti del prodotto cartesiano e quindi si può affermare che una relazione equivale ad un

sottoinsieme.

La relazione di appartenenza è una relazione primitiva e quindi è un simbolo primitivo. L’uguaglianza

∈

invece non lo è, infatti, essa si spiega grazie alla nozione di appartenenza. Il sottoinsieme che definisce la

relazione su si dice grafo della relazione. Quindi, possiamo dire che ho una relazione quando ho un

prodotto cartesiano da cui ottengo un sottoinsieme. è una relazione su ed è anche

ℛ:

ℛ

un sottoinsieme di × .

Proprietà delle relazioni

Una relazione può essere definita in base alle sue proprietà.

RELAZIONE RIFLESSIVA

Una relazione è detta riflessiva

ℛ ⇔ ∆() ⊆ ℛ.

Una relazione è detta riflessiva se e solo se per ogni elemento di un insieme, quest’elemento è in relazione

con sé stesso Tutti gli elementi si trovano sulla diagonale

∈ , ℛ. ∆().

∀

Esempi: nella vita reale le amicizie, il parallelismo, la tolleranza e l’uguaglianza sono relazioni riflessive.

L’area interna del sottoinsieme è una relazione riflessiva.

ℛ

ℛ Es: . Se in ci fosse stato

{ }, {( )}

: = , , ℛ: = , ), (, ), (,

∆()

anche l’elemento allora non sarebbe stata riflessiva perché la

ℛ

condizione deve valere per ogni elemento di .

RELAZIONE ANTIRIFLESSIVA

Una relazione è detta antiriflessiva

ℛ ⇔ ∆() ∩ ℛ = ∅.

Una relazione è detta antiriflessiva se e solo se per ogni elemento di un insieme, quest’elemento NON è in

relazione con sé stesso Nessun elemento si trova sulla diagonale

∀ ∈ , ¬ℛ. ∆().



ℛ L’area interna del sottoinsieme è una relazione antiriflessiva.

ℛ

Es: . Se in ci fosse stato

{ }, {( )}

: = , , ℛ: = , ), (, ), (,

∆()

anche un solo elemento sulla diagonale non sarebbe stata

antiriflessiva perché la condizione deve valere per ogni elemento di .

RELAZIONE NÉ ANTIRIFLESSIVA NÉ RIFLESSIVA

Una relazione si dice né riflessiva né antiriflessiva se e solo se esistono alcuni elementi che fanno parte

della diagonale e altri no.

∆()

ℛ L’area interna del sottoinsieme è una relazione né riflessiva né

ℛ

∆() antiriflessiva.

Es: .

{ }, {( )}

: = , , ℛ: = , ), (, ), (,

RELAZIONE SIMMETRICA −1

Una relazione è detta simmetrica

ℛ ⇔ ℛ = ℛ.

−1 −1

è l’insieme inverso di perciò .

{(1,2), (5,6)}, {(2,1), (6,5)}

ℛ, ℛ: = (3,4), ℛ : = (4,3),

ℛ 

Una relazione è detta simmetrica se e solo se comunque presi una coppia di elementi appartenenti

(, )

ad un insieme se la prima coordinata è in relazione con la seconda indica che la seconda è in

,

relazione con la prima ∀(, ) ∈ , ℛ ⟶ ℛ.



∆() L’area interna del sottoinsieme è una relazione simmetrica, infatti,

ℛ

ℛ il grafico è simmetrico alla diagonale.

Es: .

{ }, {( )}

: = , , ℛ: = , ), (, ), (, ), (,

La condizione deve valere per ogni elemento di .

RELAZIONE ASIMMETRICA −1

Una relazione è detta asimmetrica

ℛ ⇔ ℛ ∩ ℛ ⊆ ∆().

Una relazione è detta asimmetrica se e solo se comunque presi due elementi appartenenti ad un

(, )

insieme se il primo è in relazione con il secondo, ma quindi il secondo non è in relazione con il primo

, 

∀(, ) ∈ , ℛ ⟶ ¬ℛ.

∆() L’area interna del sottoinsieme è una relazione asimmetrica, infatti,

ℛ

ℛ il grafico non è simmetrico alla diagonale.

Es: .

{ }, {( )}

: = , , ℛ: = , ), (, ), (,

La condizione deve valere per ogni elemento di

RELAZIONE NÉ SIMMETRICA NÉ ASIMMETRICA

Una relazione si dice né simmetrica né asimmetrica se e solo se esistono solo alcuni elementi che sono (o

non sono) in relazione tra loro.

RELAZIONE TRANSITIVA

Una relazione è detta transitiva (, (, (,

ℛ ⇔ ) ∈ ℛ ⋀ ) ∈ ℛ ⇒ ) ∈ ℛ.

Una relazione è detta transitiva se e solo se per ogni gruppo di tre elementi (terna) appartenenti

(, , )

ad un insieme se è in relazione con e è in relazione con allora deve essere in relazione con

, ,

∀(, , ) ∈ , ℛ, ℛ ⟶ ℛ.

 ℛ L’area interna del sottoinsieme è una relazione transitiva, infatti, il

ℛ

primo pallino è in relazione con il terzo perché lo è anche il secondo.

Es: .

{ }, {( }

: = , , ℛ: = , ), (, ), (,

La condizione deve valere per ogni elemento di

∆()

Relazione di equivalenza

Una relazione binaria in un insieme che gode delle tre proprietà:

ℛ

1. Riflessiva.

2. Simmetrica.

3. Transitiva.

è detta relazione di equivalenza in Un’ esempio di relazione di equivalenza è l’uguaglianza. Infatti,

.

l’uguaglianza è una relazione dotata di quelle tre proprietà.

Esempio x = y, y=z. Allora x sarà = z. Se x=3 ed è = y anche y è = 3 e se y è = z allora anche z = 3. Quindi x=



e z=3, cioè x=z.

Relazioni d’ordine

Una relazione in un insieme che gode delle due proprietà:

ℛ

1. Riflessiva.

2. Transitiva.

è detta relazione di preordine in .

Una relazione in un insieme che gode delle tre proprietà:

ℛ

1. Riflessiva. E quindi deve essere un preordine.

2. Transitiva.

3. Antisimmetrica.

è detta relazione di ordine o di ordine parziale in Introduce il concetto di diseguaglianza: ≤, ≥, <, >. Una

.

relazione d’ordine si dice parziale qualora non fosse possibile mettere in relazione ogni elemento di .

Una relazione in un insieme che gode delle tre proprietà:

ℛ

1. Riflessiva.

2. Transitiva. E quindi deve essere un ordine.

3. Antisimmetrica.

4. Tricotomia.

è detta relazione di ordine totale in Una relazione d’ordine si dice totale qualora tutti gli elementi di si

.

possano mettere in relazione.

Ordinamenti 2

Per esempio, sia .

{(, }

≠ 0, × = ∶= ): (, ) ∈

2 è una proprietà o relazione su

ℛ ⊆ .

ℛ

è un ordine o ordinamento su se solo se è riflessiva,

ℛ

simmetrica e transitiva.

Relazione d’ordine:

• (, ) ∈ ℛ ⟺ ≤

• < ⟺ (, ) ∈ ℛ ⋀ (, ) ∉ ∆()

Ordine inverso: −1

• (, ) ∈ ℛ ⟺ ≥

−1

• > ⟺ (, ) ∈ ℛ ⋀ (, ) ∉ ∆()

I simboli indicano un ordinamento. Le definizioni dell’ordinamento inverso sono definite

<, ≤

implicitamente dato che per ogni ordine sulle coppie (, ):

• ≤ ⇝ ≥ ⇔ ≤

• < ⇝ > ⇔ <

L’insieme munito di un ordine è un insieme ordinato, cioè un insieme dotato di una relazione d’ordine.

≤

è un insieme detto parzialmente ordinato o POSET.

{ }

∶= , ≤

Un ordinamento su è detto totale se si verifica la proprietà di tricotomia.

tricotomica

Una relazione è se è vero uno e uno solo dei tre fatti:

● ● ●

< > =

Quindi, è un insieme detto totalmente ordinato o CATENA, se e solo se possiede la proprietà

{ }

∶= , ≤

di tricotomia. Per esempio:

L’insieme dei numeri naturali o l’insieme dei caratteri del nostro alfabeto sono totalmente ordinati.

ℕ …

… a d

0 3 e

4 b c

1 2

Esistono degli insiemi parzialmente ordinati che non sono anche totali, ma tutti gli ordini totali sono anche

parziali. Per esempio:

Sia , considero l’insieme delle parti . In introduco la

{ } { }, { }, { }�

�∅,

∶= , () ∶= , ()

relazione di inclusione classica tra insiemi. Questa relazione diventa un ordine su è un

((),

(). ⊆)

insieme parzialmente ordinato. Andiamo a rappresentarlo graficamente.

Diagramma di Hasse:

{ }

∶= , Come possiamo vedere, gli elementi

{ } { }

e non sono confrontabili e quindi è

{ } { } ((),

⊆)

un POSET ma non è totalmente ordinato.

∅ diagramma di Hasse

Nella teoria degli ordini, il è un modo per rappresentare graficamente un insieme

finito parzialmente o totalmente ordinato. In sostanza, dato un insieme S, si rappresenta ogni membro di S

come vertice e si traccia una linea che va da x a y se x < y e non esiste z tale che x < z < y. In questo caso si

dice che y copre x o che y è un successore immediato di x. Inoltre, è richiesto che i vertici siano posizionati

in modo che ogni segmento incontri esattamente due vertici: i due estremi. Ogni diagramma di questo tipo

(poiché i vertici sono etichettati) determina unicamente un ordinamento parziale ma esistono più

diagrammi corrispondenti ad un dato ordine.

Ordine indotto

Sia a un insieme in cui è introdotta una relazione d’ordine . Prendendo un sottoinsieme

{ }

∶= , ≤

si può allora dire che anche è dotato di una relazione d’ordine . Questo avviene

{ }

( ⊆ ), ∶= , ≤

perché l’ordine in è indotto, cioè è stato ereditato dall’insieme

.

Possiamo affermare che, i sottoinsiemi ordinati sono totali se anche l’insieme è totale, e che un

sottoinsieme è ordinato se anche l’insieme è ordinato.

Insieme limitato

Sia un insieme ordinato. Preso un sottoinsieme possiamo affermare che:

(

⊆ )

Un elemento è un minorante di

• ∈ �� ≤ , ∀ ∈ .

�� ≤ , ∀ ∈ .

Un elemento è un maggiorante di

• ∈ b

a Y

X

Si dice che:

è limitato inferiormente un minorante di su

• ⇔ ∃ .

è limitato superiormente un maggiorante di su

• ⇔ ∃ .

è limitato in contemporaneamente minor