# Introduction aux mathématiques/Notion d'ensemble
## Définitions
### Ensemble, élément

C'est une notion à la fois difficile à définir très proprement et à la fois très intuitive : on se contentera de l'intuition. Un ensemble est donc une « collection » d'objets qu'on appelle ses éléments. On note $x\in E$ pour signifier que l'élément $x$ appartient à l’ensemble $E$, et $x\notin E$ pour dire le contraire.

### Partie

Soient $E$ et $F$ deux ensembles. On dit que $E$ est inclus dans (ou est une partie de, ou encore est un sous-ensemble de) $F$, et on note $E\subset F$, si et seulement si $\forall x\ \left(x\in E\Rightarrow x\in F\right)$.
On note ${\mathcal {P}}(F)$ l’ensemble des parties de $F$. Ainsi $E\subset F\Leftrightarrow E\in {\mathcal {P}}(F)$.
Deux ensembles $E$ et $F$ sont égaux et on écrit $E=F$ si et seulement si $E\subset F$ et $F\subset E$, c'est-à-dire s’ils ont exactement les mêmes éléments.
Enfin, on note $E\subsetneq F$ pour signifier $E\subset F$ et $E\neq F$.

### Prédicat

Soit $E$ un ensemble. On appelle prédicat sur $E$ la donnée, pour chaque élément $x$ de $E$, d'une assertion $P(x)$.
Exemple :
* Pour tout $x$ réel, on définit $P(x)$ par : $x\geq 1$. C'est un prédicat sur $\mathbb {R}$, vrai pour 2 et faux pour 0.

### Définition d'un ensemble en compréhension

On a le droit de définir l’ensemble des éléments d'un ensemble $E$ vérifiant un prédicat $P$, on le note $\{x\in E/P(x)\}$. On parle de définition en compréhension. Il est crucial de préciser l’ensemble d'origine des éléments $x$. Sinon on pourrait considérer l’ensemble $E:=\{x/x\notin x\}$ : a-t-on $E\in E$ ?

### Ensemble vide

Il existe un ensemble qui ne contient aucun élément : en effet on considère un ensemble $E$ quelconque et l’ensemble $\emptyset :=\{x\in E/x\neq x\}$. De plus $\emptyset$ appartient à tous les ensembles. Un tel autre ensemble $E$ vérifierait alors $\emptyset \subset E$ et $E\subset \emptyset$, d'où l'égalité. On parle alors de l'ensemble vide.
Remarque : On a ${\mathcal {P}}(\emptyset )=\{\emptyset \}$ qui est donc non vide.

### Définition d'un ensemble en extension

Un ensemble peut être défini en extension, c'est-à-dire en donnant la liste de ses éléments entre accolades. Par exemple $\{a,b,c\}$ représente l’ensemble dont les éléments sont $a$, $b$ et $c$.

### Paire

Étant donnés deux objets $x$ et $y$, on peut définir l’ensemble les contenant exactement : il s'agit de la paire $\{x,y\}$.

### Couple

Pour que l’ordre des éléments ait une importance, on définit le couple $(a,b)$ par $(a,b):=\{\{a\},\{a,b\}\}$. On peut vérifier la proposition suivante :
$\forall a,b,c,d,\;(a,b)=(c,d)\Leftrightarrow a=c{\text{ et }}b=d$
* $\Leftarrow$ est triviale.
* $\Rightarrow$ : $\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$, montrons que $a=c$ et $b=d$.
** Si $a=c$ alors $\{a,b\}=\{c,d\}$ et comme $a=c$, on obtient aussi $b=d$.
** Sinon $a\neq c$, mais alors $\{a\}=\{c,d\}$ et $\{a,b\}=\{c\}$. Par suite $\{c\}=\{a,b\}=\{c,d,b\}$ et donc $a=b=c=d$ qui est absurde ici.

### Produit cartésien

On appelle alors produit cartésien de deux ensembles $E$ et $F$, l’ensemble des couples $(x,y),\;x\in E,\,y\in F$. On le note $E\times F$, lire « E croix F ». Ceci s'étend pour définir des triplets $(a,b,c)$; des quadruplets $(a,b,c,d)$; des $n$-uplets $(a_{1},a_{2},\dots ,a_{n})$.

## Opérations sur les ensembles
### Différence, complémentaire

On appelle différence A et B dans cet ordre, pour deux parties d'un ensemble E, l’ensemble noté $A\setminus B:=\{x\in E/x\in A{\text{ et }}x\notin B\}$.
En particulier on définit pour une partie A d'un ensemble E son complémentaire dans E, noté $\complement _{E}A$ ou $A^{c}$ s'il n’est pas nécessaire de préciser E.
Exercice : Que dire de $A\setminus \emptyset$ ; $\emptyset \setminus A$; $A\setminus A$, pour $A\in {\mathcal {P}}(E)$ ?

### Intersection, réunion

On appelle intersection de deux ensembles A et B l’ensemble $A\cap B:=\{x\in E\mid x\in A{\text{ et }}x\in B\}$, lire « A inter B ».
On appelle réunion de deux ensembles A et B l’ensemble $A\cup B:=\{x\in E\mid x\in A{\text{ ou }}x\in B\}$, lire « A union B ».

#### Exercice

   * Que dire de $A\cup \varnothing$ ?
   * Que dire de de $A\cap E$ pour $A\in {\mathcal {P}}(E)$ ?
   * Faire le lien entre connecteurs logiques/quantificateurs et différence/réunion/intersection. On en déduit facilement les propriétés suivantes :
Soient A, B et C trois parties d'un ensemble E. On a alors les propriétés suivantes :
* commutativité : $A\cap B=B\cap A$ et $A\cup B=B\cup A$ ;
* associativité : $(A\cap B)\cap C=A\cap (B\cap C)$ et $(A\cup B)\cup C=A\cup (B\cup C)$ ;
* distributivité de $\cap$ sur $\cup$ : $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$ ;
* distributivité de $\cup$ sur $\cap$ : $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$ ;
* lois de De Morgan : $E\setminus (A\cap B)=(E\setminus A)\cup (E\setminus B)$ et $E\setminus (A\cup B)=(E\setminus A)\cap (E\setminus B)$.

### Différence symétrique

Soient A et B deux parties d'un ensemble E. Alors $(A\cup B)\setminus (A\cap B)$=$(A\setminus B)\cup (B\setminus A)$. On appelle différence symétrique de A et B cet ensemble qu'on note $A\Delta B$, il est formé des éléments qui sont ou bien dans A ou bien dans B.
Exercice :
* Montrer que la différence symétrique est commutative et associative.
* Que dire de $A\Delta \emptyset$; de $A\Delta A$ ?
* Montrer que $\cap$ est distributive sur $\Delta$.

## Quantificateurs
### Quantificateur existentiel

* On écrit $\exists x\in E/P(x)$ pour signifier qu’il existe au moins un x élément de E tel que P(x) soit vrai.
* On écrit $\exists !x\in E/P(x)$ pour signifier qu’il existe un unique x élément de E tel que P(x) soit vrai.

### Quantificateur universel

* On écrit $\forall x\in E,P(x)$ pour signifier que pour tous les éléments x de E, P(x) est vrai.

### Négations des quantifications

On a :
* ${\text{non}}(\exists x\in E/P(x))\Leftrightarrow (\forall x\in E,{\text{non}}\,P(x))$
* ${\text{non}}(\forall x\in E,P(x))\Leftrightarrow (\exists x\in E/{\text{non}}\,P(x))$
| Rudiments de logique | Applications |