ORDONNÉS ENSEMBLES

Carte mentale

Élargissez votre recherche dans Universalis

L'ordre lexicographique

Un ordre important dans les applications les plus variées (pour tous les problèmes de classification en sciences humaines, par exemple) est l'ordre lexicographique. Il est familier à tous ceux qui ont consulté un dictionnaire.

Soit X un ensemble ordonné par ≤ que nous appellerons un alphabet. On appelle mot toute suite finie d'éléments de X, sans se préoccuper du sens éventuel de ce mot dans une langue naturelle. Par exemple, si X est l'alphabet usuel, constitué par nos vingt-six lettres,

sont des mots.

L'ordre lexicographique se définit alors sur l'ensemble E des mots de la manière suivante. Si x = x1x2 ... xp et y1y2 ... yq sont des mots, on dira que :

si on a ≤ q et x1 = y1, x2 = y2, ..., xp = yp, ou si, désignant par k le plus petit entier tel que x yk, on a x≤ yk. Ainsi, si l'un des deux mots n'est pas obtenu en rajoutant des lettres à l'autre, on classe ces mots en examinant la première lettre qui diffère, par exemple :


1  2  3  4  5
pour nos abonnés,
l’article se compose de 4 pages



Médias de l’article

Ensemble ordonné par inclusion

Ensemble ordonné par inclusion
Crédits : Encyclopædia Universalis France

dessin

Ensemble ordonné par la relation de division

Ensemble ordonné par la relation de division
Crédits : Encyclopædia Universalis France

dessin





Écrit par :

Classification


Autres références

«  ORDONNÉS ENSEMBLES  » est également traité dans :

ALGÉBRIQUES STRUCTURES

  • Écrit par 
  • Jean-Marie PRUVOST-BEAURAIN
  •  • 34 159 mots

Dans le chapitre « Espèces de structures plus riches que celle d'ensemble-préordonné »  : […] Un ensemble-filtrant-à-gauche (respectivement ensemble-filtrant-à-droite , ensemble-filtrant , ces noms étant habituellement écrits sans traits d'union) est un ensemble-préordonné (E, R) tel que toute paire d'éléments de E soit minorée (respectivement majorée, bornée – c'est alors vrai pour toute partie finie non vide). Soit (E, R) un ensemble-préordonné. Si de plus R est symétrique, alors R est […] Lire la suite

BOOLE ALGÈBRE & ANNEAU DE

  • Écrit par 
  • Gabriel SABBAGH
  •  • 610 mots
  •  • 1 média

La notion d'algèbre de Boole, introduite par G. Boole (1847) et par A. De Morgan afin d'algébriser les opérations propositionnelles de la logique , joue un rôle très utile dans plusieurs branches des mathématiques (algèbre, théorie des ensembles ordonnés, calcul des probabilités) et en logique mathématique (logique algébrique, modèles booléens). On appelle algèbre de Boole (A, ∨, ∧, ¬, 0, 1) la d […] Lire la suite

HAUSDORFF FELIX (1868-1942)

  • Écrit par 
  • Jeanne PEIFFER
  •  • 688 mots

La renommée du mathématicien allemand Felix Hausdorff repose surtout sur son ouvrage Grundzüge der Mengenlehre (1914), qui en fit le fondateur de la topologie et de la théorie des espaces métriques. Né à Breslau dans une famille de marchands aisés, Hausdorff fit ses études secondaires à Leipzig, puis étudia les mathématiques et l'astronomie à Leipzig, Fribourg-en-Brisgau et Berlin. En 1891, il ob […] Lire la suite

RELATION

  • Écrit par 
  • Jean LADRIÈRE
  •  • 7 662 mots

Dans le chapitre « Relations arithmétiques, multirelations, structure, système »  : […] La théorie des relations arithmétiques a été développée sur des bases établies par les travaux de Stephen Cole Kleene, dans le cadre de la théorie des fonctions et prédicats d'entiers. Un prédicat d'entiers à n arguments peut être considéré (extensionnellement) comme une partie de l'ensemble des n -uples d'entiers. Une fonction à n arguments peut être considérée comme une relation de type plusie […] Lire la suite

Voir aussi

Pour citer l’article

André WARUSFEL, « ORDONNÉS ENSEMBLES », Encyclopædia Universalis [en ligne], consulté le 05 juillet 2020. URL : http://www.universalis.fr/encyclopedie/ensembles-ordonnes/