Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Introduction Rappel mathématique • Définition et concepts de base de la théorie

Introduction Rappel mathématique • Définition et concepts de base de la théorie des ensembles; • Méthodes de preuve : § Par contradiction; § Par induction. • Ensembles finis, infinis, dénombrables et non dénombrables. Plan La théorie des ensembles • Égalité de deux ensembles; • Appartenance, inclusion, inclusion stricte; • L’ensemble puissance d’un ensemble; • Opérateurs ensemblistes; • Produit cartésien de deux ensembles; • Relations et fonctions; • Domaine, codomaine et image d’une relation; • Injectivité, surjectivité et bijectivité des fonctions. Définition • Un ensemble est une collection d’objets § Les objets sont appelés éléments ou membres; § Les éléments d’un ensemble ont, en général, une ou plusieurs propriétés qui les caractérisent. • Un ensemble pourrait être décrit par : § la définition des propriétés de ses éléments: A = {n: n ∈ N et n < 6} § l’énumération de ses éléments : B = {0,1,2,3,4,5}. Éléments d’un ensemble • Un ensemble peut contenir des ensembles, e.g. l’ensemble {{u},{v},{w}} • Un ensemble peut contenir à la fois des ensembles et des non ensembles, e.g. l ’ensemble {a,1,{a},{b}} • L’ensemble vide, noté {} ou ∅ est l ’ensemble qui ne contient aucun élément Ensemble infini • On décrit un ensemble infini en énumérant ses premiers éléments suivi de …, lorsque le contexte permet de comprendre ce que sont les éléments non énumérés. L’ensemble des entiers positifs pairs est {2,4,6,…} Exercice • Est-ce que les ensembles suivants sont vides? § {∅} R: Non, l’ensemble contient l’élément ∅. § {x∈ Z : x<0 et x2 <0} R: Oui, car x2 >0 même quand x < 0 donc l’ensemble ne contient aucun élément. § {{}} R: Non, l’ensemble contient l’élément {}= ∅. Définitions • Deux ensembles sont égaux si et seulement si ils ont les mêmes éléments • L’appartenance d’un objet « e » à un ensemble E est notée e ∈ E, inversement on note e ∉ E lorsque « e » n’appartient pas à l’ensemble E. • Un ensemble A est inclus dans un ensemble B, ce qui est noté A ⊆ B, si tous les éléments de A sont aussi des éléments de B. • Deux ensembles sont égaux si et seulement si A⊆B et B⊆A Définitions(suite) • A ⊂ B signifie que A est inclus dans B mais n’est pas égal à B. On dit alors que A est un sous-ensemble propre (ou strict) de B • L ’ensemble puissance de A, noté ℘(A), est l ’ensemble de tous les sous-ensembles de A. • Exemple: L ’ensemble puissance de {0,2,4} est: {∅,{0},{2},{4},{0,2},{2,4},{0,4},{0,2,4}} Opérations sur les ensembles • L’union de deux ensembles A et B, notée A ∪ B, est l’ensemble des éléments qui sont dans A ou dans B ou dans les deux ensembles; • L’intersection de deux ensembles, notée A ∩ B, est l’ensemble des éléments qui sont à la fois dans A et dans B; • La différence de deux ensembles, notée A ∖ B, est l’ensemble des éléments qui sont dans A et qui ne sont pas dans B. Opérations sur les ensembles(suite) • L’ensemble A ∖ B est appelé le complément de B par rapport à A • Le complément d’un ensemble est toujours relatif à un autre ensemble (ensemble de référence) • On peut omettre de mentionner l’ensemble de référence si le contexte permet de le déduire sans ambiguïté. Par exemple, si on parle des entiers naturels, le complément de {2,3,4} est {0,1,5,6,7,8,…} Produit cartésien • Le produit cartésien des ensembles A et B, noté A×B, est l ’ensemble de tous les couples (a,b) où a ∈ A et b ∈ B • On peut généraliser le produit cartésien à plusieurs ensembles: A1×A2 ×... ×An={(a1,a2,…,an):ai∈Ai pour i=1,2,…,n} • On écrit An au lieu de A ×A × A × A ... ×A. n fois Relation • Une relation R entre les ensembles A et B est un sous- ensemble du produit cartésien A×B, i.e. R ⊆ A×B • Une relation est caractérisée par: § Un ensemble de départ (A), § Un ensemble d’arrivée (B), § Un ensemble de couples vérifiant la relation qui est un sous-ensemble du produit cartésien A×B Définitions • Le domaine d’une relation R, noté dom(R), est l’ensemble des éléments de l’ensemble de départ qui apparaissent comme première composante d’au moins un couple de la relation § dom(R) = {e : (∃e’: (e,e’) ∈ R)} • L’image d’une relation, noté image(R), est l’ensemble des éléments de l’ensemble d’arrivée qui apparaissent au moins une fois comme deuxième composante d’au moins un couple de la relation § image(R)={e’:(∃e:(e,e’)∈R)} Définitions(suite) • Le codomaine d’une relation, noté codom(R), est l’ensemble d’arrivée de la relation. • Exemple : Soient S={2,4,6}, T={0,2,8,9,11} et R={(x,y) ∈ S×T : x est un diviseur exact de y} § L’ensemble de départ est S. § L’ensemble d’arrivée est T. § La relation R est {(2,0),(4,0),(6,0),(2,2),(2,8),(4,8)} § dom(R)={2,4,6}. § codom(R)= T. § image(R) = {0,2,8}. Définitions(suite) • Une image d’un élément « a » par une relation R est un élément « b » tel que (a,b) ∈ R. • L’ensemble image d’un ensemble est l’union des ensembles images de ses éléments. • L’image d’une relation est donc l’image de son domaine. Exemple • Soit la relation suivante: • b1 et b3 sont des images de a1 • {b1,b3} est l’ensemble image de a1 • {b4} est l’ensemble image de a3 • L’image {b1,b3,b4}, est l’image du domaine, {a1,a3} a3 a2 a1 b4 b3 b2 b1 A B Q Définition • Une fonction « f » d’un ensemble A dans un ensemble B est une relation ayant comme ensemble de départ A et comme ensemble d’arrivée B, et chaque élément de A apparaît une et une seule fois comme première composante d’un couple appartenant à « f » • Une fonction doit respecter les deux conditions suivantes: § (∀a ∈ A:(∃b ∈ B: (a,b) ∈f)), § (∀a ∈ A, b ∈ B, b’∈B :(a,b) ∈f ∧ (a,b’) ∈f ) b=b’). Exercice • Soit f: A→ B. Donner, si possible, § l’ensemble de départ de f: R: A § l’ensemble d’arrivée de f: R: B § le domaine de f: R: A, car tous les éléments doivent participer à f § le codomaine de f: R: B § l’image de f: R: inconnue. Définitions • Une fonction est injective ssi x≠y ) f(x) ≠f(y). Autrement dit, ssi deux éléments distincts de l’ensemble de départ ont deux images différentes • Une fonction est surjective ssi chaque élément de l’ensemble d’arrivée est l’image d’au moins un élément du domaine • Une fonction est bijective ssi elle est injective et surjective. Autrement dit, ssi chaque élément de l’ensemble d’arrivée est l’image d’un seul élément du domaine • Définition et concepts de base de la théorie des ensembles. • Méthodes de preuve : § Par contradiction. § Par induction. • Ensembles finis, infinis, dénombrables et non dénombrables. Plan Quantificateurs • Nous utiliserons les quantificateurs existentiel (∃) et universel (∀). • Lois de De Morgan: :(∀x:p(x)) , (∃x:¬p(x)), :(9 x:p(x)) , (∀ x:¬p(x)). Disposition des preuves expression0 op1 〈justification1〉 expression1 op2 〈justification2〉 expression2 … 〈...〉 opn 〈justificationn〉 expressionn Preuve par contradiction • On prouve un énoncé P par contradiction en montrant que : P ) faux. • La table suivante montre l ’équivalence des deux propositions: Preuve par induction • Il existe beaucoup d’équations du type: • Quelques essais peuvent nous convaincre, n = 0 21 - 1 = 20 = 1 n = 1 22 - 1 = 20 + 21 = 3 n = 2 23 - 1 = 20 + 21 + 22 = 7 mais ce n’est pas une preuve de la validité de l’équation pour tout n. Preuve par induction(Suite) • Soit P(n) un énoncé impliquant une variable entière n. Pour prouver que P(n) est vrai pour tout n ≥ n0, il faut montrer que: § P(n0) est vrai § Pour tout k ≥ n0, P(k) ⇒ P(k+1) Base d’induction Étape d’induction • Définition et concepts de base de la théorie des ensembles. • Méthodes de preuve : § Par contradiction. § Par induction. • Ensembles finis, infinis, dénombrables et non dénombrables. Plan Cardinalité d’un ensemble • La cardinalité d’un ensemble S, notée |S|, est la taille de cet ensemble, la quantité d’éléments qu’il contient • On dit que la cardinalité d’un ensemble S est inférieure ou égale à la cardinalité d’un ensemble T (dénoté par |S| ≤ |T|) ssi il existe une fonction injective f: S→T • On dit que la cardinalité d’un ensemble S est égale à la cardinalité d’un ensemble T (dénoté par |S|=|T|) ssi il existe une fonction bijective f: S→T Cardinalité d’un ensemble(suite) • On dit que la cardinalité d’un ensemble S est inférieure à la cardinalité d’un ensemble T( dénoté par |S| < |T| ) ssi |S| ≤ |T| et |S| ≠ |T|. • Autrement dit, |S| ≤ |T| ssi deux éléments distincts de S sont associés à deux éléments distincts de T. Si en plus chaque élément de T peut être associé à un élément de S, uploads/Philosophie/ seance-1-pdf.pdf