# Un cours d'algèbre constructive

Ray Mines, Fred Richman, Wim Ruitenburg, Henri Lombardi, Stefan Neuwirth

► To cite this version:

Ray Mines, Fred Richman, Wim Ruitenburg, Henri Lombardi, Stefan Neuwirth. *Un cours d'algèbre constructive*. Presses universitaires de Franche-Comté, 2020. Pratiques et techniques, série Didactiques, mathématiques, Martin Meyer, 978-2-84867-782-8. hal-03521758

HAL Id: hal-03521758

https://hal.science/hal-03521758v1

Submitted on 15 Jan 2026

**HAL** is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Un cours d'algèbre constructive

Ray Mines Fred Richman Wim Ruitenburg

Édition anglaise originale : 1988

Traduction française par Henri Lombardi
révisée par Stefan Neuwirth

14 janvier 2026
<figure><img src="image_2.png" /></figure>
Dédié à Errett Bishop
<figure><img src="image_3.png" /></figure>
# Préface

L'approche constructive aux mathématiques a connu une renaissance, en grande partie grâce à la parution du livre d'Errett Bishop *Foundations of constructive analysis* en 1967, et aussi grâce à l'influence subtile de la prolifération d'ordinateurs avec de grandes capacités de calcul. Bishop a démontré que les mathématiques pures peuvent être développées d'un point de vue constructif tout en maintenant la continuité avec la terminologie et l'esprit classiques; une bien plus grande partie des mathématiques classiques a pu être préservée par rapport à ce que l'on pouvait croire possible, et aucun théorème faux en mathématiques classiques n'en a résulté, comme cela avait été le cas pour d'autres écoles constructives, comme le constructivisme russe ou l'intuitionnisme. Les ordinateurs ont créé une conscience largement partagée de la notion intuitive de procédure effective, et de celle de calculs exécutables en principe. Ils ont en outre stimulé l'étude de l'algèbre constructive en vue de son implémentation, ainsi que du point de vue de la théorie des fonctions récursives.

En analyse, les problèmes de constructibilité apparaissent immédiatement parce que nous devons commencer avec les nombres réels, et qu'il n'y a pas de procédure finie pour décider si deux nombres réels sont égaux ou pas (les nombres réels ne forment pas un ensemble discret). Le principal obstacle pour les mathématiques constructives était en direction de l'analyse, alors que plusieurs mathématiciens, notamment Kronecker et van der Waerden, avaient fait d'importantes contributions à l'algèbre constructive. Heyting, travaillant en algèbre intuitionniste, s'est concentré sur les problèmes liés aux structures algébriques sur les nombres réels; il y a développé une partie de l'analyse plutôt qu'une théorie des structures algébriques discrètes. De manière paradoxale, c'est en algèbre que le plus souvent nous nous heurtons à des arguments sauvagement non constructifs comme ceux qui établissent l'existence d'idéaux maximaux, ou l'existence de plus que deux automorphismes du corps des nombres complexes.

Dans ce livre, nous présentons les notions de base de l'algèbre moderne d'un point de vue constructif. Les sujets les plus avancés ont été dictés par nos préférences et par nos limitations, et par la disponibilité de traitements constructifs dans la littérature. Quoique le livre soit par nécessité à peu près auto-contenu, il n'est pas censé être une première introduction à l'algèbre moderne; le lecteur est présumé avoir quelque familiarité avec le sujet classique.

Il est important de garder à l'esprit que l'algèbre constructive est de l'algèbre; en fait, c'est une généralisation de l'algèbre classique en ce que nous ne supposons pas la loi du tiers exclu, exactement comme la théorie des groupes est une
généralisation de la théorie des groupes abéliens en ce que la commutativité n'est plus supposée. Une démonstration constructive d'un théorème est en particulier une démonstration de ce théorème. Tout théorème dans ce livre peut être compris comme se référant à l'univers conventionnel du discours mathématique, et les démonstrations sont acceptables dans cet univers (aux fautes éventuelles de raisonnement près). Nous ne nous limitons pas à une classe restreinte d'«objets constructifs» comme le font les théoriciens des fonctions récursives et nous n'introduisons pas non plus de principes classiquement faux comme le font les intuitionnistes.

Nous exprimons nos remerciements à Abraham Seidenberg, Gabriel Stolzenberg, Larry Hughes, Bill Julian et Steve Merrin pour leurs suggestions.

Ray Mines

Fred Richman

New Mexico State University

Wim Ruitenburg

Marquette University
# Préface du traducteur

Il me faut avant tout remercier Fred Richman pour sa collaboration bien-
veillante à cette traduction. Il m'a fourni le fichier source latex de la version
originale du livre en anglais, et il a répondu à toutes mes demandes d'éclaircis-
sements.

Je remercie aussi chaleureusement Stefan Neuwirth, un collaborateur qui a
relu avec une précision remarquable la traduction une fois terminée. Le nombre
d'erreurs que je suis capable de commettre sans les déceler lors d'une relecture
personnelle m'a véritablement impressionné. Sa relecture nous a aussi permis
de préciser certains points délicats dans plusieurs démonstrations.

J'ai introduit un certain nombre de « notes du traducteur » en bas de page,
notées NdT. Souvent il s'agit de préciser la terminologie anglaise pour un terme
dont la traduction française est assez éloignée. Quand c'était possible, j'ai utilisé
comme terminologie française de référence celle de Bourbaki.

D'autres fois, j'ai utilisé une note de bas de page pour ajouter une précision
que j'estimais utile pour mieux comprendre le texte.

Par ailleurs les rares fois où j'ai un tout petit peu corrigé le texte, hormis
quelques fautes de frappe évidentes, je l'ai fait en accord avec Fred Richman.

Après la traduction proprement dite du livre, je fais figurer une postface
où je commente certains des aspects particulièrement marquants, notamment
certaines divergences par rapport au livre de Bishop.

Enfin Stefan Neuwirth a réalisé le chapitre final sur la réception de l'édition
originale de l'ouvrage. Il donne une liste bibliographique des travaux qui ont
cité le livre depuis sa parution.

Henri Lombardi
Université de Franche-Comté
<figure><img src="image_4.png" /></figure>
# Table des matières

<table><tr><td>Préface</td><td>v</td></tr><tr><td>I Ensembles</td><td>1</td></tr><tr><td>1 Mathématiques constructives vs. mathématiques classiques</td><td>1</td></tr><tr><td>2 Ensembles, sous-ensembles, fonctions</td><td>7</td></tr><tr><td>3 L'axiome du choix</td><td>14</td></tr><tr><td>4 Catégories</td><td>16</td></tr><tr><td>5 Ensembles ordonnés et treillis</td><td>20</td></tr><tr><td>6 Ensembles bien fondés et ordinaux</td><td>24</td></tr><tr><td>7 Notes</td><td>29</td></tr><tr><td>II Algèbre de base</td><td>35</td></tr><tr><td>1 Groupes</td><td>35</td></tr><tr><td>2 Anneaux et corps</td><td>41</td></tr><tr><td>3 Les nombres réels</td><td>48</td></tr><tr><td>4 Modules</td><td>51</td></tr><tr><td>5 Anneaux de polynômes</td><td>59</td></tr><tr><td>6 Matrices et espaces vectoriels</td><td>64</td></tr><tr><td>7 Déterminants</td><td>68</td></tr><tr><td>8 Polynômes symétriques</td><td>72</td></tr><tr><td>9 Notes</td><td>75</td></tr><tr><td>III Anneaux et modules</td><td>77</td></tr><tr><td>1 Idéaux quasi-réguliers et radical de Jacobson</td><td>77</td></tr><tr><td>2 Modules cohérents, noethériens</td><td>79</td></tr><tr><td>3 Localisation</td><td>84</td></tr><tr><td>4 Produits tensoriels</td><td>87</td></tr><tr><td>5 Modules plats</td><td>91</td></tr><tr><td>6 Anneaux locaux</td><td>96</td></tr><tr><td>7 Anneaux commutatifs locaux</td><td>102</td></tr><tr><td>8 Notes</td><td>106</td></tr></table>
<table><tbody><tr><td><strong>IV</strong></td><td><strong>Divisibilité dans les anneaux intègres</strong></td><td><strong>107</strong></td></tr><tr><td>1</td><td>Divisibilité dans les monoïdes réguliers</td><td>107</td></tr><tr><td>2</td><td>Anneaux à factorisation unique et domaines de Bézout</td><td>113</td></tr><tr><td>3</td><td>Anneaux de Dedekind-Hasse et anneaux euclidiens</td><td>117</td></tr><tr><td>4</td><td>Anneaux de polynômes</td><td>122</td></tr><tr><td>5</td><td>Notes</td><td>126</td></tr><tr><td><strong>V</strong></td><td><strong>Anneaux principaux</strong></td><td><strong>127</strong></td></tr><tr><td>1</td><td>Diagonalisation des matrices</td><td>127</td></tr><tr><td>2</td><td>Modules de présentation finie</td><td>130</td></tr><tr><td>3</td><td>Modules de torsion, p-composantes, diviseurs élémentaires</td><td>132</td></tr><tr><td>4</td><td>Transformations linéaires</td><td>134</td></tr><tr><td>5</td><td>Notes</td><td>137</td></tr><tr><td><strong>VI</strong></td><td><strong>Théorie des corps</strong></td><td><strong>139</strong></td></tr><tr><td>1</td><td>Extensions entières et anneaux impotents</td><td>139</td></tr><tr><td>2</td><td>Indépendance algébrique et bases de transcendance</td><td>144</td></tr><tr><td>3</td><td>Corps de décomposition et clôtures algébriques</td><td>150</td></tr><tr><td>4</td><td>Séparabilité et diagonalisabilité</td><td>153</td></tr><tr><td>5</td><td>Éléments primitifs</td><td>157</td></tr><tr><td>6</td><td>Séparabilité et caractéristique p</td><td>159</td></tr><tr><td>7</td><td>Corps parfaits</td><td>163</td></tr><tr><td>8</td><td>Théorie de Galois</td><td>166</td></tr><tr><td>9</td><td>Notes</td><td>173</td></tr><tr><td><strong>VII</strong></td><td><strong>Factorisation des polynômes</strong></td><td><strong>175</strong></td></tr><tr><td>1</td><td>Corps factoriels et corps séparablement factoriels</td><td>175</td></tr><tr><td>2</td><td>Extensions de corps (séparablement) factoriels</td><td>181</td></tr><tr><td>3</td><td>Corps de Seidenberg : la condition P</td><td>184</td></tr><tr><td>4</td><td>Le théorème fondamental de l'algèbre</td><td>187</td></tr><tr><td>5</td><td>Notes</td><td>190</td></tr><tr><td><strong>VIII</strong></td><td><strong>Anneaux commutatifs noethériens</strong></td><td><strong>191</strong></td></tr><tr><td>1</td><td>Le théorème de la base de Hilbert</td><td>191</td></tr><tr><td>2</td><td>Le théorème de normalisation de Noether et le lemme d'Artin-Rees</td><td>195</td></tr><tr><td>3</td><td>Le Nullstellensatz</td><td>199</td></tr><tr><td>4</td><td>L'approche de Tennenbaum pour le théorème de la base de Hilbert</td><td>202</td></tr><tr><td>5</td><td>Idéaux primaires</td><td>206</td></tr><tr><td>6</td><td>Localisation</td><td>209</td></tr><tr><td>7</td><td>Décompositions primaires</td><td>214</td></tr><tr><td>8</td><td>Anneaux de Lasker-Noether</td><td>218</td></tr><tr><td>9</td><td>Anneaux complètement de Lasker-Noether</td><td>221</td></tr><tr><td>10</td><td>Le théorème de l'idéal principal</td><td>224</td></tr></tbody></table>
<table>
  <tbody>
    <tr>
      <td>11</td>
      <td>Notes</td>
      <td>227</td>
    </tr>
    <tr>
      <td>IX</td>
      <td>Algèbres de dimension finie</td>
      <td>229</td>
    </tr>
    <tr>
      <td>1</td>
      <td>Représentations</td>
      <td>229</td>
    </tr>
    <tr>
      <td>2</td>
      <td>Le théorème de densité</td>
      <td>232</td>
    </tr>
    <tr>
      <td>3</td>
      <td>Le radical et les facteurs directs</td>
      <td>235</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Théorème de Wedderburn, première partie</td>
      <td>240</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Anneaux de matrices et algèbres à division</td>
      <td>243</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Notes</td>
      <td>245</td>
    </tr>
    <tr>
      <td>X</td>
      <td>Groupes libres</td>
      <td>247</td>
    </tr>
    <tr>
      <td>1</td>
      <td>Existence et unicité</td>
      <td>247</td>
    </tr>
    <tr>
      <td>2</td>
      <td>Ensembles de Nielsen</td>
      <td>251</td>
    </tr>
    <tr>
      <td>3</td>
      <td>Sous-groupes de type fini de groupes libres</td>
      <td>253</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Sous-groupes détachables de groupes libres de rang fini</td>
      <td>255</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Sous-groupes conjugués</td>
      <td>259</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Notes</td>
      <td>261</td>
    </tr>
    <tr>
      <td>XI</td>
      <td>Groupes abéliens</td>
      <td>263</td>
    </tr>
    <tr>
      <td>1</td>
      <td>Groupes sans torsion de rang fini</td>
      <td>263</td>
    </tr>
    <tr>
      <td>2</td>
      <td>Groupes divisibles</td>
      <td>268</td>
    </tr>
    <tr>
      <td>3</td>
      <td>Fonctions de hauteur sur les p-groupes</td>
      <td>271</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Le théorème d'Ulm</td>
      <td>275</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Construction de groupes d'Ulm</td>
      <td>279</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Notes</td>
      <td>282</td>
    </tr>
    <tr>
      <td>XII</td>
      <td>Théorie des valeurs absolues</td>
      <td>285</td>
    </tr>
    <tr>
      <td>1</td>
      <td>Valeurs absolues</td>
      <td>285</td>
    </tr>
    <tr>
      <td>2</td>
      <td>Valeurs absolues localement précompactes</td>
      <td>291</td>
    </tr>
    <tr>
      <td>3</td>
      <td>Corps pseudofactoriels</td>
      <td>294</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Espaces vectoriels normés</td>
      <td>297</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Corps réels et complexes</td>
      <td>300</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Le lemme de Hensel</td>
      <td>305</td>
    </tr>
    <tr>
      <td>7</td>
      <td>Extensions de valeurs absolues</td>
      <td>314</td>
    </tr>
    <tr>
      <td>8</td>
      <td>Indice de ramification et degré résiduel (e et f)</td>
      <td>318</td>
    </tr>
    <tr>
      <td>9</td>
      <td>Notes</td>
      <td>322</td>
    </tr>
    <tr>
      <td>XIII</td>
      <td>Domaines de Dedekind</td>
      <td>325</td>
    </tr>
    <tr>
      <td>1</td>
      <td>Ensembles de Dedekind (de valeurs absolues discrètes)</td>
      <td>325</td>
    </tr>
    <tr>
      <td>2</td>
      <td>Théorie des idéaux</td>
      <td>328</td>
    </tr>
    <tr>
      <td>3</td>
      <td>Extensions finies</td>
      <td>332</td>
    </tr>
    <tr>
      <td>Références</td>
      <td></td>
      <td>335</td>
    </tr>
  </tbody>
</table>
<table><tr><td>Index des termes</td><td>341</td></tr></table>

<table><tr><td>Postface du traducteur</td><td>355</td></tr></table>

<table><tr><td>1</td><td>La réception de l'ouvrage</td><td>355</td></tr></table>

<table><tr><td>2</td><td>Une théorie des ensembles revisitée</td><td>357</td></tr></table>

<table><tr><td>3</td><td>L'exemple des anneaux principaux et des modules de type fini sur ces anneaux</td><td>363</td></tr></table>

<table><tr><td>4</td><td>Les problèmes de factorisation</td><td>364</td></tr></table>

<table><tr><td>5</td><td>Les anneaux noethériens</td><td>367</td></tr></table>

<table><tr><td>6</td><td>Le théorème de structure de Wedderburn</td><td>372</td></tr></table>

<table><tr><td>7</td><td>Les domaines de Dedekind</td><td>375</td></tr></table>

<table><tr><td></td><td>Références</td><td>376</td></tr></table>

<table><tr><td>Réception de l'ouvrage</td><td>379</td></tr></table>
# I. Ensembles

## Sommaire

<table><tr><td>1</td><td>Mathématiques constructives vs. mathématiques classiques</td><td>1</td></tr><tr><td>2</td><td>Ensembles, sous-ensembles, fonctions</td><td>7</td></tr><tr><td>3</td><td>L'axiome du choix</td><td>14</td></tr><tr><td>4</td><td>Catégories</td><td>16</td></tr><tr><td>5</td><td>Ensembles ordonnés et treillis</td><td>20</td></tr><tr><td>6</td><td>Ensembles bien fondés et ordinaux</td><td>24</td></tr><tr><td>7</td><td>Notes</td><td>29</td></tr></table>

## 1 Mathématiques constructives vs. mathématiques classiques

Le point de vue classique sur les mathématiques est essentiellement décritif : on essaie de décrire des faits à propos d'un univers statique. Ainsi par exemple on admet qu'un polynôme de degré impair admet toujours une racine, et qu'il y a une décimale qui apparaît une infinité de fois dans le développement décimal de $\pi$. On a un point de vue opposé en mathématiques constructives, elles concentrent leur attention sur l'interaction dynamique entre l'individu et l'univers mathématique ; dans les termes de Hao Wang, il s'agit d'une mathématique du faire plutôt que d'une mathématique de l'être. Le mathématicien constructif doit montrer comment construire une racine d'un polynôme de degré impair, et comment on peut trouver une décimale qui apparaît une infinité de fois dans le développement décimal de $\pi$.

Nous imaginons un mathématicien idéalisé $U$ qui interagit avec l'univers mathématique ; c'est lui le «vous» qui trouve le $\delta$ et à qui un $\epsilon$ est donné lorsque nous disons «étant donné un $\epsilon$ vous devez trouver $\delta$». Les phrases «il existe» et «vous devez trouver» signifient que $U$ doit réaliser les constructions souhaitées. Puisque «$P_1$ ou $P_2$» signifie qu'il existe $i \in \{1, 2\}$ tel que $P_i$ est vrai, la signification du «ou» découle de la signification du «il existe», et c'est
l'interprétation de cette dernière phrase qui est fondamentale en mathématiques constructives.

Les mathématiques classiques peuvent être elles aussi décrites dans cette image; la différence réside dans le pouvoir que nous attribuons à U. Un U omniscient peut décider si une assertion mathématique donnée est vraie ou fausse; ainsi par exemple U peut inspecter la suite des décimales de $\pi$ et déterminer quelles décimales apparaissent une infinité de fois. Avec un omniscient U, notre image est simplement un portrait plus dynamique, anthropomorphique, des mathématiques classiques.

En mathématiques constructives nous supposons que $U$ peut seulement réaliser des constructions finies en nature. Comme le dit Errett Bishop, «la seule manière de démontrer qu'un objet existe est de donner une procédure finie pour le trouver». Dans ce cadre, nous n'avons pas le droit de dire qu'une décimale apparaît une infinité de fois dans le développement de $\pi$ tant que nous ne sommes pas prêts à exhiber une telle décimale ou au moins à produire un algorithme qui calculera cette décimale.

Nous considérons que $U$ est capable de réaliser n'importe quelle construction spécifiée par un algorithme, mais nous n'excluons pas la possibilité qu'il sache faire d'autres choses – y compris qu'il puisse être omniscient. Le tableau qui résulte du fait de restreindre les capacités de $U$ à des constructions finies est l'**interprétation calculatoire** des mathématiques. Comme toute assertion qui admet une preuve constructive est vraie dans l'interprétation calculatoire, nous disons que les mathématiques constructives ont une signification numérique; comme toute assertion qui admet une preuve constructive est vraie dans l'interprétation classique, nous disons que les mathématiques constructives sont une généralisation des mathématiques classiques.

Les mathématiques constructives sont les mathématiques pures faites de manière algorithmique de façon à respecter l'interprétation calculatoire. La notion centrale de processus fini, ou d'algorithme, est prise comme une notion primitive. Toute tentative de définir ce qu'est un algorithme implique en dernière analyse la notion d'existence – par exemple nous pourrions demander qu'il existe une étape à laquelle un certain programme de calcul produit une réponse. Si le terme «exister» est pris dans son sens classique ici, nous échouons à capturer la notion même d'algorithme. Si le terme est utilisé dans son sens constructif, la définition est circulaire.

Considérez la distinction entre l'usage classique et l'usage constructif du «ou». Pour prouver «$P_1$ ou $P_2$» de manière constructive, nous devons construire un algorithme qui soit prouve $P_1$, soit prouve $P_2$, et en exécutant cet algorithme nous (le mathématicien idéalisé) pouvons déterminer laquelle des deux conditions est vraie. Pour prouver «$P_1$ ou $P_2$» de manière classique, il suffit de montrer que $P_1$ et $P_2$ ne peuvent être simultanément fausses. Par exemple considérons
l'assertion $P_1$ :

il existe des entiers strictement positifs $x, y, z$, et $n$ tels que :

$$x^{n+2} + y^{n+2} = z^{n+2},$$

et soit $P_2$ le fameux théorème de Fermat, la négation de $P_1$. Si $P_1$ est faux alors $P_2$ est vrai, donc « $P_1$ ou $P_2$ » est classiquement prouvable; mais tant que le théorème de Fermat n'est pas démontré, nous ne savons pas laquelle des deux assertions $P_1$ ou $P_2$ est vraie, et nous n'avons pas de preuve constructive de « $P_1$ ou $P_2$ ».

Une démonstration constructive d'un théorème prouve plus qu'une démonstration classique : une démonstration constructive du fait qu'une suite de nombres réels converge implique que nous pouvons calculer une vitesse de convergence; une démonstration constructive du fait qu'un espace vectoriel est de dimension finie implique que nous pouvons calculer une base de cet espace vectoriel; et une démonstration constructive du fait qu'un polynôme est un produit de polynômes irréductibles implique que nous pouvons construire ces polynômes irréductibles.

Deux assertions peuvent être classiquement équivalentes sans l'être construtivement. Soit $P$ l'affirmation selon laquelle tout sous-groupe de $\mathbb{Z}$ est cyclique. Cela signifie que nous pouvons à partir d'une spécification du sous-groupe trouver un générateur de ce sous-groupe. Soit $Q$ l'affirmation selon laquelle aucun sous-groupe $G$ de $\mathbb{Z}$ ne peut avoir la propriété que pour chaque $m \in G$, il y a un entier dans $G$ qui n'est pas multiple de $m$. Les affirmations $P$ et $Q$ sont de manière immédiate équivalentes en mathématiques classiques, mais très différentes d'un point de vue constructif. L'affirmation $Q$ est vraie : comme $0$ est dans $G$, il y a un entier non nul $n$ dans $G$; comme $n$ est dans $G$, il y a un diviseur strict de $n$ dans $G$; et ainsi de suite jusqu'à ce que nous arrivions à une contradiction. Mais il n'est pas du tout crédible que $P$ soit vraie, comme nous pouvons nous en rendre compte en considérant le sous-groupe de $\mathbb{Z}$ engendré par les nombres parfaits : pour construire un générateur de $G$ nous devons construire un nombre parfait impair ou démontrer que tous les nombres parfaits sont pairs.

D'un autre côté, deux assertions constructivement équivalentes sont classiquement équivalentes; en effet, tout théorème de mathématiques constructives est aussi un théorème de mathématiques classiques : une démonstration constructive est une démonstration.

Supposons que nous essayions de trouver une démonstration constructive pour une assertion $P$ qui est classiquement vraie. Après de nombreuses tentatives infructueuses nous pourrions être tentés de chercher un contre-exemple. Mais nous ne pouvons espérer prouver la négation de $P$, ce qu'un contre-exemple de bonne foi impliquerait, car $\neg P$ est classiquement fausse. Comme cette voie nous
est fermée, nous avons besoin d'une autre alternative quand nous persistons à vouloir contredire P.

Une approche consiste à fixer un langage formel dans lequel la propriété P peut être exprimée, à préciser dans ce langage formel quelles sont les suites de mots qui constituent une démonstration, et à démontrer qu'aucune preuve formelle de P ne peut être construite (éventuellement en considérant une interprétation inattendue du langage formel et en montrant que dans cette interprétation la propriété est fausse). Un tel programme de travail est éclairant, mais on peut souvent mettre en doute que le système formel choisi reflète de manière adéquate la réalité mathématique. Une objection plus sérieuse consiste à dire que mettre en œuvre de tels arguments d'indépendance réclame un changement de point de vue drastique. Une procédure qui se situerait plus près du sujet à traiter semble préférable. À cette fin nous introduisons les idées de principe d'omniscience et d'exemple brouwerien.

Une règle qui à chaque entier naturel $n$ fait correspondre un élément $\alpha_n$ de $\{0,1\}$ est appelée une **suite binaire**<fnref n="1" />. Un **principe d'omniscience** est une affirmation vraie classiquement, de la forme « $P(\alpha)$ est vraie pour toutes les suites binaires $\alpha$ », mais qui n'est pas considérée pouvoir être prouvée constructivement. Par exemple classiquement pour toute suite $\alpha$, ou bien

(P) il existe un $n$ pour lequel $\alpha_n = 1$, ou bien

(Q) pour tout $n$, $\alpha_n = 0$.

L'affirmation selon laquelle $P$ ou $Q$ a bien lieu est appelée le **petit principe d'omniscience (LPO)**<fnref n="2" />. Étant donné que $Q$ est la négation de $P$, le petit principe d'omniscience est une forme de la **loi du tiers exclu** : l'affirmation selon laquelle pour n'importe quelle propriété $P$ on a « $P$ ou non $P$». Le petit principe d'omniscience, et à fortiori la loi du tiers exclu, ne sont pas acceptés dans l'approche constructive car personne ne croit sérieusement que l'on puisse construire un algorithme qui, étant donnée une suite $\alpha$, choisisse l'alternative correcte $P$ ou $Q$. Un autre argument contre LPO est que si on se limite à certains types d'algorithmes, comme c'est le cas pour l'école constructiviste russe, alors on peut prouver que LPO est faux. On fixe un langage de programmation capable d'exprimer les fonctions usuelles sur les entiers naturels ainsi que les manipulations symboliques ordinaires. On peut alors démontrer qu'il n'existe aucun programme d'ordinateur qui accepte en entrée des programmes de calcul et qui, appliqué à un programme qui calcule une suite binaire, retourne 1 si la suite contient 1 et 0 si la suite n'en contient pas. Ainsi si nous demandons que nos règles de calcul<fnref n="3" /> soient toutes données par des programmes d'ordinateur, on

<footnote n="1">1. **NdT.** De manière générale dans cet ouvrage, les auteurs utilisent une casse grasse pour indiquer qu'il donne une définition.</footnote>

<footnote n="2">2. **NdT.** Limited principle of omniscience.</footnote>

<footnote n="3">3. **NdT.** Celles utilisées pour produire des suites binaires, et celles utilisées pour produire le test souhaité.</footnote>
peut démontrer que LPO est faux. Ceci est un argument contre l'acceptation de LPO, parce que tout algorithme informel que nous produisons sera sans aucun doute programmable, ainsi nos théorèmes doivent être vrais dans l'interprétation où les algorithmes sont des programmes d'ordinateur; mais nous ne nous restreignons pas à cette interprétation car elle interdit d'interpréter nos théorèmes en mathématiques classiques : et en effet LPO est classiquement vrai.

Lorsque l'on peut montrer qu'une affirmation *P* implique LPO, nous abandonnons la recherche d'une preuve constructive de *P*. Mais nous n'affirmons pas pour autant que *P* est fausse : après tout, *P* peut admettre une preuve classique. Les assertions telles que LPO doivent plutôt être considérées comme *indépendantes* en ce sens que ni elles ni leurs négations ne sont valides.

Considérez par exemple la propriété *P* valide en mathématiques classiques selon laquelle tout sous-ensemble des entiers naturels est vide ou contient un élément. Étant donnée une suite binaire $\alpha$, définissez $A = \{1\}$ et $B = \{\alpha_n : n \in \mathbb{N}\}$. Alors $A \cap B$ est un sous-ensemble des entiers naturels. S'il contient un élément, ce doit être 1, et selon la définition de $B$, il existe un entier $n$ tel que $\alpha_n = 1$; si $A \cap B$ est vide, pour tout entier $n$, $\alpha_n = 0$. Ainsi, si la propriété *P* est vraie alors on a également LPO.

