Corso di Matematica Discreta I Anno Gabriella Muratore.

Corso di Matematica DiscretaI Anno

Gabriella Muratore

Programma

1. Insiemi e Funzioni

2. Equivalenze ed ordinamenti

3. Numeri interi

4. Calcolo Combinatorio

5. Introduzione ai Grafi

Introduzione

Connettivi logici E (AND) congiunzione O (OR) disgiunzione NON (NOT) negazione

Connettivo condizionale Se ….. Allora…. P D ( connettivo implicazione)

Se è vera P e se è vera P D allora è vera DLa proposizione P D è falsa solo se P è vera e D è

falsa

P ipotesi - D tesi

Notazione

N = Insieme dei numeri interi naturali 1,2,3,… (con o

senza zero, 0) (N+, N0. = Insieme dei numeri interi relativi (compreso lo zero)

…-3,-2,-1,0,1,2,3 …. Z+, Z-.

Q = Insieme dei numeri razionali …3/4, 2/3 … R o = Insieme dei numeri reali.

C= Insieme dei numeri complessi

E’ N Z Q R C

IntroduzioneDimostrazione per assurdo: P (ipotesi)D (tesi)Assumere vera l’iposi e falsa la tesi. Se il ragionamento logico deduttivo ci porta ad una

contraddizione abbiamo dimostrato che P (ipotesi)D (tesi).Doppia Implicazione (se e solamente se)P D equiv (PD ) E (D P) P è condizione necessaria e sufficiente perché accada D. PD : P è sufficiente perché accada D e D P : P è condizione necessaria perché accada DP D è vera se e solamente se P e D sono entrambe

vere o entrambe false

Introduzione

Quantificatori (esiste) quantificatore esistenziale (per tutti- per ogni) quantificatore universale

Connettori / oppure : tale che x / P(x) significa

“esiste almeno un x tale che il predicato P è vero”

x P(x) significa “ per tutti gli x il predicato P è vero”

Esempi: x / x2 1 (è vera) mentre x x2 1 (è falsa)

x x2 0 (è vera) mentre x / x2< 0 (è falsa)

Introduzione

Importanza dell’ ordine dei quantificatori.

Esempio

Supponiamo che L(x,y) significhi: la persona x è

in grado di svolgere il lavoro y y x / L(x,y) significa: “qualunque sia il

lavoro, esiste una persona in grado di svolgerlo“

x y / L(x,y) significa: “ esiste una persona che è in grado di svolgere qualunque lavoro“

Introduzione

Negazione e quantificatori

non ( x P(x)) x / ( non P(x))

non ( x / P(x)) x ( non P(x))

Uguaglianza x=y

L’uguaglianza è una relazione (predicato tra due

variabili) che esprime il fatto che x e y sono

intercambiabili a tutti gli effetti.

Introduzione

Uguaglianza

Se R è un qualunque predicato in una variabile allora è

vero che:

x y / x=y (R(x) R(y) )

Proprietà dell’Uguaglianza

x x=x (proprietà riflessiva)

x y x = y y = x (proprietà simmetrica)

x y z (x=y) e (y=z) x=z (proprietà transitiva)

Insiemi

Assumiamo il concetto di insieme come

“nozione primitiva”.

Es. Insieme degli alunni di questa classe; insieme dei numeri interi; insieme delle rette del piano; ecc.

Sinonimi: aggregato, classe, famiglia, …

Insiemi

L’espressione x T si legge: “ x appartiene all’insieme T” o “ x è un elemento di T”

Scriveremo invece x T per negare l’espressione

precedente cioè per affermare che x non appartiene a (o

non è un elemento di) T.

L’intuizione ci suggerisce di considerare uguali due

insiemi che abbiano gli stessi elementi. In simboli:

( x x A x B ) A=B

Insiemi

Il significato che abbiamo dato al segno di uguaglianza ci assicura che due insiemi aventi gli stessi elementi devono avere il medesimo ruolo in tutte le enunciazioni che fanno parte della nostra teoria. Per indicare un insieme basterà (quando è possibile) elencarne gli elementi; converremo di elencarli entro parentesi graffe. Ad esempio 2,5,6 indica l’insieme i cui elementi sono appunto i numeri 2,5 e 6. La notazione a indica l’insieme costituito dal solo elemento a ; mentre con il simbolo indicheremo uno speciale insieme, detto insieme vuoto, che non contiene alcun elemento.

InsiemiRelazione di Inclusione

Se ogni elemento di un insieme A è un elemento

dell’insieme B, cioè: x: xA x B, allora diciamo

che A è contenuto in B, oppure A è una parte o un

sottoinsieme di B, e scriviamo A B.

A B

Notiamo che la relazione A B è verificata nel caso in cui A=B. Peresprimere il fatto che A B ma èAB, cioè esistono elementi di B che non sono elementi di A, si scrive A B. Si dice in questo caso

che A è sottoinsieme proprio di B, ovvero A è propriamente contenutoin B

Costruzioni InsiemisticheProcedimenti che, partendo da insiemi assegnati, ci

forniscono nuovi insiemi.

Supponiamo che T sia un insieme e che P(x) sia una

proprietà che ha senso per gli elementi di T. Scriviamo

allora x: (xT) e P(x) per indicare il sottoinsieme di T

formato dagli elementi per cui P(x) è vera.

Es. x: (xR) e (sin x=0) rappresenta l’insieme dei

multipli interi di .

Operazioni insiemistiche

Unione

L’unione di due insiemi A e B è l’insieme formato da

quegli elementi che appartengono ad almeno uno dei due

insiemi A,B. Esso viene indicato con A B.

In simboli A B = x: (xA) o (xB) .def

A

BEs. A= 1,3,5,7,9 B= 2,3,4,5,6,8

A B=C= 1,2,3,4,5,6,7,8,9


Intersezione

L’intersezione di due insiemi A e B è l’insieme formato

dagli elementi che appartengono sia ad A sia a B. Esso si

indica con il simbolo A B. In simboli

A B = x: (xA) e (xB) .def

A

B Es. A= 1,3,5,7,9 B= 2,3,4,5,6,8A B=C= 3,5

Può accadere che i due insiemi siano disgiunti (cioè non abbiano alcun elemento in comune. Allora si scrive A B=

A B


Differenza

La differenza di B da A, che si indica con A\B oppure

con A-B, è l’insieme degli elementi di A che non

appartengono a B. In simboli A-B= x: (xA) e (xB).def

A

B Es. A= 1,3,5,7,9 B= 2,3,4,5,6,8A - B=C= 1,7,9


Differenza simmetrica

La differenza simmetrica A e B, che si indica col simbolo

AB, è l’insieme costituito dagli elementi che appartengono

a uno solo degli insiemi A e B, cioè dagli elementi di A che

non appartengono a B e dagli elementi di B che non

appartengono ad A. In simboli

A B=(A-B) (B-A)def

A

B

Es. A= 1,3,5,7,9 B= 2,3,4,5,6,8A B=C= 1,2,4,6,7,8,9

Insieme delle parti

Dato un insieme T, ammettiamo di poter considerare un insieme i cui elementi sono tutte le parti o sottoinsiemi di T; questo insieme sarà detto Insieme delle parti di T e si indicherà con il simbolo P(T). Ad esempio, se è

T=a,b,c si ha P(T)= , a, b, c, a,b, a,c, b,c, a,b,c.

Le operazioni e , nell’insieme P(T), hanno proprietà formali molto interessanti.

Proprietà formali di e

1. A A = A Proprietà di Idempotenza A A = A

2. AB = BA Proprietà Commutativa AB = BA

3. (AB) C= Proprietà Associativa (A B) C=

=A (B C) =A (B C)

4. A (B C)= Proprietà Distributiva A (B C)=

=(A B) (A C) =(A B) (A C)

5. A(A B)=A Proprietà di Assorbimento A(AB)=A


Complementare

Se A P(T), chiamiamo complementare di A rispetto a T

l’insieme di tutti gli elementi di T che non appartengono

ad A. In simboli A= T-A.

Valgono le seguenti proprietà.

6. (A) =A

7. (A B)= A B8. (A B) =A B

def

Algebra di Boole

Si dice Algebra di Boole la struttura che si ottiene assegnando in un insieme (nel nostro caso P(T)) tre operazioni: , , (unione, intersezione e complemento)aventi le proprietà 1-8 precedentemente definite.Notiamo che le proprietà 1-8 valgono anche per la logica delle proposizioni, pur di sostituire il simbolo con il connettivo logico “o”, il simbolo con il connettivo logico “e”, il simbolo con il connettivo logico “non” ed Infine il simbolo = con il connettivo logico di doppia implicazione

Famiglie Infinite di Insiemi

Le operazioni di unione ed intersezione si possono estendere al

caso di famiglie infinite di insiemi. Sia F una famiglia qualunque

di insiemi. Si indica con l’insieme costituito dagli elementi

che appartengono a qualcuno degli insiemi XF. Questo insieme

viene detto insieme unione della famiglia F. In simboli:

= x: ( X / X F e x X). Similmente si indica

con l’insieme costituito dagli elementi che appartengono a

ciascuno degli insiemi XF. Questo insieme viene detto insieme

intersezione della famiglia F. In simboli:

= x: ( X / X F x X).

FX

X

FX

X

FX

X

FX

X

ConsiderazioniSia T un insieme e sia P(x) un predicato che abbia senso in T.

Possiamo interpretare P(x) come un’equazione posta in T.

L’insieme P=x: (xT) e P(x) è evidentemente l’insieme delle

soluzioni di P(x) in T. Sia ora Q(x) un secondo predicato e sia

Q=x: (xT) e Q(x). Se per ogni xT è vero P(x) Q(x) allora

si ha PQ.

Se invece, per ogni xT è vero P(x) Q(x) si ha P=Q.

Es. Sia T=R (retta reale).Supponiamo che P(x) significhi =2x

e che Q(x) significhi x2+1=4 x2. Allora per ogni x R è vero

P(x) Q(x). Si ha quindi PQ. E’ poi Q= ; - ma

poiché - non verifica P(x) si ha P=

3

13

1

12 x

3

1

3

1

Insieme prodotto

Assumiamo come nozione primitiva la nozione di coppia

ordinata. Per aiutare l’intuizione possiamo pensare a due caselle

(la prima e la seconda casella) e di inserire in esse,rispettivamente,

due elementi, non necessariamente distinti, x e y. Per indicare la

coppia così ottenuta useremo la notazione (x,y). E’ importante

notare come la coppia (x,y) sia cosa ben diversa dall’ insieme x,y

costituito dagli elementi x e y. Infatti si ha x,y = y,x

(per gli insiemi non ha rilevanza l’ordine con cui sono elencati gli

elementi), mentre per le coppie si ha:

(x,y)=(x,y) x= x e y= y.

Insieme prodottoInsieme Prodotto. Def.

Siano dati due insiemi A e B. Diremo insieme prodotto di A per B,

e lo indicheremo con A B, l’insieme di tutte le coppie ordinate

(x,y) con x A e y B. In simboli:A B = (x,y) / x A e y B.

Notiamo che non abbiamo richiesto ai due insiemi A e B di essere

diversi. Un ben noto esempio di prodotto è , dove indica

la retta reale. La geometria analitica ci insegna a rappresentare il

piano mediante l’insieme di tutte le coppie ordinate di numeri

reali, cioè mediante .

def

O x

y (x,y)Perciò l’insieme , che comunemente viene scritto come2, viene detto anche piano (numerico).

Insieme prodotto

Dati, in un certo ordine, tre insiemi A, B, C, si chiama loro prodotto, e si indica con A B C, l’insieme di tutte le terne ordinate (x,y,z) con x A, y B, zC. La definizione si estende in modo ovvio al caso di un

numero finito qualsiasi di spazi, A1, A2,… An. Ad esempio si indica con n l’insieme di tutte le n-uple

ordinate (x1, x2… xn) di numeri reali. Il prodotto di più insiemi può essere introdotto, peraltro, utilizzando solo la nozione di prodotto di due insiemi. E’ facile vedere infatti che A B C si può introdurre indifferentemente come (A B) C oppure come A (B C).

RelazioniCon il termine relazione indichiamo un predicato in 2 variabili.

Sia ora R(x,y) una relazione che abbia senso nella teoria degli insiemi. Possiamo allora considerare l’insieme (x,y): (x,y) A B e R(x,y) , cioè il sottoinsieme di A B costituito da tutte le coppie per cui la relazione è verificata. Esso viene detto grafico della relazione. Dato un sottoinsieme G di A B risulta individuata immediatamente una relazione di cui essa è il grafico: (x,y) G. Nella teoria degli insiemi, spesso, il termine “relazione” viene usato nel significato di grafico. Anche noi utilizzeremo spesso lo stesso simbolo per indicare una relazione ed il suo grafico: scriveremo perciò indifferentemente R(x,y) oppure (x,y) R.

RelazioniEsempi.a) In N N=N2 si consideri la relazione R(m,n) che significa m

è divisore di n. Il grafico di questa relazione è:

b) In R2 si consideri la relazione x2+y21. Il suo grafico è rappresentato dal cerchio con centro nell’origine degli assi e raggio 1.

