Structures d'ordre

Relations d’ordre, arbres, treillis, algèbres de Boole et méréologies

par Philippe Muller, Laure Vieu

muller@irit.fr, vieu@irit.fr

Ordres

Non-réflexivité 

x n’est pas plus intéressant que lui-même

Asymétrie 

si x est plus intéressant que y, y n’est pas plus intéressant que x

Transitivité 

si x est plus intéressant que y et y est plus intéressant que z alors x est plus intéressant que z

On note souvent une relation d’ordre strict avec le symbole <

Formellement, si ¬ symbolise la négation, → l’implication matrielle (si . . . alors . . . ), & la conjonction et ∀ la quantification universelle (pour tout), les deux axiomes caractérisant un ordre strict sont :

Asymétrie 

∀x,y x < y →¬y < x

Transitivité 

∀x,y,z ((x < y & y < z) → x < z)

On peut alors déduire le théorème

Non-réflexivité 

∀x ¬x < x

-même et donc ≤ à elle-même), et anti-symétrique : si x ≤ y et y ≤ x alors x = y.

Réciproquement, à partir d’un ordre non strict on peut définir l’ordre strict associé. Si l’on ne spécifie pas, un ordre est en général un ordre non strict, mais comme les deux sont étroitement associés, en pratique, on utilise souvent simultanément les deux relations.

Un ordre peut être total (également dit linéaire) si toute entité considérée peut être comparée à toutes les autres, ou partiel (également dit branché) si certaines entités sont incomparables. Un exemple d’ordre total est la précédence temporelle sur les instants en physique (non relativiste). Un exemple d’ordre partiel est la relation de généralisation (hyperonymie, IS-A) sur les concepts dans une terminologie. Cette dernière relation est un ordre strict car aucun concept n’est plus général que lui-même, si un concept (ex : animal) est plus général qu’un autre (ex : chien) alors l’inverse n’est pas vrai (ex : chien n’est pas plus général qu’animal), et enfin la relation est transitive (ex : animal est plus général que chien qui est plus général que teckel, et animal est plus général que teckel). Cet ordre est partiel car certains concepts ne peuvent être comparés, par exemple, chien n’est pas plus géneral que chat et chat n’est pas plus général que chien.

Un ordre peut être discret si (i) pour toute entité x telle qu’il existe au moins une entité plus grande y, alors il existe une entité z —immédiatement supérieure— telle que x < z & ∀v(x < v → z ≤ v), et (ii), il existe, de façon duale, l’entité immédiatement inférieure : ∀x(∃y y < x →∃z(z < x & ∀v(v < x → v ≤ z))).

