cours/théorie des ensemble NBC.md

up, tags, aliases

up	tags	aliases
ensemble	s/maths/logique

Cette théorie ne se base pas sur des ensembles directement, mais sur des classes. Les classes sont caractérisées par \in, autrement dit une classe est définie par le prédicat indiquant ce qu'elle contient.

Définitions et Axiomes

[!definition] Classe Une classe C est un objet caractérisé par sa relation d'appartenance, c'est-à-dire que pour tout objet x on pourra dire si x \in C ou non. ^def-classe

[!proposition]+ Axiome d'extentionnalité Deux choses contenant les mêmes éléments sont égales. Autrement dit, C_1 = C_2 si et seulement si \forall x,\quad x \in C_1 \iff x \in C_2 ^ax-extentionnalite

[!definition] Inclusion La relation d'inclusion, notée \subseteq est définie par : C_1 \subseteq C_2 \iff \text{pour toute classe } X \text{ avec } X \in C_1 \text{ on a } X\in C_2 ^def-inclusion

[!definition] Ensemble Une classe A est un ensemble s'il existe une classe C telle que A \in C.

• i l'axiome d'extentionnalité s'applique également sur les ensembles
• i on note \mathcal{M} le prédicat "est un ensemble" (\mathcal{M}(x) \iff x \text{ est un ensemble}) ^def-ensemble

[!definition] Union et Intersection Soient C_1 et C_2 deux classes

• C_1 \cup C_2 est une classe dont les éléments sont les X qui appartiennent à C_1 ou à C_2
• C_1 \cap C_2 est une classe dont les éléments sont les X qui appartiennent à C_1 et à C_2
• i on sait par l'axiome d'extentionnalité que C_1 \cup C_2 et C_1 \cap C_2 sont uniquement déterminés par ces définitions ^def-union-intersection

[!definition] Complémentaire Soit C une classe C^{\complement} est la classe qui a pour éléments les X tels que X \notin C

• i on sait par l'axiome d'extentionnalité que C^{\complement} est uniquement déterminé par ces définitions

^def-complementaire

[!proposition]+ Axiome d'intersection Si x est un ensemble, si C est une classe, alors x \cap C est un ensemble

• i Par conséquence, si une classe C est contenue dans un ensemble A, alors C est un ensemble aussi.
  • dem car C \subseteq A entraine C = C \cap A ^ax-intersection

[!proposition]+ Axiome de la paire Si x et y sont des ensemble, alors il existe un ensemble dont les seuls éléments sont x et y. \tiny\mathcal{M}(x) \wedge \mathcal{M}(y) \implies (\exists z,\quad \mathcal{M}(z) \wedge x \in z \wedge y \in z \wedge (\forall t,\quad t \in z \implies (t=x \vee t=z)))

• i par l'axiome d'extentionnalité, on sait qu'il n'existe qu'un seul tel ensemble, que l'on note \{ x, y \}
• i si x = y on note simplement \{ x \}, c'est un singleton

[!proposition]+ Construction des couples (Kuratowski) Si x et y sont des ensembles, on pose : (x, y) = \{ \{ x \}, \{ x, y \} \} ^ax-paire

[!proposition]+ égalité sur les couples Soient x, y, x', y' des ensembles (x, y) = (x', y') \iff x=x' \wedge y=y'

[!démonstration]- Démonstration