Un principe d'omniscience plus faible est le **mini principe d'omniscience (LLPO)**<fnref n="1" /> qui affirme qu'une suite binaire $(\alpha_n)_{n \in \mathbb{N}}$ qui contient au plus un élément 1, ou bien est nulle pour tout $n$ impair, ou bien est nulle pour tout $n$ pair. Cela implique que dans une suite binaire nous pouvons dire à priori que dans le cas où un élément 1 apparaît, sa première apparition sera pour un indice pair ou impair. Comme dans le cas du principe LPO, si nous limitons nos algorithmes à ceux qui sont programmables sur ordinateur, nous pouvons réfuter LLPO. Si vous pensez à la suite binaire $\alpha$ comme à une boite noire qui retourne $\alpha_n$ lorsque vous lui donnez l'entier $n$ en entrée, il est tout à fait clair que vous ne pouvez espérer établir ni LPO ni LLPO. Considérez la suite $\alpha$ définie comme suit :

$\alpha_{2n} = 1$ si, et seulement si, il y a 100 décimales consécutives de $\pi$ égales à 6 dans les $n$ premières décimales de $\pi$;

$\alpha_{2n+1} = 1$ si, et seulement si, il y a 100 décimales consécutives de $\pi$ égales à 7 dans les $n$ premières décimales de $\pi$.

Comme on sait calculer les décimales de $\pi$, il y a un algorithme qui calcule la suite $\alpha$. Mais à moins que nous tombions par chance sur 100 décimales de $\pi$ consécutives égales à 6 ou à 7, nous aurons du mal à trouver un algorithme qui décide que si cela arrive, pour la première fois ce sera avec un entier $m$ pair ou avec un entier impair.

Un exemple brouwerien $E$ est une construction $E(\alpha)$ basée sur une suite binaire arbitraire $\alpha$. Nous disons que l'exemple brouwerien $E$ satisfait la

<footnote n="1">1. NdT. Lesser limited principle of omniscience.</footnote>
**condition C** si $E(\alpha)$ satisfait la condition C pour chaque $\alpha$; nous disons que l'exemple **E ne satisfait pas la condition C** s'il y a un principe d'omniscience «$P(\alpha)$ pour tout $\alpha$» tel que chaque fois que $E(\alpha)$ satisfait C, $P(\alpha)$ est valide. Un **contre-exemple brouwerien** à une affirmation du type «$C_1$ implique $C_2$» est un exemple brouwerien qui satisfait $C_1$ mais ne satisfait pas $C_2$.

Notre construction précédente $A \cap B$ est un exemple brouwerien d'un sous-ensemble des entiers naturels qui, ni ne contient un élément, ni n'est vide. Nous construisons maintenant une suite croissante bornée de nombres réels qui n'admet pas de borne supérieure. Pour chaque suite binaire $\alpha$ soit $E(\alpha)$ la suite $\beta$ de nombres réels définie par $\beta_n = \sup_{k=1}^n \alpha_k$. Alors $E(\alpha)$ est une suite bornée croissante de nombres réels. Soit $C$ la condition pour une suite de nombres réels qu'elle admette une borne supérieure. Nous allons montrer que $E$ ne satisfait pas la condition $C$. Soit $P(\alpha)$ la propriété que, ou bien $\alpha$ est identiquement nulle, ou bien il y a un entier $n$ tel que $\alpha_n = 1$, et supposons que $E$ satisfasse la condition $C$. Si la borne supérieure de $E(\alpha)$ est $< 1$ alors $\alpha$ est identiquement nulle. Si la borne supérieure de $E(\alpha)$ est $> 0$ alors il y a un entier $n$ tel que $\alpha_n > 0$, donc $\alpha_n = 1$. Ainsi $P(\alpha)$ est valide.

Exercices

1. Montrer que LPO implique LLPO.

2. Tout sous-ensemble de $\{0, 1\}$ contient $0$, $1$ ou $2$ éléments. Construisez un contre-exemple brouwerien pour cette affirmation.

3. Construisez un exemple brouwerien pour un ensemble d'entiers naturels qui ne contient pas de plus petit élément.

4. Construisez un exemple brouwerien pour un sous-groupe de $\mathbb{Z}$ qui n'est pas cyclique.

5. Construisez un exemple brouwerien de deux suites binaires dans la somme contient une infinité de 1, mais cependant aucune des deux ne contient une infinité de 1.

6. Dites qu'une assertion est **simplement existentielle** si elle est de la forme «il existe un entier $n$ tel que $\alpha_n = 1$» pour une certaine suite binaire $\alpha$. Montrer que LLPO est équivalent à

$$ \neg(A \text{ et } B) \text{ si, et seulement si, } \neg A \text{ ou } \neg B $$

pour toute paire d'assertions simplement existentielles $A$ et $B$.

7. Le petit principe d'omniscience faible (WLPO) est l'affirmation selon laquelle, pour toute suite binaire, ou bien elle est identiquement nulle, ou bien il est impossible qu'elle soit identiquement nulle. Montrer que LPO implique WLPO et que WLPO implique LLPO.

8. Soit $S$ l'ensemble des suites finies d'entiers strictement positifs. Par un **arbre finitaire** nous entendons un sous-ensemble $T$ de $S$ tel que
(i) pour chaque $s \in S$, $s \in T$ ou $s \notin T$,

(ii) si $(x_1, \dots, x_n) \in T$, $(x_1, \dots, x_{n-1}) \in T$,

(iii) pour tout $(x_1, \dots, x_n) \in T$, il y a un $m \in \mathbb{N}$ tel que si $(x_1, \dots, x_n, z) \in T$, alors $z \le m$.

Une **branche infinie** de $T$ est une suite $\{x_i\}_{i \in \mathbb{N}}$ d'entiers strictement positifs tels que $(x_1, \dots, x_n) \in T$ pour chaque $n$. Le **lemme de Kőnig** affirme que si $T$ est infini (s'il a des sous-ensembles arbitrairement grands), il a une branche infinie. Montrer que le lemme de Kőnig implique LLPO.

## 2 Ensembles, sous-ensembles, fonctions

Nous travaillons avec deux types de collections d'objets mathématiques, les ensembles et les catégories. Notre notion de ce qu'est un **ensemble** est une notion plutôt libérale.

**Définition 2.1.** Un ensemble $S$ est défini lorsque nous décrivons comment construire ses éléments à partir d'objets déjà construits, ou qui pourraient l'avoir été, avant $S$ lui-même, et lorsque nous expliquons ce que signifie pour deux éléments de $S$ qu'ils sont égaux.

À la suite de Bishop nous regardons la **relation d'égalité** sur un ensemble comme conventionnelle : quelque chose à préciser lorsque l'ensemble est défini, et qui est soumis à la seule contrainte d'être une relation d'équivalence, c'est-à-dire d'être

**réflexive** : $a = a$,

**symétrique** : si $a = b$, alors $b = a$,

**transitive** : si $a = b$ et $b = c$, alors $a = c$.

Une **relation** $n$-aire sur un ensemble $S$ est une propriété $P$ qui concerne les $n$-uplets d'éléments de $S$, et qui est **extensionnelle** en ce sens que si $x_i = y_i$, pour $i = 1, \dots, n$, alors $P(x_1, \dots, x_n)$ si, et seulement si, $P(y_1, \dots, y_n)$. Notez que l'égalité est une relation binaire en ce sens. La relation $P$ est **décidable** si pour chaque $n$-uplet $x_1, \dots, x_n$, ou bien $P(x_1, \dots, x_n)$ est valide, ou bien elle ne l'est pas.

Une relation unaire $P$ sur $S$ définit un **sous-ensemble** $A = \{ x \in S : P(x) \} $ de $S$ : un élément de $A$ est un élément de $S$ qui satisfait la propriété $P$, et deux éléments de $A$ sont égaux si, et seulement si, ils sont égaux comme éléments de $S$. Si $A$ et $B$ sont des sous-ensembles de $S$, et si chaque élément de $A$ est un élément de $B$, nous disons que $A$ est **contenu** dans $B$, et nous écrivons $A \subseteq B$. Deux sous-ensembles $A$ et $B$ d'un ensemble $S$ sont **égaux** si $A \subseteq B$ et $B \subseteq A$; ceci est clairement une relation d'équivalence sur les sous-ensembles de $S$. Nous avons décrit comment construire un sous-ensemble de $S$, et ce que cela
signifie d'être égaux pour deux sous-ensembles de S. Donc nous avons défini l'ensemble tous les sous-ensembles, encore appelé l'**ensemble des parties** de S. Un sous-ensemble de S est **non vide** s'il contient un élément.

La **réunion** de deux sous-ensembles A et B de S est le sous-ensemble de S défini par $A \cup B = \{ x \in S : x \in A \text{ ou } x \in B \}$. Le «ou» dans cette définition doit être interprété constructivement, de sorte que, étant donné un x dans $A \cup B$, nous puissions déterminer un des ensembles dans lequel il se trouve (même si nous ne pouvons savoir s'il est dans les deux à la fois). En termes d'existence, $x \in A \cup B$ signifie qu'il existe $i \in \{1,2\}$ tel que si $i = 1$, alors $x \in A$, et si $i = 2$, alors $x \in B$. L'**intersection** de A et B est le sous-ensemble $A \cap B = \{ x \in S : x \in A \text{ et } x \in B \}$.

Nous regardons la relation d'inégalité comme conventionnelle, comme n'étant pas nécessairement la négation de l'égalité ; l'interprétation du symbole $a \neq b$ dépendra du contexte. Sur chaque ensemble la relation de non-égalité est définie par $a \neq b$ si $a = b$ est impossible. Certains ensembles admettent une relation d'inégalité plus naturelle : si $a$ et $b$ sont des suites binaires, alors la bonne interprétation de $a \neq b$ est qu'il existe un $n$ tel que $a_n \neq b_n$. Si l'on n'a pas spécifié une inégalité sur un ensemble, nous interprétons $a \neq b$ comme étant la non-égalité. Nous employons la terminologie usuelle concernant l'inégalité : dire que $a$ et $b$ sont **distincts** signifie $a \neq b$ ; dire que $a$ est **non nul** signifie $a \neq 0$.

Une inégalité sur un ensemble peut être

**consistante** : $a \neq a$ est impossible ;

**symétrique** : si $a \neq b$, alors $b \neq a$;

**cotransitive** : si $a \neq c$, alors pour tout $b$, $a \neq b$ ou $b \neq c$;

**étroite** : si $a \neq b$ est impossible, alors $a = b$.

Nous voulons presque toujours qu'une inégalité soit symétrique parce que $a \neq b$ est supposée contenir l'idée que $a$ et $b$ sont distincts, ce qui devrait être une relation symétrique. Il est également naturel de demander la consistance, mais en pratique cette propriété est rarement nécessaire. Une inégalité symétrique, consistante et cotransitive est appelée une **relation de séparation** ; l'inégalité que nous avons décrite précédemment pour l'ensemble des suites binaires est une relation de séparation étroite, et il en va de même pour la relation d'inégalité standard sur les nombres réels (voir II.3). La non-égalité n'est pas nécessairement une relation de séparation, et elle n'est pas non plus nécessairement étroite.

On dit qu'une inégalité est **standard** si l'on peut démontrer qu'elle est équivalente à la relation de non-égalité en utilisant la loi du tiers exclu. Une inégalité étroite et consistante est standard parce que $\neg(\neg(a \neq b))$ est équivalent à $\neg(a = b)$. La non-égalité est trivialment standard. Mise à part une importante exception (pour les anneaux locaux), nous serons intéressés uniquement par des inégalités standards. Il faut noter cependant que l'exigence qu'une inégalité soit standard possède très peu de contenu constructif : on ne peut même pas démontrer
que toute inégalité standard sur l'ensemble à un élément est consistante (une affirmation qui peut être réfutée en utilisant la loi du tiers exclu n'est pas nécessairement réfutable).

Un ensemble $S$ avec une inégalité consistante est appelé **discret** si, étant donnés deux éléments $a$ et $b$ de $S$, on a $a = b$ ou $a \neq b$; si $S$ n'a pas une inégalité spécifiée, nous disons que $S$ est discret s'il est discret pour la relation de non-égalité. L'inégalité d'un ensemble discret est la non-égalité, et c'est une relation de séparation étroite. Cependant, l'affirmation selon laquelle un ensemble est discret ne fait pas à priori référence à la relation de non-égalité, mais plutôt à n'importe quelle inégalité qui arrive naturellement avec $S$: dire qu'un ensemble $S$ de suites binaires est discret signifie que pour tous $a$ et $b \in S$, ou bien $a = b$ ou bien il existe un $n$ tel que $a_n \neq b_n$.

L'ensemble $\mathbb{Z}$ des entiers est discret. L'ensemble $\mathbb{Q}$ des nombres rationnels est également discret : un nombre rationnel est un couple d'entiers $m/n$ avec $n \neq 0$, deux nombres rationnels $m_1/n_1$ et $m_2/n_2$ étant considérés comme égaux lorsque que $m_1n_2 = m_2n_1$. Un autre exemple d'ensemble discret est l'anneau $\mathbb{Z}_{12}$ des entiers modulo 12 : ses éléments sont des entiers et deux entiers sont considérés comme égaux lorsque leur différence est divisible par 12. Comme nous savons décider si un entier est divisible par 12 ou pas, l'ensemble $\mathbb{Z}_{12}$ est discret.

Si $x \in S$ et si $A$ est un sous-ensemble de $S$, nous définissons $x \notin A$ comme signifiant que $x \neq a$ pour tout $a \in A$; si l'inégalité sur $S$ est la non-égalité, ou si $S$ n'a pas d'inégalité spécifiée, alors on a $x \notin A$ si, et seulement si, $x$ ne peut pas appartenir à $A$. Le **complémentaire** de $A$ dans $S$ est l'ensemble $S \setminus A = \{x \in S : x \notin A\}$.

Un sous-ensemble $A$ d'un ensemble $S$ est **propre** s'il existe un élément $x$ de $S$ tel que $x \notin A$. Il est **détachable** si pour tout élément $x$ de $S$ on a $x \in A$ ou $x \notin A$.

Étant donnés des ensembles $S_1, S_2, \dots, S_n$ nous définissons leur **produit cartésien** $S_1 \times S_2 \times \dots \times S_n$ comme l'ensemble des $n$-uplets $(x_1, x_2, \dots, x_n)$ où $x_i \in S_i$ pour chaque $i$. Deux tels $n$-uplets $(x_1, x_2, \dots, x_n)$ et $(y_1, y_2, \dots, y_n)$ sont égaux si $x_i = y_i$ pour chaque $i$. Les relations peuvent être identifiées avec les sous-ensembles de produits cartésiens : une relation binaire sur $S$ est un sous-ensemble de $S \times S$.

Si $A$ et $B$ sont des ensembles, alors une **fonction** de $A$ vers $B$ est une règle qui fait correspondre à tout élément $a$ de $A$ un élément $f(a)$ de $B$, et qui est **extensionnelle** en ce sens que $f(a_1) = f(a_2)$ chaque fois que $a_1 = a_2$. Nous écrivons $f: A \to B$ pour indiquer que $f$ est une fonction de $A$ vers $B$. Deux fonctions $f$ et $g$ de $A$ vers $B$ sont **égales** si $f(a) = g(a)$ pour chaque $a \in A$. La **fonction identité** $f: A \to A$ est définie en posant $f(a) = a$ pour chaque $a \in A$. Pour construire une fonction de $A$ vers $B$ il suffit de construire un sous-ensemble $S$ du produit cartésien $A \times B$ qui satisfait les propriétés

(i) pour chaque $a \in A$, il existe un $b \in B$ tel que $(a, b) \in S$,
(ii) si $(a, b_1)$ et $(a, b_2)$ sont des éléments de $S$, alors $b_1 = b_2$.

Dans l'interprétation calculatoire, l'algorithme pour la fonction provient de (i), qui spécifie la construction d'un élément $b$ dépendant du paramètre $a$. En l'absence de (ii), cependant, l'algorithme implicite dans (i) n'est pas nécessairement extensionnel. Le fait qu'un sous-ensemble $S$ de $A \times B$ qui satisfait (i) et (ii) détermine une fonction $f$ telle que $(a, f(a)) \in S$ pour chaque $a \in A$ est connu comme l'**axiome du choix unique**.

Considérons une fonction $f$ de $A$ vers $B$. Nous disons que $f$ est

**injective**<fnref n="1" /> si $a_1 = a_2$ chaque fois que $f(a_1) = f(a_2)$,

**surjective**<fnref n="2" /> si pour chaque $b \in B$ il existe un $a \in A$ tel que $f(a) = b$,

**fortement extensionnelle** si $a_1 \neq a_2$ chaque fois que $f(a_1) \neq f(a_2)$.

Notez que toute fonction entre deux ensembles munis de la non-égalité est fortement extensionnelle.

Si $S \subseteq A$, l'**image** de $S$ par $f$ est l'ensemble

$$f(S) = \{ b \in B : b = f(a) \text{ pour un } a \in A \}.$$

Ainsi $f$ est surjective si, et seulement si, $f(A) = B$. Si $S \subseteq B$, l'**image réciproque** de $S$ par $f$ est l'ensemble

$$f^{-1}(S) = \{ a \in A : f(a) \in S \}.$$

Deux ensembles **ont la même cardinalité** si l'on a des fonctions $f$ de $A$ vers $B$, et $g$ de $B$ vers $A$ telles que $fg$ est la fonction identité sur $B$ et $gf$ est la fonction identité sur $A$; nous disons que les fonctions $f$ et $g$ sont **inverses** l'une de l'autre, et que chacune est une **bijection**. Si $A$ et $B$ ont la même cardinalité, nous écrivons $#A = #B$. L'axiome du choix unique implique qu'une fonction qui est à la fois injective et surjective est une bijection (exercice 6). En mathématiques classiques on pense à des ensembles de même cardinalité simplement comme à des ensembles qui ont la même **taille**; d'un point de vue constructif il est plus exact d'y penser comme à des ensembles qui ont la même **structure**. Quand nous parlons de la **cardinalité** d'un ensemble nous entendons l'ensemble lui-même en ignorant toute structure autre que l'égalité qu'il pourrait avoir. La distinction entre parler d'un ensemble et parler de sa cardinalité est avant tout une question d'intention : quand nous parlons de sa cardinalité nous ne voulons prêter aucune attention à toutes caractéristiques de l'ensemble qui ne seraient pas partagées par tous les ensembles qui ont la même cardinalité. Par exemple si $x$ est un élément d'un groupe, alors l'ensemble $S = \{1, x, x^2, x^3, \dots\}$

<footnote n="1">1. **NdT.** One-to-one.</footnote>

<footnote n="2">2. **NdT.** Onto. Dans le livre anglais, «onto» est utilisé soit comme adjectif, dans le sens de «surjectif», soit comme préposition dans le sens usuel de «sur» : une fonction de $A$ sur $B$ est une fonction de $A$ vers $B$ qui est surjective.</footnote>
est le sous-monoïde engendré par $x$, tandis que la cardinalité de $S$ est l'ordre de $x$. C'est comme la distinction entre être une fraction et être un nombre rationnel. Une manière usuelle pour traiter ce genre de situation est d'introduire les classes d'équivalence mais, à la suite de Bishop (1967), nous préférons traiter directement avec la relation d'équivalence et ne pas introduire de nouvelles entités bien encombrantes.

Si un ensemble $A$ possède la même cardinalité que $\{1, \dots, n\}$ (est vide si $n=0$) pour un entier naturel $n$, alors nous disons que $A$ est un **ensemble à n éléments**, ou que $A$ est de cardinalité $n$, et nous écrivons $\#A = n$. Un ensemble **fini** $A$ est un ensemble discret qui a la cardinalité $n$ pour un entier naturel $n$. Rappelons qu'un ensemble discret doit être discret pour son inégalité spécifiée, s'il y en a une, de sorte qu'un ensemble peut avoir une cardinalité finie sans être fini ; de tels ensembles sont quelque peu pathologiques, ce qui est la raison pour laquelle nous préférons les nommer de manière plus longue.

Un ensemble $A$ est **finiment énumérable** s'il est vide ou s'il existe une fonction de $\{1, \dots, n\}$ sur $A$. Notez qu'un ensemble finiment énumérable est discret si, et seulement si, il est fini. Nous disons que **A possède au plus n éléments** si chaque fois que $a_0, \dots, a_n \in A$, il existe des éléments $0 \le i < j \le n$ tels que $a_i = a_j$. Un ensemble est **borné en nombre**, ou **borné**, s'il a au plus $n$ éléments pour un certain $n$. Un ensemble est **infini** s'il contient des sous-ensembles finis arbitrairement grands.

Un ensemble $A$ est **dénombrable**<fnref n="1" /> s'il existe une fonction depuis un sous-ensemble détachable de l'ensemble des entiers naturels sur $A$. Ainsi l'ensemble vide est dénombrable, de même que l'ensemble des nombres parfaits impairs. Les ensembles dénombrables non vides sont les images de fonctions définies sur l'ensemble des entiers strictement positifs, de sorte que leurs éléments peuvent être énumérés (éventuellement avec des répétitions) sous la forme $a_1, a_2, \dots$.

Une **suite d'éléments** d'un ensemble $A$, ou une **suite dans $A$**, est une fonction depuis l'ensemble des entiers naturels $\mathbb{N}$ vers $A$. Nous dirons également que les fonctions depuis les entiers strictement positifs sont des suites.

Une **famille d'éléments de $A$, indexée par un ensemble $I$, est une fonction $f$ de $I$ vers $A$**; l'image de $i$ dans $A$ par $f$ est habituellement notée $f_i$ plutôt que $f(i)$. Ainsi une suite est une famille indexée par les entiers naturels $\mathbb{N}$.

Une **famille finie d'éléments de $A$ est une famille d'éléments de $A$ indexée** par $\{1, \dots, n\}$ pour un entier strictement positif $n$.

Si $\{A_i\}_{i \in I}$ est une famille de sous-ensembles de $S$, alors sa **réunion** est définie par $\bigcup_{i \in I} A_i = \{x \in S : \text{il existe un } i \in I \text{ tel que } x \in A_i\}$, et son **intersection** est définie par $\bigcap_{i \in I} A_i = \{x \in S : x \in A_i \text{ pour tout } i \in I\}$.

Si $S$ est un ensemble muni d'une inégalité et si $X$ est un ensemble, alors l'ensemble $S^X$ des fonctions de $X$ vers $S$ hérite depuis $S$ de l'inégalité obtenue en posant $f \neq g$ s'il existe un $x \in X$ tel que $f(x) \neq g(x)$.

<footnote n="1">1. NdT. Countable.</footnote>
ensemble $S$ est détachable si, et seulement si, il possède une **fonction caractéristique**, c'est-à-dire une fonction $f$ de $S$ vers $\{0, 1\}$ telle que

$$A = \{ s \in S : f(s) = 1 \}.$$

6. Montrer qu'une fonction est une bijection si, et seulement si, elle est à la fois surjective et injective.

7. Montrer qu'un ensemble finiment énumérable discret est fini. Construire un exemple brouwerien d'un ensemble finiment énumérable, avec une relation de séparation étroite, qui n'est pas fini. Montrer qu'un ensemble finiment énumérable est borné en nombre. Construire un exemple brouwerien d'un ensemble borné en nombre mais qui n'est pas finiment énumérable.

8. Montrer qu'un ensemble non vide $A$ est dénombrable si, et seulement si, il existe une fonction de $N$ sur $A$. Montrer qu'un ensemble discret est dénombrable si, et seulement si, il a la même cardinalité qu'un sous-ensemble détachable de $N$.

9. Montrer qu'un sous-ensemble $A$ de $N$ est dénombrable si, et seulement si, il existe un sous-ensemble détachable $S$ de $N \times N$ tel que $A = \pi S$, où $\pi$ est la projection de $N \times N$ sur son premier facteur.

10. Montrer que l'ensemble des fonctions depuis un ensemble borné discret $A$ vers $\{0, 1\}$ n'est pas nécessairement discret. (Suggestion : soit $A$ l'image d'une suite binaire).

11. Montrer que si un ensemble $S$ est borné en nombre, alors toute fonction injective de $S$ vers $S$ est surjective.

12. Donner un exemple brouwerien d'un sous-ensemble $A$ de $N$ tel que $A$ ne peut pas être fini, et cependant $A$ n'est pas infini.

13. Soit $S$ un ensemble non vide muni d'une relation de séparation, et soit $n$ un entier strictement positif. Montrer que les propriétés suivantes sont équivalentes.

(i) Il existe des éléments $x_0, \dots, x_n$ de $S$ tels que $x_i \neq x_j$ pour $i \neq j$.

(ii) Étant donnés des éléments $y_1, \dots, y_n$ de $S$, il existe un $z \in S$ tel que $z \neq y_i$ pour $i = 1, \dots, n$.

14. On dit qu'un ensemble avec inégalité est **Dedekind-infini** lorsqu'il est isomorphe, en tant qu'ensemble avec inégalité, à un sous-ensemble propre de lui-même. Montrer qu'un ensemble Dedekind-infini satisfait la propriété (i) de l'exercice 13 pour chaque $n$.

15. On dit qu'un ensemble $S$ est **ω-borné** lorsque, pour chaque suite $\{s_i\}$ dans $S$, il existe un $m \neq n$ tel que $s_m = s_n$. Montrer que si $S$ est un
ensemble $\omega$-borné, si $\{s_i\}$ est une suite dans $S$ et si $m$ est un entier strictement positif, alors il existe un ensemble fini $I$ formé de $m$ entiers strictement positifs tel que $s_i = s_j$ pour $i$ et $j \in I$. Montrer que si $A$ et $B$ sont des ensembles $\omega$-bornés discrets, alors il en va de même pour l'ensemble $A \times B$.

## 3 L'axiome du choix

L'axiome du choix affirme l'existence d'une fonction qui possède une certaine propriété, en conséquence sa validité sera probablement plus douteuse en mathématiques constructives, où les fonctions doivent être interprétées comme des algorithmes. Nous formulons l'axiome du choix comme suit :

**Axiome du choix.** Soient $A$ et $B$ des ensembles, et $S$ un sous-ensemble de $A \times B$ tel que pour tout $a \in A$ on a un $b \in B$ tel que $(a,b) \in S$. Alors il existe une fonction $f: A \to B$ telle que $(a, f(a)) \in S$ pour chaque $a \in A$.

L'axiome du choix peut être critiqué de deux manières d'un point de vue calculatoire. La première objection concerne le fait que nous puissions trouver un algorithme $f$ (non nécessairement extensionnel) avec la propriété requise. Nous avons déjà rencontré ce problème avec l'axiome du choix unique, et nous avons adopté la position selon laquelle un algorithme est inhérent à l'interprétation de la phrase « pour tout $a \in A$ il existe un $b \in B$ ».

Une objection plus sérieuse est que même si nous pouvons trouver un algorithme $f$ nous ne pouvons sans doute pas trouver une fonction. En fait, nous pouvons construire un contre-exemple brouwerien pour l'axiome du choix.

**Exemple 3.1.** Soit $\alpha$ une suite binaire et soit $A = \{x, y\}$ muni de l'inégalité obtenue en posant $x = y$ si, et seulement si, il existe un $n$ tel que $\alpha_n = 1$, et enfin soit $B = \{0, 1\}$. Considérons le sous-ensemble $S = \{(x, 0), (y, 1)\}$ de $A \times B$. Supposons que $f: A \to B$ satisfasse $(a, f(a)) \in S$ pour chaque $a \in A$. Si $f(x) = f(y)$, alors $\alpha_n = 1$ pour un $n$ ; si $f(x) \neq f(y)$, alors $\alpha_n = 0$ pour tout $n$. ■

Il y a deux versions affaiblies de l'axiome du choix qui sont communément acceptées en mathématiques constructives. La plus faible est la suivante.

**Axiome du choix dénombrable.** Il s'agit de l'axiome du choix lorsque l'on prend pour $A$ l'ensemble $\mathbb{N}$ des entiers naturels.

Si $A$ est l'ensemble des entiers naturels, il n'y a pas de réelle distinction entre un algorithme et une fonction dans l'interprétation calculatoire car chaque entier naturel a une représentation canonique. En conséquence cet axiome résulte de l'interprétation de la phrase « pour tout $a \in A$ il existe un $b \in B$ » comme
signifiant l'existence d'un algorithme qui transforme tout élément de $A$ en un élément de $B$.

Une version plus forte que l'axiome du choix dénombrable est la suivante.

**Axiome du choix dépendant.** Soient $A$ un ensemble non vide et $R$ un sous-ensemble de $A \times A$ tels que pour chaque $a \in A$ on ait un élément $a' \in A$ avec $(a, a') \in R$. Alors il existe une suite $a_0, a_1, \dots$ d'éléments de $A$ telle que $(a_i, a_{i+1}) \in R$ pour chaque $i$.

