Ensemble dénombrable

En mathématiques , un ensemble dénombrable est un ensemble fini ou s'il existe une correspondance avec les nombres naturels . Plus précisément, un ensemble est dit dénombrable (ou dénombrable) lorsqu'il est fini ou lorsqu'il existe une bijection entre cet ensemble et l'ensemble des entiers naturels.

En 1874 , Georg Cantor a introduit le terme d'ensemble dénombrable , opposant les ensembles qui sont dénombrables à ceux qui ne le sont pas . Aujourd'hui, les ensembles dénombrables forment la base d'une branche des mathématiques appelée mathématiques discrètes.

Définition

Un ensemble est dénombrable s'il existe une fonction injective à partir de nombres naturels puisqu'il existe une bijection évidente entre et , il n'y a pas de différence si 0 est considéré comme naturel ou non ; Dans tous les cas, cet article reprend la convention standard de la logique mathématique, où a est pris , c'est-à-dire que chaque n des naturels (domaine ou ensemble de départ) correspond à un élément de S (image ou ensemble d'arrivée) utilisant une fonction . $oui$ $F$ $\mathbb {N} =\{0,1,2,3,...\}$ $-$$\mathbb {N}$$\mathbb {N} 0}=\{1,2,3,...\}$$0\in \mathbb {N}$ $-$$oui$$F$

${\begin{array}{rccl}f:&S&\longrightarrow &N\end{array}}$

Si la fonction se trouve être également surjective (et donc bijective ), alors elle est appelée infini dénombrable. $F$$oui$

En d'autres termes, un ensemble est dénombrable infini s'il a une correspondance biunivoque avec l'ensemble des nombres naturels . $\mathbb {N}$

Comme indiqué ci-dessus, cette terminologie n'est pas universelle. Certains auteurs utilisent dénombrable dans le sens de ce qu'on appelle ici dénombrable infini , et n'incluent pas les ensembles finis.

Des formulations alternatives (équivalentes) de la définition en termes de fonction bijective ou de fonction surjective peuvent également être données. Voir ci-dessous.

Historique

En 1874, dans son premier article sur la théorie des ensembles , Cantor a prouvé que l'ensemble des nombres réels est indénombrable, montrant ainsi que tous les ensembles infinis ne sont pas dénombrables. En 1878, il a utilisé des correspondances biunivoques pour définir et comparer les cardinalités. En 1883, il étendit les nombres naturels avec leurs ordinaux infinis et utilisa des ensembles d'ordinaux pour produire une infinité d'ensembles ayant des cardinalités infinies différentes. ]

Origine du terme

La notion de dénombrabilité a été introduite par Georg Cantor dans un article de 1874, ​Sur une propriété du système de tous les nombres algébriques réels ​ où il déclare d'une part que l'ensemble des nombres algébriques réels (i.e. ensemble de nombres réels qui sont la solution d'une équation polynomiale à coefficients rationnels) est dénombrable, ​ et d'autre part que l'ensemble de tous les nombres réels ne l'est pas, d'où il déduit immédiatement l'existence de nombres transcendantaux ou non -algébrique, retrouvant ainsi un résultat de Liouville .

Son origine est liée à la conception de l'infini en mathématiques. Jusqu'à la découverte de Cantor, l'infini était l'infini potentiel , la possibilité de continuer un processus sans jamais s'arrêter. La comparaison d'ensembles infinis amène avec elle la notion d' infini atteint , effectif ou achevé : un ensemble infini vu comme un tout, concept qui a été rejeté par de nombreux mathématiciens ( Gauss , ou, au temps de Cantor, Kronecker , etc.) . Pour eux, le fait de considérer une infinité d'objets comme un tout, c'est-à-dire la notion d' ensemble infini , n'a pas de sens, mais plutôt l'infini ne peut surgir que du processus d'énumération sans répétition qui ne s'arrête jamais . Seul l'infini dénombrable peut strictement avoir un sens.

Présentation

Un ensemble est une collection d' éléments et peut être décrit de plusieurs façons. Un formulaire est simplement une liste de tous ses éléments ; Par exemple, l'ensemble constitué des entiers 3, 4 et 5 peut être noté {3, 4, 5}. Ceci n'est cependant efficace que pour les petits ensembles; pour les ensembles plus grands, cela peut prendre du temps et être source d'erreurs. Au lieu d'énumérer chaque élément, des points de suspension ("...") sont parfois utilisés si l'auteur pense que le lecteur peut facilement deviner ce qui manque; par exemple, {1, 2, 3, ..., 100} désigne vraisemblablement l'ensemble des entiers de 1 à 100. Même dans ce cas, il est toujours possible de lister tous les éléments, puisque l'ensemble est fini .

Certains ensembles sont infinis ; ces ensembles ont plus de n éléments pour tout entier n . Par exemple, l'ensemble des nombres naturels, écrits sous la forme {0, 1, 2, 3, 4, 5, ...}, a un nombre infini d'éléments, et nous ne pouvons utiliser aucun nombre normal pour donner sa taille. Cependant, il s'avère que les ensembles infinis ont une idée bien définie de la taille (ou plutôt de la cardinalité , qui est le terme technique désignant le nombre d'éléments dans un ensemble), et que tous les ensembles infinis n'ont pas la même cardinalité.

Représentation bijective d'entiers en nombres égaux.

Pour comprendre ce que cela signifie, examinons d'abord ce que cela ne signifie pas . Par exemple, il existe un nombre infini d'entiers impairs, un nombre infini d'entiers pairs et (donc) un nombre infini d'entiers en général. Cependant, il s'avère que le nombre d'entiers pairs, qui est le même que le nombre d'entiers impairs, est également le même que le nombre d'entiers en général. En effet, pour chaque entier impair, il existe une contrepartie, un entier pair : ... -2 → -4, -1 → -2, 0 → 0, 1 → 2, 2 → 4, ... Dans l'image Entiers et les nombres pairs sont arrangés dans une correspondance un à un (ou bijection ), qui est une fonction qui représente deux ensembles de telle manière que chaque élément de chaque ensemble correspond à un seul élément de l'autre ensemble.

Cependant, tous les ensembles infinis n'ont pas la même cardinalité. Par exemple, Georg Cantor (qui a introduit ce concept) a montré que les nombres réels ne peuvent pas être en correspondance biunivoque avec les nombres naturels (entiers non négatifs), et donc l'ensemble des nombres réels a une plus grande cardinalité que l'ensemble de nombres naturels.

Un ensemble est dénombrable si : (1) il est fini, ou (2) s'il a la même cardinalité (taille) que l'ensemble des nombres naturels. De manière équivalente, un ensemble est dénombrable s'il a la même cardinalité qu'un sous- ensemble de l'ensemble des nombres naturels. Sinon, c'est indénombrable .

Formulation générale sans détails

Par définition, un ensemble S est dénombrable s'il existe une fonction injective f  : S → N de S à l'ensemble des entiers naturels N = {0, 1, 2, 3, ...}.

Il peut sembler normal de diviser les ensembles en différentes classes : regrouper tous les ensembles contenant un élément ; tous les ensembles qui contiennent deux éléments ensemble ; ...; enfin, rassemblez tous les ensembles infinis et considérez-les comme ayant la même taille. Ce point de vue n'est pas tenable dans le cadre de la définition naturelle de la taille.

Pour élaborer cela, nous avons besoin du concept de bijection . Bien qu'une bijection semble être un concept plus avancé qu'un nombre, le développement habituel des mathématiques en termes de théorie des ensembles définit les fonctions avant les nombres, car elles sont basées sur des ensembles beaucoup plus simples. C'est là qu'intervient le concept de bijection : il définit la correspondance

une ↔ 1, b ↔ 2, c ↔ 3

Cela définit une bijection, puisque chaque élément de { a , b,c } correspond à un élément précis de {1, 2, 3} , et vice versa.

Nous généralisons maintenant cette situation et définissons deux ensembles de même taille si (et seulement si) il existe une bijection entre eux. Pour tous les ensembles finis, cela nous donne la définition habituelle de la taille équivalente . Que nous apprend-il sur la taille des ensembles infinis ?

Considérons les ensembles A = {1, 2, 3, ...}, l'ensemble des entiers positifs , et B = {2, 4, 6, ...}, l'ensemble des entiers positifs pairs. Nous affirmons que, selon notre définition, ces ensembles ont la même taille, et que donc B est dénombrable infini. Rappelons que pour prouver cela, nous devons prouver une bijection entre eux. Mais c'est facile, en utilisant n ↔ 2 n , de sorte que

1 ↔ 2, 2 ↔ 4, 3 ↔ 6, 4 ↔ 8, ....

Comme dans l'exemple précédent, chaque élément de A a été apparié avec un élément de B et vice versa. Ils sont donc de la même taille. Ceci est un exemple d'un ensemble de la même taille que l'un de ses propres sous-ensembles (ce qui est impossible pour les ensembles finis).

De même, l'ensemble de toutes les paires ordonnées de nombres naturels est dénombrable infini, comme on peut le voir en suivant un chemin comme celui de l'image :

La fonction de correspondance de Cantor attribue un nombre naturel à chaque paire de nombres naturels.

La représentation résultante est :

0 ↔ (0.0), 1 ↔ (1.0), 2 ↔ (0.1), 3 ↔ (2.0), 4 ↔ (1.1), 5 ↔ (0.2), 6 ↔ (3.0) ....

Cette représentation englobe toutes les paires ordonnées.

Fait intéressant, si vous traitez chaque paire comme le numérateur et le dénominateur d'une fraction vulgaire , alors pour chaque fraction positive, nous pouvons arriver à une quantité différente qui lui correspondra. Cette représentation inclut également les nombres naturels, puisque chaque nombre naturel est aussi une fraction N /1. On peut donc conclure qu'il y a exactement autant de nombres rationnels positifs qu'il y a d'entiers positifs. Ceci est également vrai pour tous les nombres rationnels, comme on peut le voir ci-dessous.

Théorème : Le produit cartésien d'un nombre fini d'ensembles dénombrables est dénombrable.

Parfois, plusieurs représentations sont utiles. C'est là que vous représentez que l'ensemble que vous voulez montrer est dénombrable infini dans un autre ensemble, puis représente cet autre ensemble de nombres naturels. Par exemple, les nombres rationnels positifs peuvent facilement être attribués à (un sous-ensemble de) les paires de nombres naturels car p / q représente ( p , q ).

Et qu'en est-il des sous-ensembles infinis des ensembles dénombrables infinis ? Contiennent-ils moins d'éléments que N ?

Théorème : Tout sous-ensemble d'un ensemble dénombrable est dénombrable. En particulier, chaque sous-ensemble infini d'un ensemble dénombrable infini est dénombrable infini.

Par exemple, l'ensemble des nombres premiers est dénombrable, en attribuant le nième nombre premier à n :

• 2 représente 1
• 3 représente 2
• 5 représente 3
• 7 représente 4
• 11 représente 5
• 13 représente 6
• 17 représente 7
• 19 représente 8
• 23 représente 9
• ...

Qu'en est-il des ensembles qui sont naturellement "supérieurs à" N ? Par exemple, l'ensemble des nombres entiers , Z , ou l'ensemble des nombres rationnels , Q , qui peuvent intuitivement sembler beaucoup plus grands que N. Mais les apparences sont trompeuses, puisque nous affirmons que :

Théorème : Z (l'ensemble de tous les nombres entiers) et Q (l'ensemble de tous les nombres rationnels) sont dénombrables.

De la même manière, l'ensemble des nombres algébriques est dénombrable. ]

Théorème : Toute union finie d'ensembles dénombrables est dénombrable. Q peut être défini comme l'ensemble de toutes les fractions du type a'/ b où a et b sont des entiers, avec b > 0. Cela peut être mappé au sous-ensemble de triplets ordonnés de nombres naturels ( a , b , c ) de tel que si a ≥ 0 et b > 0, a et b sont premiers entre eux, et c ∈ {0, 1} alors c = 0 si a / b ≥ 0, et c = 1 sinon.

• Le 0 représente (0,1,0)
• Le 1 représente (1,1,0)
• Le −1 représente (1,1,1)
• Le 1/2 représente (1,2,0)
• Le −1/2 représente (1,2,1)
• Le 2 représente (2,1,0)
• Le −2 représente (2,1,1)
• 1/3 représente (1,3,0)
• Le −1/3 représente (1,3,1)
• Le 3 représente (3,1,0)
• Le −3 représente (3,1,1)
• Le 1/4 représente (1,4,0)
• Le −1/4 représente (1,4,1)
• Le 2/3 représente (2,3,0)
• Le −2/3 représente (2,3,1)
• Le 3/2 représente (3,2,0)
• Le −3/2 représente (3,2,1)
• Le 4 représente (4,1,0)
• Le −4 représente (4,1,1)
• ...

Avec la prévoyance de savoir qu'il existe des ensembles dénombrables, on peut se demander si ce dernier résultat peut être étendu. La réponse est "oui" et "non", nous pouvons l'étendre, mais nous devons assumer un nouvel axiome pour le faire.

Théorème : (En supposant l' axiome du choix dénombrable ) L'union d'un nombre dénombrable d'ensembles dénombrables est dénombrable.

Par exemple, étant donné l'ensemble dénombrable a , b , c , ...

Énumération de nombres dénombrables d'ensembles dénombrables.

En utilisant une variante de l'énumération triangulaire vue ci-dessus :

• un ₀ représente 0
• un ₁ représente 1
• b ₀ représente 2
• un ₂ représente 3
• b ₁ représente 4
• c ₀ représente 5
• un ₃ représente 6
• b ₂ représente 7
• c ₁ représente 8
• d ₀ représente 9
• un ₄ représente 10
• ...

Notez que cela ne fonctionne que si les ensembles a , b , c , ... sont des ensembles disjoints . Sinon, alors l'union est encore plus petite et donc également énumérable par l'un des théorèmes ci-dessus.

Notez également que nous avons besoin de l' axiome du choix dénombrable pour indexer tous les ensembles a , b , c , ... simultanément.

Théorème : L'ensemble de toutes les séquences de longueur finie de nombres naturels est dénombrable.

Cet ensemble est la réunion de suites de longueur 1, longueur 2, longueur 3, qui sont des ensembles dénombrables (produit cartésien fini). Nous parlons donc d'une union dénombrable d'ensembles dénombrables, qui est dénombrable par le théorème ci-dessus.

Théorème : L'ensemble de tous les sous- ensembles finis des nombres naturels est dénombrable.

Ayant un sous-ensemble fini, vous pouvez ordonner les éléments dans une séquence finie. Il n'y a qu'un nombre dénombrable de séquences finies, donc il n'y a aussi qu'un nombre dénombrable de sous-ensembles finis.

Le théorème suivant donne des formulations équivalentes en termes de fonction bijective ou surjective . Une preuve de ce résultat peut être trouvée dans le texte de Lang.

Théorème (de base) : Soit S un ensemble. Les affirmations suivantes sont équivalentes:

1. S est dénombrable, c'est-à-dire qu'il existe une fonction injective f  : S → N .
2. Ó S est vide ou il existe une fonction surjective g  : N → S .
3. Ó S est fini ou il existe une bijection h  : N → S .

Le théorème de Cantor stipule que si A est un ensemble et P ( A ) est son ensemble de puissance , c'est-à-dire l'ensemble de tous les sous-ensembles de a , alors il n'y a pas de fonction surjective de A à P ( A ). Une preuve est donnée dans l'article Théorème de Cantor . Comme conséquence immédiate de ceci et du théorème de base précédent, nous avons :

Proposition : L'ensemble P ( N ) n'est pas dénombrable ; c'est-à-dire qu'il est indénombrable .

Pour une élaboration de ce résultat, voir l'argument diagonal de Cantor.

L'ensemble des nombres réels est indénombrable (voir la première preuve d'indénombrabilité de Cantor ), de même que l'ensemble de toutes les séquences infinies de nombres naturels.

Quelques détails techniques

Les preuves des déclarations contenues dans la section précédente sont basées sur l'existence de fonctions avec certaines propriétés. Cette section présente les fonctions les plus couramment utilisées dans ce document, mais ne vérifie pas que ces fonctions possèdent les propriétés requises. Le théorème de base est souvent utilisé pour simplifier les preuves. Notez que N dans ce théorème peut être remplacé par n'importe quel ensemble dénombrable infini.

Proposition : Tout ensemble fini est dénombrable.

Preuve : Par définition, il existe une bijection entre un ensemble fini non vide, S , et l'ensemble {1, 2, ..., n } pour tout nombre naturel positif n . Cette fonction est une injection de S dans N .

Proposition : Tout sous-ensemble d'un ensemble dénombrable est dénombrable. ]

Preuve : La restriction d'une fonction injective à un sous-ensemble de son domaine est toujours injective.

Proposition : Si S est un ensemble dénombrable et x ∉ S , alors S ∪ { x } est dénombrable. ]

