Rejoignez et rencontrez - Join and meet

Relations binaires transitives
Symétrique Antisymétrique Connecté Bien fondé A rejoint A rencontre Réfléchi Irréflexif Asymétrique Aussi connu sous le nom: Total, Semi-connex Anti-reflet Relation d'équivalence Oui ?? ?? ?? ?? ?? Oui ?? ?? Précommande (quasi-commande) ?? ?? ?? ?? ?? ?? Oui ?? ?? Commande partielle ?? Oui ?? ?? ?? ?? Oui ?? ?? Précommande totale ?? ?? Oui ?? ?? ?? Oui ?? ?? Commande totale ?? Oui Oui ?? ?? ?? Oui ?? ?? Pré-commande ?? ?? Oui Oui ?? ?? Oui ?? ?? Bien-quasi-ordre ?? ?? ?? Oui ?? ?? Oui ?? ?? Bien commander ?? Oui Oui Oui ?? ?? Oui ?? ?? Treillis ?? Oui ?? ?? Oui Oui Oui ?? ?? Join-semi-treillis ?? Oui ?? ?? Oui ?? Oui ?? ?? Rencontre-semi-treillis ?? Oui ?? ?? ?? Oui Oui ?? ?? Ordre partiel strict ?? ?? ?? ?? ?? ?? ?? Oui Oui Ordre faible strict ?? ?? ?? ?? ?? ?? ?? Oui Oui Commande totale stricte ?? ?? Oui ?? ?? ?? ?? Oui Oui Symétrique Antisymétrique Connecté Bien fondé A rejoint A rencontre Réfléchi Irréflexif Asymétrique Définitions : ${\displaystyle \scriptstyle {{\text{Pour tous}}\,a,b\,{\text{et}}\,S\neq \varnothing :}}$ ${\displaystyle \scriptstyle {aRb\Rightarrow bRa}}$ ${\displaystyle \scriptstyle {aRb\,{\text{and}}\,bRa\Rightarrow a=b}}$ ${\displaystyle \scriptstyle {a\neq b\Rightarrow aRb\,{\text{or}}\,bRa}}$ ${\displaystyle \scriptstyle {\min S\,{\text{existe}}}}$ ${\displaystyle \scriptstyle {a\vee b\,{\text{existe}}}}$ ${\displaystyle \scriptstyle {a\wedge b\,{\text{existe}}}}$ ${\displaystyle \scriptstyle {aRa}}$ ${\displaystyle \scriptstyle {{\text{not}}\,aRa}}$ ${\displaystyle \scriptstyle {aRb\Rightarrow {\text{not}}\,bRa}}$
Toutes les définitions exigent tacitement que la relation homogène soit transitive : Un " " indique que la propriété de la colonne est requise par la définition du terme de la ligne (tout à gauche). Par exemple, la définition d'une relation d'équivalence exige qu'elle soit symétrique. En vente ici sont des propriétés supplémentaires qu'une relation homogène peut satisfaire. ${\style d'affichage R}$${\displaystyle \scriptstyle {{\text{Pour tous}}\,a,b,c,{\text{ if }}aRb{\text{ et }}bRc{\text{ then }}aRc}.}$ Oui

En mathématiques , en particulier la théorie de la commande , la jonction d'un sous - ensemble d'un ensemble ordonné est la borne supérieure (borne supérieure) de notée et de même, la rencontre de est la borne inférieure (inférieure), noté En général, la jonction et se rencontrent d'un sous-ensemble d'un ensemble partiellement ordonné n'a pas besoin d'exister. Join et meet sont doubles en ce qui concerne l'inversion d'ordre. ${\style d'affichage S}$ ${\style d'affichage P}$${\style d'affichage S,}$${\displaystyle \vee S,}$${\style d'affichage S}$${\displaystyle \wedge S.}$

Un ensemble partiellement ordonné dans lequel toutes les paires ont une jointure est un join-semilattice . Doublement, un ensemble partiellement ordonné dans lequel toutes les paires ont une rencontre est une rencontre-semi-treillis . Un ensemble partiellement ordonné qui est à la fois un joint-semi-treillis et un rencontre-semi-lacet est un treillis . Un réseau dans lequel chaque sous-ensemble, et pas seulement chaque paire, possède une rencontre et une jointure est un réseau complet . Il est également possible de définir un réseau partiel , dans lequel toutes les paires n'ont pas de rencontre ou de jointure mais les opérations (lorsqu'elles sont définies) satisfont à certains axiomes.