L'axiome du choix dépendant implique l'axiome du choix dénombrable de la manière suivante. Supposons que $S$ est un sous-ensemble de $N \times B$ tel que pour chaque $n \in N$ on a un élément $b \in B$ tel que $(n, b) \in S$. Soit $A$ l'ensemble formé des suites finies $b_0, b_1, \dots, b_m$ dans $B$ telles que $(i, b_i) \in S$ pour tout $i$, et soit $R$ l'ensemble formé par tous les couples $(\alpha, \alpha')$ d'éléments de $A$ tels que, en supprimant le dernier élément de $\alpha'$, on obtienne $\alpha$. L'axiome du choix dépendant appliqué à $R$ fournit une suite dans $A$ dont les derniers éléments sont la suite requise dans $B$.

L'argument en faveur de l'axiome du choix dépendant est essentiellement le même que celui pour le choix dénombrable. Nous utiliserons librement ces deux axiomes, même si en général nous signalerons les moments où nous les utilisons.

Nous aurons l'occasion de nous référer à la forme suivante de l'axiome du choix pour laquelle nous n'avons pas de contre-exemple brouwerien, même si nous pensons que cette variante faible n'est pas démontrable dans le contexte des mathématiques constructives.

**Axiome du choix le plus simple du monde.** Soit $A$ un ensemble d'ensembles à deux éléments tel que si $a_1 \in A$ et $a_2 \in A$, alors $a_1 = a_2$. Alors il existe une fonction $f$ de $A$ vers $\{x : x \in a$ pour un $a \in A\}$ tel que $f(a) \in a$ pour chaque $a \in A$.

Exercices

1. Modifier l'exemple 3.1 de façon à montrer que l'axiome du choix implique la loi du tiers exclu.

2. Montrer que LLPO, avec l'axiome du choix dépendant, implique le lemme de Kőnig (voir l'exercice 1.7).

3. Montrer que l'axiome du choix implique l'axiome du choix le plus simple du monde.

4. Un ensemble $P$ est dit **projectif** lorsque chaque fois que l'on a deux applications $\pi: A \to B$ surjective et $f: P \to B$, il existe une application $g: P \to A$ telle que $\pi g = f$. Montrer que les ensembles finis sont projectifs. Montrer que les ensembles dénombrables discrets sont projectifs si, et seulement si, l'axiome du choix dénombrable est valide. Montrer que si les ensembles discrets sont projectifs, alors l'axiome du choix le plus simple du monde est valide.
# 4 Catégories

La collection des suites binaires forme un ensemble parce que nous savons ce que signifie pour deux suites binaires le fait d'être égales. Par ailleurs étant donnés deux groupes, ou deux ensembles, il est en général incorrect de demander s'ils sont égaux; la question pertinente est de savoir s'ils sont ou ne sont pas isomorphes, ou plus généralement quels sont les morphismes entre eux.

Une **catégorie** est une collection d'objets (comme l'est un ensemble). Une relation d'égalité sur un ensemble construit, pour deux objets $a$ et $b$ de cet ensemble, une proposition « $a = b$». Pour spécifier une catégorie $\mathcal{C}$, nous devons montrer comment construire, pour deux objets $A$ et $B$ de $\mathcal{C}$, un ensemble $\mathcal{C}(A, B)$. Dans les catégories concrètes, les objets de $\mathcal{C}$ sont des structures mathématiques d'un certain type, et l'ensemble $\mathcal{C}(A, B)$ est l'ensemble des applications de $A$ vers $B$ qui respectent cette structure : si $\mathcal{C}$ est la catégorie des ensembles, alors $\mathcal{C}(A, B)$ est l'ensemble des fonctions de $A$ vers $B$; si $\mathcal{C}$ est la catégorie des groupes, alors $\mathcal{C}(A, B)$ est l'ensemble des homomorphismes de $A$ vers $B$. De manière plus générale nous appellerons **flèche** ou **morphisme** un élément de l'ensemble $\mathcal{C}(A, B)$.

La notion de composition d'applications, présente dans ces situations con-
crètes, est abstraite sous la forme suivante dans les catégories plus générales :
chaque fois que nous avons trois objets $A, B$ et $C$ dans une catégorie $\mathcal{C}$, nous
devons avoir une fonction de $\mathcal{C}(A, B) \times \mathcal{C}(B, C)$ vers $\mathcal{C}(A, C)$, appelée **composition**
et notée par la juxtaposition, et nous devons avoir aussi un élément $1_B \in \mathcal{C}(B, B)$,
tels que si $f \in \mathcal{C}(C, D)$, $g \in \mathcal{C}(B, C)$ et $h \in \mathcal{C}(A, B)$, les propriétés suivantes
sont satisfaites.

$$
(i) \quad 1_B h = h \text{ et } g 1_B = g,
$$

$$
(ii) \quad (fg)h = f(gh).
$$

Tout ensemble $S$ peut être considéré comme une catégorie en posant

$$
S(a, b) = \{ x \in \{0\} : a = b \}.
$$

La réflexivité de l'égalité donne l'élément $1_B$, et la transitivité donne l'item (ii).

Les ensembles et fonctions introduites dans les sections précédentes consti-
tuent une catégorie : les **objets** de cette catégorie sont les ensembles et les **flèches**
sont les fonctions entre ensembles. Nous pouvons aussi considérer la catégorie
dont les objets sont les ensembles avec inégalité et dont les flèches sont les
fonctions fortement extensionnelles.

L'idée de la théorie des catégories est d'oublier la structure interne des objets
et de se concentrer sur la manière dont les flèches se combinent par composition.
Par exemple, une fonction $f$ de $A$ vers $B$ est injective si $a_1 = a_2$ chaque fois que
$f(a_1) = f(a_2)$. Cette définition s'appuie sur la structure interne des ensembles $A$
et $B$, c'est-à-dire sur les éléments de ces ensembles et les relations d'égalité sur
ces ensembles. La propriété catégorique qui correspond au fait qu'une fonction $f$ est injective est la suivante : si $g$ et $h$ sont des flèches depuis n'importe quel ensemble $C$ vers $A$ et si $fg = fh$, alors $g = h$ ; c'est-à-dire $f$ est **simplifiable à gauche** (on dit aussi **régulier à gauche**). Le fait qu'une fonction $f$ est injective si, et seulement si, elle est simplifiable à gauche, est une démonstration purement routinière.

Une fonction $f$ de $A$ vers $B$ est surjective si pour chaque $b \in B$ il existe un $a \in A$ tel que $f(a) = b$. La propriété catégorique correspondante est que $f$ est **simplifiable à droite**, c'est-à-dire que si $g$ et $h$ sont des flèches de $B$ vers n'importe quel ensemble $C$ et si $gf = hf$, alors $g = h$. Le fait qu'une fonction $f$ est surjective si, et seulement si, elle est simplifiable à droite, est une démonstration moins routinière que la démonstration du résultat correspondant pour les flèches simplifiables à la gauche.

**Théorème 4.1.** Une fonction est simplifiable à droite dans la catégorie des ensembles si, et seulement si, elle est surjective.

*Démonstration.* Supposons que $f: A \to B$ est surjective et que $gf = hf$. Pour tout $b \in B$ il existe un $a \in A$ tel que $f(a) = b$. Donc $g(b) = g(f(a)) = h(f(a)) = h(b)$, et $g = h$. Réciproquement supposons que $f: A \to B$ est simplifiable à droite, et soit $\Omega$ l'ensemble des sous-ensembles de $\{0\}$. Définissons $g: B \to \Omega$ par $g(b) = \{0\}$ pour tout $b$, et définissons $h: B \to \Omega$ par

$$h(b) = \{ x \in \{0\} : b = f(a) \text{ pour un } a \}.$$

Donc $h(b)$ est le sous-ensemble de $\{0\}$ tel que $0 \in h(b)$ si, et seulement si, il existe un $a$ tel que $b = f(a)$. Clairement $gf = hf$ est la fonction qui fait correspondre à tout élément de $A$ le sous-ensemble $\{0\}$. Donc $g = h$, et par suite $0 \in h(b)$, ce qui signifie que $b = f(a)$ pour un $a$. ■

Un **isomorphisme** entre deux objets $A$ et $B$ d'une catégorie $\mathcal{C}$ est un élément $f$ de $\mathcal{C}(A, B)$ tel qu'il existe un $g \in \mathcal{C}(B, A)$ pour lequel on a $fg = 1_B$ et $gf = 1_A$. La flèche $g$ est appelée l'**inverse** de $f$ ; on montre facilement que $g$ est unique. Une bijection entre ensembles est un isomorphisme dans la catégorie des ensembles. Nous disons que $A$ et $B$ sont **isomorphes**, et nous écrivons $A \simeq B$ s'il y a un isomorphisme entre $A$ et $B$.

Nous serons surtout intéressés par les catégories dont les objets sont les ensembles munis d'une structure algébrique, et dans lesquelles les flèches sont les fonctions qui préservent la structure algébrique. Dans ce cas les flèches sont appelées des **homomorphismes**. Si un homomorphisme est injectif, on l'appelle un **monomorphisme** ; s'il est surjectif on l'appelle un **épimorphisme**<fnref n="1" />.

<footnote n="1">1. **NdT.** Les épimorphismes au sens catégorique habituel sont les flèches simplifiables à droite. Dans la catégorie des anneaux commutatifs ils ne sont pas tous surjectifs. Le mot « épimorphisme » ici est donc pris dans un sens plus restreint, correspondant à une structure quotient dans les catégories données avec un foncteur d'oubli vers la catégorie des ensembles.</footnote>
Un homomorphisme d'un objet vers lui-même est appelé un **endomorphisme**, et un endomorphisme qui est un isomorphisme est appelé un **automorphisme**.

Un **foncteur** $T$ depuis une catégorie $\mathcal{A}$ vers une catégorie $\mathcal{B}$ est une règle qui fait correspondre à tout objet $A \in \mathcal{A}$ un objet $T(A) \in \mathcal{B}$, et qui à chaque flèche $f \in \mathcal{A}(A_1, A_2)$ fait correspondre une flèche $T(f) \in \mathcal{B}(T(A_1), T(A_2))$, telle que

(i) $T: \mathcal{A}(A_1, A_2) \to \mathcal{B}(T(A_1), T(A_2))$ est une fonction,

(ii) $T(fg) = T(f)T(g)$,

(iii) $T(1_A) = 1_{T(A)}$.

Un foncteur entre deux ensembles, lorsqu'on les considère comme des catégories, est simplement une fonction. Notons que si $f$ est un isomorphisme, alors il en va de même pour $T(f)$.

En utilisant la notion de foncteur nous pouvons étendre notre définition d'une famille d'éléments dans un ensemble à celle d'une famille d'objets dans une catégorie $\mathcal{C}$. Soit $I$ un ensemble. Une **famille** $\mathcal{A}$ d'**objets de C** **indexée par I** est un foncteur depuis $I$, vu comme une catégorie, vers la catégorie $\mathcal{C}$. Nous notons souvent une telle famille par $\{A_i\}_{i \in I}$. Si $i = j$, la flèche de $A_i$ vers $A_j$ est notée $A_i^j$, et c'est un isomorphisme.

Un élément de la **réunion disjointe** d'une famille d'ensembles $\{A_i\}_{i \in I}$ est un couple $(i, x)$ tel que $i \in I$ et $x \in A_i$. Deux éléments $(i, x)$ et $(j, y)$ de la réunion disjointe sont **égaux** si $i = j$ et $A_j^i(x) = y$. Nous identifions $A_i$ avec le sous-ensemble $\{(i, x) : x \in A_i\}$ de la réunion disjointe. Ainsi, une fois construite la réunion disjointe, nous pouvons considérer la famille $\{A_i\}_{i \in I}$ comme une famille d'éléments de l'ensemble des parties de la réunion disjointe.

Soit $\{A_i\}_{i \in I}$ une famille d'ensembles et soit $P$ un ensemble. Alors une fonction de $P$ vers $A_i$ peut être identifiée avec une fonction $f$ de $P$ vers la réunion disjointe de la famille $\{A_i\}_{i \in I}$ telle que $f(P) \subseteq A_i$. Notons $F$ l'ensemble des fonctions $f$ de $P$ vers la réunion disjointe des $\{A_i\}_{i \in I}$ telles que $f(P) \subseteq A_i$ pour un $i \in I$. Une **famille de fonctions** $\pi_i$ de $P$ vers les $A_i$ est par définition une famille $\pi$ d'éléments de $F$ telle que $\pi_i(P) \subseteq A_i$ pour chaque $i \in I$.

Soit $\{A_i\}_{i \in I}$ une famille d'objets dans une catégorie $\mathcal{C}$. Un **produit catégorique** de la famille $\{A_i\}$ est un objet $P$ avec une famille $\{\pi_i\}_{i \in I}$ de flèches (appelées projections) de $P$ vers $A_i$ telles que pour chaque objet $S$ et chaque famille de flèches $f_i$ de $S$ vers $A_i$, il existe une unique flèche $f$ de $S$ vers $P$ telle que $\pi_i f = f_i$ pour chaque $i \in I$. Un produit catégorique est unique à un isomorphisme près en ce sens que si $(P', \pi')$ en est un autre, alors il existe un (unique) isomorphisme $\theta$ de $P$ vers $P'$ tel que $\pi'_i \theta = \pi_i$ pour chaque $i$. Si $\mathcal{C}$ est la catégorie des ensembles, on vérifie facilement que l'ensemble de toutes les fonctions $\lambda$ de $I$ vers la réunion disjointe de la famille $\{A_i\}_{i \in I}$ telles que $\lambda(i) \in A_i$ pour chaque $i$, avec $\pi_i(\lambda)$ définie comme étant $\lambda(i)$, est un produit catégorique des $A_i$: nous le considérons comme le produit des $A_i$ et nous le notons $\prod_{i \in I} A_i$.
Si $I = \{1, \dots, n\}$, le produit des ensembles $A_i$ est le produit cartésien
$A_1 \times \dots \times A_n$. Si $A_i = S$ pour chaque $i \in I$, nous écrivons le produit, qui est
l'ensemble des fonctions de $I$ vers $S$, sous la forme $S^I$, ou $S^n$ si $I = \{1, \dots, n\}$.

Exercices

1. Montrer qu'une fonction $f$ est injective si, et seulement si, elle est simplifiable à gauche.

2. Montrer que le produit catégorique d'une famille d'objets dans une catégorie est unique à un isomorphisme près.

3. Montrer que, dans la catégorie des ensembles, l'ensemble de toutes les fonctions $\lambda$ de $I$ vers la réunion disjointe de la famille $\{A_i\}_{i \in I}$, telles que $\lambda(i) \in A_i$ pour chaque $i$, est un produit catégorique des $\{A_i\}_{i \in I}$.

4. Soit $I$ l'ensemble des suites binaires, et, pour chaque $i \in I$, soit $A_i = \{x \in \{0, 1\} : x \ge i_j \text{ pour tout } j\}$. Montrer que l'application naturelle de $\prod_i A_i$ vers $A_0$ est surjective si, et seulement si, WLPO est valide.

5. Considérons la catégorie des ensembles avec inégalité, avec pour flèches les fonctions fortement extensionnelles. Montrer que le produit $\prod_i A_i$ dans cette catégorie est le produit dans la catégorie des ensembles muni de l'inégalité définie par $\lambda \neq \mu$ s'il existe un $i$ tel que $\lambda(i) \neq \mu(i)$. Généraliser le théorème 2.2 dans ce contexte.

6. Soit $a$ un objet dans une catégorie $\mathcal{A}$. Montrer comment $T(b) = \mathcal{A}(a, b)$ est un foncteur de $\mathcal{A}$ vers la catégorie des ensembles. Un tel foncteur $T$ est appelé un foncteur **représentable**.

7. Si $\mathcal{C}$ est une catégorie, alors la **catégorie duale** $\mathcal{C}'$ est définie comme ayant les mêmes objets que $\mathcal{C}$, mais $\mathcal{C}'(a, b) = \mathcal{C}(b, a)$. Le **coproduit** d'une famille d'objets de $\mathcal{C}$ est le produit dans la catégorie duale $\mathcal{C}'$. Décrire de manière directe le coproduit. Quel est le coproduit dans la catégorie des ensembles ?

8. Limites directes. Un **système direct** est une suite d'objets $A_n$ et de flèches $f_n: A_n \to A_{n+1}$. Une borne supérieure d'un système direct est un objet $B$ avec des flèches $b_n: A_n \to B$ telles que $b_{n+1}f_n = b_n$ pour chaque $n$. Une **limite directe** d'un système direct est une borne supérieure $L$ telle que, pour n'importe quelle borne supérieure $B$, on a une unique flèche $\mu: L \to B$ telle que $\mu\ell_n = b_n$ pour chaque $n$.

(i) Montrer que deux limites directes sont isomorphes.

(ii) Montrer que la limite directe dans la catégorie des ensembles est la réunion disjointe des $A_n$ avec l'égalité engendrée par les égalités $a = f_n(a)$ pour chaque $a \in A_n$.
(iii) Montrer qu'une limite directe d'ensembles discrets n'est pas nécessairement un ensemble discret, mais qu'il est discret si toutes les fonctions sont injectives.

# 5 Ensembles ordonnés et treillis

Un **ensemble (partiellement) ordonné** est un ensemble $P$ muni d'une relation $a \le b$ telle que :

(i) $a \le a$,

(ii) si $a \le b$ et $b \le c$, alors $a \le c$,

(iii) si $a \le b$ et $b \le a$, alors $a = b$.

Un **morphisme** entre deux ensembles ordonnés $P_1$ et $P_2$ est une fonction $f$ de $P_1$ vers $P_2$ telle que si $a \le b$, alors $f(a) \le f(b)$. Nous serons la plupart du temps intéressés par les ensembles ordonnés discrets; dans ce cas nous écrirons $a < b$ pour $a \le b$ et $a \ne b$.

Soient $a, b$ et $c$ des éléments d'un ensemble ordonné $P$. Nous disons que $c$ est la **borne inférieure**, ou l'**infimum**, de $a$ et $b$, et nous écrivons $c = a \wedge b$, lorsque pour chaque $x \in L$ nous avons $x \le c$ si, et seulement si, $x \le a$ et $x \le b$. On voit facilement qu'un tel $c$ est unique, s'il existe. De même $c = a \vee b$ est la **borne supérieure**, ou le **supremum**, de $a$ et $b$ si pour chaque $x \in L$ nous avons $c \le x$ si, et seulement si, $a \le x$ et $b \le x$.

Un **treillis** est un ensemble ordonné dans lequel deux éléments arbitraires ont un infimum et un supremum. Si $S$ est un ensemble, alors l'ensemble de tous les sous-ensembles de $S$, ordonné par inclusion, forme un treillis : le supremum de $A$ et $B$ est $A \cup B$ et l'infimum est $A \cap B$. L'ensemble des entiers strictement positifs, ordonné en posant $a \le b$ si $b$ est un multiple de $a$, est un treillis : le supremum de $a$ et $b$ est leur plus petit commun multiple, l'infimum est leur plus grand commun diviseur. Notez que la relation $a \le b$ est décidable dans un treillis discret parce qu'elle est équivalente à $a \wedge b = a$.

Si un treillis admet un plus petit élément, alors nous notons cet élément $0$; s'il admet un plus grand élément, nous le notons $1$.

Un treillis est **distributif** lorsqu'il satisfait l'identité

$$a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c).$$

Le treillis des sous-ensembles d'un ensemble est distributif. Le treillis ci-dessous avec cinq éléments n'est pas distributif.

$$ \begin{array}{c|c|c} * & & * \\ / & \lambda & / \\ * & * & * \\ \lambda & & / \end{array} $$
Un treillis est **modulaire** si $a \lor (b \land c) = b \land (a \lor c)$ chaque fois que $a \le b$. On voit facilement qu'un treillis distributif est modulaire ; le treillis non distributif à cinq éléments décrit précédemment est modulaire. Si $G$ est un groupe abélien fini, alors l'ensemble de ses sous-groupes finis est un treillis modulaire, il est distributif seulement si $G$ est cyclique. Plus généralement l'ensemble des sous-modules d'un $R$-module forme un treillis modulaire. Le plus simple des treillis non modulaires est le treillis à cinq éléments décrit ci-dessous.

<figure><img src="image_5.png" /></figure>

Si $a \le b$ dans un ensemble ordonné $P$ alors nous utilisons la notation d'intervalle $[a, b]$ pour indiquer l'ensemble $\{x \in P : a \le x \le b\}$. Si $P$ est un treillis alors $[a, b]$ est un treillis avec les mêmes suprema et infima que dans $P$. Un fait essentiel à propos des treillis modulaires est que $[a \land d, d]$ et $[a, a \lor d]$ sont des treillis isomorphes, pour n'importe quels éléments $a$ et $d$. Nous démontrons ce fait sous une forme légèrement déguisée.

**Lemme 5.1.** Soient $a \le b$ et $c \le d$ des éléments d'un treillis modulaire $L$. Définissons

$$f(x) = a \lor (b \land x) = b \land (a \lor x)$$

$$g(y) = c \lor (d \land y) = d \land (c \lor y).$$

Alors la fonction $g$ envoie l'intervalle $[f(c), f(d)]$ isomorphiquement sur l'intervalle $[g(a), g(b)]$ avec $f$ pour fonction inverse.

**Démonstration.** Il suffit de démontrer que si $c \le x \le d$, alors $fgf(x) = f(x)$. Nous pouvons écrire $fgf(x)$ sous la forme

$$fgf(x) = b \land (a \lor c \lor (d \land b \land (a \lor x))) \quad (*)$$

ou encore sous la forme

$$fgf(x) = a \lor (b \land d \land (c \lor a \lor (b \land x))). \quad (**)$$

Pour montrer que $f(x) \le fgf(x)$, nous utilisons (*) et $f(x) = a \lor (b \land x)$. Pour montrer que $fgf(x) \le f(x)$, nous utilisons (**) et $f(x) = b \land (a \lor x)$. ■

En prenant $b = a \lor d$ et $c = a \land d$ dans le lemme 5.1 nous voyons que $[a \land d, d]$ et $[a, a \lor d]$ sont isomorphes.
Un sous-ensemble *C* d'un ensemble ordonné *P* est appelé une **chaine** si pour chaque *a* et *b* ∈ *C*, on a *a* ≤ *b* ou *b* ≤ *a* ; si *P* lui-même est une chaine, nous disons que *P* est **totalement ordonné**<fnref n="1" />. Une **chaine maximale** dans un ensemble ordonné est une chaine *C* telle que *C* ∪ {a} est une chaine seulement si *a* ∈ *C*. Le treillis non modulaire le plus simple défini précédemment contient deux chaines maximales finies, l'une de longueur 2 et l'autre de longueur 3. Pour les treillis modulaires ceci ne peut pas se produire. Nous disons que deux ensembles totalement ordonnés *C* et *D* sont **isomorphes par morceaux** s'il existe des éléments *c*₁, ..., *c*ₙ et *d*₁, ..., *d*ₙ tels que

(i) { x ∈ C : x ≤ c₁ } est isomorphe à { x ∈ D : x ≤ d₁ },

(ii) { x ∈ C : x ≥ c_n } est isomorphe à { x ∈ D : x ≥ d_n },

(iii) il existe une permutation $\sigma$ de $\{1, \dots, n-1\}$ telle que $[c_i, c_{i+1}]$ est isomorphe à $[d_{\sigma i}, d_{\sigma i+1}]$ pour chaque $i < n$.

Nous laissons la preuve que la relation d'isomorphisme par morceaux est transitive en exercice (n° 4). Si C et D sont des ensembles totalement ordonnés discrets isomorphes par morceaux, alors C et D ont la même cardinalité (exercice 5).

**Théorème 5.2** (Jordan-Hölder-Dedekind). *Si un treillis modulaire contient une chaine maximale finiment énumérable X, alors toute chaine finiment énumérable est contenue dans une chaine maximale finiment énumérable qui est isomorphe par morceaux à X.*

Démonstration. Soit $x_0 \le x_1 \le \dots \le x_m$ la chaine maximale $X$ ; nous dirons que $m$ est la **longueur formelle** de $X$. Soit $y_1 \le \dots \le y_n$ une chaine $Y$. Comme $X$ est maximale on voit tout de suite que $x_0 = 0$, $x_m = 1$ et $x_1 \wedge y_1 = 0$ ou $x_1$. Si $x_1 \wedge y_1 = x_1$, alors $Y$ est contenue dans le treillis $[x_1, 1]$. Par récurrence sur $m$, la chaine $Y$ est contenue dans une chaine maximale finiment énumérable de $[x_1, 1]$ qui est isomorphe par morceaux à $x_1 \le \dots \le x_m$, et par suite $Y$ est contenue dans une chaine maximale finiment énumérable isomorphe par morceaux à $X$. Si $x_1 \wedge y_1 = 0$ et nous sommes dans la situation suivante

<figure><img src="image_6.png" /></figure>

où $[y_1, x_1 \vee y_1]$ est isomorphe à $[0, x_1]$, et $[x_1, x_1 \vee y_1]$ est isomorphe à $[0, y_1]$. Par récurrence sur $m$ la chaine $x_1 \le x_1 \vee y_1$ est contenue dans une chaine finiment énumérable de $[x_1, 1]$, de longueur formelle $m-1$, formée d'une chaine maximale finiment énumérable $C$ de $[x_1, x_1 \vee y_1]$ de longueur formelle $\ell$, et d'une chaine

<footnote n="1">1. NdT. Linearly ordered.</footnote>
maximale finiment énumérable $D$ de $[x_1 \lor y_1, 1]$ de longueur formelle $m - \ell - 1$.
La chaine $\{y_1\} \cup D$ est une chaine maximale de $[y_1, 1]$ de longueur formelle au
plus $m - \ell$, de sorte que, par récurrence sur $m$, $Y$ est contenue dans une chaine
maximale de $[y_1, 1]$ isomorphe par morceaux à $\{y_1\} \cup D$. Le lemme 5.1 montre
que la chaine $C$ est isomorphe à une chaine maximale de $[0, y_1]$. Ainsi $Y$ est
contenue dans une chaine maximale isomorphe par morceaux à $X$. $\blacksquare$

Du théorème 5.2 on déduit que si un treillis modulaire discret contient une
chaine maximale finie de longueur $n$, alors toute chaine finie est contenue dans
une chaine maximale de longueur $n$.

On dit que l'ensemble ordonné $P$ satisfait la **condition de chaine ascendante** si pour chaque suite $p_1 \le p_2 \le p_3 \le \dots$ d'éléments de $P$, on a un $n$ tel que $p_n = p_{n+1}$; la **condition de chaine descendante** est définie de manière analogue. En mathématiques classiques, si $P$ satisfait la condition de chaine ascendante, nous pouvons trouver un $n$ tel que $p_m = p_n$ pour chaque $m \ge n$. D'un point de vue constructif, même l'ensemble à deux éléments $\{0, 1\}$ ne satisfait pas cette forme de la condition de chaine ascendante.

Nous disons qu'un élément $p$ d'un ensemble ordonné $P$ est de **profondeur** **au plus** $n$ si chaque fois que $p = p_0 \le p_1 \le p_2 \le \dots \le p_{n+1}$, alors $p_i = p_{i+1}$ pour un $i \le n$. Si $P$ est discret, nous disons que $p$ est de **profondeur au moins** $n$ s'il contient une chaine $p = p_0 < p_1 < \dots < p_n$. Un élément $a$ une **profondeur** **bornée** s'il a une profondeur au plus $n$ pour un certain $n$, il a une **profondeur finie** s'il a une profondeur au plus $n$, et au moins $n$, pour un certain $n$. Des définitions analogues sont obtenues en remplaçant **profondeur** par **hauteur**$^1$.

Exercices

1. Montrer qu'un treillis est discret si, et seulement si, la relation $a \le b$ est
décidable.

2. Montrer qu'un treillis est distributif si, et seulement si, il satisfait l'identité $a \lor (b \land c) = (a \lor b) \land (a \lor c)$.

3. Soit $L$ un treillis modulaire qui contient une chaine maximale finie (pour la non-égalité). Montrer que $L$ est discret.

4. Montrer que si deux ensembles totalement ordonnés sont isomorphes par morceaux à un troisième, alors ils sont isomorphes par morceaux entre eux.

5. Montrer que si deux ensembles totalement ordonnés discrets sont isomorphes par morceaux, ils ont la même cardinalité.

<footnote n="1">1. NdT. La hauteur est la profondeur pour l'ordre opposé.</footnote>
6. Deux intervalles $A$ et $B$ d'un treillis modulaire sont appelés **transposés** s'ils sont de la forme $[a, a \lor d]$ et $[a \land d, d]$ (ou vice versa), **projectifs**<fnref n="1" /> si l'on a une suite $A = I_1, \dots, I_n = B$ d'intervallestelle que $I_i$ et $I_{i+1}$ sont transposés pour $i = 1, \dots, n-1$. Montrer que deux chaines maximales finiment énumérées dans un treillis modulaire sont projectives par morceaux.

