$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Ordre bien fondé

Soit $(E,\leq)$ un ensemble ordonné. On dit que l'ordre est bien fondé s'il n'existe pas de suite infinie strictement décroissante d'éléments de $E$.

Exemples :

  • L'ensemble des entiers naturels, muni de son ordre usuel, est bien fondé.
  • Si $(A_1,\leq),\dots,(A_p,\leq)$ sont des ensembles ordonnées muni d'un ordre bien fondé, alors l'ordre lexicographique sur le produit cartésien $A_1\times\dots\times A_p$ est bien fondé.
Théorème (caractérisation des ordres bien fondés) : Soit $(E,\leq)$ un ensemble ordonné. L'ordre est bien fondé si et seulement si toute partie non vide $F$ de $E$ admet un élément minimal.

La notion d'ordre bien fondé est importante en algorithmique pour assurer la terminaison des programmes. Si un algorithme est défini sur un jeu de données ayant un ordre bien fondé, et qu'il est itéré avec un élément plus petit, alors il est certain qu'il va se terminer.

Consulter aussi
Recherche alphabétique
Recherche thématique