Cungjuunt cüntàbil

De Wikipedia
Va a: navegá, truvá
Vedrína
Vedrina
Quest articol chì l'è assee ben faa Vedrina
Portal Artícuj relazziunaa a matemàtica
Lumbaart ucidentaal Cheest artícul al è scrivüü in Koiné matemàtica, urtugrafía ünificada. Lombart oriental


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\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[Mudifega | mudìfica 'l sorgènt]

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[Mudifega | mudìfica 'l sorgènt]

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[Mudifega | mudìfica 'l sorgènt]

Paart d'un cungjuunt cüntàbil[Mudifega | mudìfica 'l sorgènt]

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\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[Mudifega | mudìfica 'l sorgènt]

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\mathbb{N} e una bigezziú \psi da B\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\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[Mudifega | mudìfica 'l sorgènt]

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 Ef(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[Mudifega | mudìfica 'l sorgènt]

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}I, e par tütt i da I, A_i veseent cüntàbil , al esiist una bigezziú \lambda_i da \mathbb{N}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 NI.


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 NA_i.

Cüntabilitaa dal cungjuunt di razziunaj[Mudifega | mudìfica 'l sorgènt]

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ó[Mudifega | mudìfica 'l sorgènt]