Un ordre non discret peut être dense si pour toute paire d’entités ordonnées, il existe une autre entité située entre les deux : ∀xy(x < y →∃z(x < z & z < y). Les ensembles de nombres entiers ℕ et ℤ sont discrets, alors que les rationnels ℚ et les irrationnels <math>\mathbb{R}</math> sont denses.

Un ordre peut porter sur un ensemble d’entités fini ou infini. Dans le cas fini, l’ordre est nécessairement discret.

Arbre

Un cas particulier d’ordre partiel courant est celui de la relation de dominance dans un arbre fini : cette relation a la propriété supplémentaire que toute entité a une et une seule autre entité immédiatement supérieure, sauf pour celle qui est la racine de l’arbre. On parle alors souvent du parent et des enfants d’une entité dans l’arbre pour désigner l’entité immédiatement supérieure et les entités immédiatement inférieures. Si l’on reprend l’exemple d’une terminologie sur un ensemble de concepts, cela veut dire que tout concept en possède un et un seul immédiatement plus général que lui, son parent, sauf le concept le plus général, la racine, qui subsume tous les concepts. Il s’agit alors d’une taxinomie, comme dans l’exemple de la Fig. 1. Cette figure adopte la convention des diagrammes de Hasse pour laquelle une relation d’ordre strict entre deux entités est représentée par un trait oblique ou vertical, l’entité plus grande étant située plus haut que l’autre.

Fig. 1: Exemple de relation d’ordre en arbre

Bien entendu, d’autres arbres, les arbres syntaxiques, sont très familiers aux linguistes.

Treillis

avion peut être considéré comme moins général que tas de ferraille et à la fois comme un cas particulier d’objet volant, sans que ces deux concepts soient comparables. Si avion est le plus général des concepts qui sont à la fois moins généraux que tas de ferraille et qu’objet volant, on dit qu’il est la borne inférieure (en anglais, infimum) des deux. Réciproquement un concept qui est le moins général parmi les concepts plus généraux que deux concepts choisis en est la borne supérieure (en anglais, supremum). Pour désigner les bornes inférieure et supérieure de deux entités, on utilise des opérateurs ou lois de composition notés habituellement <math>\bigwedge</math> et <math>\bigvee</math> (nommés en anglais meet et join). Si une relation d’ordre non strict possède la propriété que deux entités quelconques ont toujours une borne supérieure et une borne inférieure, on dit que la relation définit un treillis sur les entités considérées. Si la relation ne possède que la propriété d’avoir une borne supérieure (respectivement inférieure) pour toute paire d’entités on parle de semi-treillis supérieur (respectivement inférieur), comme dans l’exemple de la Fig.2.

Fig. 2: Exemple de relation d’ordre en semi-treillis supérieur

Un treillis est dit complet lorsque tout sous-ensemble d’entités (et non seulement les paires et les sous-ensembles finis) possède une borne supérieure et une borne inférieure.

Il arrive souvent que l’on caractérise un treillis à partir de la donnée de deux opérateurs <math>\bigwedge</math> et <math>\bigvee</math> vérifiant certaines propriétés (commutativité, associativité et absorption). Dans ce cas, la relation d’ordre correspondante est définie par la formule : x ≤ y si et seulement si x = x<math>\bigvee</math>y (ou, alternativement, y = x<math>\bigwedge</math>y).

Les treillis ont été abondamment utilisés en sémantique pour le traitement de la pluralité (voir cette fiche) ainsi que pour le traitement des termes de masses [7].

Algèbre de Boole

Un cas particulier important de treillis est le treillis formé par l’ensemble des parties ℘(E) ou sous-ensembles d’un ensemble E, en prenant comme relation d’ordre la relation d’inclusion entre ensembles ⊂. Les opérateurs <math>\bigwedge</math> et <math>\bigvee</math> correspondent alors à l’intersection ∩ et à l’union ∪ . Ce treillis possède les propriétés

• d’avoir un élément universel, parfois noté 1, qui est l’élément plus grand que tous les autres (ici l’ensemble E), et d’avoir un élément nul, parfois noté 0, qui est l’élément plus petit que tous les autres (ici l’ensemble vide ∅) ;
• d’être complémenté, à savoir que pour tout élément x il existe un complément —un élément y tel que x<math>\bigvee</math>y = 0 et x<math>\bigwedge</math>y = 1, que l’on peut désigner, avec l’opérateur - ou ¬, par -x ou ¬x ;
• d’être distributif (<math>\bigwedge</math> se distribue sur <math>\bigvee</math> et réciproquement)

Plus généralement, un treillis possédant ces propriétés est dit treillis distributif complémenté ou encore treillis booléen. Ce terme met en évidence le fait que la structure obtenue est une algèbre de Boole ; Boole a montré que l’ensemble des parties d’un ensemble muni de l’inclusion est isomorphe au calcul des propositions en logique : l’élément universel E correspond à Vrai, ∅ à Faux, l’inclusion à l’implication, l’intersection à la conjonction, l’union à la disjonction et l’opérateur de complément à la négation.

Au-delà de l’intérêt des treillis en logique et donc indirectement en sémantique, les algèbres de Boole ont été utilisées systématiquement dans [3] pour une approche alternative de la sémantique formelle, proposant notamment un traitement approfondi des catégories ainsi qu’une sémantique complexe des adjectifs.

Méréologie

Depuis [6], on appelle méréologie une théorie de la relation de de partie à tout. Les méréologie les plus simples sont des ordres partiels quelconques, mais ce que l’on appelle la Méréologie classique ou générale est en fait une algèbre de Boole complète de laquelle on a éliminé l’élément nul [8]. L’ordre partiel est alors muni d’un opérateur de fusion qui est caractérisé à l’aide d’une formule similaire à l’axiome de compréhension en théorie des ensembles (voir cette fiche). Les méréologies ont été utilisées pour le traitement des pluriels et des termes de masse, ce qui n’est guére étonnant vu leur proximité avec les treillis. Toutefois, l’étude systématique de ces théories envisage un plus grand nombre de cas et permet donc d’examiner en détails quelles sont les propriétés adéquates ou non pour une relation de partie à tout donnée (cf. la fiche Ontologie).

Autres exemples impliquant des ordres

• structures temporelles : temps, intervalles, événements, cf. [5, 2] ;
• structures de dominance (ordres partiels), par exemple sur des emboîtements de quantifications : Hole Semantics de Johan Bos, la Minimal Recursion Semantics de Copestake et Briscoe [1], et une comparaison de ces mécanismes de sous-spécification dans [4] (voir aussi la fiche SDRT).

Références

[1] Ivan Sag Ann Copestake, Dan Flickinger and Carl Pollard. Minimal recursion semantics : An introduction. draft 1999.

[2] H. Kamp and U. Reyle. From Discourse to Logic. Kluwer Academic Publishers, 1993.

[3] E. Keenan and L. Faltz. Boolean Semantics for Natural Language. Reidel, Dordrecht, 1985.

[4] Alexander Koller, Joachim Niehren, and Stefan Thater. Bridging the gap between underspecification formalisms : Hole semantics as dominance constraints. In Proceedings of the 11th EACL, Budapest, 2003.

[5] Fred Landman. Structures for Semantics. Kluwer, Dordrecht, 1991.

[6] Stanislaw Lesniewski. Sur les fondements de la mathématique. Hermès, Paris, 1989.

[7] Godehard Link. Algebraic Semantics in Language and Philosophy. CSLI Publications, 1998.

[8] Peter Simons. Parts - A study in ontology. Clarendon Press, Oxford, 1987.