UNC L Info 2020 Mathématiques pour l’Informatique 2 A. Giannakos Relations A :

UNC L Info 2020 Mathématiques pour l’Informatique 2 A. Giannakos Relations A : Fonctions, Relations d’Equivalence 1 Introduction Les notions de base pour définir des structures, c’est-à-dire des relations entre éléments d’ensembles et entre ensembles ont été développées dans des ordres d’exposé différents selon l’auteur. Ainsi, d’autres auteurs défi- nissent d’abord d’autres notions comme primordiaux et à travers ces premières définitions chacun considère des notions différentes comme dérivées des primordiaux : certains commencent par définir le concept fon- damental du morphisme, ensuite celui de la fonction comme cas spécial de morphisme, ensuite le produit cartésien et finalement le couple ordonné. Dans le cadre de cet exposé, nous faisons l’inverse : d’abord nous introduisons la notion du couple ordonné, d’où découle la définition du produit cartésien et de correspondance, dont les applications/fonctions sont des cas spéciaux, et les relations binaires encore comme cas des correspondances dont les relations d’équivalence et les ordres (voir la prochaine feuille) sont davantage des cas spéciaux, tandis que la notion de morphisme ne va pas nous préoccuper. Nous admettons sans expliciter les axiomes ZFC pour la théorie des ensembles (voir feuille précédent). 2 Généralités Couple ordonné Soient a, b deux éléments d’un ensemble X. Alors l’ensemble {{a}, {a, b}} est appelé couple ordonné de a et b, et il est noté (a, b); a est le premier élément du couple ordonné (a, b) – couple (a, b), s’il n’y a pas risque de confusion – et b est son deuxième élément. Evidemment si a , b alors (a, b) , (b, a) et (a, b) = (c, d) ⇔a = c et b = d. On peut généraliser la notion du couple ordonné à celle de nuplette : pour n > 2, (a1, . . . , an) = (a1, (a2, . . . , an)). Produit cartésien Soient deux ensembles A, B. On appelle produit cartésien de A et B, et on le note A × B l’ensemble contenant tous les couples ordonnés qui peuvent être formés avec un premier élément appartenant à A et un deuxième appartenant à B : A × B = {(a, b) : a ∈A, b ∈B}. Notons que A × B = B × A et que k  i=1 Ai désigne l’ensemble des kuplettes dont le premier élément vient de A1, . . . , etc., et le k−ème de Ak. Correspondance, relation binaire Soient deux ensembles A, B. Une correspondance C de A à B est un sous-ensemble de leur produit cartésien : C ⊆A × B. Si A = B, alors R ⊆A × A s’appelle relation binaire dans A 1. 1. A × A est souvent noté aussi A2. 1 3 Application/fonction Une correspondance F de A à B telle que : a) tout élément de A se trouve comme premier élément d’un couple de F et b) (a, b) ∈F et (a, c) ∈F ⇒b = c est appelée application (en anglais : mapping) de A dans B et notée F : A 7→B 2. Le terme fonction est un synonyme pour «application» mais certains auteurs le réservent pour des applications d’ensembles de nombres, tandis que d’autres ne font aucune distinction entre application et fonction. De plus, dans plusieurs contextes spécifiques, le terme fonction est à son tour remplacé par d’autres termes du contexte, comme «opérateur», «fonctionnelle», «mesure», «variable aléatoire» etc. A est appelé domaine de définition de F (ou encore : ensemble de départ – ce terme est aussi utilisé en général pour les correspondances de A vers B – et B est appelé domaine des valeurs de F (ou encore : ensemble de destination – ce terme étant lui aussi utilisé en général pour les correspondances de A à B). Soit a ∈A. Alors si (a, b) ∈F alors b est appelé l’image de a par F (ou encore : la valeur de F sur a) et noté b = F(a). Soit A′ ⊆A. Alors l’ensemble B′ ⊆B = {F(a) : a ∈A′} est appelé l’image de A′ par F et il est noté par F(A′). Soit B′ ⊆B. Alors l’ensemble f −1(B′) = {a ∈A : F(a) ∈B′} est appelé la préimage (ou encore : l’image réciproque) de B′ par F. Il se peut que pour quelques B′ ⊂B, f −1(B′) = ∅. L’ensemble F(A) est appelé range de F. Une fonction F : A 7→B est appelée surjection ssi F(A) = B. Si pour n’importe quels deux éléments distincts a1 et a2 de A, leurs images b1 = f(a1) et b2 = f(a2) sont aussi distinctes, F s’appelle injection. Si une fonction est à la fois surjection et injection, elle s’appelle bijection. Dans ce cas-là la correspondence F−1 : B 7→A telle que si F(a) = b, F−1(b) = a est aussi une fonction, et de plus, une bijection. 3.1 Quelques propriétés et catégories des fonctions Proposition 1 Soit une fonction F : A 7→B. Pour n’importe quels B1, B2 ⊆B il est F−1(B1 ∪B2) = F−1(B1) ∪F−1(B2) (la préimage de l’union est l’union des préimages). Proposition 2 Soit une fonction F : A 7→B. Pour n’importe quels B1, B2 ⊆B il est F−1(B1 ∩B2) = F−1(B1) ∩F−1(B2) (la préimage de l’intersection est l’intersection des préimages). Proposition 3 Soit une fonction F : A 7→B. Pour n’importe quels A1, A2 ⊆A il est F(A1 ∪A2) = F(A1) ∪F(A2) (l’image de l’union est l’union des images). 4 Relations d’équivalence Soit R une relation binaire dans A, avec les propriétés suivantes : - ∀a ∈A, (a, a) ∈R (réflexivité) - (a, b) ∈R ⇒(b, a) ∈R (symétrie) - (a, b) ∈R et (b, c) ∈R ⇒(a, c) ∈R (transitivité) Alors R s’appelle relation d’équivalence. Notons que la première relation d’équivalence connue depuis l’école, c’est l’égalité. Soit une relation d’équivalence R dans A; remarquons que, à cause de la réflexivité, tout élément de A participe à au moins un couple de R. Considérons, pour tout α ∈A, les ensembles Aα = {(a, b) : (a, b) ∈R}. Alors l’ensemble {Aα} 3 constitue une partition de A, c’est-à-dire, α , α′ ⇒Aα ∩A′ α = ∅et ∪αAα = A. Cet ensemble est noté A/R et appelé le quotient de A par R (ou encore : A modulo R). Les différents Aα s’appellent classes d’équivalence de A par rapport à R et les éléments d’une même classe Aα s’appellent équivalents par rapport à R. Chaque classe d’équivalence Aα peut être précisée en désignant un seul élément de la classe, son représentant. Inversement, étant donnée une partition quelconque de A en Aβ, nous pouvons définir une relation d’équiva- lence dans A comme R′ = {(a, b) : ∃β, a ∈Aβ et b ∈Aβ (a appartient au même Aβ que b)}. 2. Certains auteurs n’incluent pas la conditon a) dans la définition des fonctions, et palent de fonctions partielles lorsque cette condition n’est pas vérifiée et de fonctions totales lorsqu’elle l’est. 3. Attention! souvent pour α, α′ ∈A avec α , α′ il sera Aα = Aα′. Dans {Aα} on a retenu des Aα qui sont tous différents l’un de l’autre. 2 Exercices 1. Montrer que, étant donnée F : A 7→B et A1, A2 ⊆A, l’égalité F(A1 ∩A2) = F(A1) ∩F(A2) peut ne pas être vraie (pour démontrer ça il suffit alors de présenter un contre-exemple). 2. Montrer que, pour n’importe quelle F : A 7→B et B′ ⊆B, il est F−1  ∁B′ = ∁  F−1(B′)  . Est-il aussi vrai que pour n’importe quelle F : A 7→B et A′ ⊆A, F  ∁A′ = ∁(F(A′))? Justifier sa réponse. 3. Montrer que, si A′ ⊆A, B′ ⊆B, alors A′ × B′ ⊆A × B. En déduire que CR = {(x, y) : x, y ∈R, x2 + y2 = R2 pour un R réel quelconque } ne peut pas être exprimé en produit cartésien de deux sous-ensembles de R. 3 uploads/Litterature/ notes-math-info-2-ag-2020-sets-relations-2.pdf

Tags
littérature alors couple fonction appelé comme
Documents similaires
  • 31
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager