FANDOM


Definiția 1. Vom spune despre o mulțime M că este numărabilă dacă $ M \sim \mathbb N, \! $ adică $ \overline {\overline N}= \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