7. Montrer qu'un ensemble ordonné peut être considéré comme une catégorie $C$ dans laquelle l'ensemble des flèches $C(a, b)$ est égal à $\{x \in \{0\} : a \le b\}$. Quelle est la description catégorique de l'infimum de deux éléments ?

8. Supposons que chaque suite binaire $a_1 \le a_2 \le a_3 \le \dots$ nous puissions trouver un $m$ tel que $a_n = a_m$ chaque fois que $n \ge m$. En déduire que LPO est valide.

# 6 Ensembles bien fondés et ordinaux

Soit $W$ un ensemble muni d'une relation $a < b$. Un sous-ensemble $S$ de $W$ est dit **héréditaire** si $w \in S$ chaque fois que $w' \in S$ pour tout $w' < w$. L'ensemble $W$, ou la relation $a < b$, est dite **bien fondée** si tout sous-ensemble héréditaire de $W$ est égal à $W$. Un ensemble ordonné discret est dit bien fondé si la relation $a < b$ (i.e. $a \le b$ et $a \ne b$) est bien fondée. Un **ordinal**, ou **ensemble bien ordonné**, est un ensemble totalement ordonné discret et bien fondé.

Les ensembles bien ordonnés fournissent l'environnement pour les arguments par induction généraux. Le prototype d'un ensemble bien ordonné est l'ensemble des entiers naturels $\mathbb{N}$, avec la relation d'ordre usuelle.

## Théorème 6.1. L'ensemble des entiers naturels est bien fondé.

*Démonstration.* Soit $S$ un sous-ensemble héréditaire de $\mathbb{N}$. Alors $0 \in S$ parce que l'hypothèse $w' \in S$ pour chaque $w' < 0$ est évidemment valide (il n'y a aucun $w' < 0$). De $0 \in S$ nous déduisons $1 \in S$, de $0 \in S$ et $1 \in S$ nous déduisons $2 \in S$, etc. ■

L'ensemble des entiers naturels $\mathbb{N}$, vu comme un ordinal, est noté $\omega$. Nous observons tout d'abord que tout sous-ensemble d'un ensemble bien fondé est lui-même bien fondé. Plus généralement nous avons le théorème suivant.

## Théorème 6.2. Soient $P$ et $W$ des ensembles, chacun avec une relation $a < b$, et supposons que $W$ est bien fondé. Soit $\varphi$ une application de $P$ vers $W$ telle que $\varphi(a) < \varphi(b)$ chaque fois que $a < b$. Alors $P$ est bien fondé.

<footnote n="1">1. **NdT.** Je n'ai pas trouvé la terminologie française correspondant au « projective » de [CCA].</footnote>
**Démonstration.** Soit $S'$ un sous-ensemble héréditaire de $P$, et soit $S = \{ w \in W : \varphi^{-1}(w) \subseteq S' \}$. Nous allons montrer que $S$ est héréditaire, d'où $S = W$ et par suite $S' = P$. Supposons que $v \in S$ chaque fois que $v < w$. Si $x \in \varphi^{-1}(w)$ et $y < x$, alors $\varphi(y) < w$ de sorte que $\varphi(y) \in S$, et donc $y \in S'$. Comme $S'$ est héréditaire, cela implique que $x \in S'$ pour chaque $x \in \varphi^{-1}(w)$, d'où $w \in S$. Ainsi $S$ est héréditaire. ■

En particulier, tout sous-ensemble de $\omega$ est un ordinal. L'image d'une suite binaire fournit un exemple d'un ordinal pour lequel il peut être impossible de trouver un premier élément. Le théorème 6.2 implique que toute sous-relation d'une relation bien fondée est elle-même bien fondée.

Nous disons qu'une relation $x < y$ est **transitive** si $a < b$ et $b < c$ impliquent $a < c$. Un ensemble bien fondé ($S, <$) est **transitif** si la relation $x < y$ est transitive. Un exemple d'une relation bien fondée sur $\mathbb{N}$ qui n'est pas transitive est obtenu en définissant $a < b$ comme $a + 1 = b$. Cette relation est bien fondée d'après le théorème 6.2. Un argument d'induction par rapport à cette relation est la démonstration par récurrence telle qu'elle est ordinairement définie; un argument d'induction par rapport à la relation usuelle $a < b$ est parfois appelé une démonstration par induction complète, ou par récurrence complète.

Un ensemble bien fondé discret et transitif admet une relation d'ordre naturelle définie en posant $a \le b$ si $a < b$ ou $a = b$; la seule chose non triviale à vérifier est que $a = b$ si $a \le b$ et $b \le a$, cela résulte de ce que $a < a$ est impossible dans tout ensemble bien ordonné (exercice 1). Réciproquement la relation $a < b$ sur un ensemble ordonné discret est transitive.

On peut construire un ensemble bien fondé en additionnant des ensembles bien fondés déjà construits : on obtient l'ordinal $\omega + \omega$ en disposant deux copies des entiers naturels l'une après l'autre. Plus généralement, soit $I$ un ensemble bien fondé et soit $\{A_i\}_{i \in I}$ une famille d'ensembles bien fondés indexée par $I$. Alors la réunion disjointe $\sum_{i \in I} A_i = \{ (a, i) : a \in A_i \text{ et } i \in I \}$ peut être munie de la relation naturelle suivante :

$$ (a, i) < (b, j) \text{ si } i < j \text{ ou si } i = j \text{ et } a < b. $$

Si $I = \{1, \dots, n\}$, avec la relation d'ordre habituelle, nous écrivons $A_1 + \dots + A_n$. Notez que si $I$ et tous les $A_i$ sont discrets et transitifs (et totalement ordonnés), alors il en va de même pour $\sum_{i \in I} A_i$.

**Théorème 6.3.** Si $I$ est un ensemble bien fondé et si $\{A_i\}_{i \in I}$ est une famille d'ensembles bien fondés indexée par $I$, alors $W = \sum_{i \in I} A_i$ est un ensemble bien fondé.

**Démonstration.** Soit $S$ un sous-ensemble héréditaire de $W$. Pour chaque $i \in I$, nous posons $A'_i = \{ a \in A_i : (a, i) \in S \}$ et $I' = \{ i \in I : A'_i = A_i \}$. Nous allons montrer que $I'$ est héréditaire, d'où $I' = I$, i.e. $S = W$. Supposons que
$i' \in I'$ pour chaque $i' < i$. Nous établissons $A_i' = A_i$ en démontrant que $A_i'$ est héréditaire. Supposons que $a' \in A_i'$ pour chaque $a' < a$. Alors $w' \in S$ pour chaque $w' < (a, i)$, d'où $(a, i) \in S$ et donc $a \in A_i'$. Par suite $A_i' = A_i$ car $A_i$ est bien fondé, et donc $i \in I'$. ■

Soit $\{A_i\}_{i \in I}$ une famille d'ensembles bien fondés indexée par un ensemble discret $I$. Nous disons qu'un élément $f$ de $\prod_{i \in I} A_i$ a un **support fini** si l'on a un sous-ensemble fini $J$ de $I$ tel que pour tout $i \in I$, ou bien $1$ $i \in J$, ou bien $a < f_i$ est impossible pour $a \in A_i$ (c'est-à-dire que $f_i$ est un élément minimal de $A_i$). Notez que si $I$ est fini, alors tout élément de $\prod_{i \in I} A_i$ a un support fini, tandis que si un élément a un support fini, alors tous les $A_i$ ont des éléments minimaux, à l'exception d'un nombre fini d'entre eux. Si $I$ est un ensemble bien fondé, alors les éléments à support fini de l'ensemble produit $\prod_{i \in I} A_i$ sont munis d'une relation de **dernière différence** définie comme suit : $f < g$ si

(i) il existe un $i \in I$ tel que $f_i < g_i$, et

(ii) pour chaque $i \in I$, ou bien $f_i = g_i$, ou bien $f_j < g_j$ pour un $j \ge i$.

Si $I$ et tous les $A_i$ sont des ordinaux, cette relation peut être décrite en disant que deux éléments distincts doivent être ordonnés selon la dernière place où ils diffèrent (ordre lexicographique inverse).

**Théorème 6.4.** Soit $I$ un ordinal, et soit $\{A_i\}_{i \in I}$ une famille d'ensembles bien fondés indexée par $I$. Alors l'ensemble des éléments à support fini dans $\prod_{i \in I} A_i$ est bien fondé pour la relation de dernière différence.

*Démonstration.* Nous commençons par remarquer que le théorème est vrai lorsque $I = \{1, 2\}$; dans ce cas $F = A_1 \times A_2 = \sum_{b \in B} A(b)$ où $B = A_2$ et $A(b) = A_1$ pour tout $b \in B$. Ainsi d'après le théorème 6.3 le produit $A_1 \times A_2$ est bien fondé pour la relation de dernière différence si $A_1$ et $A_2$ sont bien fondés. En ajoutant un plus grand élément $\infty$ à l'ensemble ordonné $I$ et en posant $A_\infty = \{0\}$ on ne change rien, et nous pouvons donc supposer que $I$ a un plus grand élément $\infty$. Soit $F_i$ l'ensemble des éléments à support fini dans $\prod_{j \le i} A_j$ et soit $I' = \{i \in I : F_i$ est bien fondé$\}$. Nous allons montrer que le sous-ensemble $I'$ est héréditaire, donc égal à $I$, et par suite $F = F_\infty$ est bien fondé.

Supposons que $k \in I'$ pour chaque $k < i$. Soit $F_i^*$ l'ensemble des éléments à support fini dans $\prod_{j<i} A_j$. Alors $F_i = F_i^* \times A_i$, donc $F_i$ est bien fondé si $F_i^*$ est bien fondé. Écrivons $F_i^* = \bigcup_{k<i} G_k$ où $G_k$ est l'ensemble des éléments de $\prod_{j<i} A_j$ avec un support fini $J$ tel que $j \le k$ pour tout $j \in J$. La projection de $G_k$ sur $F_k$ préserve la relation $x < y$, de sorte que $G_k$ est bien fondé en vertu

<footnote n="1">1. **NdT.** Quand nous raisonnons constructivement, nous utilisons l'expression «ou bien..., ou bien...» avec le sens du «ou» constructif, mais pas exclusif. Cela signifie donc simplement que «l'une des deux alternatives présentées est certifiée par un algorithme». Cela facilite beaucoup la rédaction.</footnote>
du théorème 6.2. Si $S$ est un sous-ensemble héréditaire de $F_i^*$, alors $S \cap G_k$ est un sous-ensemble héréditaire de $G_k$ pour chaque $k < i$, et donc $F_i^* = S$. Ainsi $F_i^*$, et par suite $F_i$, est bien fondé, d'où $i \in I$. ■

Si $I$ est un ensemble arbitraire et si $A_i$ est un ensemble ordonné pour $i \in I$, le **produit catégorique** des $A_i$ est l'ensemble $\prod_i A_i$ muni de la relation d'ordre suivante :

$$f \le g \text{ si } f_i \le g_i \text{ pour tout } i \in I.$$

Si $I = \{1, \dots, n\}$ et si chaque $A_i$ est discret et bien fondé, alors l'application identique du produit catégorique vers le produit muni de la relation de derrière différence préserve l'ordre (mais pas le non-ordre), par suite le produit catégorique est bien fondé d'après le théorème 6.2.

Si $\alpha$ est un ordinal et si $\beta$ est un ensemble bien fondé, alors l'ensemble bien fondé des fonctions à support fini de $\alpha$ vers $\beta$ sera noté $\beta\alpha$.

Pour des ordinaux $\lambda$ et $\mu$ on définit un **plongement** de $\lambda$ dans $\mu$ comme une fonction $\rho$ de $\lambda$ vers $\mu$ telle que si $a < b$ alors $\rho a < \rho b$, et si $c < \rho b$, alors on a un $a \in \lambda$ tel que $\rho a = c$. Nous allons montrer qu'il y a au plus un plongement de $\lambda$ vers $\mu$.

**Théorème 6.5.** Si $\lambda$ et $\mu$ sont des ordinaux et si $\rho$ et $\sigma$ sont des plongements de $\lambda$ dans $\mu$, alors $\rho = \sigma$.

*Démonstration.* Soit $S = \{ a \in \lambda : \rho a = \sigma a \}$, et supposons que $a \in S$ pour tout $a < b$. Si $\sigma b < \rho b$, alors on a un $a \in \lambda$ tel que $\rho a = \sigma b < \rho b$, donc $a < b$, d'où $\rho a = \sigma a$; mais $\rho a = \sigma b > \sigma a$, une contradiction. De la même manière, nous ne pouvons avoir $\rho b < \sigma b$. Par suite $\rho b = \sigma b$, et donc $b \in S$; ainsi $S$ est héréditaire, et $S = \lambda$. ■

Lorsque l'on a un plongement de l'ordinal $\lambda$ dans l'ordinal $\mu$, nous écrivons $\lambda \le \mu$. Clairement, une composition de plongements est un plongement, donc cette relation est transitive. Le théorème 6.5 implique que si $\lambda \le \mu$ et $\mu \le \lambda$, alors $\lambda$ et $\mu$ sont isomorphes, i.e. il y a une bijection de $\lambda$ vers $\mu$ qui préserve et réfléchit l'ordre. Il est naturel de dire que deux ordinaux isomorphes sont égaux.

Exercices

1. Montrer que $a < a$ est impossible dans un ensemble bien fondé.

2. Si $a < b$ est une relation sur un ensemble $W$, on définit la clôture transitive $a <^* b$ de cette relation par : $a < b$ ou il existe $x_1, \dots, x_n$ tels que $a < x_1 < x_2 < \dots < x_n < b$. Montrer que $a <^* b$ est bien fondée si $a < b$ est bien fondée (mimer la démonstration que la récurrence ordinaire sur $\mathbb{N}$ implique l'induction complète sur $\mathbb{N}$).
3. Une relation $a < b$ est **acyclique** si $a <^* a$ est impossible pour n'importe quel $a$ (voir l'exercice 2). Montrer qu'une relation acyclique sur un ensemble à deux éléments est bien fondée. Montrer qu'une relation acyclique sur un ensemble borné en nombre est bien fondée.

4. Montrer qu'un ensemble ordonné discret bien fondé satisfait la condition de chaine descendante.

5. Soit $W$ un ensemble bien fondé. Soit $S$ un sous-ensemble de $W$ tel que, pour tout $w \in W$, ou bien $w \in S$, ou bien il existe un $w' < w$ tel que $w \in S$ si $w' \in S$. Montrer que $S = W$.

6. Montrer qu'un ensemble ordonné discret qui satisfait l'exercice 5 pour chaque sous-ensemble $W$ satisfait la condition de chaine descendante.

7. Montrer la réciproque de l'exercice 6 (cela utilise l'axiome du choix dépendant).

8. Soit $W$ l'ensemble des entiers naturels avec la relation $a < b$ définie par : $a \le b$ et $b - a$ est impair. Montrer que cette relation $a < b$ est bien fondée mais n'est pas transitive.

9. Montrer que le produit catégorique d'ensembles ordonnés tel qu'il est défini dans la section précédente est effectivement un produit catégorique dans la catégorie des ensembles ordonnés (avec pour flèches les morphismes d'ensembles ordonnés).

10. Montrer que si tout ordinal non vide possède un plus petit élément, alors LPO est valide.

11. Une **relation de rang** sur un ensemble ordonné discret $W$ est un ordinal $A$ avec un sous-ensemble $R$ de $W \times A$ qui satisfait les propriétés suivantes :

(i) pour chaque $w \in W$ il y a un $a \in A$ tel que $(w, a) \in R$,

(ii) si $v < w$ et $(w, a) \in R$, alors on a un $b < a$ tel que $(v, b) \in R$.

Démontrer le théorème 6.4 pour un ensemble ordonné discret bien fondé avec une relation de rang.

12. Un **ordinal de Grayson** est un ensemble $W$ muni d'une relation bien fondée $a < b$ qui satisfait les propriétés suivantes :

(i) si $a < b$ et $b < c$, alors $a < c$ (transitivité),

(ii) si $c < a$ est équivalent à $c < b$ pour tout $c$, alors $a = b$ (extensionnalité).

Définissons $a \le b$ sur un ordinal de Grayson comme signifiant que $c < a$ implique $c < b$ pour tout $c$. Montrer que lorsque la relation $a < b$ est décidable, alors $W$ est un ordinal de Grayson si, et seulement si, $W$ est un ordinal. (Suggestion : démontrer que $a < b$ ou $a = b$ ou $b < a$ dans un ordinal de Grayson décidable).
13. Soit $\alpha$ une suite binaire, et soit $S = \{x, y, z\}$ avec $x = y$ si $\alpha$ est identiquement nulle. On définit une relation $u < v$ sur $S$ en posant

(i) $y < z$

(ii) $x < y$ si $\alpha_n = 1$ pour un $n$

(iii) $x < z$ si $x = y$ ou $x < y$.

Montrer que cela fait de $S$ un exemple brouwerien pour un ordinal de Grayson avec des éléments tels que $x \le y < z$ sans que l'on ait $x < z$.

# 7 Notes

Bishop (1967, page 8) définit quand on peut considérer qu’un objet existe. L’idée selon laquelle la notion d’algorithme est une notion primitive a aussi été avancée par les mathématiciens russes Uspenskii et Semenov (1981) :

> “Le concept d’algorithme comme celui d’ensemble ou de nombre naturel est un concept si fondamental qu’il ne peut pas être expliqué à travers d’autres concepts et qu’il devrait être regardé comme impossible à définir.”

Les tentatives d’expliquer l’existence constructive en termes classiques sont toujours en quelque sorte peu satisfaisantes, mais la notion classique d’existence n’est pas moins mystérieuse que la notion constructive, nous sommes simplement plus familiers avec la notion classique. Quelle est la signification qu’il existe un bon ordre sur les nombres réels ? ou une base des réels comme espace vectoriel sur les rationnels ? ou un automorphisme des nombres complexes qui envoie $e$ sur $\pi$ ? ou une fonction qui ne soit pas calculable ? Des systèmes formels qui spécifient l’usage correct du « il existe » sont disponibles pour le mathématicien constructif aussi bien que pour son alter ego classique.

Notre définition d’un **ensemble** est une combinaison des formulations que l’on trouve dans [Bridges 1979, page 2] et [Heyting 1971, 3.2.1]. Beaucoup d’auteurs utilisent le terme positif **habité** pour décrire les ensembles non vides ; cela évite la confusion avec la notion d’un ensemble qui ne peut pas être vide. La notion de **relation de séparation**<fnref n="1" /> (étroite) se trouve dans [Heyting 1971, 4.1.1]. La terminologie « étroite » est due à Scott (1979). Troelstra et van Dalen utilisent le terme « pre-apartness » pour désigner ce que nous appelons une relation de séparation. La partie du théorème 2.2 qui affirme que si une inégalité sur $S$ est étroite alors il en va de même pour l’inégalité sur $S^N$, est essentiellement donnée par [Bishop 1967, Lemma 5, page 24], qui dit que l’inégalité naturelle sur les nombres réels est étroite.

Une inégalité standard sur l’ensemble $\{0\}$ est obtenue en posant $0 \neq 0$ si LPO est faux. Comme LPO est réfutable dans deux branches principales des

<footnote n="1">1. NdT. Apartness.</footnote>
mathématiques constructives – l'intuitionnisme et le constructivisme russe – nous ne pouvons pas démontrer que cette inégalité est consistante. Pour plus d'informations sur l'intuitionnisme et le constructivisme russe du point de vue des mathématiques constructives, veuillez consulter [Bridges-Richman 1987].

Les relations de différence<fnref n="1" /> sont des relations d'inégalité symétriques qui satisfont l'implication

$$ \neg x \neq y \text{ et } \neg y \neq z \text{ implique } \neg x \neq z. $$

Elles sont étudiées par van Rootselaar (1960) et par Olson (1977).

Nous pourrions demander que tout ensemble arrive avec une inégalité, en mettant l'inégalité et l'égalité sur le même plan; ce serait alors naturel de demander que toutes les fonctions soient fortement extensionnelles. Avec une telle approche, chaque fois que nous construisons un ensemble, nous devons le munir d'une inégalité, et nous devons vérifier que nos fonctions sont fortement extensionnelles. Ceci est encombrant et facile à oublier, d'où résulteront des constructions incomplètes et des démonstrations incorrectes. Voici un exemple de ces complications : si $H$ est un sous-groupe d'un groupe abélien $G$, alors l'inégalité sur $G/H$ en tant que groupe peut différer de l'inégalité sur $G/H$ en tant qu'ensemble parce que la loi de groupe sur $G/H$ n'est pas nécessairement extensionnelle par rapport à cette dernière (à moins que l'inégalité sur $G$ soit décidable) – voir l'exercice II.1.6.

Notre définition d'un **sous-ensemble** est en accord avec le traitement informel donné dans [Bishop 1967, page 32]. Une définition catégorique d'un **sous-ensemble** se trouve dans [Bishop 1967, page 63] où un sous-ensemble d'un ensemble $S$ est défini comme donné par un ensemble $A$ et par une application injective de $A$ vers $S$. La définition catégorique est attrayante pour les mathématiques constructives, dans lesquelles il est important de garder à l'esprit qu'un élément d'un sous-ensemble, du fait même qu'il appartient au sous-ensemble, comporte implicitement l'information additionnelle qui établit son appartenance au sous-ensemble. L'approche catégorique nous permet de rendre cette information additionnelle explicite. Par exemple, si $S$ est l'ensemble des suites binaires, et si $A$ est l'ensemble des suites $\alpha$ telles que $\alpha_m = 1$ pour un certain $m$, alors pour spécifier un élément de $A$, nous ne devons pas seulement construire une suite dans $S$, mais également un entier $m$ pour lequel $\alpha_m = 1$. Ainsi un élément de $A$ peut être vu comme un couple $(\alpha, m)$, deux couples $(\alpha, m)$ et $(\alpha', m')$ étant égaux si $\alpha = \alpha'$. L'application de $A$ vers $S$ qui envoie $(\alpha, m)$ sur $\alpha$ est injective mais n'est pas réellement une inclusion puisqu'elle oublie la donnée additionnelle $m$. Nous trouvons l'approche informelle plus naturelle.

L'**axiome du choix unique** nous permet d'identifier une fonction avec son graphe; Myhill l'a appelé l'**axiome du non-choix**. On voit facilement que cet

<footnote n="1">1. NdT. Difference relation.</footnote>
axiome du choix unique est équivalent à l'une quelconque des deux propriétés suivantes.

(i) Toute fonction bijective admet une inverse.

(ii) Si $S$ est un ensemble et si $S^*$ est l'ensemble des sous-ensembles à un élément de $S$, alors $S^*$ possède une fonction de choix : c'est-à-dire une fonction $f$ de $S^*$ vers $S$ telle que $f(x) \in x$ pour chaque $x \in S^*$.

Bishop utilise la notion de fonction non extensionnelle ou **opération**. Dans presque tous les cas où cette notion est utilisée, on peut considérer une opération de l'ensemble $A$ vers un ensemble $B$ comme une fonction de $A$ vers l'ensemble des parties non vides de $B$.

Notre définition d'un ensemble **fini** diffère de celles de [Bishop 1967], [Bridges 1979] et [Bishop-Bridges 1985] en ce que nous considérons qu'un ensemble vide est fini. Une autre différence plus subtile est que nous demandons que les ensembles finis soient discrets par rapport à leur propre inégalité. Ainsi un ensemble $S$ de fonctions entre deux ensembles discrets est fini seulement si pour chaque $f$ et $g \in S$, ou bien $f = g$, ou bien il existe un $x$ tel que $f(x) \neq g(x)$.

Les fonctions que nous appelons **onto**<fnref n="1" /> sont appelées **surjectives** dans [Bishop 1967] où le mot **onto** est réservé pour une application $f$ de $A$ vers $B$ qui admet une section, c'est-à-dire pour laquelle il existe une fonction $g$ de $B$ vers $A$ telle que $fg$ est l'application identique sur $B$.

Dans [Bishop 1967] un ensemble finiment énumérable est appelé **sous-fini**<fnref n="2" />, et un ensemble est réputé avoir **au plus n éléments** s'il peut être écrit sous la forme $\{x_1, \dots, x_n\}$. Le terme «sous-fini» suggère pour nous un sous-ensemble d'un ensemble fini, tandis que l'utilisation du «au plus» dans [Bishop 1967] exclut que l'on puisse dire que tout sous-ensemble de $\{1, \dots, n\}$ contienne au plus $n$ éléments.

Greenleaf (1981) examine du point de vue constructif la question de la cardinalité des ensembles, ainsi que certaines questions reliées à cette notion.

Notre définition d'ensemble **dénombrable**<fnref n="3" /> diffère de celles de [Bishop 1967], [Bridges 1979] et [Bishop-Bridges 1985] en ce que nous ne demandons pas qu'un ensemble dénombrable soit non vide (ou même que nous puissions décider s'il est vide ou pas) ; dans le cas des ensembles discrets notre définition est équivalente à celle de [Brouwer 1981].

Il semble improbable que nous soyons capables de construire un exemple brouwerien pour un sous-ensemble de $\mathbb{N}$ qui ne serait pas dénombrable. Néanmoins toute démonstration acceptable du théorème $T$ selon lequel toute partie de $\mathbb{N}$ est dénombrable pourrait sans doute être transformée en une preuve que

<footnote n="1">1. **NdT.** Nous traduisons l'expression «map onto» de [CCA] par «fonction surjective», autrement dit nous utilisons la terminologie de Bishop. Bishop utilise quant à lui «map onto» avec une signification constructivement plus forte.</footnote>

<footnote n="2">2. **NdT.** Subfinite.</footnote>

<footnote n="3">3. **NdT.** Countable.</footnote>
toute partie de $\mathbb{N}$ est récursivement énumérable, ce qui est faux. Une variante
bien connue de $T$ est le **schéma de Kripke**, selon lequel pour toute proposition $P$
il existe une suite binaire $\alpha$ telle que $P$ est valide si, et seulement si, $\alpha_n = 1$
pour un certain $n$. Le schéma de Kripke a une certaine plausibilité dans le
cadre de la théorie du sujet créatif de Brouwer, dans laquelle nous imaginons le
mathématicien idéalisé en train d'effectuer une suite qui n'est pas prédétermi-
née de tentatives de démontrer $P$, et lorsque nous gardons à l'esprit le critère
intuitionniste selon lequel démontrer $\neg P$ revient à transformer toute preuve
de $P$ en une contradiction.

Bishop utilise *non* ou *ne pas* en italique pour indiquer l'existence d'un
contre-exemple brouwerien. Par exemple nous dirions «il existe une inégalité
qui *n*'est *pas* une relation de séparation» pour signifier que «si toute inégalité
était une relation de séparation alors LPO serait valide». Nous *n*'utiliserons *pas*
cette convention.

Le mini principe d'omniscience (LLPO) a été introduit dans [Bishop 1973].
Aussi bien LPO que LLPO ont des interprétations simples en termes de nombres
réels : LPO est équivalent à l'affirmation selon laquelle tout nombre réel $x$
est $\le 0$ ou $> 0$; LLPO est équivalent à l'affirmation selon laquelle tout nombre
réel $x$ est $\le 0$ ou $\ge 0$.

Le principe de Markov affirme que si $\alpha$ est une suite binaire, et si $\alpha_n = 0$
pour tout $n$ est impossible, alors il existe un $n$ tel que $\alpha_n = 1$. L'idée est que
nous pouvons construire le nombre $n$ en calculant successivement $\alpha_1, \alpha_2, \alpha_3, $
... jusqu'à ce que nous obtenions un 1. Le principe de Markov est utilisé par l'école
constructive russe, qui est une forme constructive des mathématiques récursives ;
pour plus de détails voir [Bridges-Richman 1987]. Un argument contre le principe
de Markov est que nous n'avons aucune borne à priori, dans quelque sens que
ce soit, sur la longueur du calcul qui est demandé pour construire $n$. Nous
regardons le principe de Markov comme un principe d'omniscience.

Le point de vue selon lequel l'affirmation «pour tout $a \in A$ il existe un
$b \in B$» implique l'existence d'un algorithme (non nécessairement extensionnel)
de $A$ vers $B$ est suggéré par l'affirmation dans [Bishop 1967, page 9] que «le
fait qu'une fonction $f$ de $B$ vers $A$ est surjective par l'existence d'un algorithme $g$
de $A$ vers $B$ tel que $f(g(a)) = a$ pour tout $a \in A$.

Notre contre-exemple brouwerien de l'axiome du choix, ainsi que l'exercice 3.1
selon lequel l'axiome du choix implique la loi du tiers exclu, est dû à Myhill et
Goodman (1978). Une démonstration qui a précédé, dans le cadre de la théorie
des topos, a été donnée par Diaconescu (1975), qui démontre que l'axiome
du choix implique que tout sous-ensemble $A$ d'un ensemble $B$ possède un
**complémentaire** en ce sens qu'il existe un sous-ensemble $A'$ tel que $B = A \cup A'$
et $A \cap A' = \emptyset$.
Fourman et Scedrov (1982) ont démontré en utilisant des méthodes de la théorie des topos que l'**axiome du choix le plus simple du monde** n'est pas démontrable dans la théorie des ensembles intuitionniste avec choix dépendant.

Les arguments contre l'axiome du choix dénombrable et l'axiome du choix dépendant doivent s'appuyer sur un socle plus fondamental que celui que nous avons utilisé contre l'axiome du choix. En fait, nous devons questionner l'interprétation de la phrase «pour tout a il existe un b» selon laquelle elle implique l'existence d'un algorithme qui transforme les éléments de A en des éléments de B. Une raison de rejeter cette interprétation est que ce faisant nos théorèmes seront aussi des théorèmes dans d'autres modèles (inattendus) qui apparaissent dans la théorie des topos, et qui possèdent un intérêt en mathématiques classiques (voir par exemple [Scedrov 1986]). Une autre raison, plus pertinente peut-être, est que des arguments qui s'appuient de manière essentielle sur cette interprétation nous laissent un sentiment d'insatisfaction concernant une «complétion à l'infini» un peu arbitraire quand, en présence d'une infinité potentielle d'items d'information, nous les réunissons tous en un seul algorithme.

Une **fonction de rang**<fnref n="1" /> sur un ensemble bien fondé W est une application $\varphi$ de W vers un ordinal A tel que $\varphi(x) < \varphi(y)$ chaque fois que $x < y$. Il semble improbable que nous puissions toujours construire une telle fonction de rang même si en mathématiques classiques tout ensemble bien fondé possède une unique fonction de rang minimale. L'induction sur le rang est une technique usuelle dans la théorie classique (voir l'exercice 6.11).

