Contenuto
Funzioni iniettive, suriettive, invertibili. Q `e numerabile.
R non `e numerabile.
Q `e denso in R.
Federico Lastaria. Analisi e Geometria 1. Funzioni. Insiemi numerabili. Q denso in R. 1/17
Funzioni
x f (x )
A B
f
Definizione
Una funzione A−→ B consiste dei seguenti tre dati:f
1 Un insieme A, detto dominio di f , e denotato dom(f );
2 Un insieme B, detto codominio di f , e denotato codom(f );
3 Una legge che a ogni elemento x ∈ A associa esattamente un
Immagine di un sottoinsieme S ⊆ A
Definizione
Data A −→ B, l’f immagine di f (denotata Im(f ) o f (A)) `e
Im(f ) = f (A) = {y ∈ B | ∃x ∈ A f (x ) = y } Se S ⊆ A, l’immagine di S tramite f `e f (S ) = {y ∈ B | ∃x ∈ S f (x ) = y } In breve: f (S ) = {f (x ), x ∈ S } Esempio 1. A B S f (S ) f Esempio 2. R \ {0} −→ R,f x → f (x ) = 1x ∀x ∈ dom(f ) Se S = (0, +∞), f (S ) = (0, +∞)
Federico Lastaria. Analisi e Geometria 1. Funzioni. Insiemi numerabili. Q denso in R. 3/17
Definizione (Funzioni inettive, suriettive, bi-iettive)
Una funzione A−→ B `f e:
iniettiva se `e soddisfatta la condizione:
∀x, x0 ∈ A f (x ) = f (x0) =⇒ x = x0
In altri termini: f `e iniettiva se, e solo se, per ogni y ∈ B, esiste al pi`u un x in A tale che f (x ) = y .
suriettiva se `e soddisfatta la condizione:
∀y ∈ B ∃x ∈ A f (x ) = y
In altri termini: f `e suriettiva se, per ogni y ∈ B, esiste
almeno un x in A tale che f (x ) = y , ovvero se, e solo se, Im(f ) = codom(f ).
bi-iettiva (o invertibile) se `e sia iniettiva, sia suriettiva:
Esempi
A B f f iniettiva, non suriettiva A B g g suriettiva, non iniettiva. A B hh sia suriettiva, sia iniettiva. (bi-iettiva, o invertibile)
Federico Lastaria. Analisi e Geometria 1. Funzioni. Insiemi numerabili. Q denso in R. 5/17
Esercizi
Denotiamo con [n] = {1, 2, 3, ..., n} un insieme con n elementi.
Esercizio
1 Contare tutte le funzioni da [n] a [m].
2 Contare tutte le funzioni iniettive da [k] a [m].
3 Contare le funzioni invertibili da [n] a [n].
Esercizio
Contare i k-sottoinsiemi (sottoinsiemi con k elementi) di [m].
Esercizio
Insiemi numerabili
Definizione (Insieme numerabile)
Si dice che un insieme S `e numerabile, o che ha la stessa
cardinalit`a di N, se esiste una funzione bi-iettiva (o invertibile; cio`e
iniettiva e suriettiva) N −→ S.f
Esercizio
Dire se sono numerabili:
1 I numeri positivi pari: A = {0, 2, 4, 6, ...}.
2 I numeri interi relativi pari: B = {.... − 6, −4, −2, 0, 2, 4, 6, ...}. 3 I numeri positivi dispari: C = {1, 3, 5, 7, ..., }.
4 I quadrati perfetti: D = {0, 1, 4, 9, ....}.
(Risposta: Sono tutti numerabili.)
Federico Lastaria. Analisi e Geometria 1. Funzioni. Insiemi numerabili. Q denso in R. 7/17
Q `
e numerabile
Teorema
Dimostrazione. (Q `
e numerabile.)
Ordiniamo i numeri razionali positivi in questo modo:
.. 5 1 4 1 3 1 2 1 1 1 .. 5 2 4 2 3 2 2 2 1 2 .. 5 3 4 3 3 3 2 3 1 3 .. 5 4 4 4 3 4 2 4 1 4 .. 5 5 4 5 3 5 2 5 1 5 .. 5 6 4 6 3 6 2 6 1 6 · · · · · · · · · · · · · · · Aggiungiamo lo zero e eliminiamo i numeri che figurano gi`a in precedenza. Otteniamo:
0 1 2 3 4 5 6 7 8 9 10 11 ... ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ... 0 1 1 1 1 2 2 1 3 1 1 3 1 4 2 3 3 2 4 1 5 1 1 5 ...
Federico Lastaria. Analisi e Geometria 1. Funzioni. Insiemi numerabili. Q denso in R. 9/17
Dimostrazione. (Q `
e numerabile; continuazione)
Ora modifichiamo la successione che abbiamo trovato
0 1 2 3 4 5 6 7 8 9 10 11 ... ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ... 0 1 1 1 1 2 2 1 3 1 1 3 1 4 2 3 3 2 4 1 5 1 1 5 ...
introducendo i razionali negativi:
0 1 2 3 4 5 6 7 8 9 10 11 ... ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ... 0 1 1 1 − 1 1 1 2 − 1 2 2 1 − 2 1 3 1 − 3 1 1 3 − 1 3 1 4 ...
In questo modo abbiamo costruito una funzione bi-iettiva
f
Teorema (G. Cantor, 1890. Prima dimostrazione.)
L’insieme R dei numeri reali non `e numerabile.
Dimostrazione. Supponiamo che R sia numerabile. Sia x1, x2, x3, x4, x5, x6, ...
una successione (una “lista”) che elenchi tutti i numeri reali.
1) Troviamo un intervallo compatto I1 che non contenga x1.
2) Dentro I1, troviamo un sottointervallo compatto I2 che non
contenga x2.
.. .
k) Dentro Ik−1, troviamo un sottointervallo compatto Ik che non
contenga xk, eccetera. (Continuiamo “all’infinito”.)
L’intersezione I = ∩In, n ∈ N non `e vuota (Teorema degli intervalli
inscatolati), ma se c ∈ I , allora c non `e nella lista. (Per assurdo,
supponiamo c ∈ I e c = xk per un qualche k. Per costruzione,
c = xk ∈ I/ k. Quindi c = xk non sta nell’intersezione I di tutti gli
In). Contraddizione.
Federico Lastaria. Analisi e Geometria 1. Funzioni. Insiemi numerabili. Q denso in R. 11/17
Teorema (G. Cantor. Argomento diagonale)
L’insieme R dei numeri reali non `e numerabile.
Basta provare che [0, 1] non `e numerabile. Supponiamo il contrario, e sia N−→ [0, 1] una funzione bi-iniettiva:f
1 ↔ f (1) = 0.α11α12α13...α1n... 2 ↔ f (2) = 0. α21α22α23...α2n... ...
n ↔ f (n) = 0. αn1αn2αn3...αnn... ...
Questo significa che ogni numero reale in [0, 1] figura una volta
(suriettivit`a) e una sola (iniettivit`a) nella colonna di destra. Definiamo b = 0.β1β2· · · βn· · · ∈ [0, 1], ponendo:
βn =
(
7 se αnn `e una delle cifre 0, 1, 2, 3, 4, 3 se αnn `e una delle cifre 5, 6, 7, 8, 9.
Q `
e denso in R. (Prima forma.)
La propriet`a di Archimede implica la densit`a di Q in R, ossia il
fatto che ogni numero reale pu`o essere approssimato, con arbitraria
precisione, con numeri razionali.
Teorema (Q `e denso in R)
Per ogni a, b ∈ R, a < b, esiste un numero razionale r tra essi compreso:
a < r < b
Federico Lastaria. Analisi e Geometria 1. Funzioni. Insiemi numerabili. Q denso in R. 13/17
Dimostrazione. (Q denso in R. Prima forma.)
Dimostrazione Ci sono tre casi.
Primo caso: 0 ≤ a < b. Scegliamo n ∈ N tale che
n(b − a) = nb − na > 1 (Esiste per Archimede). Siccome nb e na
distano pi`u di 1, deve esserci (almeno) un numero intero positivo
m tra nb e na: na < m < nb. Dividendo per n, si ha a < mn < b. Secondo caso: a < b ≤ 0. Ci si riconduce al primo caso
scambiando i segni:0 ≤ −b < −a. Esiste allora un razionale m/n tale che −b < mn < −a. Dunque, a < −mn < b
Terzo caso: a < 0 < b. Basta prendere il numero 0, che `e
Q `
e denso in R. (Seconda forma.)
Teorema (Q `e denso in R)
Ogni numero reale `e limite di una successione di razionali. (Di pi`u,
`e limite di una successione di numeri decimali.)
Esempio. Il numero irrazionale
π = 3, 141592653589793... (1)
`e il limite della successione (yn) di numeri razionali (decimali): y0 = 3 y1 = 3.1 y2 = 3.14 y3 = 3.141 y4 = 3.1415 ... = ... Poich´e |π − yk| ≤ 1 10k, si ha: limn→+∞yn = π.
Federico Lastaria. Analisi e Geometria 1. Funzioni. Insiemi numerabili. Q denso in R. 15/17
Dimostrazione. (Q denso in R. Seconda forma.)
Dimostrazione Il numero reale
α = a0. a1a2a3a4a5... (2)
`e il limite della successione (yn) di numeri razionali (decimali): y0 = a0
y1 = a0. a1 y2 = a0. a1a2
. = ...
yk = a0. a1a2a3...ak... Poich´e |α − yk| ≤ 101k, si ha: limn→+∞yn = α.
Esercizi
Esercizio
Dimostrare che l’insieme dei numeri irrazionali R \ Q `e denso in R. (Suggerimento. Siano a, b ∈ R, a < b. Per la densit`a di Q in R, esiste r ∈ Q tale che a/√2 < r < b/√2.)
Esercizio
In ogni intervallo [a, b], a, b ∈ R, a < b, ci sono infiniti numeri razionali e infiniti numeri irrazionali.