Cungjuunt cüntàbil

Quest articol chì l'è assee ben faa

Purtaal:matemàtica Artícuj relazziunaa a matemàtica

Cheest artícul al è scrivüü in Koiné matemàtica, urtugrafía ünificada.

Un cungjuunt $E$ al è dii cüntàbil si al è equiputeent al cungjuunt di intreegh natüraj $\mathbb{N}$, i.e. si al esiist una bigezziú da $E$ sü $\mathbb{N}$ (u $\mathbb{N}^*$, vidé plüü in bass) ; cheest chí al equivaar a l'esistenza d'una bigezziú da $\mathbb{N}$ (u $\mathbb{N}^*$) sü $E$.

Naïvemeent, dí che un cungjuunt E al è cüntàbil al signifía che al è pussíbil da cüntá ün a ün ognidü dij söö elemeent: sa i pöö nümerá i elemeent da E senza umissiú ni repetizziú , druvaant töcc i intreegh natüraj.

Ul cungjuunt di intreegh natüraj al è cüntàbil , par che un cungjuunt al è sémpar equiputent a sí-istess, e cada cungjuunt equiputent a un cungjuunt cüntàbil al è sí-istess cüntàbil .

Un cungjuunt cüntàbil al è infinii, par che equiputent a $\mathbb{N}$, ch’al è infinii. Però la recípruca a l’è falsa : al esiist di cungjuunt infinii mia cüntàbil . Ul matemàtich Cantor, ch’a l’a intrudüii la nuzziú da cüntabilitaa, al a demustraa che ul cungjuunt di nümar reaj, nutaa $\ \mathbb{R}$, al è mia cüntàbil .

Vucabülari

L'espressiú cungjuunt cüntàbil la gh'a dò definizziú :

• Vargüne püblicazziú i dröva chesta espressiú mia noma íntal sentüü vidüü chí-da-sura però apó par designá un cungjuunt fini
• D'òolt i dröva chesta espressiú ünicameent paj cungjuunt satisfaseent la definizziú, e i preferiss druvá l'espressiú cungjuunt al plüü cüntàbil par designá un cungjuunt u bé fini, u bé cüntàbil .

Al cuventa dunca töö atenziú a la cunvenzziú druvada a l’ura da la letüra d'una püblicazziú sül süget. In cheest artícul, al è la segunda acezziú ch’a la sarà druvada.

Cungjuunt üsüaj e cüntabilitaa

Par definizziú , ul cungjuunt $\mathbb{N}$ di intreegh naturaj al è cüntàbil .

Ul cungjuunt $\mathbb{N}^*$ di intreegh naturaj mia nüj al è cüntàbil.

In efett, l'aplicazziú $\begin{matrix}\mathbb{N}^* \longrightarrow \mathbb{N} \\ n \longmapsto n-1\end{matrix}$ a l'è bigetia.

---

Ul cungjuunt di intreegh natüraj pari, nutaa $2\, \mathbb{N}$, al è cüntàbil .

In efett, l'aplicazziú $\begin{matrix}\mathbb{N} \longrightarrow \ 2\, \mathbb{N} \\ n \longmapsto 2\, n\end{matrix}$ a l'è bigetiva.

---

Ul cungjuunt di quadraa parfett, nutaa chí $\mathbb{P}$, al è cüntàbil.

In efett, l'aplicazziú $\begin{matrix}\mathbb{N} \longrightarrow \ \mathbb{P} \\ n \longmapsto n^2\end{matrix}$ a l’è bigetiva.

---

Ul cungjuunt $\mathbb{Z}$ di intreegh relatiif al è cüntàbil .

In efet, l'aplicazziú $\begin{matrix}\mathbb{Z} \longrightarrow \mathbb{N} \\ n \longmapsto \left\{\begin{matrix} 2n \mbox{si } n\in\mathbb{N} \\ -2n-1 \mbox{si } n\in\mathbb{Z} \setminus \mathbb{N} \end{matrix}\right. \end{matrix}$ a l'è bigetiva.