<footnote n="1">1. NdT. Rank function.</footnote>
<figure><img src="image_7.png" /></figure>
# II. Algèbre de base

## Sommaire

<table><tr><td>1</td><td>Groupes</td><td>35</td></tr><tr><td>2</td><td>Anneaux et corps</td><td>41</td></tr><tr><td>3</td><td>Les nombres réels</td><td>48</td></tr><tr><td>4</td><td>Modules</td><td>51</td></tr><tr><td>5</td><td>Anneaux de polynômes</td><td>59</td></tr><tr><td>6</td><td>Matrices et espaces vectoriels</td><td>64</td></tr><tr><td>7</td><td>Déterminants</td><td>68</td></tr><tr><td>8</td><td>Polynômes symétriques</td><td>72</td></tr><tr><td>9</td><td>Notes</td><td>75</td></tr></table>

## 1 Groupes

Un **monoïde** est un ensemble $G$ avec une application (ou loi de composition) $\varphi$ de $G \times G$ vers $G$, habituellement écrite sous la forme $\varphi(a, b) = ab$, et un élément spécifié de $G$, habituellement noté $1$, tel que pour tous $a, b, c \in G$

(i) $(ab)c = a(bc)$ (associativité),

(ii) $1a = a1 = a$ (élément neutre).

L'application $\varphi$ est appelée la **multiplication** et l'élément $1$ le **neutre**. L'associativité de la multiplication nous permet d'ignorer les parenthèses dans les produits $a_1 a_2 \cdots a_n$. Le monoïde est dit **abélien**, ou **commutatif**, lorsque $ab = ba$ pour tous éléments $a$ et $b$. Dans un monoïde abélien, la loi $\varphi$ est souvent appelée **addition** et écrite sous la forme $\varphi(a, b) = a + b$; l'élément neutre est alors noté $0$. Dans ce cas nous parlons d'un monoïde **additif**, en opposition à un monoïde **multiplicatif**. Dans un monoïde multiplicatif, nous écrivons le produit itéré $n$ fois $aa \cdots a$ sous la forme $a^n$ pour chaque entier strictement positif $n$, et nous posons $a^0 = 1$; dans un monoïde additif, nous écrivons la somme itérée $n$ fois $a + a + \cdots + a$ sous la forme $na$ et nous écrivons $0a = 0$.
Si $X$ est un ensemble, l'ensemble des fonctions de $X$ vers $X$ forme un monoïde : la multiplication est la composition des fonctions, et l'élément neutre est la fonction identique. L'ensemble des entiers naturels $\mathbb{N}$ est un monoïde commutatif pour l'addition, avec $0$ pour élément neutre.

Un **homomorphisme de monoïdes** est une fonction $f$ d'un monoïde $G$ vers un monoïde $H$ telle que $f(1) = 1$ et $f(ab) = f(a)f(b)$ pour tous $a$ et $b \in G$. Si $G$ est un monoïde multiplicatif, et $a \in G$, alors l'application de $\mathbb{N}$ vers $G$ qui envoie $n$ sur $a^n$ est un homomorphisme. Un homomorphisme $f$ est **non trivial** si $\{1\}$ est un sous-ensemble propre de $im \, f$. Un sous-ensemble $H$ d'un monoïde $G$ est un **sous-monoïde** si $1 \in H$ et si $H$ est stable pour la multiplication. Si $S$ est un sous-ensemble du monoïde $G$, alors l'ensemble formé par $1$ et tous les produits finis d'éléments de $S$ est un sous-monoïde de $G$ appelé le **sous-monoïde engendré par** $S$. Le sous-monoïde de $\mathbb{N}$ engendré par $\{3,4\}$ est $\mathbb{N} \setminus \{1,2,5\}$.

Soit $X$ un ensemble. Définissons $X^*$ comme l'ensemble des suites finies d'éléments de $X$, y compris la suite vide. Les éléments de $X^*$ sont appelés des **mots**. Deux mots $u \equiv x_1x_2\cdots x_m$ et $v \equiv y_1y_2\cdots y_n$ sont égaux si $m = n$ et $x_i = y_i$ pour $i = 1, 2, \dots, m$. Si $u$ et $v$ sont égaux dans $X^*$ nous écrirons $u \equiv v$. On définit une **multiplication** (appelée aussi **concaténation**) sur $X^*$ en posant $uv \equiv x_1\cdots xMy_1\cdots y_n$. Cette multiplication est associative et le mot vide est l'élément neutre, de sorte que $X^*$ est un monoïde, appelé le **monoïde libre sur l'ensemble** $X$. Si $X$ est un ensemble à un élément, $X^*$ est isomorphe au monoïde additif des entiers naturels.

Si $a$ et $b$ sont des éléments d'un monoïde et si $ab = 1$, alors disons que $a$ est un **inverse à gauche** de $b$ et que $b$ est un **inverse à droite** de $a$. Si $b$ a un inverse à gauche $a$ et un inverse à droite $c$, alors $a = a(bc) = (ab)c = c$; dans ce cas nous disons que $a$ est l'**inverse** de $b$ et nous écrivons $a = b^{-1}$. Si $b$ a un inverse nous disons que $b$ est une **unité**, ou que $b$ est **inversible**.

Un **groupe** est un monoïde $G$ dans lequel tout élément est inversible. Dans un groupe additif, l'inverse de $a$ est noté $-a$ plutôt que $a^{-1}$. Pour un entier strictement positif $n$ nous définissons $a^{-n}$ comme $(a^{-1})^n$; les lois usuelles pour les exposants sont valables. Dans un groupe additif, cette définition prend la forme $(-n)a = n(-a)$, et les lois de distributivité et d'associativité s'appliquent (voir la définition d'un $R$-module dans la section 3). Le prototype d'un groupe abélien est le groupe des entiers $\mathbb{Z}$ pour l'addition.

L'**ordre** d'un élément $a$ d'un groupe est la cardinalité de l'ensemble $\{a^n : n \in \mathbb{N}\}$. L'ordre de $a$ est $n \in \mathbb{N}$ si, et seulement si, $a^n = 1$ et $a^m \neq 1$ pour $m = 1, \dots, n-1$. Dans le groupe $\mathbb{Z}$ l'élément $0$ est d'ordre 1, comme l'élément neutre dans $n$'importe quel groupe, et tout élément non nul est d'ordre infini. Dans un groupe discret l'ordre d'un élément $a$ est la cardinalité de l'ensemble $\{n \in \mathbb{N} : a^n \neq 1$ pour tous les $m$ tels que $0 < m \leq n\}$ (cet ensemble contient 0), et par suite $c$ est un ordinal $\beta \leq \omega$.

Si $G$ et $H$ sont des groupes et si $f$ est un homomorphisme de monoïdes de $G$
vers $H$, alors $f(a^{-1}) = f(a)^{-1}$ et $f(a^{-1})f(a) = f(a^{-1}a) = f(1) = 1$. Par suite un homomorphisme de monoïdes entre deux groupes préserve toute la structure de groupe : multiplication, élément neutre et inverse. Si $G$ est un groupe et si $a \in G$, alors l'application qui envoie $x \in G$ sur $axa^{-1}$ est un automorphisme de $G$, comme on le voit facilement ; un tel automorphisme est appelé **intérieur**.

Si $G$ et $H$ sont des groupes abéliens, alors l'ensemble $\text{Hom}(G, H)$ des homomorphismes de $G$ vers $H$ a une structure naturelle de groupe abélien obtenue en posant $(f_1 + f_2)(x) = f_1(x) + f_2(x)$. Les groupes $\text{Hom}(\mathbb{Z}, H)$ et $H$ sont naturellement isomorphes en considérant l'application qui envoie $f \in \text{Hom}(\mathbb{Z}, H)$ sur $f(1) \in H$. Si $h$ est un homomorphisme de $H$ vers $H'$, alors $h$ induit un homomorphisme de $\text{Hom}(G, H)$ vers $\text{Hom}(G, H')$ qui envoie $f$ sur $hf$ ; c'est-à-dire que l'on a $h(f_1 + f_2) = hf_1 + hf_2$. De la même manière un homomorphisme $g: G' \to G$ induit un homomorphisme de $\text{Hom}(G, H)$ vers $\text{Hom}(G', H)$ qui envoie $f$ sur $fg$.

Une catégorie $\mathcal{C}$ comme la catégorie des groupes abéliens, telle que $\mathcal{C}(G, H)$ est un groupe abélien pour chaque couple d'objets $G$ et $H$ de $\mathcal{C}$, et telle que les fonctions induites de $\mathcal{C}(G, H)$ vers $\mathcal{C}(G, H')$ par une flèche $H \to H'$, et de $\mathcal{C}(G, H)$ vers $\mathcal{C}(G', H)$ par une flèche $G' \to G$, sont des homomorphismes de groupes, est appelée une **catégorie pré-additive**.

Une **permutation** d'un ensemble $X$ est une bijection de $X$ sur lui-même. L'ensemble des permutations de $X$ est un groupe appelé le **groupe symétrique** sur $X$. Si $x_1, \dots, x_n$ sont des éléments distincts dans un ensemble discret $X$, alors nous notons $(x_1, \dots, x_n)$ la permutation $\pi$ de $X$ telle que

$$ \pi x_i = x_{i+1} \text{ pour } i = 1, \dots, n-1, \quad \pi x_n = x_1, \quad \pi x = x \text{ sinon.} $$

Une telle permutation est appelée un **n-cycle** de **support** $\{x_1, \dots, x_n\}$, et deux cycles sont appelés **disjoints** si leurs supports sont disjoints. Si $X$ est un ensemble fini, alors toute permutation est un produit de cycles disjoints. Comme $(x_1, \dots, x_n) = (x_1, x_n) \cdots (x_1, x_3)(x_1, x_2)$, toute permutation d'un ensemble fini est un produit de 2-cycles (non nécessairement disjoints). Une permutation qui peut être écrite comme un produit d'un nombre pair de 2-cycles est appelée une permutation **paire**, et sinon **impaire**. Si $\pi$ est une permutation d'un ensemble fini nous définissons

$$ \operatorname{sgn} \pi = \begin{cases} 1 & \text{si } \pi \text{ est paire} \\ -1 & \text{si } \pi \text{ est impaire.} \end{cases} $$

Le produit d'un nombre pair de 2-cycles ne peut pas être égal au produit d'un nombre impair de 2-cycles (exercice 7). Par suite la signature est bien définie et $\operatorname{sgn} \pi_1 \pi_2 = (\operatorname{sgn} \pi_1)(\operatorname{sgn} \pi_2)$ (exercice 8).

Un **sous-groupe** d'un groupe est un sous-monoïde stable pour le passage à l'inverse. Si $G$ est un groupe, $G$ et $\{1\}$ sont des sous-groupes de $G$ ; nous notons
souvent le sous-groupe $\{1\}$ par 1. Si $S$ est un sous-ensemble d'un groupe $G$, alors l'ensemble

$$ \langle S \rangle = \{1\} \cup \{ s_1 s_2 \cdots s_k : s_i \in S \cup S^{-1}, k \ge 1 \} $$

de tous les produits finis d'éléments de $S$, ou d'inverses d'éléments de $S$, est un sous-groupe de $G$ appelé le **sous-groupe engendré par $S$**. Si $\langle S \rangle = G$, alors $S$ est appelé un **ensemble de générateurs**, ou un **système générateur** pour $G$. Un groupe est **de type fini** s'il possède un système générateur finiment énumérable, **cyclique** s'il possède un système générateur à un élément. Le groupe additif $\mathbb{Q}$ des nombres rationnels n'est pas de type fini ; en fait, tout sous-groupe de type fini de $\mathbb{Q}$ est cyclique (on voit facilement que tout sous-groupe de type fini de $\mathbb{Q}$ est *contenu dans* un sous-groupe cyclique).

Un sous-groupe $H$ d'un groupe $G$ est **normal** si $ghg^{-1} \in H$ pour tous $g \in G$ et $h \in H$. Tout sous-groupe d'un groupe abélien est normal. Si $f$ est un homomorphisme de $G$ vers $H$, alors on voit facilement que le **noyau** de $f$,

$$ \ker f = \{ x \in G : f(x) = 1 \} = f^{-1}(1) $$

est un sous-groupe normal de $G$. La taille du noyau de $f$ nous dit dans quelle mesure $f$ échoue à être injectif, comme le montre l'équivalence des propriétés suivantes :

— $f(a) = f(b),$

— $f(ab^{-1}) = f(a)f(b^{-1}) = f(a)f(b)^{-1} = 1,$

— $ab^{-1} \in \ker f,$

de sorte que $f$ est un monomorphisme si, et seulement si, $\ker f = 1$. Nous étudierons les structures algébriques qui sont des groupes abéliens avec une structure additionnelle. Dans ces cas le noyau d'un homomorphisme $f$ signifie le noyau de $f$ en tant qu'homomorphisme de groupes ; si le groupe est écrit additivement, comme c'est normalement le cas pour ces structures plus complexes, on a $\ker f = f^{-1}(0)$.

Tout sous-groupe normal $H$ d'un groupe $G$ est le noyau d'un homomorphisme construit comme suit. L'ensemble $G/H$ a les mêmes éléments que $G$, mais l'égalité est définie en posant $a = b$ si $ab^{-1} \in H$. Quand il est nécessaire de distinguer entre les deux égalités sur $G$ et sur $G/H$ nous écrivons $a = b$ mod $H$ pour noter l'égalité dans $G/H$. La multiplication et le passage à l'inverse restent des fonctions par rapport à l'égalité de $G/H$, et donc $G/H$ est un groupe, appelé le **groupe quotient** de $G$ par $H$. Le prototype d'un groupe quotient est obtenu en prenant pour $G$ le groupe $\mathbb{Z}$ des entiers et en prenant pour $H$ le sous-groupe de $\mathbb{Z}$ formé par les multiples d'un entier donné $n$ ; le groupe quotient $G/H$ est alors le groupe $\mathbb{Z}_n$ des entiers modulo $n$.

Les faits essentiels qui relient les sous-groupes normaux et les groupes quotients sont réunis dans le théorème suivant.
**Théorème 1.1.** Soient $N$ un sous-groupe normal d'un groupe $G$ et $f$ un homomorphisme de $G$ vers un groupe $L$ avec $f(N) = 1$. Alors $f$ est un homomorphisme de $G/N$ vers $L$. Si $f$ est surjectif et si le noyau de $f$ est $N$, alors $f$ est un isomorphisme de $G/N$ sur $L.

*Démonstration.* Si $a = b$ (mod $N$), alors $ab^{-1} \in N$, d'où $f(a) = f(b)$; par suite $f$ est une fonction sur $G/N$, qui est clairement un homomorphisme. Réciproquement si $f(a) = f(b)$, alors $f(ab^{-1}) = 1$, de sorte que $ab^{-1} \in N$ et $a = b$ (mod $N$). Par suite, si $\ker f = N$, alors $f$ est une fonction injective de $G/N$ vers $L$; et donc, si $f: G \to L$ est surjective, la fonction $f: G/N \to L$ possède un inverse $g$. Clairement $g$ est aussi un homomorphisme. ■

Soit $N$ un sous-groupe normal du groupe $G$. Un sous-groupe (normal) de $G/N$ est un sous-groupe (normal) $H$ de $G$ qui est un sous-ensemble de $G/N$, c'est-à-dire, si $a \in H$ et $a = b$ (mod $N$), alors $b \in H$. On voit facilement qu'un sous-groupe $H$ de $G$ est un sous-ensemble de $G/N$ exactement dans le cas où $N \subseteq H$. La différence entre un sous-groupe $H$ de $G$ contenant $N$ et un sous-groupe $H$ de $G/N$ est la relation d'égalité sur $H$. Nous faisons la distinction entre $H$ comme un sous-groupe de $G$ et $H$ comme un sous-groupe de $G/N$ en écrivant $H/N$ pour ce dernier. Si $H$ est un sous-groupe normal de $G$ qui contient $N$, alors $(G/N)/(H/N)$ est isomorphe à $G/H$; en fait, les éléments des deux groupes sont simplement les éléments de $G$, et les égalités sont les mêmes.

**Théorème 1.2.** Soient $H$ et $K$ des sous-groupes du groupe $G$. Si $K$ est normal, alors

(i) l'ensemble $HK = \{hk : h \in H \text{ et } k \in K\}$ est un sous-groupe,

(ii) le sous-groupe $H \cap K$ est normal dans $H$, et

(iii) les groupes quotients $HK/K$ et $H/(H \cap K)$ sont isomorphes.

*Démonstration.* Exercice. ■

Dans un groupe additif, le sous-groupe $HK$ est écrit sous la forme $H + K$.

Si $a \in G$ et si $H$ est un sous-groupe de $G$, alors $Ha = \{ha : h \in H\}$ est appelé une **classe à droite** de $H$, tandis que $aH = \{ah : h \in H\}$ est appelée une **classe à gauche** de $H$. Le passage à l'inverse induit une bijection entre classes à gauche et à droite de $H$ qui envoie $aH$ sur $Ha^{-1}$, et nous pouvons donc parler sans ambigüité de la cardinalité de l'ensemble des classes de $H$ dans $G$. Cette cardinalité est appelée l'**indice** de $H$ dans $G$ et nous le notons $[G : H]$. Si $H$ est normal, alors $Ha = aH$ pour chaque élément $a$ de $G$.

Exercices

1. Montrer que dans un monoïde fini, si $a$ possède un inverse à droite ou à gauche, alors $a^n = 1$ pour un entier strictement positif $n$, de sorte que
l'élément peut avoir au plus un inverse à droite ou à gauche. Donner
un exemple d'un élément dans un monoïde qui admet deux inverses à
gauche distincts; deux inverses à droite distincts.

2. Montrer qu'un monoïde peut être identifié avec une catégorie à un seul objet, et que les homomorphismes de monoïdes sont des foncteurs entre les catégories correspondantes. Parmi ces catégories, lesquelles correspondent à des groupes ?

3. Montrer que l'ensemble des unités d'un monoïde est un groupe.

4. Montrer que l'ensemble S des suites binaires forme un groupe abélien G pour l'addition des coordonnées modulo 2. Soit $a \in S$ et définissons $b, c \in S$ par $b_n = 1$ si, et seulement si, $a_n = 1$ et $a_m = 0$ pour tous les $m < n$, et $c_n = 1$ si, et seulement si, $b_{n-1} = 1$. Montrer que si le sous-groupe de G engendré par b et c est engendré par un sous-ensemble fini de G, alors, ou bien $a = 0$, ou bien $a \neq 0$.

5. Soit $G$ un groupe multiplicatif avec une inégalité. L'inégalité est dite **invariante par translation** si $x \neq y$ implique $zx \neq zy$ et $xz \neq yz$. Étant donnée une inégalité invariante par translation, montrer que

(i) le passage à l'inverse qui envoie $x$ sur $x^{-1}$ est fortement extensionnel si, et seulement si, l'inégalité est symétrique.

(ii) l'inégalité est cotransitive si, et seulement si, la multiplication est fortement extensionnelle (l'inégalité sur $G \times G$ est donnée par $(x_1, x_2) \neq (y_1, y_2)$ si $x_1 \neq y_1$ ou $x_2 \neq y_2$).

Enfin, démontrer que si l'inégalité est consistante et si la multiplication est fortement extensionnelle, alors l'inégalité est invariante par translation.

6. En regardant une inégalité sur $G$ comme un sous-ensemble de $G \times G$, montrer que la réunion d'une famille d'inégalités sur un groupe $G$ pour lesquelles la loi de groupe est fortement extensionnelle est elle-même une inégalité de cette sorte. Montrer qu'il existe une unique inégalité sur $G/N$ qui rend le théorème 1.1 vrai dans la catégorie des groupes avec inégalité, avec pour flèches les homomorphismes fortement extensionnels. Montrer que si $G$ est l'ensemble des suites binaires avec pour addition l'addition des coordonnées modulo 2 et si $N = \{x \in G : \text{il y a un } m \text{ tel que } x_n = 0 \text{ pour tous } n \ge m\}$, alors $x \ne 0$ dans $G/N$ si, et seulement si, $x_n = 1$ une infinité de fois et LPO est valide.

7. Soient $x_1, \dots, x_m, y_1, \dots, y_n$ des éléments distincts d'un ensemble fini $X$, soit $G$ le groupe symétrique sur $X$, et soit $1 \le i < j \le m$. Vérifiez les deux égalités suivantes sur $G$.

$$
(i) (x_i, x_j)(x_1, \dots, x_m) = (x_1, \dots, x_{i-1}, x_j, \dots, x_m)(x_i, \dots, x_{j-1})
$$

$$
(ii) (x_1, y_1)(x_1, \dots, x_m)(y_1, \dots, y_n) = (y_1, \dots, y_n, x_1, \dots, x_m).
$$
Pour $\pi \in G$, nous pouvons écrire $\pi$ d'une manière essentiellement unique comme un produit de cycles disjoints dont les supports recouvrent $X^1$. Soit $N_\pi$ le nombre de cycles dans un tel produit. En utilisant (i) et (ii), montrer que si $\tau$ est un 2-cycle, alors $N_{\tau\pi} = N_\pi \pm 1$. En conclure qu'une permutation paire ne peut pas être écrite comme produit d'un nombre impair de 2-cycles.

8. Montrer que la fonction sgn est un homomorphisme du groupe symétrique d'un ensemble fini vers le groupe multiplicatif $\{-1, 1\}$.

9. Donner un exemple brouwerien d'un sous-groupe d'un groupe abélien fini qui est engendré par un sous-ensemble dénombrable mais qui n'est pas de type fini.

10. Montrer que l'ensemble des sous-groupes normaux d'un groupe est un treillis modulaire.

## 2 Anneaux et corps

Un **anneau** est un groupe abélien additif $R$ qui est aussi un monoïde multiplicatif, les deux structures étant reliées par les **lois de distributivité** :

$$ 
\begin{aligned}
a(b+c) &= ab + ac, \\
(a+b)c &= ac + bc.
\end{aligned}
 $$

Un anneau est **trivial** si $0 = 1$. Si la structure de monoïde multiplicatif est commutative, alors $R$ est un **anneau commutatif**. Une **unité** de $R$ est une unité du monoïde multiplicatif de $R$. On dit qu'un anneau $A$ des **unités détachables** lorsque ses unités forment d'un sous-ensemble détachable.

Si $A$ est un groupe abélien, alors l'ensemble des endomorphismes $E(A) = \text{Hom}(A, A)$ est un anneau (en prenant pour multiplication la composition) appelé l'**anneau des endomorphismes** de $A$. Plus généralement, si $C$ est une catégorie pré-additive, $C(A, A)$ est un anneau pour chaque objet $A$ de $C$.

Un anneau non trivial $k$ est un **anneau à division**<fnref n="2" /> (ou un **corps gauche**) si, pour chaque $a$ et $b \in k$,

$$ a \neq b \text{ si, et seulement si, } a - b \text{ est une unité.} $$

Nous rappelons à la lectrice que l'interprétation du symbole $a \neq b$ dépend du contexte : si $k$ possède une inégalité, alors $a \neq b$ fait référence à cette inégalité, et sinon $a \neq b$ fait référence à la non-égalité. Une conséquence immédiate de la définition est que si $k$ est un anneau à division, alors l'inégalité sur $k$ est

<footnote n="1">1. **NdT.** Ici, pour recouvrir $X$, nous acceptons les cycles $(a)$, de support $\{a\}$, tous égaux à la permutation identité.</footnote>

<footnote n="2">2. **NdT.** Division ring.</footnote>
symétrique et **invariante par translation** : si $a \neq b$, alors $a + c \neq b + c$. Notez que la non-égalité est automatiquement invariante par translation parce que l'addition est une fonction.

Naturellement, nous pourrions définir l'inégalité $a \neq b$ sur un anneau arbi-
traire comme signifiant que $a - b$ est une unité et, techniquement, nous aurions
alors un anneau à division; de sorte que la théorie générale des anneaux à divi-
sion contient la théorie des anneaux. Cependant, l'idée est d'utiliser le symbole
$a \neq b$ pour représenter des relations qui peuvent être raisonnablement appelées
des inégalités : si vous prenez une inégalité stupide et que vous obtenez un
anneau à division stupide, ne nous blâmez pas. Comme règle de conduite, vous
pouvez choisir une inégalité standard. Pour l'essentiel, nous serons intéressés
par des anneaux à division qui sont discrets, et, dans une moindre mesure, par
des anneaux à division avec une relation de séparation étroite.

Les éléments non nuls d'un anneau à division sont exactement les unités ;
dans le cas discret c'est une propriété caractéristique des anneaux à division
(exercice 3). Un corps est un anneau à division commutatif. Un corps de Heyting
est un corps avec une relation de séparation étroite. Dans un corps de Heyting ou
plus généralement dans un corps avec une inégalité cotransitive, les opérations
arithmétiques sont fortement extensionnelles (exercice 5). Les nombres rationnels
Q forment un corps discret ; les nombres réels (section suivante) forment un
corps de Heyting. Les quaternions rationnels (exercice 4) forment un anneau à
division discret et non commutatif.

Un sous-ensemble d'un anneau est un **sous-anneau** si c'est un sous-groupe
additif et un sous-monoïde multiplicatif. Soit $S$ un sous-anneau d'un anneau
commutatif $R$, et soient $a_1, \dots, a_n$ des éléments de $R$. Alors l'ensemble des
sommes d'éléments de $R$ de la forme

$$
s a_1^{m_1} a_2^{m_2} \cdots a_n^{m_n},
$$

avec $s \in S$ et $m_i \in \mathbb{N}$, est un sous-anneau de $R$ que l'on note $S[a_1, \dots, a_n]$ ; il
est contenu dans tout sous-anneau de $R$ qui contient $S \cup \{a_1, \dots, a_n\}$. Si $S$ et $R$
sont des corps, alors $S(a_1, \dots, a_n)$ désigne l'ensemble des quotients $f/g$ avec
$f, g \in S[a_1, \dots, a_n]$ et $g \neq 0$. On voit facilement que $S(a_1, \dots, a_n)$ est un corps
contenu dans chaque sous-corps de $R$ qui contient $S \cup \{a_1, \dots, a_n\}$.

Un **anneau intègre**, ou encore un **domaine d'intégrité** est un anneau avec inégalité qui est isomorphe à un sous-anneau d'un corps ; de manière plus informelle, un anneau intègre est simplement un sous-anneau d'un corps. Si $R$ est un sous-anneau d'un corps, alors l'ensemble $\{ab^{-1} : a, b \in R \text{ et } b \neq 0\}$ est un corps qui contient $R$, appelé le **corps de fractions** de $R$. Le corps de fractions d'un anneau intègre est essentiellement unique (exercice 6).

Si $R$ est un anneau intègre discret, alors, pour chaque $a$ et $b \in R$,