n

m

1

1 2 3

2

3

4

Funzioni (o applicazioni)Definizione di Funzione (o applicazione)

Una relazione f definita in A B si dice applicazione o

funzione di A in B se per ogni x A esiste uno ed un solo

y B tale che (x,y) f .

A B

x y

f

Possiamo interpretare intuitivamente la nozione introdotta pensando che f “porti” i punti di A in punti di B.L’insieme A viene chiamato dominio di f, l’insieme B codominio di f

Funzioni (o applicazioni)I termini “funzione” e “applicazione” sono equivalenti:

tuttavia il termine “funzione” è più tradizionale e lo si

impiega di preferenza quando dominio o codominio sono

insiemi di numeri reali o complessi. L’espressione

f: AB scritta anche come AB

mette in evidenza il dominio e il codominio di f.

Per ogni x A l’unico elemento y B tale che (x,y) f si

indica con f(x) e si dice valore assunto dalla funzione f in x.

f

Ax

B

yy=f(x)

Funzioni (o applicazioni)

Partendo dall’espressione di f(x), la notazione completa che

rappresenta l’applicazione f è la seguente:

xf (x): A B . In questa espressione la lettera x è “muta” e

può essere sostituita con un’altra lettera qualsiasi. Spesso, però,

questa notazione (che è evidentemente ingombrante) può venire

