Principali teoremi Aritmetica, Algebra

1) Assioma del Buon Ordinamento

Ogni insieme non vuoto di numeri naturali ammette un minimo

∀S ⊆ ℕ, S ≠ ∅ ⇒ ∃ m ∈ S.t. m ≤ s ∀ s ∈ S

2) Principio di induzione I forma

Sia P(n) una proprietà definita ∀ n ≥ n₀ (n₀ ∈ ℤ)

Hp1) P(n₀) è vera

b) (Passo induttivo) ∀n≥n₀ se P(n) è vera ⇒ P(n+1) è vera

Th) P(n) è vera ∀ n≥n₀

Dim) Induzione I Hp) S = {n≥n₀ | P(n) è falsa}

Th) S = ∅

per assurdo S ≠ ∅ ⇒ per il principio del minimo ∃ m ∈ S minimo

per Hp1, P(m₀) è falsa. m₀ ≥ n₀ - (per l'ipotesi a)

⇒ m₀ > n₀, ma m₀-1 ∉ S

⇒ P(m-1) è vera

- per l'ipotesi b, P(m-1) vera ⇒ P(m) vera

assurdo ⇒ S = ∅

3) Principio di induzione II forma

Sia P(n) una proprietà definita ∀ n ≥ n₀ (n₀ ∈ ℤ)

Hp) a) P(n₀) vera

b) ∀ n ≥ n₀ P(k) è vera ∀ n₀ ≤ k≤n ⇒ P(n) è vera

Th) P(n) è vera ∀n

4) Def: 2 insiemi sono equipotenti, cioè hanno lo stesso cardinalità

A ≡ B tra loro una c. biettiva

A ≡ B ⇔ #A = #B ⇐⇒

dim: 1,...,n A b f biettivo A f^- 1,...,n,? g b B

g^- 1 se f^- - biettivo ⇔ f^- biettiva

se f ⟺ g * f^- 1

dim A ⟩ b

B c_f biettiva...

S1) < b x → b_0,1,1 x = 2^k #P(x) 2 * 1 = 2^k

P(x) = {A|A ≤ x}

dim: passo base; se k = 0 ⇒ P(x) = {∅} ⇒ #P(x) = 2⁰ = 1 ok

pass. ind. supponiamo vero la tesi per k e lo dimostro per k+1

#x = k+1

∀A ⊆ x ⟹ x⟹ a ⟹ 1x={}, 0 A A’≡ x’

{A|A ⊆ X' = {A|A ⊆ x' ∪ {x}' ∪ {x}∪ A'|A' ⊆ x'}

⇒ #P(x) = #P(x)' + #P(x)' = 2 * 2^k = 2^k+1

def.) # A ⊆ Y | #A = m = (m ) = # m-uple di el distinti di Y n-uple distinte che danno lo stesso insieme

1) Axioma del buon ordinamento

Ogni insieme non vuoto di numeri naturali ammette un minimo ∀S ⊆ ℕ, S ≠ ∅ ⇒ ∃ m ∈ S t.c. m ≤ s ∀ s ∈ S

2) Principio di induzione I forma

Sia P(m) una proprietà definita ∀ n ≥ n₀ (n ∈ ℤ)Hp) a) P(n₀) vera (passo base),b) (passo induttivo) ∀ n ≥ n₀, se P(m) è vera ⇒ P(m+1) è veraTh) P(m) è vera ∀ n ≥ n₀Dim: Induzione I Hp) S = {n ≥ n₀ | P(m) è falsa} Th) S = ∅

per assurdo S ≠ ∅ ⇒ per il principio del minimo ∃ m ∈ S minimo per Hp, P(m₀) è falsa, m₀ > n₀ (per ipotesi a)

⇒ m₀-1 > n₀, ma m₀-1 ∉ S⇒ P(m₀-1) è vera⇒ per ipotesi b, P(m₀-1) vera ⇒ P(m₀) vera assurdo ⇒ S = ∅

3) Principio di induzione II forma

Sia P(m) una proprietà definita ∀ n ≥ n₀ (n ∈ ℤ)Hp) a) P(n₀) verab) ∀ n ≥ n₀ P(k) è vera ∀ n ≤ k ⇒ P(m) è veraTh) P(n) è vera th

4) Def: 2 insiemi sono equipotenti, cioè hanno lo stesso cardinaletto ⇔ tra loro una c. bionivoca

A ≃ B equipotenti ⇔ #A = #B

dim: {1,...,n} ↔ A ↔ B f(−1)

f: A ↔ 1,...,n f: B

g: f(−1) se f(−1) è biggettiva se f(−1) biggettiva g f(−1) dim ↔ A o, ↔ B o è biggettiva ...

S) f: f(x − f₀, f₁8 = k

• #P(x) = 2 ×1² = 2^k
• P(x) = |[A|A ≤ x {

dim: passo base; se k = 0 ⇒ P(x1) = |ø| ⇒ #P(x1) = ø¹ = 1

passo ind; supponi vero la tese per k e lo dimostra per k +1

#X = k +1∀ Δ ⊆ X, x₀ < x ∃ a ⇒ a x[∃, o A' A' ≤ x1 {|A| x Δ ⊆ X, x₀ ⊂ A = A' |A| = A' ≜ x{)

{|A| ≤ A ⊆ x1 |[a| A ⊆ x1 | ∪ ∅ |⊂>(() ∪ A' |A' ⊆ x1

⇒ #P(xn) = #P(x1) + #P(x1) = 2^k + 2^k = 2^k+1

Def:

# { A ∈ Ψ | #A = m } : = ⟨m⟩ = #m-uple di el distinti di Ψm-uple esistono che danno lo stesso insieme

Teorema di divisione Euclidea

Siano a, b ∈ ℤ, b ≠ 0 ⇒ ∃! q, r ∈ ℤ t.c. a = qb+r 0 ≤ r<b

dim _esistenza

a > 0 x = { r | r = a-kb k ∈ ℤ } ⊓ ℕ

X ≠ ∅ in X ∃ perche' r = a+|a|b > 0

Allora r ₀ è il minimo di X (Accett)

ma r ₀ = a-qb

Dico che 0 ≤ r ₀ |b| rifatti accadano essere r ₀ ^o 0, osmotre

ne fosse r ₀ ≥ |b| ⇒ r₀-|b| ≥ 0 ε X ma r ₀-|b| ⊂ v. ^durante

in questo v. c'è il minimo ⇒ a-qb-|b| = q-q'b

b > 0 ∃q’ ε ℤ t.c. a-q(b+1)r 0 ≤ r ₁|b|

a−q(b) + tr