Preuve : Soit f : S → N une injection, définissons g : S ∪ { x } → N comme g ( x ) = 0 et g ( y ) = f ( y ) + 1 pour tout y dans S . Cette fonction g est une injection.

Proposition : Si A et B sont des ensembles dénombrables, alors A ∪ B sont dénombrables. ]

Preuve : Soit f : A → N et g : B → N injections, définissons une nouvelle injection h : A ∪ B → N comme h ( x ) = 2 f ( x ) si x est dans A et h ( x ) = 2 g ( x ) + 1 si x est dans B mais pas dans A .

Proposition : Le produit cartésien de deux ensembles dénombrables A et B est dénombrable. ]

Preuve : Notons que N × N est dénombrable par définition car la fonction f  : N × N → N donnée par f ( m , n ) = 2 ^m 3 ⁿ est injective. ​ Ensuite, le théorème de base du produit cartésien suit, où deux ensembles dénombrables ont un produit dénombrable. Si A et B sont dénombrables, il existe des assujettissements f  : N → A et g  : N → B . Alors

f × g  : N × N → A × B

est une sujétion d'un ensemble dénombrable N × N à l'ensemble A × B et le corollaire implique que A × B est dénombrable. Ce résultat généralise le produit cartésien de toute collection finie d'ensembles dénombrables et la preuve par récurrence du nombre d'ensembles de la collection.