più o meno abbreviata, se non vi sono equivoci. Spesso la funzione

si indica semplicemente con un’ espressione f(x), dove appunto è

sottointeso che la lettera x ha il ruolo di “variabile indipendente”.

Ad esempio si potrà parlare della funzione x2+1 in luogo di

x x2+1 : .


In certi casi si usa indicare il valore di un’applicazione scrivendo

la variabile indipendente come indice: fx anziché f(x). Ad esempio

se il dominio dell’applicazione è l’insieme N degli interi naturali,

l’applicazione viene detta successione; i valori di una successione

a (ma più frequentemente si parla dei termini della successione)

sono indicati con la notazione: a0, a1,… an,…

Le nozioni di funzione di variabile reale e di successione, che nei

testi matematici più recenti sono comprese nella nozione generale

di applicazione, venivano un tempo considerate come diverse: ciò

spiega la difformità di notazione, che è rimasta.


Esempi

a) Dato un qualunque insieme A, l‘ applicazione xx : A A si dice applicazione Identica di A e si indica con IA.

b) Dato l’insieme A ed un suo sottoinsieme B, l’applicazione

xx : B A si dice applicazione di Inclusione di B in A.

c) Siano A e B insiemi qualunque; l’applicazione

(x,y)x : A B A si dice proiezione canonica su A.