• \boxed{\implies} Supposons que x=x' et y=y', on a alors \{ x, y \} = \{ x', y' \} et \{ x \} = \{ x' \} par l'axiome d'extension. Alors, à nouveau par extentionnalité, on a \{ \{ x \}, \{ x, y \} \} = \{ \{ x' \}, \{ x', y' \} \}
• \boxed{\impliedby} Supposons réciproquement que (x, y) = (x', y') On a alors : \{ \{ x \}, \{ x, y \} \} = \{ \{ x' \}, \{ x', y' \} \} Il suit par extension que l'un des cas suivants est réalisé :
  • soit \{ x \} = \{ x' \} et \{ x, y \} = \{ x', y' \} dans ce cas, on a x=x' par extension, et de là il est évident aussi que y = y'
  • soit \{ x \} = \{ x', y' \} et \{ x, y \} = \{ x' \} dans ce cas on sait que l'on doit avoir x=y et x'=y', et on en déduit \{ x \} = x' et y=y' Les autres cas peuvent être éliminés par extentionnalité.

[!proposition]+ n-uplets On peut construire les triplets, quadruplets etc. à partir des couples :

• (x, y, z) = ((x, y), z)
• (x, y, z, w) = (((x, y), z), w)
• \vdots

[!proposition]+ Axiome : graphe de la relation \in Il existe une classe E telle que pour tous les ensemble x, y on a (x, y) \in E si et seulement si x \in y. \boxed{(x, y) \in E \iff x \in y} E est le graphe de la relation \in

[!proposition]+ Axiome : existence du domaine Si C est une classe, il existe une classe notée \operatorname{dom}(C) telle que pour tout ensemble x on aie x \in \operatorname{dom}(C) si et seulement s'il existe un ensemble y tel que (x, y) \in C. \boxed{x \in \operatorname{dom}(C) \iff \exists y \text{ ensemble},\quad (x, y) \in C}

• i On dit que \operatorname{dom}(C) est le domaine de C ^ax-domaine

[!proposition]+ Axiome : existence du codomaine Si C est une classe, il existe une classe notée \operatorname{codom}(C) telle que pour tout ensemble y on aie y \in \operatorname{codom}(C) si et seulement s'il existe un ensemble x tel que (x, y) \in C. \boxed{y \in \operatorname{codom}(C) \iff \exists x \text{ ensemble},\quad (x, y) \in C}

• i On dit que \operatorname{codom}(C) est le codomaine de C ^ax-codomaine

[!proposition]+ Axiome : existence d'une classe de domaine C Si C est une classe, il existe une classe C' dont C est le domaine (\operatorname{dom}(C') = C), autrement dit : il existe une classe C' telle que \forall y \text{ ensemble},\quad (x, y) \in C' \iff x \in C ^ax-de-domaine

[!proposition]+ Axiome : existence d'une classe de codomaine C Si C est une classe, il existe une classe C' dont C est le codomaine (\operatorname{codom}(C') = C), autrement dit : il existe une classe C' telle que \forall x \text{ ensemble},\quad (x, y) \in C' ^ax-de-codomaine

[!proposition]+ Axiome : permutation des triplets Soit C une classe, alors :

• il existe une classe D telle que pour tous les ensembles x, y, z on aie (x, y, z) \in D \iff (y, x, z) \in C
• il existe une classe D' telle que pour tout les ensemble x, y, z on aie (x, y, z) \in D' \iff (x, z, y) \in C
• i ces classes ne sont pas uniquement déterminées par l'axiome d'extension, car leurs "définitions" prescrivent uniquement leurs couples ou trouples.

[!definition]+ Classe vide Il existe une et une seule classe qui n'a aucun élément. On dit que c'est la classe vide et on la note \emptyset

[!démonstration]- Démonstration (existence et unicité) L'axiome sue le graphe de la relation \in fournit une classe E. On peut alors former la classe E \cap E^{\complement} qui, par construction, n'a aucun élément. D'après l'axiome d'extentionnalité, c'est la seule telle classe.

[!proposition]+ Axiome (NBG) : ensemble vide \emptyset est un ensemble

• i Sans cet axiome, rien ne garantit l'existence d'ensembles

[!definition] Univers La classe U = \emptyset^{\complement} est appelée univers Par définition on a x \in U pour tout ensemble x. Pour toute classe C on a C \subseteq U

• i Le paradoxe de Russell montre qu'il existe une classe R qui n'est pas un ensemble. Comme toute sous-classe d'un ensemble est un ensemble aussi, on sait alors que U n'est pas un ensemble. ^definition

[!definition] Union d'une classe Soit C une classe Il existe une unique classe dont les éléments sont les éléments des éléments de C. On note cette classe \cup C (l'union de C).

[!démonstration]- Démonstration (existence et unicité) L'existence est évidente par définition, mais on peut également utiliser l'union de éléments de C. L'unicité est donnée par l'axiome d'extentionnalité. ^def-union-monadique

[!proposition]+ Produit cartésien Soient A et B des classes, il existe une unique classe dont les éléemnts sont les (x, y) avec x \in A et y \in B. On note cette classe A \times B

Plus généralement, soit n \in \mathbb{N}^{*}, soient A_1, \dots, A_{n} des classes Il existe une classe et une seule dont les éléments sont les $n$-uplets (x_1, \dots, x_{n}) avec x_1 \in A_1, \dots, x_{n} \in A_{n} On note cette classe A_1 \times \cdots \times A_{n}

• i Lorsque A_1 = \cdots = A_{n} on note A_1 \times \cdots \times A_{n} = A^{n}

[!démonstration]- Démonstration (existence et unicité) On sait par l'axiome d'extensionnalité qu'il existe au plus une telle classe (unicité). Il existe une classe A' telle que \forall x,\quad (x, y) \in A' \iff y \in A (telle que A = \operatorname{dom}(A')) Il existe une classe B' telle que \forall y,\quad (x, y) \in B' \iff x \in B (telle que B = \operatorname{codom}(B')) Alors, A' \cap B' existe (par axiome d'intersection) et convient : \forall x,\forall y,\quad (x, y) \in A'\cap B' \implies \begin{cases} x \in A \text{ car } (x, y) \in A' \cap B' \implies (x, y) \in A' \implies x \in A\\ y \in B \text{ car } (x, y) \in B' \end{cases}

[!proposition]+ Axiome (NBG) : Union d'un ensemble Si x est un ensemble, alors \cup x est un ensemble aussi. \mathcal{M}(x) \implies \mathcal{M}(\cup x)

Graphes

[!definition] Graphe Une classe C est un graphe si tous ses éléments sont des couples.

[!proposition]+ Image directe Soit G un graphe et C une classe. Il existe une unique classe (notée G[C] ou G\langle C \rangle) dont les éléments sont les ensembles y tels qu'il existe x \in C vérifiant (x, y) \in G Autrement dit : G[C] = \text{les ensembles } y \text{ tels que } \exists x,\quad x \in C \wedge (x, y) \in G ou encore : y \in G[C] \iff \mathcal{M}(y) \wedge (\exists x,\quad x \in C \wedge (x, y) \in G)

[!démonstration]- Démonstration (existence et unicité) La classe G \cap (C \times U) a pour éléments les couples (x, y) tels que x \in C et (x, y) \in G. Son théorie des ensemble NBC#^ax-codomaine convient : G[C] = \operatorname{codom}(G \cap (C \times U)) Cela montre l'existence de G[C] Son unicité est donnée par extentionnalité

[!definition] Classe fonctionnelle Une classe F est dite fonctionnelle si pour tous ensembles x, y, z tels que (x, y) \in F et (x, z) \in F on a y = z