.. _ensembles: ================================== Théorie élémentaire des ensembles ================================== Nous donnons ici les définitions et notations indispensables à la manipulation naïve des ensembles. La théorie formelle des ensembles est une théorie mathématique qui permet de fonder rigoureusement une part gigantesque des toutes les mathématiques, en évitant soigneusement bien des paradoxes. Les objets de base de cette théorie sont les ensembles. La relation de base sur ces ensembles est l'appartenance. Langage de base =============== On écrit `x\in y` et on lit `x` *appartient* à `y` pour signifier que `x` est un élément de l'ensemble `y`. On écrit `x\subset y` et on dit que `x` *est inclus dans* `y` pour signifier que tout élément de `x` est aussi élément de `y`. On dit aussi que `y` est une *partie*, ou encore un *sous-ensemble*, de `x`. La négation de cette phrase, qui s'écrit `x\not\subset y` signifie qu'il existe un élément dans `x` qui n'appartient pas à `y`. En utilisant les quantificateur (*pour tout* : `\forall`, et *il existe* : `\exists`) et les connecteurs (*entraine* : `\then` et *et* : `\land`), ces deux phrases s'écrivent respectivement .. math:: \forall z, z\in x \then z\in y \\ \exists z, z\in x \land z\not\in y L'égalité de deux ensembles, notée `x=y` signifie qu'ils ont exactement les mêmes élément, c'est à dire `\forall z, z\in x \iff z\in y` (en utilisant le connecteur *équivaut à* : `\iff`), ou encore que `x\subset y \land y\subset x`. Quand c'est le cas, on peut remplacer dans n'importe quelle phrase `x` par `y` sans changer sa véracité. Donc pour définir un ensemble, il convient de décrire ses éléments. S'ils sont en nombre fini (et petit), on peut en faire la liste, comme par exemple `\B=\{0,1\}`, et quand c'est clair utiliser une ellipse (les trois petits points), comme par exemple `\{a,\dots,z\}` désigne l'ensemble des lettres de l'alphabet. On dit que l'on définit l'ensemble *en extension*. Dans d'autre cas, il convient pour définir l'ensemble `x` de donner une phrase équivallente à `z\in x`. On dit que l'on définit `x` *en compréhension*. L'ensemble `\{x,y\}`, par exemple, est ainsi définit par `z\in\{x,y\}` équivaut à `z=x\lor z=y`. On l'appelle *la paire* `x`, `y`. Il se peut que `x=y` auquel cas on écrit simplement `\{x\}` et on parle du *singleton* `x`. L'ensemble `\{\{x\},\{x,y\}\}` est le *couple* `x`, `y`. Pour abbreger, on préfère le noter `(x,y)`. La caractéristique des couples est que `(x,y)=(u,v)` équivaut à `x=u\land y=v`. Donc il ne faut pas confondre les paires et les couples. Par exemple on a toujours `\{x,y\}=\{y,x\}` alors que `(x,y)=(y,x)` équivaut à `x=y`. Continuons les définitions d'ensembles en compréhension. Par exemple on définit *l'intersection* de `x` et `y` par : `z\in x\cap y` équivaut à `z\in x \land z\in y`. De même on définit *l'union* de `x` et `y` par : `z\in x\cup y` équivaut à `z\in x \lor z\in y` (en utilisant le connecteur *ou* : `\lor`). De même on définit *la différence* : `x` privé de `y` par : `z\in x\setminus y` équivaut à `z\in x \land z\not\in y`. Il y a un ensemble qui ne contient aucun élément. C'est *l'ensemble vide*, noté `\emptyset`. Donc la phrase `x\in\emptyset` est toujours fausse, quel que soit `x`. Donc `\emptyset\subset y`, pour tout `y`. Quand `x` désigne un ensemble, `\powset{x}` désigne *l'ensemble des parties* de `x` : `z\in\powset{x}` équivaut à `z\subset x`. On dit aussi que `\powset{x}` est l'ensemble *puissance* de `x`. L'ensemble *produit cartesien* de `X` et `Y` est noté `X\times Y`. C'est l'ensemble des couples `(x,y)` tels que `x\in X` et `y\in Y`. Relations, fonctions, application ================================= Une *relation* `R` de `X` dans `Y` est une partie de `X\times Y`. On écrit `xRy` pour `(x,y)\in R`, ce qui se lit `x` est en relation par `R` avec `y`. On dit aussi que `y` est une *image* de `x` par `R` et que `x` est un *antécédent* de `y` par `R`. Le domaine de `R` est l'ensemble `\dom R` des `x\in X` pour lesquels il existe `y\in Y` tel que `xRy`. De façon symétrique, l'image de `R` est l'ensemble `\img R` des `y\in Y` pour lesquels il existe `x\in X` tel que `xRy`. La relation inverse de `R` est `\inverse(R)` de `Y` dans `X` définie par `y \inverse R x` si et seulement si `x R y`. Si `R` est une relation de `X` dans `Y` et si `S` est une relation de `Y` dans `Z`, alors la composée de `R` et `S` est la relation `\comp(R,S)` de `X` dans `Z` définie par `x \comp(R,S) z` si et seulement si il existe `y\in Y` tel que `x R y` et `y S z`. La relation `R` de `X` dans `Y` est *fonctionelle* si `x R y` et `x R y'` entraine `y = y'`, c'est-à-dire si tout élément `x\in X` a au plus une image par `R`. La relation `R` de `X` dans `Y` est une *application* de `X` dans `Y` si elle est fonctionelle et si `\dom R = X`, c'est-à-dire si tout élément `x\in X` a exactement une image par `R`. On note `R(x)` cette image de `x` par `R` et on note `R: X\to Y` le fait que `R` soit une application de `X` dans `Y`. Si `R:X\to Y` et si `S:Y\to Z`, alors la composée `\comp(R,S)` de `R` et `S` est une application de `X` dans `Z` notée `S\circ R` de sorte que `S\circ R(x) = S(R(x))`. Une application `R: X\to Y` est *injective* si son inverse `\inverse(R)` est fonctionelle ; et *surjective* si `\dom \inverse(R) = Y` ; et *bijective* si elle est à la fois injective et bijective, c'est-à-dire si `\inverse(R)` est une application de `Y` dans `X`, que l'on note alors `R^{-1}`. Ainsi, lorsque `R` est une application bijective, `y=R(x)` équivaut à `x=R^{-1}(y)`. Soit `f:X\to Y` et `g:Y\to Z`, et `h:Z\to X`. Si `g\circ f` est injective alors `f` l'est. Si `f\circ h` est surjective alors `f` l'est. Si `Z=X`, `g\circ f` est l'identité sur `X`, (c'est-à-dire la relation diagonale de `X\times X`, celle qui contient exactement les couples `(x,x)` quand `x` parcourt `X`, qui est aussi l'application `I_X: X\to X` telle que `I_X(x)=x` pour tout `x\in X`) et `f\circ h` est l'identité sur `Y`, alors `f` est bijective et `g=f^{-1}=h`. Familles ======== Une application d'un ensemble `I` dit ensemble d'indices dans `\powset{X}` définit une *famille* `(X_i)_{i\in I}` de parties de `X` : pour tout `i\in I`, on a `X_i\subset X`. Le produit cartésien (généralisé) de cette famille, noté `\Pi_{i\in I} X_i`, est l'ensemble des familles `(x_i)_{i\in I}` (c'est-à-dire des applications de `I` dans, par exemple, `X`) telles que `x_i\in X_i` pour tout `i \in I`. On parle de *produit dépendant* dans la mesure où les facteurs `X_i` dépendent de `i`. Si au contraire, tous les `X_i` sont égaux, par exemple à `X`, on note ce produit cartésien `X^I`, et c'est l'ensemble des aplications de `I` dans `X`. Retournons au cas d'une famille `(X_i)_{i\in I}` de parties de `X`. On note `\cap_{i\in I}X_i` l'ensemble des `x\in X` tels que `\forall i\in I, x\in X_i`. On note `\cup_{i\in I}X_i` l'ensemble des `x\in X` tels que `\exists i\in I, x\in X_i`. Cela généralise l'intersection et l'union de deux ensembles.