Similmente l’applicazione (x,y)y : A B B si dice

proiezione canonica su B.


Data un’applicazione f:AB e dato un sottoinsieme X di A si dice immagine di X il sottoinsieme di B costituito dagli elementi che provengono da qualche elemento di X. Questo sottoinsieme viene indicato con f(X). Pertanto:f(X)=y: y B e ( x X / f(x)=y. Si potrà anche scrivere, più brevemente: f(X)= f(x): x X . L’insieme f(A) si dirà immagine dell’applicazione f.

Applicazione CostanteUn applicazione f: AB si dice costante se la sua

Immagine consta di un unico elemento (cioè x1 A,

x2 A si ha f(x1)= f(x2).

def


Definizione di Applicazione Surgettiva

Un’ applicazione f:AB si dice Surgettiva se è f(A)=B

cioè se l’immagine di f coincide con B.

Se f:AB è surgettiva si usa dire che f è un’applicazione

di A su B.

Esempi

L’applicazione identica in un qualunque insieme; le

proiezioni canoniche del prodotto


Definizione di Applicazione Iniettiva

Un’ applicazione f:AB si dice Iniettiva se porta punti

distinti in punti distinti. In altre parole:

f è iniettiva ( x1 A, x2 A : f(x1)= f(x2) x1= x2)

Esempi

L’applicazione identica in un qualunque insieme,

l’applicazione di inclusione di un sottoinsieme in un

insieme

def


Definizione di Applicazione Biiettiva

Un’ applicazione f:AB si dice Biiettiva se è sia

iniettiva sia surgettiva.

Esempi.

L’applicazione identica in un insieme qualsiasi è biiettiva

L’applicazione xax+b: R R è biiettiva se è a 0.

Quando invece a =0 abbiamo un’applicazione costante

che non è iniettiva né surgettiva.


Molte volte non è necessario specificare il dominio ed il codominio di un’ applicazione, essendo sufficiente conoscere un’espressione che la definisce. Certe volte, però, la precisazione del dominio e del codominio è essenziale: per esempio, ovviamente, quando ci si chiede se un’applicazione è iniettiva e/o surgettiva. Ad esempio (indicando con R+ l’insieme dei numeri reali non negativi, ) l’applicazione xx2: R R non è iniettiva né surgettiva, l’applicazione xx2: R R+ è surgettiva ma non iniettiva, l’applicazione xx2: R+ R è iniettiva ma non surgettiva ed infine l’applicazione xx2: R+ R+ è sia iniettiva sia surgettiva cioè è una biiezione.


Spesso è comodo rappresentare gli insiemi come

immagini di opportune applicazioni. Ad esempio

l’insieme degli interi naturali pari si potrà indicare con

P= 2n : nN cioè P=g(N) dove g: NN n 2n. Sia

ora F una famiglia di insiemi, J un insieme e supponiamo

che esista un’applicazione j Xj : J F surgettiva.

Allora si possono impiegare le seguenti notazioni per

indicare l’insieme unione e l’insieme intersezione di F:

oppure ; oppure FX

X

Jj

jX

FX

X

Jj

jX

Funzioni (o applicazioni)Definizione di Applicazione Composta

Date due applicazioni f:AB e g:B’C con B B’ si dice

Applicazione composta di f e g l’applicazione g f così definita:

g f= x g(f (x)) : A C.

Nel simbolo g f (equivalentemente g(f (x))

si scrive a destra l’applicazione che viene eseguita per prima.

def

A

B C x

f(x)g(f(x))

fg


Esempio:

L’applicazione x : R R si può considerare

come composta con l’applicazione xx2+1 : R R+

e l’applicazione y: R+ R.

Se è f:AB si ha f IA=f e IB f=f dove IA e IB sono le

applicazioni identiche di A e di B rispettivamente.

12 x

y


La composizione di applicazioni gode della proprietà

associativa: se f e g sono componibili e se g e h sono

componibili si ha h (g f )= (h g) f . Basta infatti

notare che si ha (h (g f ))(x)=(h(g( f (x)))=((h g) f) (x)

Se f è un’applicazione di un insieme A in sé si possono

considerare le iterate di f, cioè le applicazioni f f ,

f f f, ecc. Si possono anche indicare con i simboli f2, f3,

ecc.


Definizione di Applicazione Inversa

Data un’applicazione f:AB si chiama inversa della f

un’ applicazione g:BA tale che g f = IA e f g= IB.

Non sempre un’applicazione è invertibile cioè esiste la

sua inversa

Per esempio l’applicazione costante non è ovviamente

invertibile. Daremo adesso una caratterizzazione delle

applicazioni invertibili.

Funzioni (o applicazioni)Teorema Sia f un’applicazione f:AB . Allora f è invertibile se e solamente se f è biiettiva.Dim. Supponiamo che f ammetta inversa, g. Dimostriamo che f è surgettiva. Infatti y B si ha f(g(y))=y. Dunque esiste un elemento di A, x=g(y) tale che f(x)=y.

Dimostriamo che f è iniettiva. Sia quindi f(x1)= f(x2)=y. Allora è

x1= g(f(x1))= g(y) e x2= g(f(x2))= g(y). Dunque x1= x2. Supponiamo adesso che f sia biiettiva. Essendo f surgettiva y B esiste qualche x tale che f(x)=y. Ma essendo f anche iniettiva questo x è unico. Quindi è ben individuata un’applicazione g:BA che fa corrispondere a y l’unico


elemento x A tale che f(x)=y. Dunque per ogni y B è

f(g(y))=y cioè f g= IB. Inoltre per ogni x A è anche

g(f(x))=x cioè g f = IA. cvd.

Teorema

L’applicazione inversa di un’applicazione f:AB, se

esiste, è unica.

Dim.

Supponiamo dunque che g e g siano applicazioni BA

tali che g f = IA e f g= IB. e g f = IA e f g = IB..

Funzioni (o applicazioni)Per la proprietà associativa della composizione si ha:

(g f) g = g ( f g). Ma è g f = IA e f g= IB.

IA g = g IB. cioè g = g .cvd

L’applicazione inversa di f si indica con il simbolo f-1.

E’ evidente che (f -1)-1=f. Dunque se f è invertibile lo è

anche la sua inversa.

Dati due insiemi A e B, se esiste un’applicazione AB

invertibile, diciamo che A e B ( senza più necessità di

considerarli in ordine) si possono mettere in corrispondenza

biunivoca.


Definizione della restrizione di un’applicazione

Data un’applicazione f:AB e dato un sottoinsieme C di

A, si dice restrizione di f a C e si indica con f |C

l’applicazione x f (x) : C B.

In altre parole, indicando con j l’applicazione di

Inclusione, C A, si ha f |C = f jdef


Data un’applicazione f:AB, abbiamo già definito l’immagine

f(X) di un sottoinsieme X di A. L’applicazione X f(X) è

un’applicazione P(A) P(B) che, benché impropriamente, verrà

indicata con il medesimo simbolo f. Ovviamente è f()= .

Analogamente si potrà introdurre un’applicazione f-1: P(B) P(A)

ponendo, per ogni YB: f-1(Y)= x: xA e f (x) Y.

L’insieme f-1(Y) si dirà immagine inversa di Y. Osserviamo che

questa applicazione, denotata (anch’essa impropriamente f-1) esiste

anche quando f non è invertibile.

E’ evidente poi che, quando Y f(A) = è f-1(Y) = .

def


Teorema

Se f è un’applicazione f:AB e X e Y sono sottoinsiemi

di A, si ha:

1. f(XY)=f(X) f(Y)

2. f(XY) f(X) f(Y)

Dim.

1. Ricordiamo che f(X)=y: y B e ( x X / f(x)=y).

Allora f(XY)= y: y B e ( x X Y / f(x)=y)=

y: y B e ( x X / f(x)=y) y: y B e ( x Y / f(x)=y)=

=f(X) f(Y). cvd


2. w f(XY) z XY / f(z)=w.z X f(z)=w f(X)z Y f(z)=w f(Y). Quindi w f(X) f(Y) cioè f(XY) f(X) f(Y) . Cvd.Teorema (Esercizio)Sia f un’applicazione f:AB e siano X e Y sottoinsiemi di B. Si ha:• f -1(X Y)= f -1(X ) f –1(Y ) • f -1(X Y)= f -1(X ) f –1(Y ) • f -1(X)= (f -1(X)) dove X indica il complementare di X in B

e, analogamente, (f -1(X)) indica il complementare di f -1(X) in A


Dim:

1. f -1(X Y)= a: aA / f (a) X Y=

= a: aA / (f (a) X) o (f (a) Y)=

= a: aA / (f (a) X) a: aA / (f (a) Y) =

= f -1(X) f -1(Y). Cvd.

2. f -1(X Y)= a: aA / f (a) X Y=

= a: aA / (f (a) X) e (f (a) Y)=

= a: aA / (f (a) X) a: aA / (f (a) Y) =

= f -1(X ) f –1(Y ). Cvd


3. f -1(X)=a: aA / f (a) X= a: aA / f (a) X=

= a: aA e a f -1(X)=a: aA e a (f -1(X)) =

= (f -1(X)) . Cvd.

Cardinalità di un insieme

Preso un nN consideriamo l’insieme degli interi che

precedono n, cioè l’insieme In=0,1,2,…n-1.

Gli insiemi In si prestano bene come insiemi campione.

Definizione.

Si dice che un insieme X è finito se esiste un nN tale

che X si possa mettere in corrispondenza biunivoca con

In; in questo caso si dice che X ha numero cardinale n e si

scrive c(X)=n. Se non esiste alcun n per cui questo è

possibile, si dice che X è infinito.

Cardinalità di un insieme

La nozione di corrispondenza biunivoca sta alla base della nozione di numero: contare significa stabilire una corrispondenza biunivoca tra un insieme di oggetti ed un insieme “campione”. Risulta molto naturale la seguente Definizione Dati due insiemi, si dice che essi hanno lo stesso numero cardinale se essi possono essere posti in corrispondenza biunivoca.Per indicare che due insiemi X e Y hanno lo stesso numero cardinale scriveremo c(X)=c(Y). Questa relazione gode della proprietà riflessiva, simmetrica e transitiva.

Principi di Somma, Prodotto e Quoziente

Il problema fondamentale che vogliamo affrontare è il

seguente: dati certi insiemi finiti (anzi: dati semplicemente

i loro numeri cardinali) calcolare il numero cardinale di

insiemi che si ottengono da essi mediante le operazioni

insiemistiche fondamentali.

Principio della Somma

Se X e Y sono insiemi finiti disgiunti si ha

c(XY)= c(X) + c(Y)

Principi di Somma, Prodotto e Quoziente

Principio del Prodotto.Se X e Y sono insiemi finiti, si ha: c(X Y)= c(X) *c(Y)Principio del Quoziente.Nell’insieme X, sia R una relazione di equivalenza tale che tutte le classi di equivalenza abbiano il medesimo numero cardinale r. Allora si ha c(X)=r*c(X/ R).Notiamo che i termini insieme prodotto ed insieme quoziente prendono nome proprio da questi principi.

Corso di Matematica Discreta I Anno Gabriella Muratore.

Documents

Transcript of Corso di Matematica Discreta I Anno Gabriella Muratore.