---

Ul cungjuunt $\mathbb{N}\times\mathbb{N}$ di para d'intreegh naturaj al è cüntàbil, par che l'aplicazziú

$\begin{matrix}\mathbb{N}\times\mathbb{N} \longrightarrow \mathbb{N}^* \\ (n,m) \longmapsto 2^n(2m+1) \end{matrix}$

a l'è bigetiva (tütt intreegh natüraal stregjameent pusitiif sa i faturiza da manera ünica sota furma dal prudüit d'una pudenza da 2, e d'un intreegh díspari).

---

Ul cungjuunt $\mathbb{Q}$ di nümar razziunaj al è cüntàbil (vidé plüü sota una demustrazziú da chesta afirmazziú ).

---

Ul cungjuunt $\overline{\mathbb{Q}}$ di nümar algebraich (reaj u cumpless) al è cüntàbil . Cuma nissü di düü cungjuunt $\mathbb{R}$ e $\mathbb{C}$ al è cüntàbil , sa en dedüiss l'esistenza da nümar (reaj u cumpless) trascendeent.

Vargüne prupietaa

Paart d'un cungjuunt cüntàbil

Cada paart A da $\mathbb{N}$ a l’è al plüü cüntàbil .

In efett, si $A$ al è finii, alura a fortiori $A$ al è al plüü cüntàbil .

Süpusemm adess $A$ infinii. Cuma ch’al è una paart mia vöja da $\mathbb{N}$, $A$ al amet dunca un plüü petit elemeent. Notemm-al $a_0$.

Al síes $n\in\mathbb{N}$. Sa süpusa da iga pruvaa l'esistenza d'elemeent da $A$ nutaa $a_0,a_1,\ldots,a_n$ taj che:

(i) $a_0 < a_1 < \ldots < a_n$

(ii) $\forall x\in A \setminus \{a_0, a_1, \ldots, a_n\}, a_n < x$

Ul cungjuunt $A' = A \setminus \{a_0, a_1, \ldots, a_n\}$ al è mia vöj par che $A$ al è infinii, dunca $A'$ al amet un plüü petit elemeent che sa l nota $a_{n+1}$. Sa gh'a alura :

$a_{n+1}\in A'$ dunca $a_n < a_{n+1}$

$\forall x\in A \setminus \{a_0, a_1, \ldots, a_n, a_{n+1}\} = A' \setminus \{a_{n+1}\}, a_{n+1} < x$

