Cardinalité des ensembles finis PDF

denombrabilite.pdf

14 mai 2005 On conclut que E et P(E) ne sont pas équipotents. Corollaire 19 L'ensemble des parties de R n'est ni dénombrable ni équipotent `a R. Exercice ...

Annexe A - Ensembles dénombrables

Si p = 0 alors n = 0 car il n'existe pas d'application d'un ensemble non vide dans l'ensemble vide. On suppose le résultat acquis jusqu'au rang p ? 1 (p ? N

TD 0 : correction

contient sont donc non dénombrables. En effet notons P ? N l'ensemble des nombres pairs : on associe à ... de P

RUDIMENTS SUR LA CARDINALITE Introduction. Pour comparer la

Il existe des ensembles infinis non-dénombrables. En particulier l'ensemble P(N) est infini non-dénombrable. Preuve. Résulte immédiatement du a) ci-dessus

Théorie dintégration DM 1 Bernhard Haak et Elizabeth Strouse

Conclure. On définit ?(S) = ?k?SPn. Alors ? est une injection de l'ensemble P(N) dans T . DoncT contient un ensemble non–dénombrable; ainsi T

Cardinalité des ensembles finis

Il n'existe pas d'application bijective de E dans. P(E). On en déduit que P(N) n'est pas dénombrable. Théorème. L'ensemble [0

Chapitre 4 : Ensembles finis et infinis 1 Ensembles finis

Proposition 3 Soit E un ensemble et n et p des entiers naturels. S'il existe une bijection Proposition 15 P(N) et R ne sont pas dénombrables. Preuve.

12.2 Exercices du chapitre 2 - 12.2.1 Tribus

T(S) = P(E). • On suppose maintenant que E est infini non dénombrable. n est aussi au plus dénombrablece qui donne (?p?NAp)c ? A et.

Probabilités

(4) : R P(N) et AN avec Card(A) ? 2 ne sont pas dénombrables. (2) : Un ensemble non vide est fini ou dénombrable si et seulement s'il existe une ...

Variables aléatoires dénombrables

plus petit élément p qui n'appartient pas à son image : Si E contient un sous-ensemble infini non dénombrable alors E n'est pas dénom- brable.

[PDF] 35 “plus déléments” que N : les ensembles non dénombrables

ensembles étaient dénombrables puisque Z est dé- Soit f : A ?? P(A) une application surjective N vers {012} est donc non dénombrable C Q F D

[PDF] Ensembles dénombrables

On montre le résultat par récurrence sur p ? N Si p = 0 alors n = 0 car il n'existe pas d'application d'un ensemble non vide dans l'ensemble vide

[PDF] DENOMBRABILITE

14 mai 2005 · On conclut que E et P(E) ne sont pas équipotents Corollaire 19 L'ensemble des parties de R n'est ni dénombrable ni équipotent `a R Exercice

[PDF] 2 Ensembles et dénombrabilité

Les ensembles infinis dénombrables en bijection avec IN de cardinal noté 0 Les ensembles infinis non-dénombrables impossibles à mettre en

[PDF] 1 Ensembles

Correction de l'exercice 5 1 On rappelle qu'un ensemble E est dit dénombrable (ou au plus dénombrable) s'il existe une application ? : N ? E surjective

Exercices corrigés -Ensembles dénombrables ensembles équipotents

(N) P ( N ) n'est pas dénombrable Exercice 7 - [0

[PDF] Chapitre 4 : Ensembles finis et infinis 1 - Ceremade

Proposition 3 Soit E un ensemble et n et p des entiers naturels il suit que R n'est pas dénombrable car sinon P(N) le serait

[PDF] (P 2019) Le groupe symétrique SN est-il dénombrable ? Corrigé

Corrigé : Nous allons démontrer que SN n'est pas dénombrable Nous avons pour cela trois méthodes : construire une bijection entre SN et un ensemble non

[PDF] Cardinalitepdf - Laboratoire de Mathématiques Blaise Pascal

Il existe des ensembles infinis non-dénombrables En particulier l'ensemble P(N) est infini non-dénombrable Preuve Résulte immédiatement du a) ci-dessus

[PDF] DÉNOMBRABLE OU CONTINU