$$
\text{si } a \neq 0 \text{ et } b \neq 0, \text{ alors } ab \neq 0. \qquad (*)
$$
Inversement, si $R$ est un anneau commutatif intègre discret qui satisfait la condition $(*)$, alors nous pouvons **immerger**<fnref n="1" /> $R$ dans un corps discret $k$ en imitant la construction du corps des nombres rationnels $\mathbb{Q}$ à partir de l'anneau des nombres entiers $\mathbb{Z}$. Soit $k = \{(a,b) \in R \times R : b \neq 0\}$ avec $(a,b) = (c,d)$ si $ad = bc$. Nous définisons la multiplication sur $k$ par $(a,b) \cdot (c,d) = (ac,bd)$ et l'addition par $(a,b) + (c,d) = (ad + bc,bd)$. On vérifie sans peine que cela fait de $k$ un anneau avec l'élément neutre additif $(0,1)$ et l'élément neutre multiplicatif $(1,1)$. Si $(a,b) \neq (0,1)$, alors $a \neq 0$ et donc l'élément $(b,a)$ est dans $k$ et $(a,b)(b,a) = (1,1)$; inversement, si $(a,b)(c,d) = (1,1)$, alors $ac = bd \neq 0$, d'où $a \neq 0$ et $(b,a) \in k$, et par suite $k$ est un corps. Nous immergeons $R$ dans $k$ en envoyant $a$ sur $(a,1)$.

Une caractérisation intrinsèque d'un anneau intègre arbitraire est donnée dans l'exercice 7. Pour démontrer que cette caractérisation est correcte, construisez le corps de fractions comme dans le cas discret.

Si $k$ est un corps, alors le sous-corps de $k$ formé par tous les éléments de la forme $(n \cdot 1)/(m \cdot 1)$ où $m$ et $n$ sont des entiers et $m \cdot 1 \neq 0$, est le plus petit sous-corps de $k$, et il est appelé le **sous-corps premier**<fnref n="2" /> de $k$. Ce corps est le corps de fractions du sous-anneau $\{n \cdot 1 : n \in \mathbb{Z}\}$ de $k$. Si $a_1, \dots, a_n \in k$ et si $k_0$ est le sous-corps premier de $k$, nous disons que $k$ est **engendré par** $a_1, \dots, a_n$ si $k_0(a_1, \dots, a_n) = k$. Un **corps premier** est un corps égal à son sous-corps premier.

Une fonction $f$ d'un anneau $R$ vers un anneau $S$ est un **homomorphisme d'anneaux** si c'est un homomorphisme des groupes additifs et un homomorphisme des monoïdes multiplicatifs. La fonction de l'anneau des entiers $\mathbb{Z}$ vers $S$ qui envoie $n$ sur $n \cdot 1$ est un homomorphisme d'anneaux. Un sous-groupe additif $I$ d'un anneau $R$ est un **idéal** si pour tous $x \in I$ et $r \in R$ les éléments $rx$ et $xr$ sont dans $I$. On voit facilement que si $f$ est un homomorphisme d'anneaux, alors $ker \ f = f^{-1}(0)$ est un idéal. Un idéal $I$ est **propre** si $1 \notin I$. Un **idéal à gauche** (resp. **idéal à droite**) $I$ d'un anneau $R$ est un sous-groupe additif de $R$ tel que pour tous $r \in R$ et $x \in I$ l'élément $rx$ (resp. $xr$) appartient à $I$. Un idéal à gauche $I$ d'un anneau est **non nul** si $I$ contient un élément non nul. Pour éviter la confusion entre idéaux à gauche, idéaux à droite et idéaux, un idéal est souvent appelé un **idéal bilatère**. Si $I$ est un idéal bilatère de l'anneau $R$, alors la multiplication est une loi de composition sur le groupe quotient $R/I$, de sorte que $R/I$ est un anneau.

Soient $X$ et $Y$ des sous-ensembles de l'anneau $R$. On définit $XY$ comme le sous-groupe additif de $R$ engendré par $\{xy : x \in X \text{ et } y \in Y\}$. Si $X$, $Y$ et $Z$ sont des sous-ensembles de $R$, alors $(XY)Z = X(YZ)$. Un sous-ensemble non vide $I$ est un idéal si, et seulement si, $RIR = I$, tandis que $I$ est un idéal à

<footnote n="1">1. **NdT.** To embed. Nous utilisons dans la traduction de cet ouvrage la terminologie peu habituelle « immerger *A* dans *B* » pour dire qu'on donne un isomorphisme de l'objet *A* sur un sous-objet de *B*. Nous disons aussi parfois « plonger *A* dans *B* », et nous utilisons les termes de « plongement » ou « immersion ».</footnote>

<footnote n="2">2. **NdT.** Prime field of $k$.</footnote>
gauche (resp. à droite) si $RI = I$ (resp. $IR = I$).

Si $S$ est un sous-ensemble d'un anneau $R$, alors $(S) := RSR$ est le plus petit idéal de $R$ contenant $S$, et on l'appelle l'idéal engendré par $S$. Si $S$ est la famille finie $\{s_1, \dots, s_n\}$, alors l'idéal engendré par $S$ est noté $(s_1, \dots, s_n)$. L'idéal à gauche engendré par $S$ est $RS$, tandis que l'idéal à droite engendré par $S$ est $SR$; si $S$ est un ensemble à un élément $\{s\}$, alors l'idéal à gauche ou à droite correspondant est appelé **principal**, et on le note $Rs$ ou $sR$.

Si $I$ et $J$ sont des idéaux, alors $IJ$ et $I \cap J$ sont des idéaux. L'ensemble $I \cup J$ n'est pas nécessairement un idéal; l'idéal engendré par $I \cup J$ est l'ensemble $\{i + j : i \in I \text{ et } j \in J\}$ et on le note $I + J$. Plus généralement, si $\{I_i\}$ est une famille d'idéaux, alors l'idéal engendré par $\bigcup_i I_i$ est noté $\sum_i I_i$.

Le **transporteur**<fnref n="1" /> d'un ensemble $S$ dans un idéal à gauche $I$ est l'idéal à gauche

$$I : S = \{ x \in R : xS \subseteq I \}.$$

Le **radical** d'un idéal $I$ dans un anneau commutatif est l'idéal $\sqrt{I} = \{ x \in R : x^n \in I \text{ pour un } n \}.$

Le théorème fondamental des homomorphismes d'anneaux résulte immédiatement du théorème correspondant pour les groupes.

**Théorème 2.1.** Soit $I$ un idéal de l'anneau $R$. Si $f$ est un homomorphisme de $R$ vers un anneau $S$ avec $f(I) = 0$, alors $f$ est un homomorphisme de $R/I$ vers $S$. Si $f$ est surjectif et si le noyau de $f$ est l'idéal $I$, alors $f$ est un isomorphisme de $R/I$ sur $S$.

Soit $I$ un idéal de l'anneau $R$. Un idéal (à gauche) de $R/I$ est un idéal (à gauche) $J$ de $R$ contenant $I$. Si $J$ est un idéal de $R$ contenant $I$, alors $R/J \simeq (R/I)/(J/I)$.

**Théorème 2.2.** Soient $R$ un anneau, $S$ un sous-anneau et $I$ un idéal de $R$. Alors $S + I$ est un sous-anneau de $R$ contenant $I$ en tant qu'idéal, $S \cap I$ est un idéal de $S$, et $(S + I)/I \simeq S/(S \cap I)$.

*Démonstration.* Clairement $S + I$ est un sous-anneau et $I$ est un idéal de $S + I$. Définissons une fonction $f$ de $S/(S \cap I)$ vers $(S + I)/I$ en posant $f(s) = s$. Notez que $f$ est bien une fonction parce que si $s_1 = s_2$ dans $S/(S \cap I)$, alors $s_1 - s_2 \in I$ et donc $s_1 = s_2$ dans $(S + I)/I$. Clairement $f$ est un homomorphisme. Maintenant définissons une fonction $g$ de $(S + I)/I$ vers $S/(S \cap I)$ en posant $g(s + i) = s$. Pour voir que $g$ est une fonction nous remarquons que si $s_1 + i_1 = s_2 + i_2$ dans $(S + I)/I$, alors $s_1 - s_2 \in I$, et donc $s_1 = s_2$ dans $S/(S \cap I)$. Il s'ensuit que $f$ est un isomorphisme. ■

<footnote n="1">1. NdT. Quotient of a left ideal $I$ by a set $S$</footnote>
Si $P$ est un idéal d'un anneau commutatif $R$, alors nous disons que $P$ est un **idéal premier**<fnref n="1" /> si chaque fois que $xy \in P$, alors $x \in P$ ou $y \in P$. Si $P$ est un idéal détachable propre de $R$, alors on voit facilement que $P$ est premier si, et seulement si, $R/P$ est un anneau intègre. Si $p$ est un nombre premier, alors l'idéal $(p)$ de $\mathbb{Z}$ est un idéal premier détachable propre, et il en va de même pour l'idéal 0.

**Théorème 2.3.**<fnref n="2" /> Soient $P_1, \dots, P_n$ des idéaux détachables d'un anneau commutatif $R$ tels que $P_i$ est premier pour $i \le n-2$. Si $I$ est un idéal de type fini de $R$, alors, ou bien $I \subseteq P_i$ pour un $i$, ou bien il existe un $z \in I \setminus \bigcup_i P_i$.

*Démonstration.* Soit $\{x_1, \dots, x_m\}$ un système générateur de $I$ et soit $F$ l'ensemble des sous-ensembles finis $S$ de $\{1, 2, \dots, n\}$ tels que $\{x_1, \dots, x_m\} \subseteq \bigcup_{j \in S} P_j$. Nous raisonnons par récurrence<fnref n="3" /> sur $\#F$, le nombre des éléments de $F$. Si $\#F = 0$, alors $x_j \in I \setminus \bigcup_i P_i$ pour un $j$. Sinon prenons un $S \in F$ qui minimise $\#S$. Si $\#S \le 1$, alors $I \subseteq P_i$ pour un $i$. Sinon $\#S \ge 2$ et pour chaque $i \in S$, il existe $a_i \in \{x_1, \dots, x_m\}$ tel que $a_i \in P_i \setminus \bigcup_{S \subseteq \{i\}} P_j$. Si $\#S = 2$, alors posons $x_{m+1} = \sum_{i \in S} a_i \in I \setminus \bigcup_{i \in S} P_i$. Si $\#S > 2$, alors $P_i$ est premier pour un $i \in S$, de sorte que $x_{m+1} = a_i + \prod_{j \in S \setminus \{i\}} a_j \in I \setminus \bigcup_{i \in S} P_i$. Dans chaque cas nous pouvons agrandir $\{x_1, \dots, x_m\}$, sans agrandir $I$, d'où $S \notin F$, et nous terminons par récurrence sur $\#F$. ■

**Théorème 2.4.** Soient $I_1, \dots, I_n$ des idéaux de type fini dans un anneau commutatif $R$ et soit $P$ un idéal premier de $R$ tel que le produit $I_1 \cdots I_n$ est contenu dans $P$. Alors $I_i \subseteq P$ pour un $i$.

*Démonstration.* Par récurrence sur $n$ il suffit de considérer le cas où $n = 2$. Soient $I_1 = (a_1, \dots, a_s)$ et $I_2 = (b_1, \dots, b_t)$. Puisque $a_i b_j \in P$, on a pour chaque $i$ ou bien $a_i \in P$, ou bien $b_j \in P$ pour tous les $j$. ■

Un corps par négation est un anneau commutatif qui est un corps pour la non-égalité et tel que 0 est un idéal premier. Un corps discret est un corps par négation. Un idéal maximal dans un anneau commutatif $R$ est un idéal $M$ tel que $R/M$ est un corps par négation; ainsi, un idéal $M$ de $R$ est maximal si, et seulement si, d'une part $M$ est un idéal premier, et d'autre part $\langle x \in R \setminus M \rangle$ équivaut à $\langle \exists r \in R, rx - 1 \in M \rangle$. Un idéal maximal détachable $M$ est un idéal tel que $R/M$ est un corps discret.

<footnote n="1">1. **NdT.** En mathématiques classiques, les idéaux premiers sont définis comme des idéaux propres, i.e. avec $1 \notin P$. Certaines démonstrations en mathématiques constructives préfèrent ne pas utiliser cette propriété, notamment lorsque l'idéal n'est pas à priori détachable.</footnote>

<footnote n="2">2. **NdT.** Cette forme constructive du lemme d'évitement des idéaux premiers sera très utile dans les chapitres VIII et X.</footnote>

<footnote n="3">3. **NdT.** Plutôt qu'une démonstration par récurrence coutumière, les auteurs donnent ici une démonstration de terminaison d'un algorithme.</footnote>
La **caractéristique** d'un anneau $k$ est l'ordre de l'élément $1$ dans le groupe additif de $k$. Une convention standard est de dire que $k$ est de **caractéristique 0** si l'ordre de $1$ est infini. Ainsi la caractéristique d'un anneau discret $k$ est le plus petit entier strictement positif $n$ tel que $n \cdot 1 = 0$, si un tel entier existe, et est égale à $0$ sinon. Le corps des nombres rationnels est de caractéristique $0$, et le corps $\mathbb{F}_p = \mathbb{Z}/(p)$ est de caractéristique $p$. La caractéristique d'un corps discret n'est pas nécessairement un élément de $\mathbb{N}$ comme le montre l'exemple brouwerien suivant.

Une suite binaire qui contient au plus un élément $1$ est appelée une **suite binaire fugitive**.

**Exemple 2.5.** Soit $a$ une suite binaire fugitive. Définissons $p_n$ par

$$p_n = \begin{cases} 0 & \text{si } a_n = 0 \\ \text{le } n\text{-ième nombre premier} & \text{si } a_n = 1. \end{cases}$$

Soit $P$ l'idéal de $\mathbb{Z}$ engendré par les nombres $p_n$, et soit $R = \mathbb{Z}/P$. Alors $R$ est un anneau intègre discret ; soit $k$ son corps de fractions. La caractéristique de $k$ n'est pas un élément de $\mathbb{N}$. ■

Exercices

1. Montrer les identités suivantes dans un anneau arbitraire.

(i) $a0 = 0a = 0$,

(ii) $a(-b) = (-a)(b) = -ab$.

2. Utiliser les anneaux $\mathbb{Z}$ et $\mathbb{Q}$ pour construire un exemple brouwerien d'un anneau intègre discret dont les unités ne sont pas détachables.

3. Montrer qu'un anneau discret est un anneau à division si, et seulement si, les éléments non nuls forment un groupe multiplicatif.

4. Les **quaternions rationnels**. On écrit les éléments $(a, b, c, d)$ de $R = \mathbb{Q}^4$ comme des sommes formelles $a + bi + cj + dk$, où les éléments de $\mathbb{Q}$ commutent avec $i, j, k$, et où on pose $i^2 = j^2 = -1$ et $k = ij = -ji$. Notez que

$$(a + bi + cj + dk)(a - bi - cj - dk) = a^2 + b^2 + c^2 + d^2$$

et montrez que $R$ est un anneau à division non commutatif discret.

5. Montrer que dans un corps avec une inégalité cotransitive les opérations d'addition, de soustraction, de multiplication et de division (restreinte aux unités) sont fortement extensionnelles (voir l'exercice 1.5).

6. Soit $R$ un sous-anneau d'un corps $K$. Montrer que

$$k = \{ ab^{-1} : a, b \in R \text{ et } b \neq 0 \}$$
est un corps qui contient $R$. Montrer que si $R$ est un sous-anneau d'un autre corps $K'$, et si les inégalités sur $K$ et $K'$ coïncident sur $R$, alors $k$ est isomorphe à $k'$. Montrer que l'inégalité sur $R$ est consistante, cotransitive, étroite ou discrète si, et seulement si, l'inégalité sur $k$ possède la même propriété.

7. Montrer qu'un anneau commutatif est un anneau intègre si, et seulement si, les conditions suivantes sont satisfaites :

(i) $1 \neq 0$,

(ii) $a \neq b$ si, et seulement si, $a - b \neq 0$,

(iii) si $a \neq 0$ et $ab = 0$, alors $b = 0$,

(iv) $a \neq 0$ et $b \neq 0$ si, et seulement si, $ab \neq 0$,

Montrer qu'une condition nécessaire et suffisante pour qu'un anneau commutatif avec la non-égalité soit un anneau intègre est que l'on a $a \neq 0$ si, et seulement si, $a$ est **simplifiable**<fnref n="1" /> ($ab = 0$ implique $b = 0$).

8. Montrer les propriétés suivantes pour les idéaux dans un anneau commutatif.

(i) $IJ \subseteq I \cap J$

(ii) $IJ \subseteq K$ si, et seulement si, $I \subseteq K : J$

(iii) Si $I \subseteq J$ alors $K : J \subseteq K : I$

(iv) $(\bigcap_i I_i) : J = \bigcap_i (I_i : J)$

(v) $I : \sum_i J_i = \bigcap_i (I : J_i)$

(vi) $I : JK = (I : J) : K$

9. Montrer les propriétés suivantes pour les idéaux dans un anneau commutatif.

(i) $\sqrt{IJ} = \sqrt{I \cap J} = \sqrt{I} \cap \sqrt{J}$.

(ii) Si $I^n \subseteq J$ pour un $n$, alors $\sqrt{I} \subseteq \sqrt{J}$.

(iii) $\sqrt{I + J} = \sqrt{\sqrt{I} + \sqrt{J}}$.

(iv) $\sqrt{\sqrt{I}} = \sqrt{I}$.

10. Soit $\varphi : R \to R'$ un homomorphisme d'anneaux commutatifs, et soient $I$ et $J$ des idéaux de $R'$. Montrer que $\varphi^{-1}(I) \cap \varphi^{-1}(J) = \varphi^{-1}(I \cap J)$, que $\varphi^{-1}(I)\varphi^{-1}(J) \subseteq \varphi^{-1}(IJ)$, et que $\sqrt{\varphi^{-1}(I)} = \varphi^{-1}(\sqrt{I})$. Montrer que si $\varphi$ est surjective, alors $\varphi^{-1}(I : J) = \varphi^{-1}I : \varphi^{-1}J$.

11. Montrer que (12) ∪ (45) n'est pas un idéal de l'anneau des entiers Z. Montrer que (12) + (45) et (12) : (45) sont des idéaux principaux.

12. Dans le théorème 2.3 il n'est pas nécessaire de savoir lesquels des $n - 2$ idéaux sont premiers. Démontrer le théorème 2.3 sous l'hypothèse plus faible selon laquelle si $a_i b_i \in P_i$ pour $i = 1, \dots, n$, alors pour au moins $n - 2$ indices $i$, ou bien $a_i \in P_i$ ou bien $b_i \in P_i$.

<footnote n="1">1. NdT. On dit aussi régulier.</footnote>
13. Modifier le théorème 2.3 de manière qu'aucun des idéaux $P_i$ ne soit supposé être premier, et la conclusion est alors que $I \subseteq P_i$ pour un certain $i$, ou alors il existe trois indices $j$ distincts tels que $P_j$ n'est pas premier (en un sens fort, convenable). Pouvez-vous démontrer que les trois idéaux $P_j$ sont distincts (et pas seulement leurs indices) ?

14. Soient $B$ et $C$ deux sous-groupes détachables d'un groupe $G$. Montrer que si $A$ est un sous-groupe de type fini de $G$, ou bien $A \subseteq B$, ou bien $A \subseteq C$, ou bien il existe un $x$ dans $A \setminus (B \cup C)$. Donner un contre-exemple (non brouwerien) pour montrer que le résultat est faux pour trois sous-groupes.

15. Montrer qu'un anneau discret non trivial $R$ est un anneau à division si, et seulement si, tout idéal de type fini est égal à $R$ ou à 0. Donner un exemple brouwerien pour un idéal de $\mathbb{Q}$ qui n'est égal ni à $\mathbb{Q}$ ni à 0.

16. Montrer qu'un idéal d'un anneau commutatif $R$ est un idéal premier propre si, et seulement si, c'est le noyau d'un homomorphisme de $R$ dans un corps par négation.

17. Montrer qu'un anneau intègre fini est un corps. Montrer qu'un idéal détachable $I$ de $\mathbb{Z}$ est maximal si, et seulement si, $I = (p)$ pour un nombre premier $p$.

## 3 Les nombres réels

Le prototype d'un corps de Heyting est le corps des nombres réels $\mathbb{R}$. L'ensemble $\mathbb{Q}^\mathbb{N}$ des suites de nombres rationnels forme un anneau commutatif pour l'addition et la multiplication coordonnée par coordonnée. Une suite de nombres rationnels $\{q_n\}$ est une **suite de Cauchy** si pour tout $\varepsilon \in \mathbb{Q}^{*+}$ il existe un $N \in \mathbb{N}$ tel que

$$|q_n - q_m| \le \varepsilon \text{ pour tous } m, n \ge N.$$

On voit immédiatement que l'ensemble $C$ des suites de Cauchy de nombres rationnels forme un sous-anneau de $\mathbb{Q}^\mathbb{N}$.

Une suite de nombres rationnels $\{q_n\}$ **converge vers 0** si pour tout $\varepsilon \in \mathbb{Q}^{*+}$, il existe un $N \in \mathbb{N}$ tel que $|q_n| \le \varepsilon$ pour tout $n \ge N$. On vérifie facilement que l'ensemble $I$ des suites de nombres rationnels qui convergent vers zéro forme un idéal de l'anneau $C$ des suites de Cauchy. L'ensemble $\mathbb{R}$ des **nombres réels** est l'anneau quotient $C/I$. À chaque élément $q \in \mathbb{Q}$ nous pouvons faire correspondre la suite dont tous les éléments sont égaux à $q$, et nous immergeons ainsi de manière naturelle $\mathbb{Q}$ dans $\mathbb{R}$.

L'ensemble des nombres réels $\mathbb{R}$ possède un ordre naturel. On définit le fait que $a \in \mathbb{R}$ est **strictement positif** en demandant qu'il existe un $\varepsilon \in \mathbb{Q}^{*+}$ et un $N \in \mathbb{N}$ tels que $a_n \ge \varepsilon$ pour tout $n \ge N$. On vérifie facilement que cette
définition respecte l'égalité de $\mathbb{R} = C/I$, et que l'ensemble des nombres réels strictement positifs est stable pour l'addition et la multiplication. Nous écrivons $a < b$, ou $b > a$, si $b - a$ est strictement positif; en particulier, $a > 0$ signifie que $a$ est strictement positif.

**Théorème 3.1.** *Les conditions suivantes pour un nombre réel $a$ sont équivalentes.*

(i) Il existe un $\varepsilon \in \mathbb{Q}^{*+}$ et un $N \in \mathbb{N}$ tels que $|a_n| \ge \varepsilon$ pour tout $n \ge N$.

(ii) $a < 0$ ou $a > 0$.

(iii) $a$ est inversible.

*Démonstration.* Supposons (i). Nous pouvons supposer que $|a_N - a_n| < \varepsilon/2$ pour tout $n \ge N$. Si $a_N \ge \varepsilon$, alors $a_n > \varepsilon/2$ pour tout $n \ge N$, donc $a > 0$. De même, si $a_N \le -\varepsilon$, $a < 0$.

Supposons (ii), par exemple $a > 0$. Il existe un $\varepsilon \in \mathbb{Q}^{*+}$ et un $N \in \mathbb{N}$ tels que $a_n > \varepsilon$ pour tout $n \ge N$. Nous pouvons supposer que $a_n > \varepsilon$ pour tout $n \in \mathbb{N}$. Alors la suite $\{1/a_n\}$ est une suite de Cauchy et elle est l'inverse de $a$ dans $\mathbb{R}$.

Finalement supposons (iii). Il existe une suite de Cauchy $\{b_n\}$ telle que $a_n b_n - 1$ converge vers 0. Considérons un $\varepsilon \in \mathbb{Q}^{*+}$ tel que $|b_n| < 1/\varepsilon$ pour tout $n$. Alors $|a_n|$ est plus grand que $\varepsilon$ pour $n$ assez grand. ■

Nous définissons une inégalité sur $\mathbb{R}$ en disant que $a \ne b$ signifie que $b - a$ est inversible, de sorte que le théorème 3.1 nous dit que $a \ne b$ si, et seulement si, $a < b$ ou $b < a$. La cotransitivité de $a < b$ est le substitut constructif de la loi de trichotomie classique.

**Théorème 3.2 (cotransitivité).** *Soient $a, b$ et $c$ des nombres réels. Si $a < c$, alors $a < b$ ou $b < c$.*

*Démonstration.* Considérons $m \in \mathbb{N}$ et $\varepsilon > 0$ tels que $a_m < c_m - 6\varepsilon$ et, pour tout $n \ge m$,

$$ 
\begin{aligned}
& |a_n - a_m| < \varepsilon, \\
& |c_n - c_m| < \varepsilon \text{ et} \\
& |b_n - b_m| < \varepsilon.
\end{aligned}
 $$

Ou bien $b_m < c_m - 3\varepsilon$, auquel cas $b_n < c_n - \varepsilon$ pour tout $n \ge m$, et donc $b < c$, ou bien $b_m > a_m + 3\varepsilon$, auquel cas $b_n > a_n + \varepsilon$ pour tout $n \ge m$, et donc $b > a$. ■

Nous écrivons $a \le b$ lorsque $a < b + \varepsilon$ pour tout $\varepsilon > 0$. Cette relation est clairement transitive et réflexive. Pour démontrer que c'est une relation d'ordre, nous avons besoin du résultat suivant.

**Théorème 3.3.** *Si $a \le b$ et $b \le a$, alors $a = b$.*
**Démonstration.** Soit un $\varepsilon \in \mathbb{Q}^{*+}$. Comme $a \le b$, nous avons un $N \in \mathbb{N}$ tel que $a_n - b_n < \varepsilon$ pour tout $n \ge N$. Comme $b \le a$, nous avons un tel $N$ qui vérifie en outre que $b_n - a_n < \varepsilon$ pour tout $n \ge N$. Cela dit que $|a_n - b_n| < \varepsilon$ pour tout $n \ge N$, et nous avons donc montré que $a_n - b_n$ converge vers 0, ce qui signifie que $a = b$. ■

**Corolaire 3.4.** $\mathbb{R}$ est un corps de Heyting.

**Démonstration.** Si $a + b \ne 0$, ou bien $a + b > 0$, ou bien $a + b < 0$, et nous pouvons supposer que $a + b > 0$. Alors ou bien $a > 0$, ou bien $a < a + b$, en vertu du théorème 3.2; dans le premier cas on a $a \ne 0$, dans le second on a $0 < b$ et donc $b \ne 0$. Ainsi l'inégalité sur $\mathbb{R}$ est cotransitive.

Pour montrer que l'inégalité est étroite, supposons que $a \ne 0$ soit impossible. Pour chaque $\varepsilon > 0$, ou bien $a > 0$, ou bien $a < \varepsilon$ en vertu du théorème 3.2; le premier cas est impossible, donc $a < \varepsilon$. Par suite $a \le 0$. De manière analogue $a \ge 0$, de sorte que $a = 0$ par le théorème 3.3. ■

L'ensemble $\mathbb{R}$ n'est pas seulement un ensemble ordonné, c'est un treillis. Si $a$ et $b$ sont des nombres réels, alors la suite $c_n = \max(a_n, b_n)$ définit un nombre réel $c$ qui est le supremum de $a$ et $b$, ce que l'on écrit $c = \sup(a, b)$. L'infimum de $a$ et $b$ est $\inf(a, b) = -\sup(-a, -b)$. On peut définir la valeur absolue du nombre réel $a$ comme $|a| = \sup(a, -a)$.

Le corps $\mathbb{C}$ des **nombres complexes** est obtenu à partir de l'espace vectoriel $\mathbb{R}^2$ en définissant la multiplication $(a, b)(c, d) = (ac - bd, ad + bd)$. On vérifie facilement que $\mathbb{C}$ est un corps de Heyting avec le neutre multiplicatif (1,0). Nous posons $i = (0, 1)$ et nous voyons que $i^2 = -1$ et que $\mathbb{C} = \mathbb{R} + \mathbb{R}i$.

Un **espace métrique** est un ensemble $S$ donné avec une fonction $d$, appelée la **métrique**, ou encore la **distance**, de $S \times S$ vers $\mathbb{R}$ telle que

$$ (i) \ d(x, y) = d(y, x) \ge 0, $$

$$ (ii) \ d(x, y) = 0 \text{ si, et seulement si, } x = y, $$

$$ (iii) \ d(x, z) \le d(x, y) + d(y, z). $$

Les nombres réels forment un espace métrique pour la distance $d(x, y) = |x - y|$. Une **suite de Cauchy** dans un espace métrique $S$ est une suite $\{x_n\}$ dans $S$ telle que pour tout $\varepsilon \in \mathbb{Q}^{*+}$ il existe un $N \in \mathbb{N}$ tel que

$$ d(x_n, x_m) \le \varepsilon \text{ pour tous } m, n \ge N. $$

