Logica e matematica discreta - Appunti

MINIMO

Dimostriamo che ogni insieme ≠ Ø ha minimo

S ⊆ N => il minimo di S esiste

S ≠ Ø

Supponiamo per assurdo che S ≠ Ø e S non ha min.

Ø ∈ P (∀ m ≤ n ∈ P) => n ∈ P

⁷ 32 94 120

S...S¯ (N-S) ∈ P

∀ z ∉ P ovvero P = N => S = Ø assurdo

quindi S ha minimo

RELAZIONI

una relazione su A e' un sottoinsieme

R ⊆ A x A -> R ⊆ A

• (a,b) ∈ R
• R(a,b)
• a R b

es.

S ⊆ N x N

• S = {(n,m) ∈ N x N ntp n = m}

n ≤ m p ∈ N ntp n = m

es.

R ⊆ N x N

R ⊆ (N x N) x (N x N)

(x,y) R (z,w) x = z

PROPRIETA'

• (1) R e' riflessiva se ∀ a ∈ A: (a R a)
• (2) R e' transitiva se ∀ a, b, c ∈ A: (a R b & b R c => a R c)
• (3) R e' simmetrica se ∀ a, b ∈ A: (a R b => b R a)

se R gode di (1) (2) (3) e' detta relazione di equivalenza ~ ≃ ≅ =

Z x Z / R = Q

numeri razionali

Z² /R =

[ [n,m]_R | (n,m) ∈ Z² ]

a/b è equivalente a c/d se e solo se da = cb

+ Q -> Q

[ [m,n] ] + [ [p,q] ] = [ [mq + np, nq] ]

es

f: Q -> Q

f( [ [n,m] ] ) =

[ [0,m] ] se n = Z

[ [1,m] ] se n ≠ Z

non è una funzione

A ∼ ∈ A x A

A_n

f: A -> B

f( [ [a] ] = b_n se a_n ∼ a₂

f[[a₁] = f[ [a₂]

equipotenti

A e B sono equivalenti (hanno la stessa cardinalità)

|A| = |B| s.se ∃ F: A→B biunivoca

DEF.

• A è finito s.se ∃n∈N t.c. |A|=|I_n|

∃ f_n:In→A

• f(0)=a_o∈A
• f(1)=a₁∈A
• ...
• f(n-1)=a_n-1∈A

• A è infinito (non è finito) s.se

∄ n, f, t.c. f:I_n→A e una bisezione

• A è numerabile se ∃ f f:N→A biunivoca
• f: A→A er iniettiva s.se f er surpettiva

A, B

|A| = m |B| = n

|A^B| = |A|^|B|

{f | f: A -> B e f iniettiva}

quanto possono essere queste funzioni f?

m > n -> |f| = 0

m ≤ n -> |f| = n! / (n-m)!

Corollario

m = n

|f| = n! / 0! = n!

Permutazione

{f | f: A -> A f biunivoca} = |A| ! = n!

|A| = n

f è detta permutazione di A

ℕ ≃ ℤ

equipotente

ℕ ≃ ℚ ℝ

ℚ ≃ ℚ x ℕ (bitti)

A ∈ ℝ punto e B ⊆ A allora A ≠ B

ℕ ≃ ℕ x ℕ

ℤ ≃ ℤ x ℤ