Matematica discreta / 4 - 09/10/2015

Note preliminari

• per la corretta visualizzazione di questa pagina occorre utilizzare un browser che supporta mathml.
• il testo di riferimento (in inglese) è Discrete mathematics di Norman L. Biggs
• sono utilizzati i seguenti caratteri, di cui si suppone che il lettore conosca il significato:
  • ℕ l'insieme dei numeri naturali
  • ∩ intersezione di insiemi
  • ∅ insieme vuoto
  • ∈ appartiene all'insieme (es. n∈ℕ significa n appartiene all'insieme dei naturali)
  • ∀ per ogni (es. n+1=n+1 ∀ n∈ℕ si legge n+1=n+1 per ogni n appartenente di naturali)
  • ∃ Esiste
  • ⇒ determina (es. a<b, b<c ⇒ a<c)
  • < minore, > maggiore, ≤ minore o uguale, ≥ maggiore o uguale, ≠ diverso

Numeri naturali

I numeri naturali sono il primo insieme, che tutti pensano di conoscere

Assioma

Un assioma è un enunciato non dimostrato, dato "per buono", che supponiamo essere sempre vero.

Teorema

Enunciato dimostrato partendo da assiomi (aggiungo io: o da altri teoremi, utilizzando un insieme di regole logiche)

Assiomi dei numeri naturali

ℕ ha due operazioni: somma (indicata sempre da +) e prodotto (indicato da x oppure · o ancora scrivendo di seguito due elementi).

In questa trattazione, il numero più piccolo contenuto in ℕ è 1 (zero è escluso). In simboli, ℕ ∩ {0} = ∅

I primi nove assiomi

1. se a, b ∈ ℕ, a+b ∈ ℕ
2. se a, b ∈ ℕ, ab ∈ ℕ
3. se a, b ∈ ℕ, a+b = b+a (proprietà commutativa della somma)
4. se a, b, c ∈ ℕ, (a+b)+c = a+(b+c) (proprietà associativa della somma)
5. se a, b ∈ ℕ, ab = ba (proprietà commutativa del prodotto)
6. se a, b, c ∈ ℕ, (ab)c = a(bc) (proprietà associativa del prodotto)
7. ℕ contiene un elemento, il cui simbolo è 1, che ha la proprietà che, n·1 = n ∀ n∈ℕ (si legge n per uno è uguale a n per ogni n appartenente ai naturali).
8. se n, m, z ∈ ℕ e n·z = m·z allora n=m
9. a·(b+c) = a·b+a·c

Con questi primi nove assiomi, che non identificano ancora l'insieme dei naturali (per es. l'insieme ℚ⁺ di numeri razionali positivi soddisfa tutti gli assiomi), possiamo già dimostrare qualche teorema.

Definizione D1 (multiplo)

Se n, m ∈ ℕ diciamo che m è un multiplo di n se ∃ (esiste) un numero r ∈ ℕ tale che m=nr.

Teorema T1

Se a, b ∈ ℕ sono multipi di n ∈ ℕ, allora ∀ x, y ∈ ℕ xa+yb è multiplo di n.

Dimostrazione

Se a, b sono multipli di n, allora possiamo scriverli come a=rn, b=sn (r, s ∈ ℕ).

xa+yb = x(rn)+y(sn)

assioma 8: x(rn)+y(sn) = (xr)n+(ys)n

assioma 9: n(xr+ys)

siccome xr+ys appartiene ai naturali, xa+yb è multiplo di n.

Definizione D2 (minore di)

Se n, m ∈ ℕ l'enunciato m<n significa che esiste un numero x ∈ ℕ tale che m+x=n

Teorema T2

Se a, b, c ∈ ℕ e a<b e b<c allora a<c

Dimostrazione

Poiché a<b e b<c, ∃ x, y ∈ ℕ tali che a+x=b e b+y=c (per D2)

assioma 4: allora a+(x+y) = (a+x)+y = b+y = c

Assioma 10