Une suite $\{x_n\}$ dans $S$ **converge** vers $y \in S$ si pour tout $\varepsilon \in \mathbb{Q}^{*+}$ il existe un $N \in \mathbb{N}$ tel que $d(x_n, y) \le \varepsilon$ pour tout $n \ge N$. Si $\{x_n\}$ converge vers $y$, nous disons que $y$ est la **limite** de la suite $\{x_n\}$. On vérifie facilement que toute suite convergente est une suite de Cauchy. Si, inversement, toute suite de Cauchy converge vers un élément de $S$, nous disons que l'espace métrique $S$ est **complet**. L'espace $\mathbb{R}$ est complet.
En imitant la construction de $\mathbb{R}$ à partir de $\mathbb{Q}$, nous pouvons immerger
n'importe quel espace métrique $S$ dans sa **complétion** $\hat{S}$, dont les éléments sont
les suites de Cauchy dans $S$, avec $d(a, b)$ égal à la limite de $d(a_n, b_n)$, et en
définissant $a = b$ par $d(a, b) = 0$. L'espace $S$ est **dense** dans $\hat{S}$, i.e. pour tout $\varepsilon$
strictement positif et tout $s \in \hat{S}$, on a un $a \in S$ tel que $d(a, s) < \varepsilon$. L'espace $\hat{S}$
est complet.

Exercices

1. Montrer que $a > b$ est impossible si, et seulement si, $a \le b$.

2. Montrer que les propriétés suivantes sont équivalentes.

(i) Pour tout $a \in \mathbb{R}$, ou bien $a > 0$ ou bien $a \le 0$.

(ii) LPO.

3. Montrer que $\mathbb{R}$ est un treillis distributif pour la relation d'ordre $\le$.

4. Montrer que $|a| \ge 0$, et que $|a|$ est $> 0$ si, et seulement si, $a \ne 0$. Montrer
que $|a+b| \le |a| + |b|$.

5. Montrer que les propriétés suivantes sont équivalentes.

(i) LLPO.

(ii) Pour tout $a \in \mathbb{R}$, ou bien $a \le 0$ ou bien $a \ge 0$.

(iii) Pour tous $a, b \in \mathbb{R}$, si $ab = 0$, alors $a = 0$ ou $b = 0$.

(iv) Si $a, b \in \mathbb{R}$, alors on a un $c \in \mathbb{R}$ tel que $a = cb$ ou $b = ca$.

(v) Pour tous $a, b \in \mathbb{R}$, si $\sup(a, b) = 1$, alors $a = 1$ ou $b = 1$.

6. Montrer que le principe de Markov équivaut à ce que $\mathbb{R}$ soit un corps
par négation.

7. Le corps des nombres $p$-adiques. Si $p$ est un nombre premier, la **métrique $p$-adique sur $\mathbb{Q}$** est définie pour $x_1 \neq x_2$ en posant $d(x_1, x_2) = p^n$ lorsque $p^n(x_1 - x_2)$ peut être écrit avec un numérateur et un dénominateur non divisibles par $p$. Montrer que $d$ est une métrique, et que la complétion de $\mathbb{Q}$ pour cette métrique est un corps de Heyting.

8. Montrer que tout espace métrique est dense dans sa complétion, et que sa complétion est un espace métrique complet.

4 Modules

Si $R$ est un anneau, un $R$-module **à gauche** est un groupe abélien additif $M$
donné avec une fonction $\mu$ de $R \times M$ vers $M$, écrite $\mu(r, a) = ra$, appelée
**multiplication scalaire**, telle que

$$
(i) r(a + b) = ra + rb
$$

$$
(ii) (r + s)a = ra + sa
$$
$$
(iii) \ (rs)a = r(s a)
$$

$$
(iv) \ 1 \cdot a = a
$$

pour tous $r, s \in R$ et $a, b \in M$. Les $R$-modules à droite sont définis de la même manière, à ceci près que la multiplication scalaire est à droite : la seule réelle différence se trouve dans (iii) que l'on doit lire $a(rs) = (ar)s$, de sorte que pour les modules à droite, multiplier par $rs$ est la même chose que d'abord multiplier par $r$ et ensuite multiplier par $s$, tandis que pour les modules à gauche, multiplier par $rs$ est la même chose que multiplier d'abord par $s$ puis par $r$.

Tout groupe abélien est un Z-module. L'ensemble Rn des n-uplets d'éléments de R est un R-module pour l'addition et la multiplication scalaire coordonnée par coordonnée. Si R est un anneau à division, un R-module est appelé un espace vectoriel sur R.

Soient $M$ et $N$ des $R$-modules à gauche. Un homomorphisme de groupes $f$
de $M$ vers $N$ est un **homomorphisme de $R$-modules**, ou **une application $R$-linéaire**, si $f(ra) = rf(a)$ pour tous $r \in R$ et $a \in M$. Le **noyau** de $f$ est
ker $f = \{a \in M : f(a) = 0\}$, et l'**image** de $f$ est im $f = \{f(a) : a \in M\}$. On
vérifie facilement que la catégorie des $R$-modules est une catégorie pré-additive.

L'ensemble E(M) des endomorphismes d'un groupe abélien M forme un
anneau, où la multiplication est la composition des fonctions. Si R est un anneau
et f est un homomorphisme d'anneaux de R vers E(M), alors M peut être muni
d'une structure de R-module en posant rm = f(r)m pour r ∈ R et m ∈ M.
Inversement, si M est un R-module, alors on peut définir un homomorphisme
d'anneaux ϕ de R vers E(M) en posant ϕ(r)(m) = rm. L'homomorphisme ϕ
est appelé une **représentation** de R comme anneau d'endomorphismes de M.
Les représentations et les modules sont deux manières de regarder la même
chose. Si le noyau de la représentation est nul, la représentation est dite **fidèle**.
Un R-module M est fidèle si r = 0 chaque fois que rm = 0 pour tout m ∈ M.

Un sous-groupe *N* d'un *R*-module *M* est un *R-sous-module* si $ra \in N$ pour tous $a \in N$ et $r \in R$. Le sous-module de *M* engendré par un sous-ensemble *X* est le sous-groupe additif engendré par l'ensemble $\{rx : r \in R \text{ et } x \in X\}$. Le groupe quotient $M/N$ est un $R$-module parce que la multiplication scalaire opère sur lui. Les théorèmes 1.1 et 1.2 s'appliquent pour les $R$-modules si nous remplaçons partout « groupe » par « module », et si nous considérons que tous les sous-modules sont normaux (ce qu'ils sont en tant que sous-groupes).

Si $R$ et $S$ sont des sous-anneaux d'un anneau $A$, alors $A$ est, entre autres
choses, un $R$-module à gauche et un $S$-module à droite. Ce genre de situation se
produit suffisamment souvent pour mériter un nom. Soient $R$ et $S$ des anneaux
et soit $M$ un $R$-module à gauche qui est aussi un $S$-module à droite. Alors on dit
que $M$ est un $R$-$S$-bimodule si $(ra)s = r(as)$ pour tous $r \in R$, $a \in M$ et $s \in S$.
Ainsi l'anneau $R$ est un $R$-$R$-bimodule, et tout $R$-module est un $R$-$\mathbb{Z}$-bimodule.
Si $R$ est un anneau commutatif, il n'y a aucune différence entre $R$-modules à
droite et à gauche, et chacun est un *R*-**R**-bimodule.

Les idéaux de $R$ peuvent être décrits en termes des structures de modules sur $R$: un idéal à gauche est un sous-module du module à gauche $R$, un idéal à droite est un sous-module du module à droite $R$, et un idéal bilatère est un sous-module du *R*-**R**-bimodule $R$.

Soient $M$ un $R$-module et $\{A_i\}_{i \in I}$ une famille de sous-modules de $M$. Le sous-module de $M$ engendré par $\bigcup_{i \in I} A_i$ est noté $\sum_{i \in I} A_i$. Les $A_i$ sont dits **indépendants** si lorsque $i_1, \dots, i_n, j \in I$ et $x \in A_j \cap (A_{i_1} + \dots + A_{i_n})$, alors ou bien $x=0$ ou bien $i_m = j$ pour un $m$. Nous disons que $M$ est la **somme directe** (interne) des sous-modules $A_i$, et nous écrivons $M = \bigoplus_{i \in I} A_i$, si $M = \sum_{i \in I} A_i$ avec les $A_i$ indépendants. Si $I = \{1, \dots, n\}$, nous écrivons $M = A_1 \oplus \dots \oplus A_n$. Lorsque $I = \{1, 2\}$, on a $M = A_1 \oplus A_2$ si, et seulement si, $M = A_1 + A_2$ et $A_1 \cap A_2 = 0$. Par exemple, $M = \mathbb{Z}/(6)$, $A_1 = \{0, 2, 4\}$, et $A_2 = \{0, 3\}$.

Le produit d'une famille de $R$-modules $\{A_i\}_{i \in I}$ possède une structure naturelle de $R$-module pour laquelle il est le produit catégorique, ou **produit direct**, des modules $A_i$. Si $f$ et $g$ sont des fonctions dans ce produit, on définit $f + g$ par $(f + g)(i) = f(i) + g(i)$, et $rf$ par $(rf)(i) = rf(i)$. Le produit direct est noté $\prod_{i \in I} A_i$.

Soient $I$ un ensemble discret et $\{A_i\}_{i \in I}$ une famille de $R$-modules. Nous pouvons construire le coproduit catégorique (somme directe externe) de la manière suivante. Un élément $f \in \prod_{i \in I} A_i$ a un **support fini** s'il existe un sous-ensemble fini $J$ de $I$ tel que $f(i) = 0$ pour $i \in I \setminus J$. Pour un ensemble discret $I$, la somme directe externe de la famille $\{A_i\}_{i \in I}$ est l'ensemble des éléments du produit direct qui ont un support fini. On voit facilement que si $f$ et $g$ ont des supports finis, alors il en va de même pour $f + g$ et $rf$, de sorte que la somme directe externe est un sous-module du produit direct. Notez que si $I$ est fini, alors le produit direct et la somme directe externe sont le même module. Si nous identifions le module $A_i$ avec le sous-module $\{f : f(j) = 0 \text{ pour } j \neq i\}$, nous voyons que la somme directe externe est une somme directe.

La construction précédente pose un problème si l'ensemble d'indices $I$ n'est pas discret, parce que si $A_i$ est discret et si $\{f : f(j) = 0 \text{ pour } j \neq i\}$ contient un élément non nul, alors $\{i\}$ est une partie détachable de $I$. Pour construire une **somme directe externe** lorsque l'ensemble d'indices $I$ n'est pas nécessairement discret, on considère l'ensemble $F$ des suites finies d'éléments de la réunion disjointe des $A_i$. Soit alors l'égalité sur $F$ engendrée par

$$ (i) \ (a_1, \dots, a_n) = (a_{\sigma(1)}, \dots, a_{\sigma(n)}) \text{ si } \sigma \text{ est une permutation de } \{1, \dots, n\}. $$

$$ (ii) \ (a_1, \dots, a_{n-1}, a_n) = (a_1, \dots, a_{n-1}) \text{ si } a_n = 0. $$