La jointure/rencontre d'un sous-ensemble d'un ensemble totalement ordonné est simplement son élément maximal/minimal, si un tel élément existe.

Si un sous-ensemble d'un ensemble partiellement ordonné est également un ensemble dirigé (vers le haut) , alors sa jointure (si elle existe) est appelée jointure dirigée ou supremum dirigé . Doublement, si est un ensemble dirigé vers le bas, alors sa rencontre (si elle existe) est une rencontre dirigée ou un infimum dirigé . ${\style d'affichage S}$${\style d'affichage P}$${\style d'affichage S}$

Approche par commande partielle

Soit un ensemble d' ordre partiel et soit Un élément de est le${\style d'affichage A}$ ${\style d'affichage \,\leq ,\,}$${\style d'affichage x,y\dans A.}$${\style d'affichage z}$${\style d'affichage A}$ rencontrer (ouplus grande borne inférieure ouinfimum ) desi les deux conditions suivantes sont remplies : ${\displaystyle x{\text{ et }}y}$

1. ${\displaystyle z\leq x{\text{ et }}z\leq y}$(c'est-à-dire qu'il s'agit d' une borne inférieure de ).${\style d'affichage z}$${\displaystyle x{\text{ et }}y}$
2. Pour tout si alors (c'est-à-dire, est supérieur ou égal à toute autre limite inférieure de ).${\displaystyle w\in A,}$${\displaystyle w\leq x{\text{ et }}w\leq y,}$${\style d'affichage w\leq z}$${\style d'affichage z}$${\displaystyle x{\text{ et }}y}$

S'il y a une rencontre de alors c'est unique, car si les deux sont les plus grandes limites inférieures de alors et donc Si la rencontre existe, elle est notée Certaines paires d'éléments peuvent ne pas avoir de rencontre, soit parce qu'elles n'ont aucune limite inférieure du tout , ou puisqu'aucune de leurs bornes inférieures n'est supérieure à toutes les autres. Si toutes les paires d'éléments de ont une rencontre, alors la rencontre est une opération binaire sur et il est facile de voir que cette opération remplit les trois conditions suivantes : Pour tous les éléments${\displaystyle x{\text{ et }}y,}$${\displaystyle z{\text{ et }}z^{\prime }}$${\displaystyle x{\text{ et }}y,}$${\displaystyle z\leq z^{\prime }{\text{ et }}z^{\prime }\leq z,}$${\displaystyle z=z^{\prime }.}$${\displaystyle x\coin y.}$${\style d'affichage A}$${\style d'affichage A}$${\style d'affichage A,}$${\style d'affichage x,y,z\dans A,}$

1. ${\displaystyle x\wedge y=y\wedge x}$( commutativité ),
2. ${\displaystyle x\wedge (y\wedge z)=(x\wedge y)\wedge z}$( associativité ), et
3. ${\style d'affichage x\coin x=x}$( idempotence ).

Les jointures sont définies de manière duale avec la jointure de s'il existe, notée par Un élément de est le ${\displaystyle x{\text{ et }}y,}$${\displaystyle x\vee y.}$${\style d'affichage j}$${\style d'affichage A}$rejoindre (ouborne supérieure ousupremum ) deinsi les deux conditions suivantes sont remplies : ${\displaystyle x{\text{ et }}y}$${\style d'affichage A}$

1. ${\displaystyle x\leq j{\text{ et }}y\leq j}$(c'est-à-dire qu'il s'agit d' une limite supérieure de ).${\style d'affichage j}$${\displaystyle x{\text{ et }}y}$
2. Pour tout si alors (c'est-à-dire, est inférieur ou égal à toute autre limite supérieure de ).${\displaystyle w\in A,}$${\displaystyle x\leq w{\text{ et }}y\leq w,}$${\style d'affichage j\leq w}$${\style d'affichage j}$${\displaystyle x{\text{ et }}y}$

Si toutes les paires d'éléments de n'ont pas de rencontre (respectivement, join), alors la rencontre (respectivement, join) peut toujours être considérée comme une opération binaire partielle sur${\style d'affichage A}$${\style d'affichage A.}$

Approche de l'algèbre universelle

Par définition, une opération binaire sur un ensemble est une rencontre si elle satisfait les trois conditions a , b et c . La paire est alors une rencontre-semi-treillis . De plus, on peut alors définir une relation binaire sur A , en énonçant que si et seulement si En fait, cette relation est un ordre partiel sur Indeed, pour tout élément${\style d'affichage \,\coin \,}$${\style d'affichage A}$${\style d'affichage (A,\coin )}$ ${\style d'affichage \,\leq \,}$${\style d'affichage x\leq y}$${\style d'affichage x\coin y=x.}$${\style d'affichage A.}$${\style d'affichage x,y,z\dans A,}$

• ${\style d'affichage x\leq x,}$puisque par c ;${\style d'affichage x\coin x=x}$
• si alors par un ; et${\displaystyle x\leq y{\text{ et }}y\leq x}$${\displaystyle x=x\coin y=y\coin x=y}$
• si alors depuis lors par b .${\displaystyle x\leq y{\text{ et }}y\leq z}$${\style d'affichage x\leq z}$${\displaystyle x\wedge z=(x\wedge y)=y\wedge z=x\wedge (y\wedge z)=x\wedge y=x}$

Les rencontres et les jointures satisfont également à cette définition : quelques opérations de rencontre et de jointure associées produisent des ordres partiels qui sont l'inverse l'un de l'autre. En choisissant l'un de ces ordres comme principaux, on détermine également quelle opération est considérée comme une rencontre (celle donnant le même ordre) et laquelle est considérée comme une jointure (l'autre).

Équivalence des approches

Si est un ensemble partiellement ordonné , tel que chaque paire d'éléments dans a une rencontre, alors en effet si et seulement si puisque dans ce dernier cas en effet est une borne inférieure de et puisque est la plus grande borne inférieure si et seulement si c'est une borne inférieure bondir. Ainsi, l'ordre partiel défini par la rencontre dans l'approche de l'algèbre universelle coïncide avec l'ordre partiel d'origine. ${\style d'affichage (A,\leq )}$${\style d'affichage A}$${\style d'affichage x\coin y=x}$${\style d'affichage x\leq y,}$${\style d'affichage x}$${\displaystyle x{\text{ et }}y,}$${\style d'affichage x}$

Inversement, si est un semi-treillis , et l'ordre partiel est défini comme dans l'approche de l'algèbre universelle, et pour certains éléments alors est la plus grande borne inférieure de par rapport à puisque ${\style d'affichage (A,\coin )}$${\style d'affichage \,\leq \,}$${\displaystyle z=x\coin y}$${\style d'affichage x,y\dans A,}$${\style d'affichage z}$${\displaystyle x{\text{ et }}y}$${\style d'affichage \,\leq ,\,}$

et par conséquent la même façon, et si est une autre borne inférieure puis où ${\displaystyle z\leq x.}$${\displaystyle z\leq y,}$${\style d'affichage w}$${\displaystyle x{\text{ et }}y,}$${\displaystyle w\wedge x=w\wedge y=w,}$ Ainsi, il y a une rencontre définie par l'ordre partiel défini par la rencontre d'origine, et les deux rencontres coïncident.

En d'autres termes, les deux approches conduisent à des concepts essentiellement équivalents, un ensemble doté à la fois d'une relation binaire et d'une opération binaire, tels que chacune de ces structures détermine l'autre, et remplit les conditions d'ordres partiels ou satisfait, respectivement.

Rencontres de sous-ensembles généraux

Si est une rencontre-semi-treillie, alors la rencontre peut être étendue à une rencontre bien définie de tout ensemble fini non vide , par la technique décrite dans les opérations binaires itérées . Alternativement, si la rencontre définit ou est définie par un ordre partiel, certains sous-ensembles ont effectivement une infima par rapport à cela, et il est raisonnable de considérer une telle infimum comme la rencontre du sous-ensemble. Pour les sous-ensembles finis non vides, les deux approches donnent le même résultat, et donc l'une ou l'autre peut être considérée comme une définition de rencontre. Dans le cas où chaque sous-ensemble de a une rencontre, il s'agit en fait d' un treillis complet ; pour plus de détails, voir l' exhaustivité (théorie de l'ordre) . ${\style d'affichage (A,\coin )}$${\style d'affichage A}$${\style d'affichage A}$${\style d'affichage (A,\leq )}$

Remarques

Les références