Proposition : Les entiers Z sont dénombrables et les nombres rationnels Q sont dénombrables.

Preuve : Les entiers Z sont dénombrables grâce à la fonction f  : Z → N donnée par f ( n ) = 2 ⁿ si n n'est pas négatif f ( n ) = 3 ^{− n} si n est négatif, c'est une fonction injective. Les nombres rationnels Q sont dénombrables grâce à la fonction g  : Z × N → Q donnée par g ( m , n ) = m /( n + 1) est un assujettissement de l'ensemble dénombrable Z × N aux rationnels Q.

Proposition : Les nombres algébriques A sont dénombrables.

Preuve : Puisque tous les nombres algébriques (y compris les nombres complexes) sont les racines d'un polynôme. Soit un polynôme , et le nombre algébrique est la kème racine du polynôme (Premièrement, trié par valeur absolue du plus petit au plus grand, puis, trié par argument du plus petit au plus grand). On peut définir une fonction injective (c'est-à-dire biunivoque) f  : A → Q donnée par , où est le nième premier .$a_{0}x^{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots +a_{n}x^{n}$$?$$f(\alpha )=2^{k-1}\cdot 3^{a_{0}}\cdot 5^{a_{1}}\cdot 7^{a_{2}}\cdot \dots \cdot {p_{n+2}}^{a_{n}}\cdot \dots$$p_{n}$

Proposition : Si A _n est un ensemble dénombrable pour tout n dans N alors l'union de tous A _n est aussi dénombrable. ]

Preuve : Ceci est une conséquence du fait que pour tout n il existe une fonction subjective g _n  : N → A _n et donc la fonction

$G:\mathbf {N} \times \mathbf {N} \to \bigcup{n\in \mathbf {N} }A_{n},$

donné par G ( n , m ) = g _n ( m ) est une sujétion. Puisque N × N est dénombrable, le corollaire implique que l'union est dénombrable. Nous utilisons l' axiome du choix dénombrable dans cette preuve pour choisir pour chaque n dans N un assujettissement g _n dans l'ensemble non vide des assujettissements de N à A _n .

Une preuve topologique de l'indénombrabilité des nombres réels est décrite dans la propriété d'intersection finie .

Modèle minimal de la théorie des ensembles

S'il existe un ensemble qui est un modèle standard (voir modèle interne ) de la théorie des ensembles ZFC, alors il n'y a pas de modèle standard minimum ( voir univers constructible ). Le théorème de Löwenheim-Skolem peut être utilisé pour montrer que ce modèle minimal est dénombrable. Le fait est que la notion d'« indénombrabilité » fait sens dans ce modèle, et en particulier ce modèle M contient des éléments qui sont :

• Sous-ensembles de M , donc dénombrables
• Mais d'innombrables sous le point de vue de M

Au début de l'existence, cette théorie était considérée comme un paradoxe (voir le paradoxe de Skolem ).

Le modèle standard minimum comprend tous les nombres algébriques et tous les nombres transcendantaux effectivement calculables , ainsi que de nombreux autres types de nombres.

Total des commandes

Les ensembles dénombrables peuvent être totalement ordonnés de différentes manières, par exemple :

• Avec un bon ordre (voir aussi nombre ordinal ):
  • L'ordre habituel des nombres naturels (0 , 1, 2, 3, 4, 5, ...)
  • Entiers dans l'ordre (0, 1, 2, 3, ...; -1, -2, -3, ...)
• Autres (en mauvais ordre):
  • L'ordre habituel des nombres entiers (..., -3, -2, -1, 0, 1, 2, 3, ...)
  • L'ordre habituel des nombres rationnels (ne peut pas être écrit explicitement comme une liste ordonnée)

Notez que dans les deux exemples de bon ordre, tout sous-ensemble a un élément mineur ; et dans les exemples des désordres, certains sous-ensembles n'ont pas de moindre élément . C'est la définition clé qui détermine si une commande totale est également une bonne commande.

Exemples

${\begin{array}{|rcr|}\hline n&\longmapsto &p\\\hline 1&\longmapsto &2\\2&\longmapsto &0\\3&\longmapsto &4\\4&\longmapsto &-2\\ 5&\longmapsto &6\\6&\longmapsto &-4\\7&\longmapsto &8\\8&\longmapsto &-6\\\cdots &\longmapsto &\cdots \\\end{array}}$

• L'ensemble de tous les nombres pairs est dénombrable car la fonction :

${\begin{array}{rccl}f:&N&\longrightarrow &P\\&n&\longmapsto &p=f(n)\end{array}}$

$f(n)={\begin{cases}p=n+1&,\;if :&n{\text{ est impair}}\\p=2-n&,\;if :&n{\text{ est pair}}\end{cases}}$

est une bijection : à tout nombre naturel correspond un seul nombre pair et inversement.

• L'ensemble de tous les nombres entiers est également dénombrable.$\mathbb{Z}$
• De plus, l'ensemble de tous les nombres rationnels est dénombrable. ]$\mathbb{Q}$
• L'ensemble est dénombrable.$\mathbb {N} \fois \mathbb {N}$
• Il découle de l'énoncé précédent que l'ensemble de tous les rationnels est également dénombrable, en tenant compte du fait que , où ne contient pas le 0 .$\mathbb {N} \times \mathbb {N'} =\mathbb {Q}$$\mathbb {N'}$
• Par induction, on peut prouver qu'ils sont dénombrables pour tout nombre naturel k .$\mathbb {N}<k},\mathbb {Z}<k},\mathbb {Q}<k}$

Voir aussi

• Nombre ordinal (théorie des ensembles)
• Alef (cardinaux)
• Compter
• nombre cardinal
• Paradoxe de l'hôtel de Hilbert
• ensemble fini
• ensemble infini
• espace compact
• ensemble indénombrable
• Hypothèse du continu

Liens externes

• Cet ouvrage contient une traduction complète dérivée de " Countable set " de Wikipedia anglais , en particulier cette version , publiée par ses éditeurs sous la licence de documentation gratuite GNU et la licence Creative Commons Attribution-ShareAlike 3.0 Unported .