METHODOLOGIE[COURS][ENSEMBLES FINIS]
6Ensembles finisNous supposons avoir une idée intuitive de l’ensembleN sur lequel il existe une relation d’ordre strict"<". Nous supposons de plus l’assertion suivante :Toute partie non-vide deN admet un plus petit élément pour < (1)Un tel élément est alors unique. Nous rappelons le théorème suivant :1Théorème 1 Soient E,F deux ensembles non-vides et f: E →F une application.1. Il y a équivalence entre(a) f est injective;(b) il existe une application g: f(E)→E telle que g◦f =Id .E2. Il y a équivalence entre(a) f est surjective;(b) il existe une application g: F →E telle que f ◦g =Id .F3. Il y a équivalence entre(a) f est bijective;(b) il existe une application g: E →F telle que f ◦g =Id et g◦f =Id .F E∗Rappelons que nous notons pour n∈N ,N = [1,n] =Z∩[1,n].nDéfinition 2 Soient E,F deux ensembles. On dit queE et F sont équipotents s’il existe une bijectionϕ: E →F.∗Lemme 3 Soient n,m∈N et ϕ:N →N .m n1. Si ϕ est injective m6n;2. Si ϕ est surjective n6m;3. Si ϕ est bijective alors n =m;preuve:∗1. Posons P(m) la propriété "Pour tout n ∈ N , si ϕ:N → N est une application injective alorsm nm6n".∗ 2 ∗P(1) est vraie car pour tout n∈N , 16n. Soit m> 1 tel que P(m) soit vraie. Soit n∈N tel qu’ilexiste une application ϕ:N →N injective.m+1 ner1 cas : Supposons ϕ(m + 1) = n. Alors ϕ(N ) ⊆ N , donc nous disposons d’une applicationm n−1injectiveψ : N → Nm n−1x 7! ϕ(x)et par l’hypothèse de récurrence nous concluons que m6n−1 c’est-à-dire m+16n.ème2 cas : ...