Fandom

Math Wiki

Mulțime numărabilă

1.029pages on
this wiki
Add New Page
Comments0 Share

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Definiția 1. Vom spune despre o mulțime M că este numărabilă dacă M \sim \mathbb N, \! adică \overline {\overline M}= \chi_0. \! Dacă \overline {\overline M}\le \chi_0 \! vom spune că M este cel mult numărabilă; în caz contrar, spunem că M este nenumărabilă.


Propoziția 1. Dacă M și P sunt două mulțimi numărabile disjuncte, atunci M \cup P \! este numărabilă.

Demonstrație Cum M și P sunt numărabile, avem două bijecții f: \mathbb N \rightarrow M \! și g: \mathbb N \rightarrow P. \! Se probează imediat că h: \mathbb N \rightarrow M \cup P, \!

h(n) = \left \{  \begin{matrix} f(\frac n 2) & daca \; n \; este \; par \\ \\ g(\frac{n+1}{2}) & daca \; n \; este \ impar \end{matrix} \right. \!

este bijecție, de unde concluzia că M \cup P \! este numărabilă. QED.


Corolar 1. O reuniune finită de mulțimi numărabile disjuncte este numărabilă.


Lema 1. Funcția numărare diagonală f: \mathbb N \times \mathbb N \rightarrow \mathbb N \! definită pentru (x, y) \in \mathbb N \times \mathbb N \! prin f(x, y) = \frac {(x+y+1)(x+y)}{2} + x \! este bijectivă.

Demonstrație Să arătăm la început că dacă (x, y), (x', y') \in \mathbb N \times \mathbb N \! și f(x, y) = f(x', y'), \! atunci x=x' \! și y=y'. \!

Să presupunem prin absurd că x \neq x' \! (de exemplu x>x', \! adică x=x' +r \! cu r \in \mathbb N^* \!). Obținem atunci egalitatea:

\frac {(x'+r+y+1)(x'+r+y)}{2}+r= \frac{(x'+y'+1)(x'+y')}{2} \!

de unde deducem că:

(x'+r+y+1)(x'+r+y)<(x'+y'+1)(x'+y') \!

și astfel y'> r+y. \! Alegând y'=r+y+s \! cu s \in \mathbb N^* \! obținem că

\frac {z(z-1)}{2} +r = \frac {(z+s)(z+s+1)}{2}, \!

unde z=x' +r+y+1, \!

lucru absurd deoarece:

\frac{z(z-1)}{2} +r  < \frac {z(z-1)}{2}+z = \frac {(z+1)z}{2} \le \frac {(z+s)(z+s-1)}{2}. \!

Prin urmare x=x' \! iar egalitatea f(x, y) = f(x', y') \! devine

\frac{(x'+y+1)(x'+y)}{2} = \frac {(x'+y'+1)(x'+y')}{2} \!

de unde obținem imediat că y=y', \! adică f este injectivă.

Pentru a proba surjectivitatea lui f vom arăta prin inducție matematică că pentru orice n \in \mathbb N \! există x, y \in \mathbb N \! a.î. f(x, y) =n. \! Avem că 0=f(0, 0) \! și să presupunem că n=f(x, y) \! cu x, y \in \mathbb N. \!

Dacă y \in \mathbb N^* \! avem

n+1=f(x, y) + 1= \frac {(x+y+1)(x+y)}{2} + x+1= f(x+1, y-1) \!

pe când dacă y=0 \! avem

n+1=\frac{x(x+1)}{2} +x+1=\frac {(x+1)(x+2)}{2} = f(0, x+1). \!

Dacă x=y=0, \! atunci n=0, \! deci n+1=1=f(0, 1). \! QED.


Corolar 2. \chi_0 \cdot \chi_0 = \chi_0. \!


Propoziția 2. \mathbb Z, \mathbb Z^* \! și \mathbb Q \! sunt mulțimi numărabile.

Demonstrație. Se probează imediat că f: \mathbb Z \rightarrow \mathbb N \!

f(x) = \begin{cases} 2x & daca \; x \ge 0 \\ -2x-1 & daca \; x<0 \end{cases} \!

și g: \mathbb Z \rightarrow \mathbb Z^*, \!

g(x) = \begin{cases} x+1 & daca \; x \ge 0 \\ x & daca \; x<0. \end{cases} \!

sunt bijective. Să probăm acum că și \mathbb Q \! este numărabilă. Cum \mathbb N \subseteq \mathbb Q \! deducem că \overline {\overline {\mathbb Q}} \ge \chi_0. \! Să considerăm f: \mathbb Z \times \mathbb Z \rightarrow \mathbb Q, \; f(x, y) = \frac x y \! pentru orice x, y \in \mathbb Z \times \mathbb Z^*. \!

Cum f este surjectivă, există g: \mathbb Q \rightarrow \mathbb Z \times \mathbb Z^* \! a.î. f \circ g = 1_{\mathbb Q}. \![1] Deducem că g este injectivă,[2] adică \overline {\overline {\mathbb Q}} \le \overline {\overline {\mathbb Z \times \mathbb Z^*}} = \chi_0 \cdot \chi_0 = \chi_0, \! de unde egalitatea \overline {\overline {\mathbb Q}} = \chi_0, \! adică \mathbb Q \! este numărabilă. QED.


Propoziția 3. Mulțimea \mathbb R \! a numerelor reale este nenumărabilă.

Demonstrație. Deoarece f: \mathbb R \rightarrow (0, 1), \; f(x)= \frac 1 2 + \frac {1}{\pi} \arctan x \! este bijectivă, este suficient să arătăm că intervalul (0, 1) \! nu este o mulțime numărabilă iar pentru aceasta să arătăm că orice funcție f: \mathbb N \rightarrow (0, 1) \! nu este surjectivă (procedeul diagonal al lui Cantor).

Pentru fiecare n \in \mathbb N \! putem scrie pe f(n) \! ca fracție zecimală:

f(n) = 0, a_{n1}, a_{n2}, \cdots , a_{nn}, \cdots \! cu a_{ij} \in \{ 0, 1, \cdots , 9 \}. \!

Dacă vom considera b \in (0, 1) \!:

b= 0, b_1, b_2, \cdots , b_n \cdots \!

unde pentru orice k \in \mathbb N^*, \; b_k \notin \{ 0, 9, a_{kk} \}, \! atunci b \notin \mathfrak {Im} f, \! adică f nu este surjectivă. QED.


Definiția 2. Vom spune despre o mulțime M că este infinită:

(i) în sens Dedekind, dacă există M' \subset M \! a.î. M' \sim M \!

(ii) în sens Cantor, dacă conține o submulțime numărabilă

(iii) în sens obișnuit, dacă M \not \sim S_n \! pentru orice n \in \mathbb N^* \! (unde S_n= \{ 1, 2, \cdots , n \} \!).


Teorema 1. Cele trei definiții ale mulțimilor infinite din cadrul Definiției 2 sunt echivalente două câte două.

Demonstrație.

 (i) \Rightarrow (ii). \! Fie M o mulțime infinită în sens Dedekind; atunci există M' \subset M \! și o bijecție f: M \rightarrow M'. \! Cum M' \subset M, \! există x_0 \in M \! a.î. x_0 \not \in M'. \! Construim prin recurență șirul de elemente x_1=f(x_0), \; x_2=f(x_1), \cdots . x_n= f(x_{n-1}), \cdots \! și să arătăm că funcția \varphi : \mathbb N \rightarrow M, \; \varphi(n) = x_n \! pentru orice n \in \mathbb N \! este injectivă. Pentru aceasta vom demonstra că dacă n, n' \in \mathbb N, \; n \neq n', \! atunci \varphi (n) \neq \varphi (n'). \! Vom face lucrul acesta prin inducție matematică după n. \!

Dacă n=0, \! atunci n' \neq 0, \! de unde \varphi(0)= x_0 \! și \varphi(n') = f(x_{n'-1}) \in M' \! și cum \varphi (0) = x_0 \notin M' \! deducem că \varphi (n') \neq \varphi(0). \! Să presupunem acum că pentru orice n \neq m' \; \varphi(n) \neq \varphi (m') \! și să alegem acum n' \neq n+1. \!

Dacă n' =0, \! atunci \varphi(n') = \varphi(0) = x_0 \not \in M' \! și x_{n+1} = f(x_n) \in M', \! deci \varphi(n+1) \neq \varphi (n'). \!

Dacă n' \neq 0, \! atunci \varphi (n')=f(x_{n'-1}) \! și \varphi(n+1) = f(x_n). \! Cum n'-1 \neq n, \! atunci x_{n'-1} \neq x_n \! și cum f este injectivă deducem că f(x_{n'-1}) \neq f(x_n), \! adică \varphi(n') \neq \varphi (n+1). \! Rezultă deci că \varphi \! este injectivă și deci \varphi (\mathbb N) \subseteq M \! este o mulțime numărabilă.

 (ii) \Rightarrow (i). \! Fie M o mulțime infinită în sensul lui Cantor, adică există M' \subseteq M \! a.î. M' \sim \mathbb N \! (fie f: \mathbb N \rightarrow M' \! o funcție bijectivă). Se observă imediat că \varphi : M \rightarrow M \setminus \{ f(0) \} \! definită prin

\varphi (x) = \begin{cases} x & daca \; x \notin M' \\ f(n+1) & daca \; x=f(n) \; cu \; n \in \mathbb N \end{cases} \!

este bine defintă și să arătăm că \varphi \! este chiar bijecție.


Fie deci x, x' \in M \! a.î. \varphi (x) = \varphi (x'). \!

Deoarece M=M' \cup (M \setminus M') \! și \varphi(x) = \varphi(x'), \! atunci x, x' \in M' \! sau x, x' \not \in M'. \! Dacă x, x' \not \in M', \! atunci în mod evident din \varphi(x) = \varphi (x') \! deducem că x=x'. \! Dacă x, x' \in M', \! atunci dacă x=f(k), \; x'= f(t) \! deducem că f(k+1) = f(t+1), \! de unde k+1 = t+1 \; \Leftrightarrow \; k=t \Rightarrow x=x'. \!

Să arătăm acum că \varphi \! este surjectivă. Pentru aceasta fie y \in M \setminus \{ f(0) \}. \! Dacă y \not \in M' \! atunci y= \varphi (y), \! iar dacă y \in M', \! atunci y=f(n) \! cu n \in \mathbb N. \! Cum y \neq f(0), \! atunci n \neq 0 \Rightarrow \; n \ge 1 \! deci putem scrie y=f(n-1+1) = \varphi (n-1). \!

 (ii) \Rightarrow (iii). \! Această implicație este evidentă deoarece \mathbb N \not \sim S_n \! pentru orice n \in \mathbb N^*. \!

 (iii) \Rightarrow (ii). \! Vom utiliza următorul fapt: dacă M este o mulțime infinită în sens obișnuit, atunci pentru orice n \in \mathbb N^* \! există o funcție injectivă \varphi : S_n \rightarrow M. \!

Vom proba lucrul acesta prin inducție matematică referitor la n. \!

Pentru n=1 \! există o funcție injectivă \varphi : S_1 \rightarrow M \! (deoarece M \neq \varnothing \!). Să presupunem acum că pentru n \in \mathbb N^* \! există \varphi : S_n \rightarrow M \! injectivă. Cum am presupus că M este infinită în sens obișnuit, atunci \varphi(S_n) \neq M, \! deci există x_0 \in M \! a.î. x_0 \not \in \varphi (S_n). \!

Atunci \psi : S_{n+1} \rightarrow M \! cu:

\psi (x) = \begin{cases} \varphi(x) & pentru \; x \in S_n \\ x_0 & pentru \; x=n+1 \end{cases} \!

este în mod evident funcție injectivă.

Să trecem acum la a demonstra efectiv implicația (iii) \Rightarrow (ii). \! Din rezultatul expus anterior deducem că:

M_k = \{ \varphi: S_k \rightarrow M \; | \; \varphi \! este injecție  \} \neq \varnothing \!

pentru orice k \in \mathbb N^*. \! Cum pentru k \neq k', \; S_k \cap S'_k = \varnothing. \! Conform axiomei alegerii \! aplicată mulțimii T = \{ M_k \; : \; k \in \mathbb N \}, \! există S \subseteq T \! a.î. S \cap M_k \neq \varnothing \! și este formată dintr-un singur element. Atunci

M' = \underset {\varphi \in S}{\bigcup} \mathfrak {Im}(\varphi) \!

este o submulțime numărabilă a lui M. QED.

Vezi şi Edit

Note Edit

  1. Vezi articolul Funcție.
  2. Idem.

Surse Edit

Also on Fandom

Random Wiki