|
[Je viens de relir le tout. J'ai suivi ton habitude de préciser les définition et les théorème dans le titre. J'ai viré les crochets qui jalonnait la page en mettant des exos à la place. pour la dernière section, j'ai fais quelques retouches, j'ai vu que tu les avais vu, voilà je vais etre devant mon ordi si tu veux en reparler, sinon on peut le balancer ce truc là je crois ?]
[Okay, je me suis permis de retirer les crochers restants. Je vois rien à redire (sauf un léger manque d'illustrations parfois, mais ça peut se régler plus tard), je suis sur IRC si tu as besoin de détails sur le qui/quoi/quand/comment du publiage.]
=Rudiments de logique=
* <math>\text{non}(\exists x\in E / P(x)) \Leftrightarrow (\forall x\in E, \text{non}\, P(x))</math>
* <math> \text{non}(\forall x\in E, P(x))\Leftrightarrow (\exists x\in E / \text{non}\, P(x))</math>
=Notion d'ensemble=
==Définitions==
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 ces '''éléments'''. On note <math>x\in E</math> pour signifier que l'élément <math>x</math> appartient à l'ensemble <math>E</math>, et <math>x \notin E</math> pour dire le contraire.
Soient <math>E</math> et <math>F</math> deux ensembles. On dit que <math>E</math> est inclus dans (où est une partie de, où encore est un sous ensemble de) <math>F</math>, et on note <math>E\subset F</math>, ssi <math>\forall x, \; x\in E \Rightarrow x\in F</math>. On note <math>\mathcal{P}(F)</math> l’'''ensemble de ces parties''' <math>E\subset F</math>. Ainsi <math>E\subset F\Leftrightarrow E\in\mathcal{P}(F)</math>. Enfin on note <math>E\subsetneq F</math> pour signifier <math>E\subset F</math> et <math>E\neq F</math>.
Deux ensembles <math>E</math> et <math>F</math> sont égaux et on écrit <math>E=F</math> ssi <math>E\subset F</math> et <math>F\subset E</math>, ''ie.'' qu'ils ont exactement les mêmes éléments.
On a le droit de définir l'ensemble des éléments d'un ensemble <math>E</math> vérifiant un prédicat <math>\mathcal{P}</math>, on le note <math>\{x\in E / \mathcal{P}(x)\}</math>. On parle de définition en '''compréhension'''. Il est crucial de préciser l'ensemble d'origine des éléments <math>x</math>. Sinon on pourrait considérer l'ensemble <math>E:=\{x/x\notin x\}</math> : a-t-on <math>E\in E</math> ?
Il existe un ensemble qui ne contient aucun élément : en effet on considère un ensemble <math>E</math> quelconque et l'ensemble <math>\emptyset:=\{x\in E / E \neq E \}</math>. De plus <math>\emptyset</math> appartient à tous les ensembles. Un tel autre ensemble <math>E</math> vérifierait alors <math>\emptyset\subset E</math> et <math>E\subset\emptyset</math>, d'où l'égalité. On parle alors de '''l'ensemble vide'''.
Remarque : On a <math>\mathcal{P}(\emptyset)=\{\emptyset\}</math> qui est donc non vide.
Étant donnés deux objets <math>x</math> et <math>y</math> on peut définir l'ensemble les contenant exactement : il s'agit de la '''paire''' <math>\{x,y\}</math>. Ce procédé s'entend également pour construire des ensembles à plus de deux éléments et on écrit par exemple <math>\mathcal{P}(\{x,y\})=\{\emptyset,\{x\},\{y\},\{x,y\}\}</math>. Lors d'une telle énumération, on dit qu'on définit l'ensemble '''en extension'''. On a par exemple <math>\{a,b\}=\{b,a\}=\{a,b,a\}</math>.
Pour que l'ordre des éléments ait une importance on définit le '''couple''' <math>(a,b)</math> par <math>(a,b):=\{\{a\},\{a,b\}\}</math>, on vérifie en effet la
{{Théorème|titre=Proposition|contenu=
<math>\forall a,b,c,d, \; (a,b)=(c,d) \Leftrightarrow a=c \text{ et }b=d</math>
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
* <math>\Leftarrow</math> est triviale.
* <math>\Rightarrow</math> : Si <math>=\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}</math> montrons que <math>a=c</math> et <math>b=d</math>.<br />
On suppose d'abord <math>a=c</math> alors <math>\{a,b\}=\{c,d\}</math> et comme <math>a=c</math>, <math>b=d</math>.<br />
Sinon <math>a\neq c</math>, mais alors <math>\{a\}=\{c,d\}</math> et <math>\{a,b\}=\{c\}</math>. Par suite <math>\{c\}=\{a,b\}=\{c,d,b\}</math> et donc <math>a=b=c=d</math> qui est absurde ici.
}}
On appelle alors '''produit cartésien''' de deux ensembles <math>E</math> et <math>F</math>, l'ensemble des couples <math>(x,y),\; x\in E,\, y\in F</math>. On le note <math>E\times F</math>, lire « ''E'' croix ''F'' ». Ceci s'étend pour définir des '''triplets''' <math>(a,b,c)</math>; des quadruplets <math>(a,b,c,d)</math>; des <math>n</math>-uplets <math>(a_1,a_2,\dots,a_n)</math>.
==Opérations sur les ensembles==
===Différence, complémentaire===
{{définition|titre=Définition : différence|contenu=
[[Image:Venn-not.svg|200px|left]]
On appelle '''différence''' ''A'' et ''B'' dans cet ordre, pour deux parties d'un ensemble ''E'', l'ensemble noté <math>A\setminus B:=\{x\in E/ x\in A \text{ et } x\notin B\}</math>.
}}
En particulier on définit pour une partie ''A'' d'un ensemble ''E'' son '''complémentaire''' dans ''E'', noté <math>\complement_E A</math> ou <math>A^c</math> s'il n'est pas nécessaire de préciser ''E''.
Exercice : que dire de <math>A\setminus\emptyset</math> ; <math>\emptyset\setminus A</math>; <math>A\setminus A</math>, pour <math>A\in\mathcal{P}(E)</math> ?
===Intersection, réunion===
{{définition|titre=Définition : intersection|contenu=
[[Image:Venn-and.svg|200px|left]]
On appelle '''intersection''' de deux parties quelconques ''A'' et ''B'' d'un ensemble ''E'', l'ensemble noté <math>A\cap B:=\{x\in E / x\in A \text{ et } x\in B\}</math>, lire « ''E'' inter ''F'' ».
}}
{{définition|titre=Définition : réunion|contenu=
[[Image:Venn-or.svg|200px|left]]
On appelle '''réunion''' de deux parties quelconques ''A'' et ''B'' d'un ensemble ''E'', l'ensemble noté <math>A\cup B:=\{x\in E / x\in A \text{ ou } x\in B\}</math>.
}}
Exercice :
# Que dire de <math>A\cap E</math> et <math>A\cup\emptyset</math> pour <math>A\in\mathcal{P}(E)</math> ?
# Faire le lien entre connecteurs logiques/quantificateurs et différence/réunion/intersection. On en déduit facilement la :
{{Théorème|titre=Propriétés des opérations ensemblistes|contenu=
Soient ''A'', ''B'' et ''C'' trois parties d'un ensemble ''E''. On a alors les propriétés suivantes :
# Commutativité : <math>A\cap B=B\cap A</math> et <math>A\cup B=B\cup A</math>,
# Associativité : <math>(A\cap B)\cap C=A\cap(B\cap C)</math> et <math>(A\cup B)\cup C=A\cup(B\cup C)</math>,
# Distributivité de <math>\cap</math> sur <math>\cup</math> : <math>A\cap (B\cup C)=(A\cup B)\cap(A\cup C)</math>
# Distributivité de <math>\cup</math> sur <math>\cap</math> : <math>A\cup (B\cap C)=(A\cap B)\cup(A\cap C)</math>
# Lois de Morgan : <math>E\setminus(A\cap B)=(E\setminus A)\cup(E\setminus B)</math> et <math>E\setminus(A\cup B)=(E\setminus A)\cap(E\setminus B)</math>
}}
===Différence symétrique===
{{Théorème|Titre=Proposition et définition : différence symétrique|contenu=
[[Image:Venn-xor.svg|200px|left]]
Soient ''A'' et ''B'' deux partie d'un ensemble ''E''.<br />
Alors <math>(A\cup B) \setminus (A\cap B)</math>=<math>(A\setminus B)\cup (B\setminus A)</math>.<br />
On appelle '''différence symétrique''' de ''A'' et ''B'' cet ensemble qu'on note <math>A\Delta B</math>, 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 <math>A\Delta\emptyset</math>; de <math>A\Delta A</math> ?
# Montrer que <math>\cap</math> est distributive sur <math>\Delta</math>.
=Relations binaires=
Ici <math>E</math> désigne un ensemble.
==Généralités==
===Définition, exemples===
{{Définition|titre=Définition et notation : relations binaires|contenu=
On appelle '''relation binaire''' sur ''E'', toute partie de ''E'' × ''E''.
Si <math>\mathcal{R}</math> est une telle relation sur ''E'' et si <math>x,y \in E</math>, on note <math>x \mathcal{R} y</math> plutôt que <math>(x,y) \in \mathcal{R}</math>. }}
Exemples :
# Pour <math>E=\mathbb{N}</math>, posons <math>\mathcal{R}=\{ (0,1), (3,7), (3,4), (1,1)\}</math>. On a <math>0\mathcal{R}1</math>, <math>3\mathcal{R}7</math>, <math>3\mathcal{R}4</math> mais pas <math>3\mathcal{R}5</math>.
# L'égalité (<math>=</math>) sur <math>E</math> provient de <math>\Delta=\{ (x,x), x \in E\}</math>. Ici on préfèrera <math>x=y</math> à <math>x \Delta y</math>.
# L'inclusion sur <math>\mathcal{P}(E)</math> : <math>\mathcal{R}=\{ (X,Y)\in\mathcal{P}(E)^2 / X\subset Y\}</math>.
# L'ordre sur <math>\mathbb{R}</math> : <math>\mathcal{R}=\{ (x,y)\in\mathbb{R}^2 / x\leq y \}</math>.
===Qualités d'une relation binaire===
Soit <math>\mathcal{R}</math> une relation binaire sur ''E''. <math>\mathcal{R}</math> est dite :
* '''réflexive''' ssi <math>\forall x\in E, x\mathcal{R}x</math> (les exemples 2, 3, et 4 ci-dessus illustrent cette propriété) ;
* '''transitive''' ssi <math>\forall x,y,z \in E, (x\mathcal{R}z\, \text{et}\, z\mathcal{R}y)\Rightarrow x\mathcal{R}y</math> (exemples 1, 2, 3, et 4) ;
* '''symétrique''' ssi <math>\forall x,y \in E, x\mathcal{R}y \Rightarrow y\mathcal{R}x</math> (exemples 2 et 3 si ''E'' est vide) ;
* '''antisymétrique''' ssi <math>\forall x,y \in E, x\mathcal{R}y\, \text{et}\, y\mathcal{R}x \Rightarrow x=y</math> (exemples 1, 2, 3, et 4).
==Relations d'équivalence==
{{Définition|titre=Définitions et notations : relations d'équivalence|contenu=
On appelle '''relation d'équivalence''' sur ''E'' toute relation binaire <math>\mathcal{R}</math> sur ''E'' à la fois ''réflexive'', ''transitive'' et ''symétrique''.
Pour tout <math>x\in E</math> on appelle '''classe d'équivalence''' de ''x'' modulo <math>\mathcal{R}</math> la partie de ''E'' notée <math>\overline{x}:=\{ y\in E / x\mathcal{R} y \}</math>.
}}
{{Théorème|titre=Lemme|contenu=
Soit ''X'' une classe d'équivalence modulo <math>\mathcal{R}</math>.
Alors <math>\forall a\in X, X=\overline{a}</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Fixons <math>x\in X</math> tel que <math>X=\overline{x}</math>.
Soit maintenant <math>a\in X</math>. Montrons que <math>X=\overline{a}</math>.
Montrons que <math>X\subset \overline{a}</math> : soit <math>y\in X=\overline{x}</math>. Ainsi <math>x\mathcal{R}y</math>. Par ailleurs <math>a \in X=\overline{x}</math> donc <math>x\mathcal{R}a</math> et par symétrie et transitivité, on a : :<math>a\mathcal{R}y</math>, ie <math>y\in \overline{a}</math>.
Réciproquement, montrons que <math>\overline{a}\subset X</math> : soit <math>y\in \overline{a}</math> ''ie'' tel que <math>a\mathcal{R} y</math>. On a déjà vu que <math>x\mathcal{R}a</math> d'où par transitivité <math>x\mathcal{R}y</math> ''ie'' <math>y\in\overline{x}=X</math>.
}}
{{Définition|titre=Définition : ensemble quotient|contenu=
L'ensemble de ces classes d'équivalence, qui est une partie de <math>\mathcal{P}(E)</math> est appelé '''ensemble quotient de <math>E</math> par <math>\mathcal{R}</math>''', noté <math>E/\mathcal{R}</math>.
}}
{{Théorème|titre=Proposition|contenu=
Les éléments de l'ensemble quotient <math>E/\mathcal{R}</math> forment une partition de ''E''.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Déjà <math>E/\mathcal{R}</math> est bien une partie de <math>\mathcal{P}(E)</math>.
Si <math>X \in E/\mathcal{R}</math> alors ''X'' est la classe d'équivalence d'un élément <math>x\in E</math>, et par réflexivité <math>x\in X</math>, donc <math>X\neq\emptyset</math>.
Si <math>X,Y \in E/\mathcal{R}</math> sont non disjointes, montrons qu'alors <math>X=Y</math>. On fixe <math>a \in X\cap Y</math>, mais alors <math>X=\overline{a}=Y</math>, d'après le lemme.
Enfin <math>E=\bigcup_{X\in E/\mathcal{R}}X</math>. On a évidement <math>\bigcup_{X\in E/\mathcal{R}}X \subset E</math>.
Réciproquement soit <math>x \in E</math>, alors <math>x\in\overline{x}</math> donc <math>x\in\bigcup_{X\in E/\mathcal{R}}X</math>, ce qui clos la preuve.
}}
Exercice : Etant donnée une partition de <math>E</math>, définir une relation d'équivalence canoniquement associée à la partition. Quelles en sont les classes d'équivalence ?
{{Définition|titre=Définition : projection canonique|contenu=
On définit l'application <math>\pi : E \rightarrow E/\mathcal{R}, x \mapsto \overline{x}</math>. C'est une projection, appelée '''projection''' (ou '''surjection''') '''canonique'''.}}
==Relations d'ordre==
{{Définition|titre=Définitions et notations : relations d'ordre, ensembles ordonnés, ordres totaux|contenu=
On appelle '''relation d'ordre''' sur ''E'' toute relation binaire <math>\mathcal{R}</math> sur ''E'' à la fois ''réflexive'', ''transitive'' et ''antisymétrique''.
On appelle '''ensemble ordonné''' un tel couple <math>(E,\mathcal{R})</math>.
On note plus volontiers <math>\leq</math> une telle relation.
L'ordre est dit ''total'' ssi pour tous éléments <math>x,y \in E , x\leq y \,\text{ou}\, y\leq x</math>. C'est le cas de l'ordre usuel sur <math>\mathbb{R}</math> mais pas de l'inclusion sur <math>\mathcal{P}(E)</math> dès que <math>E</math> a au moins deux éléments.
}}
Éléments remarquables d'un ensemble ordonné <math>(E,\leq)</math> :
{{Théorème|titre=Proposistion et définition : plus petit et plus grand éléments|contenu=
Soit <math>A\subset E</math>.
Alors il existe au plus un élément <math>m\in A / \forall x\in A, x\leq m</math>.
Un tel élément est appelé '''plus grand élément''' de <math>A</math>, noté <math>\max A</math>.On définit de même un éventuel '''plus petit élément'''.
}}
{{Définition|titre=Définitions : majorants, minorants, bornes supérieure et inférieure|contenu=
Une partie <math>A\subset E</math> est dite '''majorée''' (''resp'' : '''minorée''') ssi <math>\exists m\in E / \forall x\in A , x\leq m</math>.
Un tel élément s'appelle un '''majorant''' (''resp'' : '''minorant'''). <math>\max A</math> s'il existe en est un.
Si l'ensemble des majorants (''resp'' : minorants) de ''A'' admet un plus petit élément (''resp'' : plus grand élément), celui-ci unique, s'appelle la '''borne supérieure''' (''resp'' : '''inférieure''') de ''A''.
}}
Exercices :
# Soit <math>\leq</math> un ordre sur <math>E</math>. On définit <math>\geq</math>, par <math>\forall x,y\in E,\, x\geq y\Leftrightarrow y\leq x</math>. Montrer que c'est un ordre. Quelles en sont les éléments remarquables ?
# Soit <math>\leq</math> une relation binaire sur <math>E</math> transitive et reflexive. Montrer que la relation binaire définie par <math>\forall x,y\in E,\, x\sim y \Leftrightarrow x\leq y \text{ et } y\leq x</math> est une relation d'équivalence. Munir le quotient d'un ordre canonique.
=Applications=
==Graphes==
Soient <math>E</math> et <math>F</math> deux ensembles.
{{Définition|titre=Définition : graphe|contenu=
On appelle '''graphe''' de <math>E</math> vers <math>F</math> toute partie de <math>E\times F</math>.<br />
On appelle '''application''' de <math>E</math> vers <math>F</math> tout triplet <math>f=(E,F,\Gamma)</math> où <math>\Gamma</math> est un graphe de <math>E</math> vers <math>F</math> tel que : <math>\forall x\in E, \exists ! y\in F / (x,y)\in\Gamma</math>
}}
Dans pareil cas, on dit que
* <math>E</math> est '''l'ensemble de départ''' ou '''la source''' de <math>f</math>,
* <math>F</math> '''l'ensemble d'arrivée''' ou '''le but''' de <math>f</math>,
* <math>\Gamma</math> '''le graphe''' de <math>f</math>.
Pour un <math>x\in E</math>, l'unique <math>y</math> de la définition est appelé '''image''' de <math>x</math> par <math>f</math>, noté <math>f(x)</math>. On note souvent <math>f:E\rightarrow F,\, x\mapsto f(x)</math>.<br />
Deux applications sont donc égales ssi elles ont même source même but et même graphe.<br />
Dans les cas particulier où <math>F=\mathbb{R}</math> (resp:<math>\mathbb{C}</math>) on parle de '''fonction numérique''' (resp: '''complexe'''). Si <math>E=\mathbb{N}</math> on parle de '''suite''' d'éléments de <math>F</math>.<br />
On appelle '''identité''' de <math>E</math>, l'application <math>id_E:E\rightarrow E,\, x\mapsto x</math>.
==Restrictions, prolongements==
Soit <math>f:E\rightarrow F</math> une application et <math>A\subset E</math>.
{{Définition|titre=Définitions : restriction, corestriction|contenu=
On appelle '''restriction''' de <math>f</math> à <math>A</math>, notée <math>f_{|A}\,</math>, l'application <math>f_{|A}: A\rightarrow F,\, x\mapsto f(x)</math>.
Soit maintenant <math>B\subset F</math> telle que <math>\forall x\in E, f(x)\in B</math>.
On appelle alors '''corestriction''' de <math>f</math> à <math>B</math> l'application <math>f^{|B}:E\rightarrow B, \, x\mapsto f(x)</math>.
Soit <math>E'</math> un sur-ensemble de <math>E</math>, on appelle '''prolongement''' de <math>f</math> à <math>E'</math> toute application <math>g:E'\rightarrow F</math> telle que <math>\forall x\in E, f(x)=g(x)</math>.
}}
==Composition==
Soient <math>f:E\rightarrow F</math> et <math>g:F\rightarrow G</math> deux applications. On définit alors '''l'application composée''' de <math>f</math> et <math>g</math> par <math>g\circ f:E\rightarrow G, \, x\mapsto g(f(x))</math>.
{{Théorème|titre=Proposition|contenu=
Soient <math>f:E\rightarrow F</math>, <math>g:F\rightarrow G</math> et <math>h:G\rightarrow H</math> trois applications.<br />
Alors <math>h\circ(g\circ f)=(h\circ g)\circ f</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
On doit montrer l'égalité de deux applications, on vérifie donc qu'elles ont
* même source : E,
* même but : H,
* même graphe : soit <math>x\in E</math>, alors <math>[h\circ(g\circ f)](x)=h(g\circ f(x))=h(g(f(x))=h\circ g (f(x))=[(h\circ g)\circ f](x)</math>.
}}
Ainsi la notation <math>h\circ g\circ f</math> est sans ambiguité.
==Injections, surjections et bijections==
===Définitions===
Soient <math>f:E\rightarrow F</math> une application et <math>y\in F</math>
{{Définition|titre=Définition : antécédent|contenu=
On appelle antécédent de <math>y</math> par <math>f</math> tout élément <math>x\in E</math> tel que f(x)=y.
}}
Exemple : pour <math>f:\mathbb{R}\rightarrow \mathbb{R},\, x\mapsto x^2</math>; <math>-2</math> n'a pas d'antécédent alors que <math>2</math> en a deux.
{{Définition|Définitions= injections, surjections, bijections|contenu=
On dit que <math>f</math> est '''injective''' ssi tout élément de <math>F</math> a au plus un antécédent dans <math>E</math>, cela équivaut à <math>\forall x,x'\in E ,\, x\neq x'\Rightarrow f(x)\neq f(x')</math> où encore, en contraposant, <math>\forall x,x'\in E,\, f(x)=f(x') \Rightarrow x=x'</math>.<br />
On dir que <math>f</math> est '''surjective''' ssi tout élément de <math>F</math> a au moins un antécédent dans <math>E</math>, ie <math>\forall y\in F, \exists x\in E / f(x)=y</math>.<br />
On dit que <math>f</math> est '''bijective''' sssi elle est à la fois injective et surjective, ce qui équivaut à <math>\forall y\in F, \exists ! \, x\in E /f(x)=y</math>.
}}
Exercice : Restreindre l'application <math>f</math> de l'exemple précédent au départ et/où à l'arrivée pour la rendre injective; surjective; bijective.
===Stabilité par composition===
{{Théorème|titre=Proposition|contenu=
Soient <math>f:E\rightarrow F</math> et <math>g:F\rightarrow G</math> deux injections.<br />
Alors <math>g\circ f</math> l'est aussi.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Soit <math>x,x'\in E</math>. Supposons que <math>g\circ f(x)=g\circ f (x')</math> alors <math>g(f(x))=g(f(x'))</math> et par injectivité de <math>g</math>, <math>f(x)=f(x')</math>. Par injectivité de <math>f</math>, <math>x=x'</math>.
}}
{{Théorème|titre=Proposition|contenu=
Soient <math>f:e\rightarrow F</math> et <math>g:F\rightarrow G</math> deux surjections.<br />
Alors <math>g\circ f</math> l'est aussi.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Soit <math>z\in G</math>. Comme <math>g</math> est surjective on peut fixer <math>y\in F / z=g(y)</math>. Comme <math>f</math> est surjective on peut fixer <math>x\in E / y=f(x)</math>. Finalement <math>z=g(y)=g(f(x))</math>. Bref, <math>x</math> est un antécédent de <math>z</math> par <math>g\circ f</math> dans <math>E</math>.
}}
Réciproquement...
{{Théorème|titre=Proposition|contenu=
Soient <math>f:E\rightarrow F</math> et <math>g:F\rightarrow G</math> deux applications.<br />
Si <math>g\circ f</math> est injective, alors <math>f</math> l'est aussi.<br />
Si <math>g\circ f</math> est surjective, alors <math>g</math> l'est aussi.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Supposons <math>g\circ f</math> injective. Fixons <math>x,x'\in E/ f(x)=f(x')</math>. Alors <math>g(f(x))=g(f(x'))</math> et par injectivité de <math>g\circ f</math>, <math>x=x'</math>.<br />
Supposons <math>g\circ f</math> surjective. Fixons <math>z\in G</math>. Comme <math>g\circ f</math> est surjective, on peut fixer <math>x\in E / z=g(f(x))</math>, mais alors <math>y=f(x)</math> est un antécédent de <math>z</math> par <math>g</math> dans <math>F</math>.
}}
===Bijection réciproque===
Soit <math>f:E\rightarrow F</math> une bijection. Pour tout <math>y\in F</math>, on note <math>f^{-1}(y)</math> l'unique <math>x\in E / f(x)=y</math>. Ceci permet de definir une application <math>f^{-1}:F\rightarrow E,\, y\mapsto f^{-1}(y)</math>. On appelle cete application '''bijection réciproque''' de <math>f</math>.
On a clairement les deux égalités <math>f\circ f^{-1}=id_F</math> et <math>f^{-1}\circ f=id_E</math>. Réciproquement
{{Théorème|titre=Proposition|contenu=
S'il existe une application <math>g:F\rightarrow E</math> telle que <math>f\circ g=id_F</math> et <math>g\circ f=id_E</math>,<br />
alors <math>f</math> est bijective, de plus <math>f^{-1}=g</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Puisque <math>f\circ g=id_F</math> est bijective elle est surjective donc <math>f</math> aussi.<br />
Puisque <math>g\circ f=id_E</math> est bijective elle est injective donc <math>f</math> aussi.<br />
À ce stade on a prouvé que <math>f</math> est bijective, on dispose donc de <math>f^{-1}</math>. Montrons que c'est <math>g</math>. Ces deux applications ont même source et même but, et fixant <math>y\in F</math>, on a <math>f(g(y))=y</math>, ''ie.'' que <math>g(y)</math> est l'antécédent de <math>y</math> par <math>f</math>. par définition de <math>f^{-1},\, g(y)=f^{-1}(y)</math>.
}}
{{Théorème|titre=Corollaire|contenu=
Si <math>f:E\rightarrow F</math> est bijective,<br />
alors <math>f^{-1}:F\rightarrow E</math> l'est aussi.<br />
Auquel cas <math>(f^{-1})^{-1}=f</math>
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Pour le premier point on applique la proposition précédente à <math>f\circ f^{-1}=id_F</math> et <math>f^{-1}\circ f=id_E</math>.<br />
Pour le second, on constate que les deux applications ont bien même source et même but. Enfin pour <math>x\in E</math> on a <math>f^{-1}(f(x))=x</math>, ''ie.'' que <math>f(x)</math> est l'antécédent de <math>x</math> par <math>f^{-1}</math>.
}}
Ainsi pour montrer qu'une application est bijective on peut :
* ou bien le faire à la main : à <math>y</math> fixé dans <math>F</math>, on montre qu'il existe un seul et unique antécédent ;
* ou bien construire une bijection réciproque (qui s'avère être la bijection réciproque).
==Familles==
{{Définition|titre=Définitions et notations : familles, suites|contenu=
Soit <math>I</math> et <math>E</math> deux ensembles.
On appelle '''famille''' d'éléments de <math>E</math> indexée par <math>I</math> toute application <math>f:I\rightarrow E</math>.
On note plus volontiers <math>f_i\,</math> que <math>f(i)\,</math> pour <math>i\in I</math> — on préfère également <math>(f_i)_{i\in I}</math> à <math>f:I\rightarrow E</math>.
Plusieurs cas de figure se présentent parfois :
* Si l'index <math>I</math> est fini (au sens intuitif du terme), la famille est dite ''finie''.
* Si <math>I=\mathbb{N}</math>, on parle de '''suite''' d'élément de <math>E</math>.
* Si <math>J\subset I</math>, on appelle '''sous-famille''' de la famille <math>(f_i)_{i\in I}</math>, la restriction de <math>f</math> à <math>J</math>.
Pour une famille <math>(A_i)_{i\in I}</math> d'éléments de <math>\mathcal{P}(E)</math>, on pose
* <math>\bigcap_{i\in I}A_i:=\{ x\in E / \forall i\in I, x\in A_i \}</math>, '''l'intersection''' des <math>A_i</math>,
* <math>\bigcup_{i\in I}A_i:=\{ x\in E / \exists i\in I / x\in A_i \}</math>, leur '''réunion'''.
}}
==Images directes et réciproques==
Soit <math>f:E\rightarrow F</math> une application.
===Définition===
Pour <math>A\subset E</math>, on appelle '''image directe''' de <math>A</math> par <math>f</math> la partie de <math>F</math>, notée <math>f(A)</math> et définie par <math>f(A):=\{y\in F / \exists x\in A / y=f(x)\}</math>. En particulier <math>f(E)</math> est appelé '''l'image''' de <math>f</math>.<br />
Pour <math>B\subset F</math>, on appelle '''image réciproque''' de <math>B</math> par <math>f</math> la partie de <math>E</math>, notée <math>f^{-1}(B)</math> et définie par <math>f^{-1}(B):=\{x\in E / f(x)\in B\}</math>.
Remarques :
* <math>f^{-1}(B)</math> est toujours envisageable, même si <math>f</math> n'est pas bijective
* <math>f^{-1}(F)=E</math> alors qu'en générale <math>f(E)\neq F</math>. C'est le cas ssi <math>f</math> est surjective.
Exercice : étudier l'injectivité/surjectivité/bijectivité des applications <math>\mathcal{P}(E)\rightarrow\mathcal{P}(F), A\mapsto f(A)</math> et <math>\mathcal{P}(F)\rightarrow\mathcal{P}(E), B\mapsto f^{-1}(B)</math> en fonction de celles de <math>f:E\rightarrow F</math>.
===Fibres===
Soit <math>y\in F</math>, les ensembles <math>f^{-1}(\{y\})=\{ x\in E / f(x)=y \}</math> sont appelés les '''fibres''' de <math>f</math>. Lorsque <math>f</math> est surjective, elles forment une partition de <math>E</math>, exercice dont on reparlera...
Remarques : Dire que <math>f</math> est
* injective équivaut à dire que toute fibre de <math>f</math> a au plus un élément,
* surjective équivaut à dire qu'aucune fibre de <math>f</math> n'est vide,
* bijective équivaut à dire que toute fibre de <math>f</math> est réduite à un singleton.
===Quelques propriétés===
{{Théorème|titre=Proposition|contenu=
Soit <math>(B_i)_{i\in I}</math> une famille de parties de <math>F</math>.<br />
Alors <math>f^{-1}(\bigcap_{i\in I}B_i)=\bigcap_{i\in I}f^{-1}(B_i)</math> et <math>f^{-1}(\bigcup_{i\in I}B_i)=\bigcup_{i\in I}f^{-1}(B_i)</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
<math>
\begin{align}
\forall x\in E, \, x\in f^{-1}(\bigcap_{i\in I}B_i) & \Leftrightarrow f(x)\in \bigcap_{i\in I}B_i \\
& \Leftrightarrow \forall i\in I, \, f(x) \in B_i \\
& \Leftrightarrow \forall i\in I, \, x\in f^{-1}(B_i) \\
& \Leftrightarrow x \in \bigcap_{i\in I}f^{-1}(B_i) \\
\forall x\in E,\, x\in f^{-1}(\bigcup_{i\in I}B_i) & \Leftrightarrow f(x)\in \bigcup_{i\in I}B_i \\
& \Leftrightarrow \exists i\in I / f(x) \in B_i \\
& \Leftrightarrow \exists i\in I / x\in f^{-1}(B_i) \\
& \Leftrightarrow x \in \bigcup_{i\in I}f^{-1}(B_i)
\end{align}</math>
}}
{{Théorème|titre=Proposition|contenu=
Soit <math>(A_i)_{i\in I}</math> une famille de parties de <math>E</math>.<br />
Alors <math>f(\bigcap_{i\in I}A_i)\subset\bigcap_{i\in I}f(A_i)</math> et <math>f(\bigcup_{i\in I}A_i)=\bigcup_{i\in I}f(A_i)</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
<math>
\begin{align}
\forall y\in F, \, y\in f(\bigcap_{i\in I}A_i) & \Leftrightarrow \exists x\in \bigcap_{i\in I}A_i / y=f(x) \\
& \Leftrightarrow \exists x\in E / \forall i\in I, x\in A_i \text{ et } y=f(x) \\
& \Rightarrow \forall i\in I,\exists x\in A_i / y=f(x)\\
& \Rightarrow \forall i\in I, y\in f(A_i) \\
& \Rightarrow y\in \bigcap_{i\in I}f(A_i)
\end{align}</math>
On notera que l'interversion des quantificateurs ne donne qu'une implication, en effet « en haut » il y a un <math>x</math> commun a tous les indices <math>i</math>, tandis qu' « en bas » les <math>x</math> dépendent de l'indice ce qui est plus faible.
<math>
\begin{align}
\forall y\in F, \, y\in f(\bigcup_{i\in I}A_i) & \Leftrightarrow \exists x\in \bigcup_{i\in I}A_i / y=f(x) \\
& \Leftrightarrow \exists x\in E \exists i\in I / x\in A_i \text{ et } y=f(x) \\
& \Leftrightarrow \exists i\in I,\exists x\in A_i / y=f(x)\\
& \Leftrightarrow \exists i\in I / y\in f(A_i) \\
& \Leftrightarrow y\in \bigcup_{i\in I}f(A_i)
\end{align}</math>
}}
==Compatibilité avec les relations d'équivalence ou d'ordre==
===Avec l'équivalence===
Soit <math>f:E\rightarrow F</math> une application et <math>\sim\,</math> une relation d'équivalence sur <math>E</math>. On dit que <math>f</math> est '''compatible''' avec <math>\sim\,</math> ssi <math>\forall x,x' \in E,\, x\sim x' \Rightarrow f(x)=f(x')</math>. L'application <math>f</math> '''passe au quotient''' ''ie.'' qu'on peut définir une nouvelle application <math>\tilde{f}:E/\sim\rightarrow F,\overline{x}\mapsto f(x)</math>.
Exercices :
# Étant donnée une application <math>f:E\rightarrow F</math>, la rendre canoniquement surjective. On note encore <math>f</math> la surjection obtenue.
# On considère la relation binaire sur <math>E</math> définie par <math>\forall x,x'\in E,\, x\sim x' \Leftrightarrow f(x)=f(x')</math>. Montrer qu'il s'agit d'une relation d'équivalence. Que dire de l'application obtenue en passant au quotient ?
===Avec l'ordre===
{{Définition|titre=Définition : application croissante ou décroissante|contenu=
Soit <math>f:E\rightarrow F</math> une application et <math><,\leq</math> deux ordres sur <math>E</math> et <math>F</math> respectivement. On dit que <math>f</math> est '''croissante''' (''resp'' : '''decroissante''') ssi :
:<math>\forall x,x' \in E,\, x<x'\Rightarrow f(x)\leq f(x')</math>.
:(''resp'' : <math>\forall x,x' \in E,\, x'<x\Rightarrow f(x)\leq f(x')</math> )
}}
Exemple : <math>\mathcal{P}(E)\rightarrow\mathcal{P}(E), A\mapsto A^c</math> est décroissante pour l'inclusion.
Exercices :
#Soit <math>\Phi:\mathcal{P}(E)\rightarrow\mathcal{P}(E)</math> croissante pour l'inclusion. Montrer que <math>\Phi</math> admet un point fixe, ''ie.'' une partie <math>A\subset E</math> telle que <math>\Phi(A)=A</math>.
#Soit <math>f:E\rightarrow F</math> et <math>g:F\rightarrow E</math> deux injections. Montrer le théorème de Cantor-Bernstein : « Il existe une bijection de <math>E</math> sur <math>F</math>. »
Indications :
# Considérer <math>\mathcal{A}:=\{A\subset E / \Phi(A)\subset A\}</math> et <math>A_0:=\bigcap_{A\in\mathcal{A}}A</math>.
# Faire un dessin et appliquer 1/, où aller voir sur Wikipédia...
=Entiers naturels=
==Axiomatique de Peano==
{{Définition|titre=Axiome : dit de Peano|contenu=
Il existe une ensemble ordonné non vide <math>(\mathbb{N},\leq)</math>, appelé ensemble des '''entiers naturels''' et vérifiant :
* (N1) : Toute partie non vide de <math>\mathbb{N}</math> admet un plus petit élément,
* (N2) : Toute partie non vide et majorée de <math>\mathbb{N}</math> admet un plus grand élément,
* (N3) : <math>\mathbb{N}</math> lui même n'admet de plus grand élément.
}}
Remarques : En utilisant (N1) on obtient :
* En tant que partie non vide de lui-même, <math>\mathbb{N}</math> admet un plus petit élément appelé '''zéro''' et noté <math>0</math>.
* La paire <math>\{x,y\}\subset\mathbb{N}</math>, si elle existe, est une partie non vide de <math>\mathbb{N}</math>. elle admet un plus petit élément : si c'est <math>x</math> alors <math>x\leq y</math>; si c'est <math>y</math> alors <math>y\leq x</math>. Bref, <math>\mathbb{N}</math> est totalement ordonnée.
Fixons <math>n\in \mathbb{N}</math> et considérons l'ensemble <math>M:=\{p\in\mathbb{N}/n<p\}</math>. Où <math>n<p</math> signifie <math>n\leq p</math> et <math>n\neq p</math>. <math>M</math> est une partie non vide de <math>\mathbb{N}</math>. Montrons qu'elle est non vide : sinon <math>\forall p\in\mathbb{N},\, p\leq n</math>, ce qui contre dit (N3). Ainsi, par (N1), <math>M</math> admet un plus petit élément, appelé succeseur de <math>n</math>, noté <math>\sigma(n)</math>.
{{Théorème|titre=Proposition et |contenu=
L'application <math>\sigma:\mathbb{N}\rightarrow \mathbb{N}\setminus\{0\},n\mapsto \sigma(n)</math> est bijective.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
* <math>\sigma</math> est bien à valeur dans <math>\mathbb{N}\setminus\{0\}</math> car si <math>n\in\mathbb{N}</math> était un antécédant de <math>0</math>, alors <math>n<0</math>, ce qui contre-dit la définition de zéro.
* <math>\sigma</math> est injective :<br />
soit <math>m,n\in \mathbb{N} / \sigma(n)=\sigma(m)</math>. Montrons que <math>m\leq n</math>, ainsi par symétrie des rôles <math>n\leq m</math> et par antisymétrie <math>m=n</math>.<br />
Supposons donc le contraire, alors <math>n<m</math> car l'ordre est total. D'où par définition du successeur <math>\sigma(n)\leq m<\sigma(m)</math>. Or par hypothèse <math>\sigma(n)=\sigma(m)</math> donc <math>\sigma(m)\neq\sigma(m)</math> qui est la contradiction cherchée.
*Montrons que <math>\sigma</math> est surjective :<br />
soit donc <math>p\in\mathbb{N}\setminus\{0\}</math>. On considère l'ensemble <math>B:=\{n\in\mathbb{N}/ n<p\}</math>. C'est une partie non vide (<math>0\in B</math>) de <math>\mathbb{N}</math> et majorée par <math>p</math>. D'après (N2), elle admet un plus grand élément; notons-le <math>\mu</math> et montrons que <math>p=\sigma(\mu)</math>. D'une part, comme <math>\mu\in B, \, \mu<p, \, \sigma(\mu)\leq p</math>; d'autre par <math>\sigma(\mu)>\mu=\max B</math> donc <math>\sigma(\mu)\notin B</math> ie <math>\sigma(\mu)\geq p</math>. On conclut par antisymétrie.
}}
On note <math>1=\sigma(0)</math>, puis <math>2,3,4,5,6,7,8,9</math> les neufs premiers itérés de <math>0</math>, pour ne pas à avoir recours à une infinité de symboles on a trouvé un moyen plus malin dont il sera question plus tard...
==Récurrences==
{{Théorème|titre=Théorème de récurrence|contenu=
Soit <math>\mathcal{P}</math> un prédicat sur <math>\mathbb{N}</math>, tel que
* <math>\mathcal{P}(0)</math> est vraie. C'est l''''initialisation''' de la récurrence,
* <math>\forall n\in\mathbb{N},\, \mathcal{P}(n)\Rightarrow \mathcal{P}(\sigma(n))</math>. C'est l''''hérédité'''.
Alors <math>\forall n\in\mathbb{N},\, \mathcal{P}(n)</math> est vrai.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Supposons le contraire ie <math>\exists n\in\mathbb{N} / \text{non}\mathcal{P}(n)</math>. D'après (N1) on peut donc considérer le plus petit de ces entiers, notons le <math>m</math>. Comme <math>\mathcal{P}(0)</math> est vrai, <math>m\neq 0</math>, et admet donc un antécédent par <math>\sigma</math> qu'on note <math>\mu</math>. Ainsi <math>\mu<m</math> et donc par définition de <math>m, \mathcal{P}(\mu)</math> est vrai. Par hérédité <math>\mathcal{P}(m)</math> est vrai, ce qui est contradictoire.
}}
Exercice : Montrer par récurrence que <math>\forall n\in\mathbb{N},\, \sum_{i=1}^n i =\frac{n(n+1)}{2}</math>.
En appliquant le théorème à <math>\mathcal{Q}(n):=\mathcal{P}(n+n_0)</math>, où <math>n,n_0\in\mathbb{N}</math> et <math>\mathcal{P}</math> et <math>\mathcal{Q}</math> sont des prédicats sur <math>\mathbb{N}</math> et <math>\{n\in\mathbb{N}/n\geq n_0\}</math> respectivement on obtient le
{{Théorème|titre=Corollaire|contenu=
Soient <math>n_o\in\mathbb{N}</math> et <math<\mathcal{Q}</math> un prédicat sur <math>\{n\in\mathbb{N}/n\geq n_0\}</math>, tel que
* <math>\mathcal{Q}(n_0)</math> est vraie,
* <math>\forall n\geq n_0,\, \mathcal{Q}(n)\Rightarrow \mathcal{Q}(\sigma(n))</math>.
Alors <math>\forall n\geq n_0,\, \mathcal{Q}(n)</math> est vrai.
}}
Voici un autre corollaire, parfois utile
{{Théorème|titre=Corollaire : récurrence forte|contenu=
Soit <math>\mathcal{P}</math> un prédicat sur <math>\mathbb{N}</math>, tel que
* <math>\mathcal{P}(0)</math> est vraie. C'est l''''initialisation''' de la récurrence,
* <math>\forall n\in\mathbb{N},\, (\mathcal{P}(0) \text{ et }\mathcal{P}(1)\text{ et }\dots\text{ et }\mathcal{P}(n))\Rightarrow \mathcal{P}(\sigma(n))</math>. C'est l''''hérédité'''.
Alors <math>\forall n\in\mathbb{N},\, \mathcal{P}(n)</math> est vrai.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
On pose <math>\mathcal{Q}(n):=(\mathcal{P}(0) \text{ et }\mathcal{P}(1)\text{ et }\dots\text{ et }\mathcal{P}(n))</math>.<br />
Alors <math>\mathcal{Q}(0)</math> est vraie car <math>\mathcal{P}(0)</math> l'est.<br />
Pour <math>n\in\mathbb{N}</math> supposant <math>\mathcal{Q}(n)</math> vraie on en déduit que <math>\mathcal{P}(\sigma(n))</math> l'est, et donc <math>\mathcal{Q}(\sigma(n))</math> aussi.<br />
Le théorème de récurrence appliqué à <math>\mathcal{Q}(n)</math> montre que <math>\forall n\in\mathbb{N},\, \mathcal{Q}(n)</math> est vrai, en particulier <math>\mathcal{P}(n)</math> l'est.
}}
{{Théorème|titre=Théorème : suite définie par une relation de récurrence|contenu=
Soient <math>f:E\rightarrow E</math> une application d'un ensemble non vide et <math>a\in E</math>.<br />
Alors il existe une unique suite <math>(u_n)_{n\in\mathbb{N}}</math> d'éléments de <math>E</math> vérifiant
*<math>u_0=a</math>,
*<math>\forall n\in\mathbb{N},\, u_{\sigma(n)}=f(u_n)</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
*unicité :
supposant trouvée <math>u</math> et <math>v</math>, montrons qu'elles sont égales. La propriété <math>u_n=v_n</math> est triviale en zéro : <math>u_0=a=v_0</math>.<br />
De plus si <math>u_n=v_n</math> pour un certain <math>n\in\mathbb{N}</math>, alors <math>u_{\sigma(n)}=f(u_n)=f(v_n)=v_{\sigma(n)}</math>.<br />
On conclut grace au théorème de récurrence.
*Existence :
On commence d'abord par montrer qu'on peut construire une suite finie (<math>U^n_k)_{0\leq k \leq n}</math> satisfaisant les deux points. C'est facile par une récurrence finie. On a de plus <math>\forall n\in\N,\, U^{\sigma(n)}_{\sigma(n)}=f(U^n_n)</math>, l'inclure dans la-dite récurrence. On pose alors <math>u:\N\rightarrow E, n\mapsto U^n_n</math>. La petite remarque précédente montre que <math>u</math> vérifie bien le second point, le premier étant évident.
}}
==Somme, produit et division euclidienne dans <math>\mathbb{N}</math>==
===Définitions de la somme et du produit dans <math>\N</math>===
On a bien sur reconnu en <math>\N</math> notre ensemble usuel pour compter, ceci fera l'objet du prochain chapitre, mais avant cela il nous faut donner un sens à l’'''addition''' et la '''multiplication'''. Faisons le proprement ici : Pour un élément <math>m\in\N</math>, on définit la suite suivante par récurrence :
:<math>\begin{cases} s^m_0 = m \\ s^m_{\sigma(n)} = \sigma(s^m_n), \forall n \geq 1 \end{cases}</math>
On note alors <math>m+n:=s^m_n</math>.
{{Théorème|titre=Proposition|contenu=
<math>\forall m\in\N,\, m+0=0+m=m\,</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Que <math>m+o=m</math> résulte de la définition.<br />
On montre l'autre égalité par récurrence sur <math>m</math>. L'initialisation est encore la définition de la somme. Supposant que <math>0+m=m</math>, on en déduit <math>0+\sigma(m)=s^0_{\sigma(m)}=\sigma(s^0_m)=\sigma(0+m)=\sigma(m)</math>. Ceci étant valable pour tout <math>m\in\N</math>, on conclut grâce au théorème de récurrence.
}}
On remarque alors que <math>\forall n\in\N,\, \sigma(n)=\sigma(n+0)=\sigma(s^n_0)=s^n_{\sigma(0)}=n+\sigma(0)=n+1</math>. Dorénavant, on utilisera volontiers cette égalité.
Exercice : Montrer qu'on à également <math>\forall n\in\N,\, \sigma(n)=1+n</math>
{{Théorème|titre=Proposition|contenu=
<math>\forall m,n,p\in\N,\, (m+n)+p=m+(n+p)</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
On récure sur <math>p\in\N</math> :
* La proposition précédente donne l'initialisation : <math>\forall m,n\in\N,\, (m+n)+0=m+n=m+(n+0)</math>.
* Pour l'hérédité on suppose <math>(m+n)+p=m+(n+p)</math>, alors <math>(m+n)+\sigma(p)=s^{m+n}_{\sigma(p)}=\sigma(s^{m+n}_p)=\sigma((m+n)+p)=\sigma(m+(n+p))=\sigma(s^m_{n+p})=s^m_{\sigma(n+p)}=m+\sigma(s^n_p)=m+(n+\sigma(p))</math>, et de conclure.
}}
{{Théorème|titre=Proposition|contenu=
<math>\forall m,n\in\N,\, m+n=n+m</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
On récure (avec l'éponge, oui oui) sur <math>\forall m\in\N</math> en posant <math>\mathcal{P}(n)=\forall m\in\N,\, m+n=n+m</math>.<br />
* Initialisation : c'est la première proposition.
* Hérédité : On suppose donc que <math>\forall m\in\N,\, m+n=n+m</math>, et on constate que <math>m+\sigma(n)=m+(n+1)=(m+n)+1=(n+m)+1=n+(m+1)=n+(1+m)=(n+1)+m=\sigma(n)+m</math>. On conclut comme précédemment.
}}
Remarque : on résumera bientôt ces trois propositions en disant que <math>(\N,+)</math> est un monoïde commutatif.
Exercice :
# En lisant les preuves, bien justifier (dans sa tête, ça suffit) chaque égalité, par exemple quand a-t-on utilisé l'exercice précédent ?
# À titre d'entraînement faire les preuves des propositions suivantes concernant la multiplication.
On définit maintenant à <math>m</math> fixé dans <math>\N</math>, la suite <math>\begin{cases}p^m_0=0 \\ p^m_{\sigma(n)}=p^m_n +m, \forall n\geq 1\end{cases}</math>, et on note bien sûr <math>m\times n:=p^m_n, \forall m,n\in\N</math>, bien qu'on omette souvent le signe <math>\times</math> ou qu'on le remplace par <math>\cdot</math>.
{{Théorème|titre=Proposition|contenu=
<math>\forall m\in\N,\, m\times 1=1\times m=m</math>.<br />
<math>\forall m,n,p\in\N,\, (mn)p=n(mp)</math>.<br />
<math>\forall m,n\in\N,\, mn=nm</math>.
}}
===Liens avec l'ordre, division euclidienne===
Dans <math>\N</math> l'ordre <math>\leq</math> est compatible avec l'addition et la multiplication au sens où
{{Théorème|titre=Proposition|contenu=
<math>\begin{align}
\forall a,b,c\in\N,\, & a\leq b \Leftrightarrow a+c\leq b+c \\
& a\leq b \Rightarrow ac\leq bc
\end{align}</math>.
}}
La preuve étant laissée en exercice.
{{Théorème|titre=Proposition|contenu=
<math>\forall a,b\in\N,\,a\leq b \Leftrightarrow \exists! c\in\N / a+c=b</math>.<br />
Cet unique entier est noté <math>b-a</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
<math>\Rightarrow</math>
* Existence : On fixe <math>a\in\N</math>. Soit donc <math>b\geq a</math>. Si <math>b=a</math> alors ''0'' convient. Sinon, alors <math>b>a\geq 0</math> et <math>\sigma^{-1}(b)\geq a</math>, on lui applique une hypothèse de récurrence bien choisie, pour obtenir <math>\sigma^{-1}(b)=a+c</math> et donc <math>b=a+(c+1)</math>.
* Unicité : Si <math>a+c=b=a+c'</math>, alors d'après la proposition précédente <math>c\leq c'</math> mais aussi <math>c'\leq c</math>, d'où l'égalité cherchée.
<math>\Leftarrow</math> : Supposant le contraire on a <math>a>b</math> et donc d'après l'existence dans <math>\Rightarrow</math> il existe <math>a=b+c'=a+c+c'</math>. D'après l'unicité <math>c+c'=0\leq c</math>, on utilise la première proposition pour avoir <math>c'\leq 0</math> et donc <math>c'=0</math> qui donne finalement la contradiction <math>a=b</math>.
}}
{{Théorème|titre=Proposition|contenu=
<math>\forall (a,b)\in\N\times\N^*, \exists n\in\N / nb\geq a</math>. ( où <math>\N^*:=\N\setminus\{0\}</math>)<br />
On résume ce fait en disant que l'ordre est '''archimédien''' sur <math>\N</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
On considère l'ensemble <math>A:=\{n\in\N / nb \leq a\}</math> qui contient ''0'' et est majoré par <math>a</math>, essentiellement car <math>b\geq 1</math>.<br />
On appelle ''q'' son plus grand élément, ''q+1'' n'étant pas dans ''A'', il convient.
}}
Le résultat qui suit est une amélioration de ce dernier :
{{Théorème|titre=Théorème et définition|contenu=
Soit <math>(a,b)\in\N\times\N^*</math>.<br />
Alors <math>\exists!(q,r)\in\N^2/ a=bq+r \text{ et } 0\leq q <r</math>.<br />
<math>q</math> (resp: <math>r</math>) est appelé le '''quotient''' (resp: le '''reste''') de la '''division euclidienne''' de <math>a</math> par <math>b</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
* On reprends les notation de la preuve précédente, et on pose <math>q:=\max A</math>. Ainsi <math>qb\leq a</math>, on peut donc poser <math>r:=a-bq</math>. On a déjà <math>a=bq+r</math>. Comme <math>q+1\notin A,\, a<(q+1)b</math>, ainsi <math>r=a-bq<b</math>, ce qui prouve l'existence.<br />
* Traitons l'unicité : on suppose disposer de deux tels couples <math>(q,r)</math> et <math>(q',r')</math>. Supposons un instant <math>q\neq q'</math>. Quitte à permuter <math>q</math> et <math>q'</math>, on peut supposer <math>q<q'</math>, ie <math>1\leq q'-q</math>. On a alors <math>b\leq b(q'-q)=r-r'</math>. Par ailleurs comme <math>r<b</math>, on a <math>r-r'<b</math> qui fournit l'absurdité, donc : <math>q=q'</math>. Par suite <math>r=r'</math>.
}}
=Rudiments de combinatoire=
==Ensembles finis==
Pour tout <math>n\geq 1</math>, on pose <math>\mathbb{N}_n=\{1,2,..n\}</math> et <math>\mathbb{N}_0=\emptyset</math>.
{{Théorème|titre=Proposition|contenu=
Soit <math>m,n\in\mathbb{N}</math>.<br />
S'il existe une injection <math>\mathbb{N}_m\rightarrow \mathbb{N}_n</math>,<br />
alors <math>m\leq n</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
On procède par récurrence sur <math>m</math>. On pose <math>\mathcal{P}(m):=\forall n\in\mathbb{N}</math>, s'il existe une injection <math>\mathbb{N}_m\rightarrow \mathbb{N}_n</math>, alors <math>m\leq n</math>.[j'aimerais des guillemets]<br />
<math>\mathcal{P}(O)</math> est vrai, c'est la définition de zéro.<br />
On suppose <math>\mathcal{P}(m)</math> vrai pour un certain <math>m</math>, et on considère une injection <math>f:\mathbb{N}_{m+1}\rightarrow \mathbb{N}_n</math>. remarquons qu'alors <math>n\geq 1</math>. On distingue deux cas :
* <math>f(m+1)=n</math>.<br />
On est en mesure de restreindre <math>f</math> en une application <math>\mathbb{N}_m\rightarrow \mathbb{N}_{n-1}</math>, qui reste injective, et à laquelle on applique l'hypothèse de récurrence. Finalement <math>m\leq n-1</math> et donc <math>m+1\leq n</math>.
* <math>f(m+1)\neq n</math>.<br />
On se ramène alors au premier cas en considérant la permutation <math>\tau</math> de <math>\mathbb{N}_n</math> qui échange <math>f(m+1)</math> et <math>n</math>. C'est une bijection car <math>\tau\circ\tau</math> (au Canada) est l'identité. La composé <math>\tau\circ f</math> est une injection satisfaisant au premier cas.
}}
{{Théorème|titre=Corollaire|contenu=
Soit <math>m,n\in\mathbb{N}</math>.<br />
<math>\mathbb{N}_m\sim \mathbb{N}_n \Leftrightarrow m=n</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
* <math>\Leftarrow</math> : Evident, non ?
* <math>\Rightarrow</math> : S'il existe une bijection <math>f:\mathbb{N}_m\rightarrow \mathbb{N}_n</math> alors c'est en particulier une injection donc <math>m\leq n</math>. De plus <math>f^{-1}:\mathbb{N}_n\rightarrow \mathbb{N}_m</math> fournit <math>n\leq m</math>, et donc <math>m=n</math>.
}}
Ceci permet de définir
{{Définition|titre=Définition : ensembles finis, cardinal|contenu=
On dit d'un ensemble <math>E</math> qu'il est '''fini''' ssi il existe <math>n\in\mathbb{N}</math> tel que <math>E</math> soit en bijection avec <math>\mathbb{N}_n</math>.<br />
Dans ce cas cet entier est unique, et appelé '''cardinal''' de <math>E</math>, noté <math>\#E</math>.
}}
Ainsi dans « l'ensemble » des ensembles finis, le cardinal caractérise les « classes d'équivalence » de la relation <math>\sim\,</math>.
==Propriétés des ensembles finis==
===Parties d'un ensemble finie===
{{Théorème|titre=Lemme|contenu=
Soient <math>E</math> un ensemble fini non vide et <math>x\in E</math>.<br />
alors <math>E\setminus \{x\}</math> est fini de cardinal <math>\# E -1</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Notons <math>n=\# E\geq 1</math> et fixons une bijection <math>f:E\rightarrow \mathbb{N}_n</math>. Comme précédemment quitte à composer par la permutation échangeant <math>f(x)</math> et <math>n</math> on peut supposer <math>f(x)=n</math>. Ainsi <math>f</math> induit une bijection <math>E\setminus \{x\}\rightarrow \mathbb{N}_{n-1}</math>.
}}
{{Théorème|titre=Lemme|contenu=
Soient <math>E</math> un ensemble fini et <math>a\subset E</math>.<br />
Alors <math>A</math> est fini <math>\# A\leq \# E</math> avec égalité ssi <math>A=E</math>.
}}
Remarque : ce résultat ne s'étend pas aux ensembles infinis : <math>\mathbb{R}</math> et <math>\mathbb{R}^*_+</math> sont équipotents bien que l'inclusion soit stricte.
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
On récurre sur <math>\# E</math>.
* Si <math>\# E=0</math>, c'est évident...
* Supposant le résultat vrai pour tout ensemble de cardinal <math>n\in \mathbb{N}</math>, on suppose <math>\# E=n+1</math>.<br />
Si <math>A=E</math>, alors <math>A</math> est finis et <math>\# A=\# E</math>.<br />
Si <math>A\subsetstrict E</math> [il faut le bon code...], on peut fixer <math>x\in E\setminus A</math> et appliquer l'hypothèse de récurrence à <math>A\subset E\setminus\{x\}</math>, car d'après le lemme <math>\#E\setminus\{x\}=n</math>. Bref <math>A</math> est fini de cardinal <math>\# A\leq n <\# E</math>.<br />
Le cas d'égalité à été traité car on a envisagé tous les cas.
}}
===Union d'ensembles finis===
{{Théorème|titre=Proposition|contenu=
Soient <math>E</math> un ensemble quelconque et <math>F,G</math> deux parties finies de <math>E</math>.<br />
Alors <math>F\cup G</math> est finie et <math>\# F\cup G=\#F +\# G -\# F\cap G</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
1/ On traite le cas où <math>F\cap G=\emptyset</math>.<br />
Si <math>F</math> ou <math>G</math> est vide c'est évident on suppose dons le contraire.<br />
On note <math>m=\# F</math> et <math>n=\# G</math> et on fixe <math>f:F\rightarrow \mathbb{N}_m</math> et <math>g:G\rightarrow \mathbb{N}_n</math> deux bijections. On veut construire une bijection <math>F\cup G\rightarrow \mathbb{N}_{m+n}</math>.<br />
On définie <math>\phi:F\cup G\rightarrow\mathbb{N}_{m+n}, x \mapsto
\begin{cases} f(x) \text{ si }x\in F\\ g(x) +m \text{ si } x\in G\end{cases}
</math> bien définie car <math>F\cap G=\emptyset</math>; On définie également <math>\psi:\mathbb{N}_{m+n}\rightarrow F\cup G, k \mapsto
\begin{cases} f^{-1}(k) \text{ si }k\leq m\\ g^{-1}(k-m) \text{ si } m< k\leq m+n\end{cases}
</math>.<br />
On vérifie qu'il s'agit de deux bijections réciproques l'une de l'autre… Ce qui donne bien la formule <math>\# F\cup G =m+n-0=\#F +\# G -\# F\cap G</math>.
2/ Dans le cas général on décompose <math>F\cup G=F\cup (G\setminus F)</math> et <math>G=(G\setminus F)\cup(F\cap G)</math> qui sont deux réunions disjointes auxquelles on applique le premier cas : <math>\# F\cup G = \#F +\#(G\setminus F)</math> et <math>\#G =\#(G\setminus F)+ \#F\cap G</math>, pour obtenir la formule annoncée.
}}
{{Théorème|titre=Corollaire|contenu=
Soient <math>E</math> un ensemble et <math>F_1,F_2,\dots,F_n</math> des parties finies de <math>E</math> deux à deux disjointes.<br />
Alors <math>\bigsqcup_{i=1}^n F_i</math> est finie de cardinal <math>\sum_{i=1}^n \# F_i</math>.
}}
{{Théorème|titre=Corollaire|contenu=
Soient <math>E</math> et <math>F</math> deux ensembles finis.<br />
Alors <math>E\times F</math> est fini de cardinal <math>\#E \# F</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
On écrit la partition <math>E\times F=\bigsqcup_{x\in E}\{x\}\times F</math>, et on justifie que <math>\#\{x\}\times F=\# F</math> par la bijection <math>\{x\}\times F \rightarrow F, (x,y)\mapsto y</math>. Il suffit alors d'appliquer le corollaire précédent.
}}
Ce résultat s'étend à un produit fini, et en particulier on a <math>\#(E^n)=(\# E)^n</math>.
===Applications entre ensembles finis===
{{Théorème|titre=Lemme|contenu=
Soient <math>E</math> un ensemble fini, <math>F</math> un ensemble quelconque et <math>f:E\rightarrow F</math>.<br />
Alors <math>f(E)</math> est fini et <math>\#f(E)\leq \# E</math>, avec égalité ssi <math>f</math> est injective.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Notons encore <math>f</math> la restriction <math>f^{|f(E)}</math>. On construit une injection de <math>f(E)</math> sur une partie de <math>E</math> de sorte que <math>\#f(E)\leq \# E</math>.<br />
Pour ce faire on fixe une bijection entre <math>E</math> et <math>\mathbb{N}_{\# E}</math> qui permet de transporter l'ordre induit par celui de <math>\mathbb{N}</math> sur <math>E</math>. On a ainsi un moyen de choisir un élément <math>x_y</math> dans chaque fibre <math>f^{-1}(y)</math> de <math>f</math> : le plus petit par exemple. Ceci permet de construire une application <math>g:f(E)\rightarrow E, y \mapsto x_y</math>, elle est injective, essentiellement car <math>f</math> est une application.
Traitons maintenant l'égalité : Si <math>f</math> est injective, elle induit bien une bijection de <math>E</math> sur <math>f(E)</math>, d'où l'égalité des cardinaux.<br />
Réciproquement si <math>\#f(E)=\# E</math>, alors la partition <math>E=\bigsqcup_{y\in f(E)}f^{-1}(\{y\})</math> donne <math>\# E=\sum_{y\in f(E)}\#f^{-1}(\{y\})</math>. Par ailleurs <math>\#E=\sum_{y\in f(E)} 1</math> donc <math>0=\sum_{y\in f(E)}\#f^{-1}(\{y\})-1</math> somme de termes positifs, donc tous nuls, c'est exactement dire que les fibres sont réduites à des singletons et donc que <math>f</math> est injective.
}}
{{Théorème|titre=Lemme|contenu=
Soient <math>E</math>, <math>F</math> deux ensembles finis de même cardinal et <math>f:E\rightarrow F</math>.<br />
Alors <math>f</math> injective <math>\Leftrightarrow \;f</math> surjective <math>\Leftrightarrow \;f</math> bijective.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
<math>\begin{align}
f \text{ injective } & \Leftrightarrow \# f(E) =\# E \\
& \Leftrightarrow \# f(E) =\# F \\
& \Leftrightarrow f(E)=F \\
& \Leftrightarrow f \text{ surjective}
\end{align}</math>.
Auquel cas <math>f</math> est bijective, et réciproquement bijective <math>\Rightarrow</math> injective et surjective.
}}
==Quelques cardinaux usuels==
{{Théorème|titre=Proposition|contenu=
Soient <math>E</math> et <math>F</math> deux ensembles finis.<br />
Alors <math>F^E</math>, ensemble des applications <math>E\rightarrow F</math> est fini de cardinal <math>\#F^{\#E}</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Si <math>E</math> est vide, il n'y a en effet qu'une application partant du vide et la convention <math>n^0=1</math> valide la formule.<br />
Si <math>F</math> est vide sans que <math>E</math> ne le soit il n'existe aucune application <math>E\rightarrow F</math>, ce qui donne bien <math>0=0</math>.<br />
Traitons le cas plus significatif de deux ensembles non vides : on considère <math>\phi:F^E\rightarrow F^{\#E}, f\mapsto (f(x_i))_{1\leq i \leq \#E}</math>. On a ici numéroté les éléments de <math>E</math>, possible par choix d'une bijection <math>E\rightarrow \mathbb{N}_{\#E}</math>. Cette application est bien une bijection, ce qui livre la proposition.
}}
Remarque : cela « justifie » un peu la notation <math>F^E</math>.
On considère maintenant un ensemble fini <math>E</math>. Pour toute partie <math>A\subset E</math>, on définit la fonction '''indicatrice''' de <math>A</math> par <math>\chi_A:E\rightarrow \{0,1\},x\mapsto \begin{cases}1 \text{ si } x\in A\\0 \text{ sinon}\end{cases}</math>.
Exercice : exprimer <math>\chi_{A^c},\, \chi_{A\cup B},\, \chi_{A\cap B}\, \chi_{A\Delta B}</math> en fonction de <math>\chi_A</math> et <math>\chi_B</math>.
{{Théorème|titre=Proposition|contenu=
L'ensemble <math>\mathcal{P}(E)</math> des parties de <math>E</math> est fini et de cardinal <math>2^{\# E}</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Il suffit de montrer que l'application <math>\chi:\mathcal{P}(E)\rightarrow \{0,1\}^E, A\mapsto \chi_A</math> est bijective. Pour cela on peut considérer l'application <math>\psi:\{0,1\}^E\rightarrow\mathcal{P}(E), f\mapsto f^{-1}(\{1\})</math> et montrer que c'est la réciproque de <math>\chi</math>.
}}
Étant donnés deux ensembles finis <math>E</math> et <math>F</math> de cardinaux respectifs <math>m</math> et <math>n</math>, et après avoir fixé deux bijection <math>\phi</math> et <math>\psi</math> on a une bijection naturelle <math>F^E\rightarrow \mathbb{N}_n^{\mathbb{N}_m},f\mapsto \psi\circ f\circ \phi</math> dont on aurait d'ailleurs pu se servir pour calculer <math>\#F^E</math>. Cette bijection échange les injections (exercice). Pour calculer le nombre de ces injections noté <math>A_n^m</math>, on supposera qu'on a faire aux ensembles d'entiers canoniques.
{{Théorème|titre=Proposition|contenu=
<math>A_n^m=\begin{cases}\frac{n!}{(n-m)!} \text{ si } m\leq n\\ 0 \text{ sinon}\end{cases}</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
En effet si <math>m>n</math> il n'existe pas de telle injection.<br/>
Une injection <math>\mathbb{N}_m\rightarrow\mathbb{N}_n</math> est déterminée par la donné de l'image <math>x</math> de <math>m</math> et par une injection <math>\mathbb{N}_{m-1}\rightarrow\mathbb{N}_n\setminus\{x\}</math>. On a donc la relation de récurrence <math>A_n^m=n A_{n-1}^{m-1}=\dots=n(n-1)(n-2)\dots(n-m+1)A_{n-m}^0</math>, ce qui donne bien la formule compte tenu du fait que l'unique application partant du vide est bien injective.
}}
En particulier, on en déduit qu'il y a <math>n!</math> bijections d'un ensemble à <math>n</math> éléments dans lui même.
On s'intéresse maintenant au nombre <math>C_n^p</math> de parties à <math>p</math> éléments dans un ensemble <math>E</math> à <math>n</math> éléments. On notera ici <math>\mathcal{P}_p(E)</math> cet ensemble et <math>\mathcal{A}_n^p</math> celui des <math>p</math>-uplets d'éléments deux à deux disjoints de <math>E</math>. C'est un ensemble de cardinal <math>A_n^p</math>, est-ce clair ?<br />
De plus l'application <math>\mathcal{A}_n^p\rightarrow \mathcal{P}_p(E), (x_k)_{1\leq k \leq p}\mapsto \{x_1,x_2,\dots,x_k\}</math> est surjective et chaque fibre contient <math>p!</math> éléments : c'est le nombre de façon d'ordonner le <math>p</math>-uplet <math>(x_k)_{1\leq k \leq p}</math>. On obtient donc, en vertu de la partition en fibres <math>\# \mathcal{A}_n^p=p! \#\mathcal{P}_p(E)</math>. Finalement <math>C_n^p=\begin{cases}\frac{n!}{p!(n-p)!} \text{ si } p\leq n \\ 0 \text { sinon}\end{cases}</math>. On préfèrera désormais la notation <math>\binom{n}{p}</math>, lire « <math>p</math> parmi <math>n</math> », à celle plus franco-française <math>C_n^p</math>. En résumé, on a obtenu le
{{Théorème|titre=Théorème : coefficients binomiaux|contenu=
Soient <math>p,n</math> deux entiers.<br />
Le nombre de parties à <math>p</math> éléments d'un ensemble à <math>n</math> éléments est <math>\binom{n}{p}=\begin{cases}\frac{n!}{p!(n-p)!} \text{ si } p\leq n \\ 0 \text { sinon}\end{cases}</math>.
}}
Remarques : ces coefficients interviennent naturellement dans la formule dites du « binôme » qui permet de développer <math>(a+b)^n</math>, si <math>a</math> et <math>b</math> commutent. On les appelle '''coefficients binomiaux'''.
Exercice : Montrer avec des arguments combinatoires les deux relations suivantes :
* <math>\binom{n}{p}+\binom{n}{p+1}=\binom{n+1}{p+1}</math> dite de Pascal,
* <math>\sum_{k=1}^n \binom{n}{k}=2^n</math>.
==Les infinis==
===Généralités===
L'ensemble des entiers naturels nous a servi à classer les ensembles finis suivant leur cardinal. Mais par exemple <math>\N</math> lui-même n'est pas fini, c'est un exemple d'ensemble '''infini'''. On souhaiterait quand même les classer. L'idée intuitive est que si l'on peut injecter un ensemble dans un autre, alors le premier est plus petit.
Cette « relation binaire », qui n'en n'est pas une car on ne peut considérer l'ensemble des ensembles, est réflexive (l'identité est injective) et transitive (la composée d'injections l'est aussi). C'est un « pré-ordre » et le théorème de Cantor-Bernstein montre que les classes d'équivalence associées sont exactement les ensembles équipotents entre-eux.
La seconde question qui vient est : tous les ensembles infinis sont-ils équipotents entre-eux ? La proposition suivante y répond par la négative, mais laisse entre-voir une théorie intéressante traitant des cardinaux infinis.
{{Théorème|titre=Proposition|contenu=
Soit <math>E</math> un ensemble.<br />
Alors il n'existe pas de surjection, et donc a fortiori de bijection, de <math>E</math> sur <math>\mathcal{P}(E)</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Procédons par l'absurde et fixons <math>f:E\rightarrow \mathcal{P}(E)</math> une surjection. On s'intéresse alors à la partie <math>A</math> de <math>E</math> définie par <math>A:=\{x\in E/ x\notin f(x)\}</math> et on choisit <math>a\in E</math> un antécédent de <math>A</math>. Si <math>a\in A=f(A)</math>, alors <math>a\notin A</math>. Et aussi, si <math>a\notin A=f(A)</math> alors <math>a\in A</math>, ce qui est manifestement une contradiction.
}}
{{Théorème|titre=Proposition|contenu=
Si un ensemble <math>E</math> est infini, il existe une injection <math>\phi:\N\rightarrow E</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
A nouveau on peut construire pour tout <math>n\in\N</math> une injection <math>\phi_n:\N_n\rightarrow E</math> telle que <math>\forall n\in\N,\, \phi_{n+1}(n)=\phi_n(n)</math>. On pose alors <math>\phi:\N\rightarrow E,n\mapsto \phi_n(n)</math>, il reste à vérifier que <math>\phi</math> est bien injective : si on se donne <math>m,n\in\N / \phi(m)=\phi(n)</math>, alors pour <math>\mu:=\max\{m,n\}</math> on a <math>\phi_{\mu}(m)=\phi_{\mu}(n)</math> et par construction <math>\phi_{\mu}</math> est injective, d'où <math>m=n</math>.
}}
En quelque sorte, <math>\N</math> est le plus petit ensemble infini, on s'intéresse plus particulièrement à sa « classe d'équivalence » dans la section suivante.
===Ensembles dénombrables===
{{Définition|titre=Définition : ensembles dénombrables|contenu=
Un ensemble ''E'' est dit '''dénombrable''' si et seulement s'il existe une bijection de ''E'' dans <math>\N</math>. On dira '''au plus dénombrable''' si l'ensemble est fini ou dénombrable.
}}
Outre l'intérêt purement théorique de cette notion, et des « cardinaux infinis », on peut citer quelques exemples d'application. On les mentionne pour culture, car ils supposent une certaine familiarité avec des notions non encore introduites (dans de prochains cours, qui sait).
Voici d'abord quelques exemples classiques d'ensembles dénombrables:
# <math>\N</math> est dénombrable ;
# <math>\Z</math> est dénombrable ;
# <math>\N \times \N</math> est dénombrable ;
# <math>\Q</math> est dénombrable ;
# L'ensemble des suites finies d'entiers naturels est dénombrable.
Remarque : souvent, montrer qu'un ensemble est dénombrable consiste à expliciter une bijection de cet ensemble vers <math>\N</math> ou vers un autre ensemble dénombrable.
{{boîte déroulante|titre=Preuves|contenu=
:1. L'application identité est une bijection de <math>\N</math> dans lui-même, donc <math>\N</math> est dénombrable.
:2. Posons ''ƒ'' l'application de <math>\N</math> dans <math>\Z</math> qui agit de la manière suivante : <math>f(0) = 0</math>, <math>f(1) = 1</math>, <math>f(2) = -1</math>, <math>f(3) = 2</math>, <math>f(4) = -2</math>… Alors ''ƒ'' est clairement une bijection de <math>\N</math> sur <math>\Z</math>, ces deux ensembles sont donc isomorphes, donc <math>\Z</math> es dénombrable.
:3. Ici encore, construisons une application bijective de <math>\N</math> dans <math>\N \times \N</math> [ce qui est beaucoup plus lisible sur une illustration…] : <math>f(0)=(0,0)</math>, <math>f(1)=(0,1)</math>, <math>f(2)=(1,0)</math>, <math>f(3)=(0,2)</math>, <math>f(4)=(1,1)</math>, <math>f(5)=(2,0)</math>… <math>\N</math> est ainsi isomorphe à <math>\N \times \N</math>, lequel est donc dénombrable.
:4. Remarquons que tout nombre rationnel peut s'écrire de manière unique comme une fraction irréductible, dont le numérateur est un entier relatif et le dénominateur un entier naturel : <math>\Q</math> est isomorphe à <math>\Z \times \N</math>. Or <math>\Z</math> est isomorphe à <math>\N</math> d'après (2), et <math>\N \times \N</math> est dénombrable d'après (3). Par conséquent, <math>\Q</math> est dénombrable.
Remarque : on peut également expliciter une bijection de <math>\N</math> sur <math>\Q</math> dans cette dernière preuve, par un procédé analogue à celui utilisé en (4), appelé ''diagonalisation'' ou ''procédé diagonal''.
:5. Une suite de ''n'' entiers peut être vue comme un élément de <math>\N \times \N \times \cdots \times \N</math>. En regroupant deux à deux <math>\N</math>, on se ramène au cas du (4), si bien que l'ensemble des telles suites est dénombrable.
}}
Par analogie avec les ensembles finis, nous introduisons la notion de cardinal pour les ensembles ''infinis'' dénombrables :
{{définition|titre=Définition : <math>\aleph_0</math> |contenu=
On note <math>\aleph_0\,</math> (lire « aleph-0 ») le cardinal des entiers naturels. Un ensemble a <math>\aleph_0\,</math> pour cardinal si et seulement s'il est infini et dénombrable.
}}
La question qui se pose est alors : l'ensemble des nombres réels est-il un ensemble dénombrable ? La réponse, comme nous allons le voir, est non : <math>\R</math> n'est pas dénombrable. Cet ensemble, infini, est d'une toute autre nature. La démonstration qui suit utilise un procédé diagonal et un raisonnement par l'absurde.
{{boîte déroulante|titre=Preuve : l'ensemble des réels n'est pas dénombrable|contenu=
Procédons par l'absurde : considérons l'intervalle [0, 1[. On le suppose dénombrable, si bien que l'on peut affecter à chacun de ses nombres un numéro. D'autre part, tout réel ''x''<sub>''i''</sub> de cet intervalle peut s'écrire sous forme décimale :
:<math>x_i = 0, x_{i,1} x_{i,2} x_{i,3} x_{i,4}\ldots</math>
La liste de tous les réels de [0, 1[ possède l'allure suivante :
:<math>x_1 = 0,35592632\ldots</math>
:<math>x_2 = 0,19373237\ldots</math>
:<math>x_3 = 0,42598689\ldots</math>
:<math>x_4 = 0,16834435\ldots</math>
:<math>\;\vdots</math>
Construisons un nombre ''u'' de la manière suivante :
* son premier chiffre après la virgule, <math>u_1</math> est ''différent'' de <math>x_{1,1}</math> ;
* <math>u_2</math> est différent de <math>x_{2,2}</math> ;
* <math>u_3</math> est différent de <math>x_{3,3}</math> ;
* …
Nous avons alors un nombre de l'intervalle [0, 1[, qui ne peut pas être égal à <math>x_1</math> (il diffère d'au moins un chiffre), ni à <math>x_2</math> pour la même raison, ni à <math>x_3</math>… ni à aucun nombre de cette liste. Dans l'exemple ci-dessus, un ''u'' envisageable serait : 0,2842…
Par conséquent, [0, 1[ n'est pas dénombrable, or il s'agit d'une partie de <math>\R</math>, donc <math>\R</math> n'est pas dénombrable.
}}
On peut même montrer que <math>\R\sim\mathcal{P}(\N)</math>, par contre on ne sait pas<ref>Pour être précis, on ne peut pas décider avec le jeu d'axiomes (ZF, ZFC) usuel (Gödel 1938, Cohen 1963).</ref> s'il existe des ensembles strictement compris, au sens de l'injection, entre <math>\N</math> et <math>\R</math> : c'est '''l'hypothèse du continu'''. On admet souvent qu'il n'y a rien entre les deux et on note alors <math>\aleph_1</math> le cardinal de la classe de <math>\R</math> : on parle d'ensemble ayant la '''puissance du continu'''.
Puisque l'ensemble des entiers naturels est compris dans celui des nombres réels, et que l'ensemble des nombres réels n'est pas dénombrable, <math>\R</math> est dans un certain sens « strictement plus grand » que <math>\N</math>. De ceci, on établit des résultats importants :
{{Théorème|titre=Existence des nombres irrationnels et des nombres transcendants|contenu=
'''Existence des nombres irrationnels :'''
* L'ensemble des rationnels est dénombrable.
* L'ensemble des réels est indénombrable, et contient <math>\Q</math>.
Par conséquent, il existe des nombres réels qui ne sont pas rationnels, appelés '''nombres irrationnels''', et l'ensemble <math>\R \setminus \Q</math> des nombres irrationnels est indénombrable.
'''Existence des nombres transcendants :'''
* L'ensemble des suites finies d'entiers naturels (donc, relatifs) est dénombrable.
* Ainsi, l'ensemble des polynômes à coefficients entiers constants est dénombrable.
* Le nombre de zéros d'un polynôme est fini.
Par conséquent, l'ensemble des nombres qui sont racines d'un polynôme à coefficients entiers est dénombrable. Or l'ensemble des nombres réels est indénombrable : il existe donc des nombres qui ne sont pas de telles racines, appelés '''nombres transcendants''', et l'ensemble des nombres transcendants est indénombrable.
}}
Remarque : contrairement à l'intuition, il y a « ''infiniment'' plus » de nombres transcendants ou irrationnels (comme ''π'', racine de 2 ou ''e'') que de nombres « naturels » (comme 0, 1 ou ½).
==Notes et références==
<references>
| 