0 ; 1 [ n'est pas dénombrable C Ensembles ayant la puissance du continu L'intervalle ] –1 ; 1 [ a la puissance du continu

Comment montrer qu'un ensemble n'est pas dénombrable ?
Alors ?n ? 1, x = xn car an = an,n, ce qui est une contradiction. Un sous-ensemble A ? R tel que ? A = 0, n'est pas dénombrable. R n'est pas dénombrable. L'ensemble des nombres réels irrationnels n'est pas dénombrable (si tel n'´tait pas le cas, R = (R ? Q) ? Q) serait dénombrable).
Pourquoi n'est dénombrable ?
L'ensemble des entiers relatifs Z est dénombrable. Pour cela, on considère f:Z?N f : Z ? N telle que f(n)=2n f ( n ) = 2 n si n?0 n ? 0 et f(n)=?(2n+1) f ( n ) = ? ( 2 n + 1 ) si n<0 et on vérifie que f est une bijection de Z sur N.
Pourquoi l'ensemble R n'est pas dénombrable ?
Pour démontrer que ? est non dénombrable, il suffit de démontrer la non-dénombrabilité du sous-ensemble [0, 1[ de ?, donc de construire, pour toute partie dénombrable D de [0, 1[, un élément de [0, 1[ n'appartenant pas à D. Soit donc une partie dénombrable de [0, 1[ énumérée à l'aide d'une suite r = (r₁, r₂, r₃, … ).
En mathématiques, un ensemble est dit dénombrable, ou infini dénombrable, lorsque ses éléments peuvent être listés sans omission ni répétition dans une suite indexée par les entiers.

Cardinalité

Université de Toulouse

Année 2020/2021

1 / 23

Cardinalité des ensembles finis

Cardinalité des ensembles finis2 / 23

Ensembles équipotents

SoientE=fa;b;c;dgetF=f1;2;3g.Il existe une application surjective deEsurF, mais pas d"application injective.Il existe application injective deFsurE, mais pas d"application surjective. En fait, il n"y a pas assez d"éléments dansF(ou trop peu dansE). Le cardinal d"un ensemble précise la notion de nombre d"élémentsEnsemble de même cardinal Deux ensembles (fini ou non) sontéquipotentsou demême cardinals"il existe une bijection entre eux. Cardinalité des ensembles finisEnsembles équipotents3 / 23

Cardinal d"un ensemble fini

Définition

Un ensembleEestfinisiE=;ou si9n2?tel queEest en bijection avecf1;:::;ng. Cet entier est unique, il est appelé lecardinaldeEnoté

Card(E). SiE=;, on poseCard(E) =0.Pour montrer que cet entier est définit de manière unique, on prouve la

proposition suivante :Proposition S"il existe une application injective def1;:::;ngdansf1;:::;kgalors nk.S"il existe une application surjective def1;:::;ngdansf1;:::;kg alorsnk.S"il existe une application bijection def1;:::;ngdansf1;:::;kgalors n=k.Cardinalité des ensembles finisCardinal d"un ensemble fini4 / 23

Cardinal d"un ensemble fini

Définition

Un ensembleEestfinisiE=;ou si9n2?tel queEest en bijection avecf1;:::;ng. Cet entier est unique, il est appelé lecardinaldeEnoté Card(E). SiE=;, on poseCard(E) =0.Qui se traduit de la manière suivante avec les cardinaux.

Proposition

SoientEetFdeux ensembles finis. On a :Il existe une application injective deEdansFsi et seulement si Card(E)Card(F).Il existe une application surjective deEdansFsi et seulement si Card(E)Card(F).Il existe une application bijective deEdansFsi et seulement si Card(E) =Card(F).Cardinalité des ensembles finisCardinal d"un ensemble fini4 / 23

Principe des tiroirs

SoientEetFdeux ensembles finis non vides etf:E!Fune application. SiCard(E)>Card(F)alors il existex1;x22Etels quef(x1) =f(x2).Nombre moyen de cheveux : 150000

Nombre d"habitant à Paris : 2,2 million

Il y a au moins deux personnes à Paris qui ont exactement le même nombre de cheveux.Principe des tiroirs généralisé SoientEetFdeux ensembles finis non vides etf:E!Fune application. SiCard(E)>kCard(F)aveck2?alors il existe une valeur defqui est répétée au moinsk+1 fois.Cardinalité des ensembles finisPrincipe des tiroirs5 / 23

Principe des tiroirs

SoientEetFdeux ensembles finis non vides etf:E!Fune application. SiCard(E)>Card(F)alors il existex1;x22Etels quef(x1) =f(x2).Nombre moyen de cheveux : 150000

Nombre d"habitant à Paris : 2,2 million

Dénombrement

Dénombrement6 / 23

Pourquoi dénombrer un ensemble fini?

En informatique vous utiliserez la notion de dénombrement au moins dans

les deux cas de figures suivants :dénombrer le nombre de cas à analyser par un algorithme en vu

d"étudier sa complexité;lorsqu"on tire au hasard un élément dans un univers finis de manière équiprobable (c"est à dire que chaque élément à la même probabilité d"être tiré), la probabilité que cet élément soit dans l"ensembleA est

P(A) =Card(A)Card(

):DénombrementMotivations7 / 23 Dénombrement et opérations sur les ensembles Union

Card(A[B) =Card(A) +Card(B)Card(A\B)AB

abcd efgh DénombrementOpération sur les ensembles8 / 23 Dénombrement et opérations sur les ensembles Union

Card(A[B) =Card(A) +Card(B)Card(A\B)

Card(A[B[C) =Card(A) +Card(B) +Card(C)Card(A\B)

Card(A\C)Card(B\C) +Card(A\B\C)AB

C abcd efgh i jkl m DénombrementOpération sur les ensembles8 / 23 Dénombrement et opérations sur les ensembles

Produit cartésien

Card(AB) =Card(A)Card(B)

Card(A1 An) =Card(A1) Card(An)a

1a 2a 3a

4(a1;b1)(a1;b2)(a1;b3)(a2;b1)(a2;b2)(a2;b3)(a3;b1)(a3;b2)(a3;b3)(a4;b1)(a4;b2)(a4;b3)A=fa1;a2;a3;a4g,B=fb1;b2;b3g,Card(AB) =43=12DénombrementOpération sur les ensembles9 / 23

Dénombrement et opérations sur les ensembles

Passage au complémentaire

Card A

=Card(

)Card(A)DénombrementOpération sur les ensembles10 / 23

Arrangement

Permutation denélémentsNombre de façon de rangernobjets dans l"ordre. n! =n(n1)(n2) 21Examples :

DénombrementArrangement11 / 23

Arrangement

Permutation denélémentsNombre de façon de rangernobjets dans l"ordre. n! =n(n1)(n2) 21Examples : Voici les 4! =24 permutations de quatre éléments distincta,b,cetd: abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cdba cdab cdba dabc dacb dbac dbca dcab dcba

DénombrementArrangement11 / 23

Arrangement

De combien de façons pouvez-vous ranger 10 livres sur une étagère?DénombrementArrangement11 / 23