Surjection

PCSI1-PCSI2 DNS n 04 - Cahier vacances ˚ 2011-2012 Ce qui suit fera office de cours sur les notions d’injection/surjection/bijection. Les exercices obligatoires, à traiter en priorité sont les suivants : , , , et et , , , et , , . Les autres exercices n’en sont pas moins intéressants pour autant, et doivent mériter votre attention. 1 Définitions de injection-surjection-bijection On considère une application , où est l’ensemble de départ (ensemble de définition , par . existe (de manière

définition de la restriction de f : E → F à E ⊂ E notée f| E . Définition d’un prolongement. Exemples. 4. Composition : définition de la composée de f par g notée g ◦ f . Associativité et non commutativité (contreexemple sur ). R 5. Injection, surjection et bijection : définitions et négations des trois notions. exp : → ∗ est surjective de dans ∗ et non injective sur . f est bijective de E dans F ssi il existe g : F → E telle que f ◦ g = IF et g ◦ f = IE , on note g = f −1 . Définition d’une involution

{n}) dans N2 . Ainsi on peut construire une surjection φ : N → e ∪n≥0 An . Pour tout x ∈ ∪n≥0 An on pose f (x) = inf{n ∈ φ−1 (x)}. L’application f est bien d´finie e et injective. Ainsi ∪n≥0 An est en bijection avec f (E) qui est une partie infinie de N, ce qui termine la preuve du r´sultat. e 1.(b) Si E est infini alors il contient une partie N en bijection avec N. Ainsi P(E) contient P(N ) qui est en bijection avec P(N). Or il n’existe pas de surjection de P(N) dans N. Donc P(N) n’est pas d´nombrable

on a toujours, ce dont on se sert souvent, |A ∪ B| ≤ |A| + |B|. Soient E et F deux ensembles finis, on a 1 2 • |P(E)| = 2|E| , • |E × F | = |E| × |F |, • |F E | = |F ||E| , • si f est une injection de E dans F alors |E| ≤ |F |, • si f est une surjection de E dans F alors |E| ≥ |F |, • si f est une bijection de E dans F alors |E| = |F |, CHAPTER 1. RAPPELS 1.3 Changements de base 7302 = 7 × 103 + 3 × 102 + 0 × 101 + 2 × 100 . On est habitu´s ` ´crire les nombres en base 10, quand on

◦ h) et ( f ◦ g) ◦ h. 4. Pour la fonction f : R → R définie par x → x2 représenter et calculer les ensembles suivants : f ([0, 1[), f (R), f (] − 1, 2[), f −1 ([1, 2[), f −1 ([−1, 1]), f −1 ({3}), f −1 (R \ N). 3. Injection, surjection, bijection 3.1. Injection, surjection Soit E, F deux ensembles et f : E → F une application. Définition 3 f est injective si pour tout x, x ∈ E avec f (x) = f (x ) alors x = x . Autrement dit : ∀ x, x ∈ E f (x) = f (x ) =⇒ x = x Définition 4 f est surjective si

définie par f (n)  2n si n  0 et f (n)  2n  1 si n  0 est bijective.  Encore des exemples !!! 5 Algèbre 1 Expression de l’application, l’injection, la surjection et de la bijection à l’aide des symboles :  Une application : ? = ? ⟹ ? ? = ? ? .  Une injection : ? ? = ? ? ⟹ ? = ? ?? ? ≠ ? ⟹ ? ? ≠ ? ? .  Une surjection : ∀??? ∃? ∈ ? ??? ??? ? = ? ? .  Une bijection : ∀??? ∃! ? ∈ ? ??? ??? ? = ? ? . Théorème : Une application est bijective ssi elle admet une réciproque. Pour la

(k )(n −k ) . n k =0 n Exercice 54 Soit E et F deux ensembles finis non vides de cardinaux respectifs n et p . p On note Sn le nombre de surjections de E sur F . 1 n p a) Calculer Sn , Sn et Sn pour p > n . b) On suppose p ≤ n et on considère a un élément de E . On observant qu’une surjection de E sur F réalise, ou ne réalise pas, une surjection de E \ {a } p −1 p sur F , établir Snp = p (Sn −1 + Sn −1 ) . p c) En déduire que Snp = ∑ (−1) p−k k k n . k =0 p Exercice 55 Pour n ∈ ℕ∗ et

exemple : • si un seul ny est égal à 2 alors f n’est pas injective. • Si l’un des ny est égal à 0, alors f n’est pas surjective. • Pour que f soit bijective il faut que {ny , y ∈ F } = {1}. Définition 1.7. On dit qu’une application f : E → F est une surjection ou est surjective ssi f vérifie l’une des trois propriétés équivalentes : (1) Tout élément y ∈ F admet au moins un antécédent dans E. (2) Pour tout élément y ∈ F , l’équation { x∈E f (x) = y admet au moins une solution (3) ∀y ∈ F, ∃x ∈ E tel que

que parmi toutes ces bijections f , il n’en existe aucune qui v´rifie en plus les propri´t´s 1 e ee ˜ est continue , f est continue et f ˜ e la notation f d´signant la fonction r´ciproque de f . e Avant cela, indiquons rapidement qu’il existe des surjections continues [0, 1] → [0, 1]2 . Une fa¸on d’en construire est la c suivante, due ` Peano ( 1890). Il s’agit de construire une suite de fonctions continues f n : [0, 1] → [0, 1]2 telles que a ◦ si l’on note δn la distance maximale d’un point de [0,

orthonormé R du plan étant choisi, le graphe de f s’identifie à l’ensemble des points de coordonnées (x; f (x)) pour x décrivant E, appelé courbe représentative f dans R. PCSI 1 Lycée Descartes 2 LES FONCTIONS USUELLES I.2 Injection, surjection, bijection Définition I.3 Une application f : E → F est : • injective si tout élément de F possède un unique antécédent par f . • surjective si tout élément de F possède au moins un antécédent par f . • bijective si elle est injective et surjective