Sa a inscí mustraa par recürenza l'esistenza d'una sequenza $(a_n)_{n\in\mathbb{N}} \in A^{\mathbb{N}}$ stregjameent cressenta. Punemm $B = \{(a_n \;|\; n\in\mathbb{N}\}$. $B$ al è cüntàbil e cuntegnüü in $A$. Mustremm l'inclüsiú inversa. Al síes $n$ elemeent da $A$. La sequenza $(a_n)_{n\in\mathbb{N}}$ a l’è stregjameent cressenta, dunca sa gh'a $n \le a_n$, dunca dapress (ii) $n\not\in A \setminus \{a_0, a_1, \ldots, a_n\}$, dunca $n\in\{a_0, a_1, \ldots, a_n\}$ e dunca $n\in B$.

Sa a inscí pruvaa che $A=B$, e dunca che $A$ al è cüntàbil .

In töcc i caas, A a l’è dunca al plüü cüntàbil .

Tüta paart d'un cungjuunt al plüü cüntàbil al è al plüü cüntàbil .

Al síes $E$ un cungjuunt al plüü cüntàbil e $F$ una paart da $E$. Al síes $\varphi$ una bigezziú da $E$ sü una paart da $\mathbb{N}$. La restrizziú da $\varphi$ a $F$ a l’è una bigezziú da $F$ sü $\varphi (F)$ ch’al è una paart da $\mathbb N$, dunca al plüü cüntàbil dapress la prupietaa chí-da-sura. $F$ étant equiputent a $\varphi (F)$ al è sí-istess al plüü cüntàbil .

Prudüit da cungjuunt cüntàbil

Tütt prudüit cartesià d'una famèja finida da cungjuunt cüntàbil al è cüntàbil .

I síes $A$ e $B$ düü cungjuunt cüntàbil . Al esiist una bigezziú $\varphi$ da $A$ sü $\mathbb{N}$ e una bigezziú $\psi$ da $B$ sü $\mathbb{N}$. Definissemm:

$\lambda : \begin{matrix}A\times B \longrightarrow \mathbb{N}\times\mathbb{N} \\ (x, y) \longmapsto (\varphi(x), \psi(y))\end{matrix}$

Chesta aplicazziú a l’è bigetiva da $A \times B$ sü $\mathbb{N}\times\mathbb{N}$ ch’al è cüntàbil . Dunca $A \times B$ al è cüntàbil .

Una recürenza la permett d'esteend cheest resültaa al prudüit cartesià da cada famèja finida da cungjuunt cüntàbil .

Imàgen e imàgen recípruca da cungjuunt cüntàbil

I síes $E$ e $F$ düü cungjuunt mia vöj, e $f$ una aplicazziú da $E$ in $F$.

1. Si $f$ al è ingetiva e si $F$ al è al plüü cüntàbil , alura $E$ al è al plüü cüntàbil

$f$ a l’è ingetiva, dunca la indüiss una bigezziú da $E$ sü $f(E)$. Adess, $f(E)$ al è una paart da $F$ e al è dunca al plüü cüntàbil . $E$ al è dunca al plüü cüntàbil .

2. Si $f$ al è sürgetiva e si $E$ al è al plüü cüntàbil , alura $F$ al è al plüü cüntàbil

E al è al plüü cüntàbil , dunca al esiist $\varphi : E \to A$ bigetiva, cun $A \subset \mathbb{N}$. Adess $\mathbb{N}$ al è bé urdenaa, dunca E al pöö vess münii d'un bun úrden (definii chí esplicitameent, senza ul recuurs abitüaal a l'assioma da la scèrnida), pusaant $\forall (a,b) \in E^2, a \leq_E b \Leftrightarrow \varphi(a) \le \varphi(b)$ ; alura, tüta paart mia vöja da E la gh’a un mínim.

Al síes $y\in F$, $f$ sürgetiva, $f^{-1}(\{ga\})$ al è un sübcungjuunt mia vöj da E. Sa la definiss alura :