$$ (iii) \ (a_1, \dots, a_{n-1}, a_n) = (a_1, \dots, a_{n-1} + a_n) \text{ si } a_{n-1} \text{ et } a_n \text{ sont des éléments d'un même } A_i. $$

Plus précisément, disons que deux suites de $F$ sont **adjacentes** lorsqu'une permutation de l'une est obtenue en appliquant (ii) ou (iii) à une permutation
de l'autre. Alors $\sigma$ et $\tau$ sont égales dans $F$ si l'on a une chaine de suites de $F$

$$ \sigma = s_1, s_2, \dots, s_m = \tau $$

telle que $s_i$ est adjacente à $s_{i+1}$ pour $i = 1, \dots, m-1$.

Nous désirons identifier $\{(a) \in F : a \in A_i\}$ avec $A_i$. Pour ce faire nous devons montrer que si $(a) = (b)$, alors $a = b$. Cela est une conséquence de la propriété de Church-Rosser pour $F$.

**Lemme 4.1** (propriété de Church-Rosser). Supposons que les suites $\sigma$ et $\tau$ sont égales dans $F$, et notons $\ell(s)$ la longueur de la suite $s$. Alors il existe une chaine $\sigma = s_1, s_2, \dots, s_m = \tau$ de suites de $F$ telle que $s_i$ est adjacente à $s_{i+1}$ pour $i = 1, \dots, m-1$, et pour $i = 2, \dots, m-1$, si $\ell(s_{i-1}) < \ell(s_i)$, alors $\ell(s_i) < \ell(s_{i+1})$.

*Démonstration.* Soit $\sigma = s_1, s_2, \dots, s_m = \tau$ une chaine de suites de $F$ telle que $s_i$ est adjacente à $s_{i+1}$ pour $i = 1, \dots, m-1$. Nous procédons par récurrence sur $N = \sum_i \ell(s_i)$, en montrant que si $\ell(s_{i-1}) < \ell(s_i)$ et $\ell(s_i) > \ell(s_{i+1})$ pour un $i$, alors nous pouvons diminuer $N$.

Supposons que nous allions de $s_i$ à $s_{i+1}$ en supprimant un zéro $z$. Si $z$ apparaît dans $s_{i-1}$, nous pouvons remplacer $s_i$ par $s_{i-1}$ dans laquelle nous supprimons $z$. Sinon $s_{i-1}$ provient de $s_i$ en supprimant $z$, auquel cas nous pouvons omettre $s_i$. Le même argument s'applique si nous allions de $s_i$ à $s_{i-1}$ en supprimant un zéro.

Supposons que nous allions de $s_i$ à $s_{i+1}$, et de $s_i$ à $s_{i-1}$, en appliquant (iii). Dépendant du nombre de positions distinctes de $s_i$ qui sont concernées, nous pouvons décrire les différents cas comme suit

$$ \begin{array}{ccc} s_{i-1} & s_i & s_{i+1} \\ (a+b) & (a,b) & (a+b) \\ (a+b,c) & (a,b,c) & (a,b+c) \\ (a+b,c,d) & (a,b,c,d) & (a,b,c+d) \end{array} $$

Dans le premier cas nous pouvons omettre $s_i$ et $s_{i+1}$. Dans le second cas, nous pouvons remplacer $s_i$ par $(a+b+c)$, et dans le troisième nous pouvons remplacer $s_i$ par $(a+b,c+d)$. ■

Deux suites de $F$ sont additionnées en les concaténant, la multiplication scalaire est faite coordonnée par coordonnée, et la suite vide sert d'élément neutre. Vu la relation d'égalité nous pouvons de manière sûre et sans ambigüité écrire un élément $(a_1, a_2, \dots, a_n)$ de $F$ comme une somme formelle $a_1 + a_2 + \dots + a_n$.

En identifiant le module $A_i$ avec $\{(a) : a \in A_i\}$, nous voyons que $F$ est somme directe interne des $A_i$; la vérification de cette affirmation téméraire est laissée en exercice 5.

Si $I$ est discret et si $(a_1, \dots, a_n) \in F$, nous pouvons supposer que $a_m \in A_{im}$ avec $i_m \neq i_{m'}$ si $m \neq m'$, et nous pouvons identifier $F$ avec l'ensemble des éléments de $\prod_{i \in I} A_i$ qui ont un support fini, comme précédemment.
Si chaque $A_i$ est un même module $M$ et si $I$ est un ensemble d'indices arbitraire, nous notons la somme directe externe par $M^{(I)}$.

Le théorème suivant dit qu'une somme directe interne (et donc aussi la somme directe externe que nous avons identifiée à une somme directe interne) est un coproduit catégorique.

**Théorème 4.2.** Si $M = \bigoplus_{i \in I} A_i$ et si $f_i: A_i \to N$ est une famille d'applications $R$-linéaires, alors il y a une unique application $R$-linéaire $f$ de $M$ vers $N$ telle que $f = f_i$ sur $A_i$ pour tout $i \in I$.

*Démonstration.* Si $x \in M = \sum_{i \in I} A_i$, alors $x = \sum_{m=1}^n a_{im}$, avec $a_{im} \in A_{im}$. Par suite $f(x)$ doit être égal à $\sum_{m=1}^n f_{im}(a_{im})$, et donc $f$ est unique. Si nous définissons $f(x)$ comme égal à $\sum_{m=1}^n f_{im}(a_{im})$, nous devons montrer que $f(x)$ est bien défini ; il suffit de montrer que si $x = 0$, alors $f(x) = 0$. Supposons que $x = \sum_{m=1}^n a_{im} = 0$. Comme les $A_i$ sont indépendants, ou bien $a_{im} = 0$ pour chaque $m$, ou bien il y a un $m \neq m'$ tel que $i_m = i_{m'}$. Dans le dernier cas, nous pouvons additionner $a_{im}$ et $a_{im'}$ dans $A_{im}$, et par suite $f(x) = 0$ pas récurrence sur $n$. On vérifie facilement que $f$ est une application $R$-linéaire. ■

Un $R$-module $F$ est **libre** sur une famille d'éléments $\{x_i\}_{i \in I}$ de $F$ si pour chaque fonction $f$ qui envoie $I$ dans le $R$-module $M$, il y a une unique application $R$-linéaire $f^*$ de $F$ vers $M$ telle que $f^*(x_i) = f(i)$. Nous disons que $\{x_i\}_{i \in I}$ est une **base** pour $F$. L'unicité de $f^*$ implique que des modules libres sur $\{x_i\}_{i \in I}$ et sur $\{y_i\}_{i \in I}$ sont isomorphes pour un isomorphisme qui envoie $x_i$ sur $y_i$, de sorte que des modules libres dont les bases ont le même ensemble d'indices sont essentiellement les mêmes. Si $F = \bigoplus_{i \in I} R x_i$ et si la fonction de $R$ vers $Rx_i$ qui envoie $r$ sur $rx_i$ est un isomorphisme pour chaque $i \in I$, le théorème 4.2 montre que $F$ est libre sur $\{x_i\}_{i \in I}$. Si $R$ est un anneau non trivial, alors $x_i \neq 0$ pour chaque $i \in I$, de sorte que si $x_i = x_j$, alors $i = j$ ; ainsi les éléments $x_i$ de la base sont en correspondance bijective avec les éléments $i$ de $I$. Ainsi lorsque nous nous restreignons aux anneaux non triviaux, nous pourrons définir une base comme un ensemble plutôt que comme une famille. Si $R$ est un anneau trivial, alors toute famille d'éléments de n'importe quel $R$-module $M$ est une base pour $M$.

Soit $I$ un ensemble discret, et pour chaque $i \in I$ soit $\delta_i \in R^{(I)}$ tel que $\delta_i(i) = 1$ et $\delta_i(j) = 0$ pour $j \neq i$. Alors $R^{(I)}$ est libre sur $\{\delta_i\}_{i \in I}$. Pareillement, supposons que $I$ est un ensemble d'indices arbitraire, et que $\{R_i\}_{i \in I}$ est une famille telle que chaque $R_i$ est une copie de $R$. Si pour chaque $i \in I$ nous définissons $x_i$ comme la suite de longueur 1 dont l'élément est le neutre multiplicatif de $R_i$, alors $R^{(I)}$ est libre sur $\{x_i\}_{i \in I}$. Par abus de langage nous dirons que $R^{(I)}$ est le **module libre sur I**.

Si $I = \{1, \dots, n\}$, alors nous écrivons $R^n$ au lieu de $R^{(I)}$. Un module $M$ possède une base de $n$ éléments si, et seulement si, il est isomorphe à $R^n$, auquel cas nous disons que $M$ est un **module libre de rang** $n$. Dans la section 6 nous
verrons que pour un anneau commutatif non trivial $R$, le rang de $M$ est un invariant. L'exercice 3 donne un exemple d'un anneau non commutatif non trivial $R$ tel que les $R$-modules à gauche $R$ et $R^2$ sont isomorphes.

Un $R$-module $M$ est **de type fini** s'il existe une application $R$-linéaire surjective de $R^n$ sur $M$ pour un $n$ strictement positif ; c'est-à-dire s'il existe des éléments $x_1, \dots, x_n$ de $M$ tels que tout élément de $M$ peut s'écrire sous la forme $\sum_{i=1}^n r_i x_i$. Un $R$-module $M$ est **cyclique** s'il existe une application $R$-linéaire surjective de $R$ sur $M$ ; c'est-à-dire s'il existe un $x \in M$ tel que tout élément de $M$ est un multiple scalaire de $x$.

**Théorème 4.3.** Soit $R$ un sous-anneau d'un anneau $E$. Si $M$ est un $E$-module de type fini (libre de rang $n$) et si $E$ est un $R$-module de type fini (libre de rang $m$), alors $M$ est un $R$-module de type fini (libre de rang $mn$).

*Démonstration.* Soient $\varphi: R^m \to E$ un épimorphisme (isomorphisme) de $R$-modules et $\psi: E^n \to M$ un épimorphisme (isomorphisme) de $E$-modules. Alors $\varphi^n: R^{mn} \to E^n$ est un épimorphisme (isomorphisme) de $R$-modules, et $\psi\varphi^n: R^{mn} \to M$ est un épimorphisme (isomorphisme) de $R$-modules. ■

Un $R$-module $P$ est dit **projectif** si pour toute application $R$-linéaire $g$ d'un $R$-module $A$ sur un $R$-module $B$, et toute application $R$-linéaire $f$ de $P$ vers $B$, il existe une application $R$-linéaire $h: P \to A$ telle que $gh = f$. Les modules libres de rang fini sont projectifs : si $x_1, \dots, x_n$ est une base de $P$, alors il existe $a_1, \dots, a_n \in A$ tels que $g(a_i) = f(x_i)$ pour chaque $i$, et on a une application $R$-linéaire $h$ telle que $h(x_i) = a_i$ pour chaque $i$ ; les applications $R$-linéaires $gh$ et $f$ sont égales parce qu'elles coïncident sur la base.

Soit $M$ un $R$-module de type fini. Si $\pi$ est un épimorphisme d'un $R$-module libre de rang fini $F$ sur $M$, de noyau $K$, alors $M$ est isomorphe à $F/K$. Le théorème suivant montre ce qu'il advient lorsque nous obtenons la même chose pour d'autres couples $(F, \pi)$ ; le résultat ressemble à la règle pour déterminer quand deux fractions sont égales.

**Théorème 4.4** (l'astuce de Schanuel). Soient $M$ un $R$-module, $P_1$ et $P_2$ des $R$-modules projectifs, et $\pi_i$ une application $R$-linéaire de $P_i$ sur $M$ ($i = 1, 2$). Si $K_i$ est le noyau de $\pi_i$, alors $K_1 \oplus P_2$ est isomorphe à $K_2 \oplus P_1$.

*Démonstration.* Comme les modules $P_i$ sont projectifs, nous avons des applications $R$-linéaires $\varphi_1: P_2 \to P_1$ et $\varphi_2: P_1 \to P_2$ qui vérifient $\pi_1\varphi_1 = \pi_2$ et $\pi_2\varphi_2 = \pi_1$. Considérons l'application $R$-linéaire de $K_1 \oplus P_2$ vers $K_2 \oplus P_1$ qui envoie $(k_1, p_2)$ sur $(k_2, p_1)$ où

$$k_2 = p_2 - \varphi_2(k_1 + \varphi_1 p_2), \quad p_1 = k_1 + \varphi_1 p_2$$

et l'application $R$-linéaire de $K_2 \oplus P_1$ vers $K_1 \oplus P_2$ qui envoie $(k_2, p_1)$ sur $(k_1, p_2)$ où

$$k_1 = p_1 - \varphi_1(k_2 + \varphi_2 p_1), \quad p_2 = k_1 + \varphi_2 p_1$$
On vérifie facilement que ces applications $R$-linéaires sont inverses l'un de l'autre. $\blacksquare$

Un élément $e$ d'un anneau est **idempotent** si $e^2 = e$. Un sous-module $A$ de $M$ est un **facteur direct** de $M$ s'il existe un sous-module $B$ de $M$, appelé un **supplémentaire** de $A$ dans $M$, tel que $M = A \oplus B$. Les sous-modules $0$ et $M$ de $M$ sont toujours facteurs directs supplémentaires l'un de l'autre.

**Théorème 4.5.** Soit $A$ un sous-module d'un $R$-module $M$. Alors $A$ est un facteur direct de $M$ si, et seulement si, il y a un endomorphisme idempotent $e$ de $M$ tel que $A = eM$. Dans ce cas le sous-module $(1-e)M$ et un supplémentaire de $A$.

*Démonstration.* Supposons que $M = A \oplus B$. Si $x \in M$, nous pouvons écrire $x$ de manière unique sous la forme $a + b$ pour un $a \in A$ et un $b \in B$. On définit un endomorphisme $e$ de $M$ en posant $e(x) = a$. On voit facilement que $e$ est idempotent et que $eM = A$.

Inversement, supposons que $e$ est un endomorphisme idempotent de $M$ et que $A = eM$. Posons $B = (1-e)M$. Comme $x = ex + (1-e)x$, nous avons $A+B = M$. Si $x \in A \cap B$, alors $x = (1-e)y$ et $x = ez$. Donc $ex = e(1-e)y = (e-e^2)y = 0$ et $ex = e^2z = ez = x$, de sorte que $x = 0$. Ainsi $A \cap B = 0$. $\blacksquare$

L'idempotent $e$ dans le théorème 4.5 est appelé la **projection** de $M$ sur $A$ (parallèlement à $B$).

Exercices

1. L'**anneau opposé** $R^{op}$ d'un anneau $R$ est formé avec le groupe additif $R$ et la multiplication $ab \in R^{op}$ définie comme le produit $ba$ de $R$. Montrer que tout $R$-module à gauche est un $R^{op}$-module à droite de manière naturelle. Si $R$ est un anneau commutatif, l'anneau opposé est isomorphe à $R$, donc tout $R$-module à gauche est aussi un $R$-module à droite, et il n'est pas nécessaire de distinguer entre $R$-modules à gauche et à droite.

2. Soit $R$ un anneau et soit $M$ un $R$-module. Montrer qu'il existe un homomorphisme surjectif d'un $R$-module libre sur $M$.

3. Soient $A$ et $B$ des espaces vectoriels sur un corps discret $k$, chacun avec une base dénombrable infinie. Soit $V = A \oplus B$ et soit $R$ l'anneau des endomorphismes de $V$. Construire un $x \in R$ tel que $xA = 0$ et $x : B \to V$ est un isomorphisme, et un $y \in R$ tel que $yB = 0$ et $y : A \to V$ est un isomorphisme. Montrer que $Rx \simeq Ry \simeq R$ comme $R$-modules, et que $R = Rx \oplus Ry$. Que nous dit cet exercice ?

4. Soient $M$ un $R$-module et $\{A_i\}_{i \in I}$ une famille de $R$-modules. Soit $\{f_i\}_{i \in I}$ une famille d'homomorphismes de $R$-modules telle que $f_i$ envoie $M$ dans
$A_i$. Soit $\pi_i$ la projection de $\prod_{i \in I} A_i$ vers $A_i$. Montrer qu'il existe une unique application $R$-linéaire $f$ de $M$ vers $\prod_{i \in I} A_i$ telle que $\pi_i f = f_i$ pour chaque $i \in I$.

5. Soit $F$ la somme directe externe de la famille $\{A_i\}_{i \in I}$, pour un ensemble d'indices arbitraire $I$. Montrer que l'homomorphisme de $A_i$ vers $F$ défini en envoyant $a \in A_i$ sur la suite $(a)$ définie avant le lemme 4.1 est un monomorphisme. Montrer que si nous identifions $A_i$ avec son image par ce monomorphisme, alors $F = \bigoplus_{i \in I} A_i$.

6. Un facteur n'est pas nécessairement facteur direct. Soit $a$ une suite binaire fugitive, et soit $S = \{0, s, 2s, t, 2t\}$ avec
   — $s = t$ et $2s = 2t$ si $a_n = 1$ pour un entier pair $n$,
   — $s = 2t$ et $2s = t$ si $a_n = 1$ pour un entier impair $n$.

Soit $I = \{x, y\}$ avec $x = y$ si $a_n = 1$ pour un $n$. Enfin soient $A_x = \{0, s, 2s\}$ et $A_y = \{0, t, 2t\}$ avec leurs structures évidentes de groupes à trois éléments. Montrer que l'on obtient ainsi un exemple brouwerien (LLPO) avec $A_x$ qui n'est pas facteur direct dans $\bigoplus_{i \in I} A_i$.

7. Soient $\{A_i\}_{i \in I}$ une famille de modules et $f_i : A_i \to A$ une famille d'isomorphismes. Montrer que le noyau de l'homomorphisme $f : \bigoplus_{i \in I} A_i \to A$ induit par les isomorphismes $f_i$ est un supplémentaire de chaque sous-module $A_i$.

8. Montrer que $A \oplus B$ est projectif si, et seulement si, $A$ et $B$ sont projectifs. Construire un module projectif à deux éléments sur l'anneau $\mathbb{Z}/(6)$.

9. Montrer qu'un module libre sur un ensemble projectif (voir l'exercice I.3.4) est projectif. Quel est le module libre sur un ensemble vide ?

10. Les modules libres ne sont pas nécessairement projectifs. Construire un exemple brouwerien pour une application $R$-linéaire $\alpha$ depuis un module $F_1$ libre de rang 2 sur un module libre $F_2$ tel qu'il n'y a pas d'application $R$-linéaire $\varphi$ de $F_2$ vers $F_1$ avec $\alpha\varphi$ égal à l'application identique sur $F_1$. Suggestion : soient $F_2$ et $F_1$ des $k$-modules libres sur les ensembles $A$ et $B$ de l'exemple 3.1, où $k$ est l'anneau des entiers modulo 2.

11. Montrer que si les modules libres sur des bases discrètes sont projectifs, alors l'axiome du choix le plus simple du monde est valide.

12. Soient $I$ un ensemble discret et $\varphi$ un homomorphisme non trivial de $\mathbb{Z}$-modules, de $\mathbb{Z}^{(I)}$ vers $\mathbb{Z}$. Montrer que ker $\varphi$ est un facteur direct de $\mathbb{Z}^{(I)}$ si, et seulement si, im $\varphi$ est cyclique. Construire un exemple brouwerien d'un homomorphisme $\varphi$ (pas nécessairement non trivial) tel que ker $\varphi$ est facteur direct mais im $\varphi$ n'est pas cyclique.
# 5 Anneaux de polynômes

Si $M$ est un monoïde et $R$ un anneau, notons $R^{(M)}$ le $R$-module libre sur l'ensemble $M$. Nous pouvons voir les éléments de $R^{(M)}$ comme des sommes formelles finies $r_1m_1 + \cdots + r_nm_n$ avec les $m_i \in M$ et les $r_i \in R$. Définissons le produit de deux éléments de $R^{(M)}$ par

$$ \left( \sum_{i=1}^{n} r_i m_i \right) \left( \sum_{j=1}^{n'} r'_j m'_j \right) = \sum_{i=1}^{n} \sum_{j=1}^{n'} (r_i r'_j) (m_i m'_j). $$

Le produit $m_i m'_j$ est le produit dans le monoïde $M$, tandis que $r_i r'_j$ est le produit dans l'anneau $R$. Cela fait de $R^{(M)}$ un anneau, que l'on appelle **la R-algèbre du monoïde** $M^1$, avec pour élément neutre multiplicatif $1 = 1_R 1_M$. Si $M$ est un groupe, alors $R^{(M)}$ est **la R-algèbre du groupe** $M^2$. La fonction qui envoie $r$ sur $r1$ est un isomorphisme de $R$ sur un sous-anneau de $R^{(M)}$, et nous pouvons voir $R$ comme un sous-ensemble de $R^{(M)}$ défini par cette immersion, autrement dit, l'élément $r1$ sera noté $r$ et $1$ sera identifié à $1_R$.

Soit $M$ le monoïde libre sur l'ensemble à un élément $\{X\}$. Alors

$$ R^{(M)} = \{ r_0 + r_1 X + \cdots + r_n X^n : r_i \in R \text{ et } n \in \omega \}. $$

L'élément $X$ est appelé une **indéterminée** et les éléments de $R^{(M)}$ sont appelés des **polynômes**. L'algèbre $R^{(M)}$ est notée $R[X]$ et on l'appelle l'**anneau de polynômes**$^3$ en (l'indéterminée) $X$ (sur $R$).

L'anneau des polynômes en $n$ indéterminées, $R[X_1, \dots, X_n]$ est défini de manière inductive comme $R[X_1, \dots, X_{n-1}][X_n]$. Un élément de $R[X_1, \dots, X_n]$ écrit sous la forme $X_1^{e_1} \cdots X_n^{e_n}$ est appelé un **monôme** de **degré** $\sum_{i=1}^n e_i$. Si l'anneau $R$ est discret, alors le **degré (total)** d'un polynôme non nul $f \in R[X_1, \dots, X_n]$ est le maximum des degrés des monômes qui apparaissent dans $f$ avec un coefficient non nul. L'anneau $R[X_1, \dots, X_n]$ est le $R$-module libre sur l'ensemble des monômes; en fait, les monômes forment un monoïde commutatif, et $R[X_1, \dots, X_n]$ est la $R$-algèbre de ce monoïde.

Si $R$ est un sous-anneau d'un anneau commutatif $S$, un polynôme $f \in R[X_1, \dots, X_n]$ définit une fonction de $S^n$ vers $S$: si $a_1, \dots, a_n$ sont des éléments de $S$, nous définissons $f(a_1, \dots, a_n)$ comme le résultat de la substitution des $a_i$ aux $X_i$ dans l'expression formelle de $f$, et en interprétant les opérations formelles dans $R[X_1, \dots, X_n]$ comme des opérations dans $S$. Nous demandons la commutativité parce que les indéterminées commutent les unes avec les autres ainsi qu'avec les éléments de $R$. Comme les $a_i$ commutent entre eux, ainsi qu'avec les éléments de $R$, la fonction qui envoie $f$ sur $f(a_1, \dots, a_n)$ est un homomorphisme d'anneaux.

<footnote n="1">1. NdT. Monoid ring.</footnote>

<footnote n="2">2. NdT. Group ring.</footnote>

<footnote n="3">3. NdT. Polynomial ring.</footnote>
Pour $n \in \mathbb{N}$, un polynôme $f \in R[X]$ qui peut être écrit sous la forme $\sum_{i=0}^{n-1} r_i X^i$ est dit être de **degré au plus** $n-1$, ce que l'on écrit deg $f \le n-1$, ou deg $f < n$. Un polynôme est nul si, et seulement si, il a un degré au plus $-1$. Si deg $f \le d$ et si $r_d = 1$, nous disons que $f$ est **unitaire**. Notez que ces définitions ne font pas référence à une inégalité sur $R$. Si $r_i \ne 0$ pour un $i \ge d$, nous disons que $f$ est de **degré au moins** $d$, ce que l'on écrit deg $f \ge d$. Si deg $f \le d$ et deg $f \ge d$, nous disons que $f$ est de **degré** $d$, et l'on écrit deg $f = d$; dans ce cas nous disons que $r_d$ est le **coefficient dominant** de $f$. Si $R$ n'est pas discret, alors $f$ n'a pas nécessairement un degré, même s'il a un coefficient non nul.

Si $f$ et $g$ sont des polynômes, nous écrivons deg $f \le deg g$ si deg $g < n$ implique deg $f < n$ pour tout $n \in \mathbb{N}$; et nous écrivons deg $f < deg g$ si deg $g < n+1$ implique deg $f < n$ pour tout $n \in \mathbb{N}$. Notez que si $g = X^n + r_{n-1}X^{n-1} + \cdots + r_0$, alors deg $f \le deg g$ si, et seulement si, deg $f \le n$, y compris si l'anneau est trivial.

**Théorème 5.1.** Soient $k$ un corps et $f, g \in k[X]$. Si deg $f = m$ et deg $g = n$, alors deg $fg = m + n$.

**Démonstration.** Soient $a$ le coefficient dominant de $f$ et $b$ le coefficient dominant de $g$. Alors $ab$ est le coefficient dominant de $fg$, et deg $fg = \text{deg } f + \text{deg } g$. ■

**Théorème 5.2 (algorithme de division).** Soit $R$ un anneau commutatif et soient $f, g \in R[X]$ des polynômes tels que deg $f \le m$ et deg $g \le n \le m + 1$. Soit $a$ le coefficient de $X^n$ dans $g$. Il existe des polynômes $q, r \in R[X]$ tels que $a^{m-n+1}f = qg + r$ et deg $r \le n - 1$.

**Démonstration.** Nous procédons par récurrence sur $m-n$. Si $m-n = -1$, on prend $q=0$ et $r=f$. Si $m-n \ge 0$ et $f = b_0 + b_1X + \cdots + b_mX^m$, posons $f_1 = af - b_mX^{m-n}g$. Alors deg $f_1 \le m-1$, donc par récurrence $a^{m-n}f_1 = q_1g + r$ pour un couple $(q_1, r)$ de $R[X]$ avec deg $r \le n-1$. Ainsi $a^{m-n+1}f = (q_1 + a^{m-n}b_mX^{m-n})g + r$. ■

Si le diviseur $g$ est unitaire, ce que l'on peut supposer lorsque $R$ est un corps discret, l'algorithme de division a une forme beaucoup plus agréable.

**Corolaire 5.3.** Soient $f, g \in R[X]$ des polynômes sur un anneau commutatif $R$ avec $g$ unitaire. Alors il y a un unique couple $(q, r)$ de $R[X]$ tel que $f = qg + r$ et deg $r < \text{deg } g$.

**Démonstration.** Par le théorème 5.2 on a $q$ et $r \in R[X]$, avec deg $r < \text{deg } g$, tel que $f = qg + r$. Pour démontrer l'unicité, on suppose que $f = q_1g + r_1$ avec deg $r_1 < \text{deg } g$. Alors $(q-q_1)g = r_1 - r$ et deg$(r_1-r) < \text{deg } g$, donc $q-q_1=0$ parce que $g$ est unitaire (par récurrence sur l'entier $n$ tel que deg$(q-q_1) \le n$), et ainsi $r_1-r=0$. ■
**Corolaire 5.4** (théorème du reste<fnref n="1" />). Soient $f \in R[X]$ un polynôme sur un anneau commutatif $R$, et $a$ un élément de $R$. Alors il existe un unique $q \in R[X]$ tel que $f(X) = q(X)(X-a) + f(a)$.

*Démonstration.* Par le théorème 5.2 il existe $q \in R[X]$ et $r \in R$ uniques tels que $f(X) = q(X)(X-a) + r$. Mais alors $f(a) = q(a)(a-a) + r = r$. ■

Sur un corps donné, nous pouvons construire un polynôme de degré au plus $n$ qui prend des valeurs prescrites en $n+1$ points distincts. Le théorème du reste montre que ce polynôme est unique, de sorte qu’un polynôme de degré au plus $n$ ne peut pas avoir $n+1$ racines distinctes. Ceci est l’un des quelques résultats dans la théorie générale des corps (comme opposés aux corps discrets ou aux corps de Heyting).

**Théorème 5.5** (interpolation unique). Soient $a_0, \dots, a_n$ des éléments deux à deux distincts dans un corps $k$, et soient $n+1$ éléments $v_0, \dots, v_n$ de $k$. Alors il existe un unique polynôme $f \in k[X]$ de degré au plus $n$ tel que $f(a_i) = v_i$ pour chaque $i$.

*Démonstration.* Nous démontrons l’existence par récurrence sur $n$. Si $n=0$, prenons $f = v_0$. Si $n > 0$, alors par hypothèse de récurrence, on a un polynôme $g$ de degré au plus $n-1$ tel que $g(a_i) = (v_i - v_0)/(a_i - a_0)$ pour $1 \le i \le n$. Prenons $f(X) = (X - a_0)g(X) + v_0$.

Pour démontrer l’unicité, il suffit de montrer que si $f$ est un polynôme de degré au plus $n$ et si $f(a_i) = 0$ pour chaque $i$, alors $f = 0$. Nous procédons par récurrence sur $n$. Si $n=0$, alors $f$ est une constante, donc $f=0$ parce que $f(a_0) = 0$. Supposons $n > 1$. Par le théorème du reste, nous pouvons écrire $f(X) = (X - a_n)g(X)$, où $\deg g \le n-1$. Comme $a_j \ne a_n$ pour $j < n$ et comme $k$ est un corps, nous obtenons que $g(a_j) = 0$ pour $j < n$, donc $g = 0$ par récurrence. Par suite $f=0$. ■

La démonstration du théorème 5.5 donne une construction par récurrence des coefficients $\lambda_i$ de la **formule d'interpolation de Newton**

$$f = \lambda_0 + \lambda_1(X - a_0) + \lambda_2(X - a_0)(X - a_1) + \dots + \lambda_n(X - a_0)(X - a_1) \dots (X - a_{n-1}).$$

Pour la **formule d'interpolation de Lagrange**, voir l'exercice 5.

Nous établissons l’algorithme d’Euclide pour les anneaux commutatifs discrets avec unités détachables, plutôt que seulement pour les corps discrets. L’algorithme construit le facteur commun recherché ou une non-unité non nulle. Une application typique est avec l’anneau $k[X]/(f)$, où $k$ est un corps discret : la construction d’une non-unité non nulle donne une factorisation de $f$.

<footnote n="1">1. NdT. Remainder theorem.</footnote>
**Théorème 5.6** (algorithme d'Euclide<fnref n="1" />). *Soient R un anneau commutatif discret avec unités détachables et I un idéal de type fini de R[X]. Ou bien l'idéal I est principal, ou bien il existe un élément de R non inversible et non nul.*

*Démonstration.* Ou bien $I = 0$, et alors $I$ est principal, ou bien il y a un $n \in \mathbb{N}$ et un polynôme non nul $f \in I$ de degré $\deg f = n$. Nous pouvons supposer que $f$ est unitaire (sinon nous avons une non-unité non nulle) et nous procédons par récurrence sur $n$. Si $n = 0$, alors $f = 1$, et donc $I = k[X] = (f)$. Si $n > 0$, alors chaque générateur $g$ de $I$ peut s'écrire comme $g = qf + r$ avec $\deg r < n$. Notons que $r \in I$. Ou bien chaque $r$ est nul, ou bien l'un des $r$ est $\neq 0$. Si chaque $r$ est nul, alors $I = (f)$. Si un $r$ est $\neq 0$, alors nous avons un polynôme non nul dans $I$ de degré $< n$, et nous terminons par récurrence. ■

Si $c = ab$ dans un anneau commutatif, alors nous disons que **a** **divise** $c$; si **a** **divise** $c$ nous disons que **a** est un **diviseur**, ou un **facteur**, de $c$.

**Corolaire 5.7.** *Soient $k$ un corps discret et $a, b \in k[X]$. Alors il existe $s, t \in k[X]$ tels que $sa + tb$ divise $a$ et $b$. Par suite $sa + tb$ est le plus grand commun diviseur de $a$ et $b$ au sens où tout diviseur commun de $a$ et $b$ divise $sa + tb$.*

*Démonstration.* Soit $I$ l'idéal de $k[X]$ engendré par $a$ et $b$. Comme $k$ est un corps discret, le théorème 5.6 dit que $I$ est principal; autrement dit il existe $s$ et $t$ tels que $sa + tb$ divise $a$ et $b$. ■

Nous disons que deux éléments $a$ et $b$ dans un anneau commutatif sont **étrangers**<fnref n="2" /> ou **fortement premiers entre eux** s'il existe des éléments $s$ et $t$ tels que $sa + tb = 1$. Ainsi le corolaire 5.7 implique que si deux polynômes sur un corps discret n'ont pas de facteur commun de degré strictement positif, ils sont étrangers. On voit facilement que si $a$ et $b$ sont étrangers et si $a$ et $c$ sont étrangers, alors $a$ et $bc$ sont étrangers (multiplier les deux équations).

Exercices

1. Soient $R$ et $S$ des anneaux commutatifs, $\varphi$ un homomorphisme d'anneaux de $R$ vers $S$, et $s_1, \dots, s_n$ des éléments de $S$. Montrer que $\varphi$ admet une unique extension en un homomorphisme de $R[X_1, \dots, X_n]$ vers $S$ qui envoie $X_i$ sur $s_i$.

2. Un anneau **intègre** avec relation de séparation (**étroite**) est un anneau intègre dont l'inégalité est une relation de séparation (**étroite**). Montrer que le corps de fractions d'un anneau intègre avec relation de séparation

<footnote n="1">1. **NdT.** L'algorithme d'Euclide est presque toujours utilisé sous la forme du corollaire 5.7, pour le cas où $R$ est un corps discret. Voir cependant la démonstration du lemme IX.3.5.</footnote>

<footnote n="2">2. **NdT.** Strongly relatively prime.</footnote>
étroite est un corps de Heyting. Soient $f$ et $g$ des polynômes sur un
anneau intègre avec relation de séparation $R$. Montrer que si deg $f \ge i$
et deg $g \ge j$, alors deg $fg \ge i + j$. Utiliser ce résultat pour montrer que
si $R$ est un anneau intègre avec relation de séparation (étroite), alors il
en va de même pour $R[X]$.

3. Soit $R$ un anneau. L'**anneau des séries formelles**<fnref n="1" /> $R[[X]]$ est défini comme l'ensemble des suites $\{a_n\}$ dans $R$, écrites sous la forme

$$
a_0 + a_1 X + a_2 X^2 + \dots,
$$

avec l'addition et la multiplication suggérées par la notation. Montrer
que si $R$ est un anneau intègre avec relation de séparation, il en va de
même pour $R[[X]]$.

Idée. Supposez que $R$ est un anneau intègre avec relation de séparation et que $fg = h \in R[[X]]$ avec

$$
f = f_0 + f_1 X + \dots,
$$

$$
g = g_0 + g_1 X + \dots,
$$

$$
h = h_0 + h_1 X + \dots.
$$

Supposez que $f_i \neq 0$ et $g_j \neq 0$ pour un $i, j$; montrez que $h_k \neq 0$ pour un $k \le i + j$.

4. Interpolation de Lagrange. Montrer que le polynôme suivant satisfait le théorème 5.5.

$$
f(X) = \sum_{i=0}^{n} v_i \prod_{j \neq i} \frac{X - \alpha_j}{\alpha_i - \alpha_j}.
$$

5. Soit $k$ un corps de Heyting et soit $f \in k[X]$ un polynôme non nul de degré au plus $m$. Montrer que si $a_0, a_1, \dots, a_m$ sont des éléments distincts de $k$, alors il existe un $i$ tel que $f(a_i) \neq 0$.

6. Soit $k$ un corps de Heyting et soit $f \in k[X_1, \dots, X_n]$ un polynôme non nul de degré au plus $m$ en chaque variable séparément. Montrer que si $k$ contient $m+1$ éléments distincts, alors $f(a_1, \dots, a_n) \neq 0$ pour des $a_i \in R$.

7. Soit $k$ un corps discret. Montrer que tout idéal premier propre non nul de $k[X]$ est maximal.

8. Soit $f$ un polynôme non nul sur un corps discret $k$ et soit $a \in k$. Montrer qu'il existe un unique entier naturel $n$ et un unique polynôme $u \in k[X]$ tels que $f(X) = (X-a)^n u(X)$ et $u(a) \neq 0$. Si $n=1$, $a$ est appelé une **racine simple** de $f$; si $n > 1$, $a$ est appelé une **racine de multiplicité** $n$.

<footnote n="1">1. NdT. Formal power series ring.</footnote>
9. Donner un polynôme de degré 2 sur l'anneau des entiers modulo 6 avec 3 racines distinctes. Faire la même chose pour les quaternions rationnels.

10. Donner un contre-exemple brouwerien pour l'affirmation selon laquelle deg $f \le deg g$ ou $deg g \le deg f$ pour tous les polynômes $f$ et $g$ sur un anneau commutatif.

# 6 Matrices et espaces vectoriels

Soit $\alpha$ une application $R$-linéaire depuis un $R$-module à droite libre $N$ vers un $R$-module à droite libre $M$. Si $e_1, \dots, e_n$ est une base pour $N$ et $f_1, \dots, f_m$ est une base pour $M$, alors $\alpha$ détermine, et est déterminé par, la matrice $A = \{a_{ij}\}$ de format $m \times n$ telle que

$$ \alpha(e_j) = \sum_{i=1}^{m} f_i a_{ij}. $$

Si $\beta$ est un homomorphisme d'un $R$-module libre $L$ de base $d_1, \dots, d_\ell$ vers $N$, alors nous obtenons une matrice $B = \{b_{jk}\}$ de format $n \times \ell$ telle que

$$ \beta(d_k) = \sum_{j=1}^{n} e_j b_{jk}. $$

Ainsi

$$ \alpha\beta(d_k) = \alpha \sum_{j=1}^{n} e_j b_{jk} = \sum_{j=1}^{n} \alpha(e_j)b_{jk} = \sum_{j=1}^{n} \sum_{i=1}^{m} f_i a_{ij} b_{jk}, $$

de sorte que la matrice qui correspond à $\alpha\beta$ est la **matrice produit AB**, qui est une matrice de format $m \times \ell$ dont l'entrée $ik$ est $\sum_{j=1}^{n} a_{ij}b_{jk}$. Si nous considérons les applications $R$-linéaires de $N$ vers $N$, nous obtenons un isomorphisme entre l'anneau $E_R(N)$ des endomorphismes du $R$-module à droite libre $N$ et l'anneau $\mathrm{Mat}_n(R)$ des matrices de format $n \times n$ sur l'anneau $R$. La matrice qui correspond à l'endomorphisme identité est appelée une **matrice identité** et on la note I.

Si $e'_1, \dots, e'_n$ est une autre base pour $N$, et $f'_1, \dots, f'_m$ est une autre base pour $M$, notons $\sigma$ et $\tau$ les automorphismes de $N$ et $M$ définis par $\sigma(e_j) = e'_j$, et $\tau(f_i) = f'_i$, et soient $S$ et $T$ les matrices de $\sigma$ et $\tau$ par rapport aux anciennes bases. Alors la matrice de $\alpha$ par rapport aux nouvelles bases est donnée par

$$ \alpha(e'_j) = \alpha(\sigma e_j) = \alpha\left(\sum_i e_i s_{ij}\right) = \sum_{i,k} f_k a_{ki} s_{ij} = \sum_{i,k} \tau^{-1}(f'_k) a_{ki} s_{ij} $$

Ainsi $\tau\alpha(e'_j) = \sum_{ik} f'_k a_{ki} s_{ij}$, et donc la nouvelle matrice de $\tau\alpha$ est $AS$, et la nouvelle matrice de $\alpha$ est $T^{-1}AS$, où $T^{-1}$ est la matrice de $\tau^{-1}$.

La $i$-ième **ligne** ($a_{i1}, \dots, a_{in}$) de $A$ peut être considérée comme un élément du $R$-module à gauche $R^n$. L'espace des lignes de $A$ est le sous-module de $R^n$
engendré par les lignes de $A$. Une **manipulation élémentaire de lignes**<fnref n="1" /> sur $A$ consiste à

(i) échanger deux lignes, ou

(ii) multiplier une ligne par une unité de $R$, ou

(iii) ajouter un multiple d'une ligne à une autre ligne.

La matrice qui est obtenue à partir d'une manipulation élémentaire de lignes de $A$ est la matrice de $\alpha$ par rapport à une autre base de $M$. Celle obtenue en échangeant les lignes $s$ et $t$ de $A$ est la matrice de $\alpha$ si nous échangeons les éléments de base $f_s$ et $f_t$. Celle obtenue en multipliant la ligne $s$ de $A$ par l'unité $u$ est la matrice de $\alpha$ si nous remplaçons l'élément de base $f_s$ par $f_s u^{-1}$. Celle obtenue en ajoutant $r$ fois la ligne $s$ à la ligne $t$ est la matrice de $\alpha$ si nous remplaçons l'élément de base $f_s$ par $f_s - f_t r$. L'espace des lignes de $A$ est inchangé par les manipulations élémentaires de lignes.

La $j$-ième colonne $(a_{1j}, \dots, a_{mj})$ de $A$ peut être considérée comme un élément du $R$-module à droite $R^m$. Une **manipulation élémentaire de colonnes**<fnref n="2" /> sur $A$ consiste à

(i) échanger deux colonnes, ou

(ii) multiplier une colonne par une unité de $R$, ou

(iii) ajouter un multiple d'une colonne à une autre colonne.

La matrice qui est obtenue à partir d'une manipulation élémentaire de colonnes de $A$ est la matrice de $\alpha$ par rapport à une autre base de $M$. Celle obtenue en échangeant les colonnes $s$ et $t$ de $A$ est la matrice de $\alpha$ si nous échangeons les éléments de base $e_s$ et $e_t$. La matrice obtenue en multipliant (à droite) la colonne $s$ de $A$ par l'unité $u$ est la matrice de $\alpha$ si nous remplaçons l'élément de base $e_s$ par $e_s u$. Celle obtenue en ajoutant $r$ fois la colonne $s$ à la colonne $t$ est la matrice de $\alpha$ si nous remplaçons l'élément de base $e_t$ par $e_t + e_s r$.

Une **matrice élémentaire** est une matrice obtenue en appliquant une manipulation élémentaire de lignes à une matrice identité. Si $E$ est la matrice obtenue en appliquant la manipulation élémentaire de lignes $\rho$ à la matrice identité, alors $E$ peut être obtenue en appliquant une manipulation élémentaire de colonnes $\rho'$ à la matrice identité. De plus, si $A$ et $B$ sont des matrices de formats convenables, alors $EA$ est obtenue en appliquant la manipulation $\rho$ à $A$, et $BE$ est obtenue en appliquant la manipulation $\rho'$ à $B$.

Une matrice avec exactement un 1 dans chaque ligne et chaque colonne et tous les autres coefficients nuls est appelée une **matrice de permutation**, et c'est un produit de matrices élémentaires.

On voit facilement qu'une matrice élémentaire a une inverse (à droite et à gauche) qui est aussi élémentaire.

<footnote n="1">1. **NdT.** Elementary row operation.</footnote>

<footnote n="2">2. **NdT.** Elementary column operation.</footnote>
Si $k$ est un anneau à division, alors un $k$-module est appelé un **espace vectoriel** sur $k$. En mathématiques classiques tout espace vectoriel sur un anneau à division est libre. Ce n’est plus le cas constructivement, même pour les espaces vectoriels de type fini sur les corps discrets, comme le montre l’exemple brouwerien suivant.

**Exemple 6.1.** Soit $a$ une suite binaire, soit $i^2 = -1$ et considérons la suite des sous-corps

$$k_n = \{ s + ta_n i : s, t \in \mathbb{Q} \}.$$

du corps des nombres de Gauss $\mathbb{Q}(i)$. Posons $k = \bigcup k_n$. Alors $k$ est un corps discret, et $\mathbb{Q}(i)$ est un $k$-module discret engendré par les deux éléments $1$ et $i$. Mais nous ne pouvons pas construire une base de $\mathbb{Q}(i)$ sur $k$. ■

Si l'espace vectoriel $V$ est un $k$-module libre de rang $n$, alors $n$ est appelé la **dimension** de $V$ et on écrit $n = \dim_k V$, ou simplement $\dim V$; l'espace $V$ est alors appelé un **espace vectoriel de dimension finie** sur $k$. Le théorème suivant montre, entre autres choses, que $\dim V$ est bien définie si $k$ est discret.

**Théorème 6.2.** Soient $V$ et $W$ des espaces vectoriels sur un anneau à division discret $k$, de dimensions respectives $n$ et $m$, et soit $T$ une application linéaire de $V$ vers $W$. Alors il existe des bases $e_1, \dots, e_n$ de $V$ et $f_1, \dots, f_m$ de $W$, et un indice $\ell \le n$, tels que $T(e_\ell) = f_\ell$ pour $\ell \le \ell$, et $T(e_i) = 0$ pour $i > \ell$.

**Démonstration.** Soit $A = \{a_{ij}\}$ la matrice de $T$ par rapport aux bases données pour $V$ et $W$. Par des manipulations élémentaires de lignes et de colonnes nous pouvons faire que $a_{ij} = 0$ pour $i \ne j$, que $a_{ii} \in \{0, 1\}$, et que $a_{ii} \ge a_{jj}$ si $i \le j$. Et ceci revient à construire les nouvelles bases voulues pour $V$ et $W$. ■

En prenant pour $f$ l'application identique dans le théorème 6.2, nous voyons que la dimension d'un espace vectoriel de dimension finie est bien définie. Le théorème 6.2 implique de manière immédiate que $\ker T$ et $\im T$ sont des facteurs directs de dimension finie, et que $\dim \ker T + \dim \im T = \dim V$.

La difficulté dans l'exemple 6.1 est que le $k$-sous-espace engendré par $1$ n'est pas détachable : nous ne pouvons pas dire si $i$ est ou n'est pas dans ce sous-espace. Un facteur direct $A$ d'un espace vectoriel discret est détachable parce que $x \in A$ si, et seulement si, la projection de $x$ dans $A$ est égale à $x$. Par suite le corolaire suivant implique que les sous-espaces vectoriels de type fini d'un espace vectoriel de dimension finie sont détachables.

**Corolaire 6.3.** Soit $V$ un espace vectoriel de dimension finie sur un anneau à division discret $k$. Soit $W$ un sous-espace de type fini de $V$. Alors $W$ est un facteur direct de dimension finie de $V$.

**Démonstration.** Puisque $W$ est de type fini, il existe un espace vectoriel de dimension finie $F$ sur $k$ et une application linéaire $T$ de $F$ sur $W$. Le théorème 6.2 montre que $W$ est un facteur direct de dimension finie. ■