Dati n, m ∈ ℕ, allora esattamente uno dei seguenti tre enunciati è vero:

• n<m
• n=m
• n>m

Definizione D3 (minore o uguale)

a≤b significa a<b oppure a=b

(idem per maggiore o uguale)

Teorema T3

se m, n, r ∈ ℕ, m<n determina che m+r<n+r

Dimostrazione

(la dimostrazione è lasciata per esercizio, Biggs esercizio 4.2.2)

Teorema T4

se m, n, r ∈ ℕ, se m+r=n+r allora m=n

Dimostrazione

Assioma 10: m<n oppure m=n oppure m>n

Teorema 3: Se m<n, m+x<n+x. Omologo per m>n. Quindi per l'assioma 10 m=n.

Assioma 11 (principio di induzione)

Supponiamo che P_(n) sia un enunciato con le seguenti proprietà:

• P₍₁₎ è vero (base dell'induzione)
• dato un k ∈ ℕ, se supponiamo P_(k) vero, allora segue che P_(k+1) è vero anch'esso (passo induttivo)

allora P_(n) è vero ∀ n∈ℕ

Un breve commento di mio pugno: due delle difficoltà maggiori nel comprendere questo assioma sono:

1. entrambi i punti sono supposizioni! Non funziona che il secondo punto deriva dal primo! Per esempio, se dico P_(n) è minore di 10, e lo dimostro per P₍₁₎, poi devo anche dimostrarlo con il passo induttivo
2. spesso è utile pensare che il passo induttivo si applichi semplicemente a P₍₂₎, perché spesso negli esempi sono riportate lunghe serie in cui si è portati a immaginare k come un numero molto grande, mentre è più semplice pensare al passo induttivo come applicato semplicemente al numero 2.

Esempio

Si dimostri che n³+5n è sempre multiplo di 6 per ogni n ∈ ℕ.

Base: P₍₁₎ è vero, poiché 1³+5x1 = 6, che è evidentemente multiplo di 6.

Passo induttivo: Supponiamo vera P_(k). Dimostriamo P_(k+1): (k+1)³+5(k+1) è multiplo di 6.

1. Sviluppiamo (k+1)³ e otteniamo k³+3k²+3k+1, e moltiplichiamo 5 per k+1 = 5k+5
2. k³+5k è multiplo di 6 perché abbiamo supposto vero P_(k)
3. 1+5 = 6, quindi anche la costante è divisibile per 6
4. raccogliendo 3k: 3k²+3k = 3k(k+1). Ora, o k o k+1 sono pari, quindi 3k(k+1) è sicuramente divisibile per 6

quindi (k+1)³+5(k+1) = k³+5k+6+3k(k+1) è divisibile per 6 e abbiamo dimostrato il passo induttivo.

Esempio

Si dimostri che, dato P_(n) = 1+2+3+4+...+n,

$P_{\left(n\right)}=\frac{n\left(n+1\right)}{2}$

Base: P₍₁₎ è vero, poiché P₍₁₎ = 1

Passo induttivo: Supponiamo vera P_(k). Dimostriamo P_(k+1)

$P_{\left(k+1\right)}=\frac{\left(k+1\right)\left(\left(k+1\right)+1\right)}{2}=\frac{\left(k+1\right)\left(k+2\right)}{2}$

Questo deve essere uguale alla somma di tutti i numeri da 1 a k più k+1:
1+2+3+4+...+k+(k+1)

La prima parte (in blu) è P_(k), che abbiamo supposto vera. Aggiungiamo k+1 e otteniamo:

$\frac{k\left(k+1\right)}{2}+\left(k+1\right)$

Mettiamo a fattor comune:

$\frac{k\left(k+1\right)}{2}+\left(k+1\right)=\frac{k\left(k+1\right)2\left(k+1\right)}{2}$

Raccogliamo (k+1):

$\frac{k\left(k+1\right)2\left(k+1\right)}{2}=\frac{\left(k+1\right)\left(k+2\right)}{2}$

che è esattamente P_(k+1).