$g : F \to E, y \mapsto\min(f^{-1}(\{y\})$ ($\ g(y)$ al è ul plüü petit antecedeent da y par f)

Par custrüzziú , par tütt $\ y \in F,\, f(g(y)) = y$, dunca l'aplicazziú g al è ingetiva. Ul cungjuunt $E$ al è al plüü cüntàbil , dunca al risülta da 1. che $F$ al è al plüü cüntàbil .

Curulari : le tré prupusizziú sigütante i è equivalente :

• ul cungjuunt $E$ al è al plüü cüntàbil ;
• al esiist una ingezziú da $E$ veers $\mathbb{N}$ ;
• al esiist una sürgezziú da $\mathbb{N}$ veers $E$.

Reüniú da cungjuunt cüntàbil

Tüta reüniú cüntàbil da cungjuunt cüntàbil a l’è cüntàbil

Plüü furmalameent, si $I$ al è un cungjuunt cüntàbil e si $(A_i)_{i\in I}$ a l’è una famèja da cungjuunt cüntàbil , alura $A = \bigcup_{i\in I} A_i$ al è un cungjuunt cüntàbil . $I$ al è cüntàbil , dunca al esiist una bigezziú $f$ da $\mathbb{N}$ sü $I$, e par tütt $i$ da $I$, $A_i$ veseent cüntàbil , al esiist una bigezziú $\lambda_i$ da $\mathbb{N}$ sü $A_i$. Sa l ponn alura :

$\varphi : \begin{matrix} \mathbb{N}\times\mathbb{N} \longrightarrow A \\ (a,b) \longmapsto \lambda_{f(a)}(b) \end{matrix}$.

$\varphi$ a l’è bé una aplicazziú da che ul cungjuunt da rivada a l’è $A$ gja che $f(a)\in I$, dunca $\lambda_{f(a)}(b)\in A_{f(a)} \subset A$.

Mustremm che $\varphi$ al è sürgetiva. Al síes $x\in A$. Al esiist $i$ taal che $x\in A_i$. Al síes $a\in\mathbb{N}$ taal che $i = f(a)$. $x\in A_i$ e $\lambda_i$ al è una bigezziú da $\mathbb{N}$ in $A_i$, dunca $\exists b\in\mathbb{N}, x = \lambda_i(b) = \lambda_{f(a)}(b)\,$, vargot ch’al dà bé $x = \varphi(a,b)\,$

Inscí, $\varphi$ al è sürgetiva e $\mathbb{N}\times\mathbb{N}$ al è cüntàbil , dunca $A$ al è cüntàbil .

Tüta reüniú finida da cungjuunt cüntàbil al è cüntàbil

Íntal caas indúe $I$ al è finii, al è assée da retöö la demustrazziú precedenta, però cun $f$ sürgetiva da $\mathbb N$ sü $I$.

Tüta reüniú al plüü cüntàbil da cungjuunt al plüü cüntàbil al è al plüü cüntàbil

Íntal caas indúe vargü $A_i$ i è finii, al è assée da retöö la demustrazziú precedent<, però cun $\lambda_i$ sürgetiva da $\mathbb N$ sü $A_i$.

Cüntabilitaa dal cungjuunt di razziunaj

Sa la gjüstífega chí, cul jütt da vargüne da le prupietaa sura stabilide, la cüntabilitaa dal cungjuunt $\ \mathbb{Q}$. Tütt razziunaal $\ r$ sa l scriif d'almaanch una manera sota la furma $\frac{p}{q}$, indúe $\ p \in \mathbb{Z}$ e $\ q \in \mathbb{N}^*$ ; cheest chí al signifía che l'aplicazziú $\ f : \mathbb{Z} \times \mathbb{N}^* \to\mathbb{Q}, (p,\, q) \mapsto\frac{p}{q}$ a l’è sürgetiva ; adess $\ \mathbb{Z}$ e $\ \mathbb{N}^*$ i è cüntàbil : ul sò prudüit cartesià al è dunca da l’istessa manera cünàbil, e l'esistenza da la sürgezziú f la implica che $\ \mathbb{Q}$ al è al plüü cüntàbil ; però al è infinii, dunca cüntàbil .

Sa pöö mustrá da l’istessa manera che la sequenza $(x_n)_{n \in \mathbb N}$ definida da la manera sigütaant la dà una bigezziú intra $\mathbb N$ e ul cungjuunt di razziunaj positiif u nüj :

$x_0 = 0$

$\forall n \ge 0, x_{n+1} = g(x_n)$ cun $g(x) = {1 \over 1 + 2E(x) - x}$, indúe $E(x)$ al designa la paart intrega da $x$.

Voici le prime valuur da la sequenza :

$0, 1, {1 \over 2}, 2, {1\over 3}, {3\over 2}, {2\over 3}, 3, {1\over 4}, {4\over 3}, {3\over 5}, {5\over 2}, {2\over 5}, {5\over 3}, {3\over 4}, 4, {1\over 5}, {5\over 4}, {4\over 7}, {7\over 3}, {3\over 8}, \ldots$

Vidée apó

• Ipòtesi dal cuntínü
• Georg Cantor