Ensembles commandés

Définition 1. Un tas de M appelé commandé, si une relation est établie entre ses éléments un b(" un précédé b"), ayant les propriétés suivantes : 1) entre deux éléments quelconques un Et b il existe une et une seule des trois relations : un = b, un b, b un; 2) pour trois éléments quelconques un, b Et c depuis un b, b c suit un c.

Un ensemble vide est considéré comme commandé.

Commentaire. On entend toujours le signe = dans le sens d'identité, de coïncidence d'éléments. Enregistrer un = b signifie simplement qu'en lettres un Et b désigne le même élément de l'ensemble M. Par conséquent, de la propriété 1), il résulte qu’entre deux éléments différents, une et une seule des deux relations est vraie un b ou b un.

Si un précédé b, alors ils disent que b suit un et écrire: b > un.

Attitude un > b Il possède, comme on peut facilement le vérifier, des propriétés similaires à 1) et 2). Il peut être pris comme principal, définissant alors à travers lui la relation un b.

Si dans un ensemble ordonné M changer les rôles de la relation, c'est-à-dire plutôt un b écrire un > b, et vice versa, on obtient un nouvel ensemble ordonné M", dont l’ordre est dit inverse à l’ordre M. Par exemple, pour l’ordre ci-dessus dans l’ensemble des nombres naturels, l’ordre sera inversé :

Deux ensembles ordonnés composés des mêmes éléments, mais disposés dans des ordres différents, sont considérés comme différents. Par conséquent, lors de la définition d’un ensemble ordonné à travers ses éléments, il est nécessaire d’indiquer leur ordre. Nous supposerons que la notation de gauche à droite correspond à l’ordre des éléments, et nous conserverons la notation précédente avec accolades. Un même ensemble peut être ordonné de différentes manières (s'il contient au moins deux éléments). Ainsi, l'ensemble des nombres naturels peut être ordonné de la manière habituelle ou dans l'ordre inverse ; les nombres impairs peuvent être placés devant les nombres pairs ou vice versa, en les classant par ordre croissant ou décroissant. On obtient des ensembles ordonnés

On dira qu'un nombre naturel et plus qu'un nombre naturel b(et désigner une > b), s'il existe un nombre naturel k tel que a = b + k.

Théorème 1. Un n’est pas supérieur à n’importe quel nombre naturel.

En effet, la condition 1 > a entraîne 1 = a + k, ce qui est impossible : pour k = 1 on obtient 1 = a /, ce qui contredit le premier axiome des nombres naturels ; pour k ¹ 1, nous retrouvons son prédécesseur et arrivons à nouveau à la même contradiction.

Cette relation « plus » est antireflet(ce n'est pas vrai que a > a) et transitif(a > b /\ b > c => a > c), c'est-à-dire est relation d'ordre strict. De plus, cette relation est une relation d'ordre linéaire, c'est-à-dire que pour l'ensemble des nombres naturels le théorème de trichotomie est valable :

Théorème de trichotomie : Pour deux nombres naturels quelconques, une et une seule des trois affirmations suivantes est vraie :

Preuve: Nous montrons d’abord qu’aucune des trois conditions n’est satisfaite simultanément. Supposons que les conditions 1 et 2 soient remplies.

a = b + k, b = a + n => a = a + (n + k) => a > a,

ce qui contredit l’anti-réflexivité de l’attitude du « plus ». De même, l'incompatibilité des conditions 2 et 3 et des conditions 1 et 3 est établie.

Nous allons maintenant prouver que l’une des trois conditions est nécessairement vraie pour tous les nombres a et b. Nous utilisons l'induction mathématique sur b. Pour b = 1, en fonction de a : soit a = 1 = b, soit pour a il y a un prédécesseur, alors

a = c / = c + 1 = 1 + c = b + c => a > b.

Ainsi, pour b = 1, le théorème est vrai. Faisons l'hypothèse d'induction que le théorème est valable pour certains x, à savoir que x est comparable au nombre a, c'est-à-dire que trois options sont possibles : soit a > x, soit x > a, soit x = a. Puis nous prouvons que x/ est également comparable à a. Dans le premier cas, a > x, c'est-à-dire a = x + k. Selon que k donné est égal à 1 ou non, on obtient

a) a = x + 1 = x / (le théorème est vrai)

b) une = x + c / = x + c + 1 = x + 1 + c = x / + c => une > x / .

Dans le deuxième cas x > a, mais alors

x / = (une + m) +1 = une + (m + 1),

c'est-à-dire x /> a. De même, pour x = a, x / = x + 1 = a + 1, c'est-à-dire encore x / > a. Le théorème est complètement prouvé.

Vous pouvez maintenant présenter les concepts<, £, ³.

un< b ó b >un;

une £ b ó une< b \/ a = b

a ³ b ó a > b \/ a = b.

Propriétés de monotonie :

Pour l’opération d’addition :

1) une > b => une + c > b + c ;

2) a + c > b + c => a > b ;

3) a > b /\ c > d => a + c > b + d.

<, £, ³.

Pour l'opération de multiplication :

4) a > b => a×c > b×c ;

5) Loi de contraction : ac = bc => a = b

6) ac > bc => a > b ;

7) a > b /\ c > d => ac > bd.

Les mêmes propriétés se produisent pour d'autres signes<, £, ³.

Donnons comme exemple la preuve des propriétés 4 et 5. Puisque a > b, par définition a = b + k, alors a×c = (b + k)×c = b×c + k×c, ce qui signifie que a ×c > b×c, et la propriété 4 est prouvée. Nous prouvons la propriété 5 par contradiction. Soit ac = bc, mais supposons que a ≠ b, mais alors, par le théorème de trichotomie, soit a > b, soit b > a, mais cela signifie, d'après la propriété 4, que soit ac > bc, soit bc > ac, ce qui contredit la condition (ac = bc).

Théorème de discrétion. Vous ne pouvez pas insérer un nombre naturel entre deux nombres naturels adjacents :

(" a, x О N) il n'est pas vrai qu'un< x < a /

Preuve(par méthode de contradiction). Laissez un< x < a / . Тогда х = а + k,

a / = x + n = a + k + n => a + 1 = a + k + n => 1 = k + n.

La dernière égalité est impossible, car elle contredit le théorème selon lequel un n’est pas plus grand qu’un nombre naturel.

Tour d'Archimède. Pour tout nombre naturel a et b, il existe un nombre naturel n tel que a< bn.

On effectue la preuve par induction sur b. Pour b = 1, n = a / . Faisons l'hypothèse inductive que pour b = k le n requis existe, c'est-à-dire a< kn. Но тогда тем более a < k / n = kn + k. Теорема доказана.

Le plus petit élément de l'ensemble M nous appellerons un élément avec О М tel que pour tout élément m О M l'inégalité suivante est vraie : с ≤ m.

Théorème des moindres éléments. Tout sous-ensemble non vide de l’ensemble des nombres naturels possède le plus petit élément.

Preuve: Si M est un sous-ensemble de N contenant 1, alors 1 sera le plus petit élément souhaité. Si 1 n'est pas inclus dans l'ensemble M, alors considérons l'ensemble auxiliaire A, composé de tous les nombres naturels plus petits que tous les nombres naturels de l'ensemble M :

A = (a О N| (" m О M) une< m}.

De cette construction, en particulier, il résulte que les ensembles A et M n'ont pas d'éléments communs. De plus, A n'est pas vide, puisque 1 Î A. Dans A il y a aussi un élément b, tel que b / Ï A. En effet, s'il n'y avait pas un tel élément, alors par l'axiome d'induction il serait possible de prouver que A = N, mais alors M serait vide, ce qui ne correspond pas aux conditions du théorème. L'élément b / = c sera précisément le plus petit élément de l'ensemble M. En effet, c £ m pour tout m ОМ (si ce n'était pas le cas, alors l'inégalité c > m serait vraie pour au moins un m naturel, mais b О A , donc b< m < c = b / , что противоречит теореме о дискретности). Кроме того, с не может быть строго меньше всех элементов множества М, иначе с Î А, что противоречит его выбору. Таким образом, с равен хотя бы одному элементу из М, а значит с Î М, то есть действительно с – наименьший элемент множества М. Теорема доказана.

Notez que tous les sous-ensembles de l’ensemble des nombres naturels n’ont pas un plus grand élément, mais si ce sous-ensemble est fini, alors il a également un plus grand élément. L'inverse est également vrai. Si un sous-ensemble de l’ensemble des nombres naturels possède le plus grand élément, alors ce sous-ensemble est fini. Il est possible de prouver une affirmation encore plus générale : un sous-ensemble non vide de l'ensemble des nombres naturels est borné par le haut si et seulement s'il est fini (a le plus grand élément).

Tâches pour une solution indépendante

N° 1.8. Montrer que la relation « plus que » est anti-réflexive et transitive sur l'ensemble des nombres naturels.

N° 1.9. Prouvez les propriétés de monotonie 1, 2, 3, 6, 7 de cette section.

N° 1.10. Prouver les inégalités pour tous les nombres naturels n

a) 5n > 7n – 3 ;

b) 2n +2 ​​​​> 2n + 5 ;

Valide (réel) les nombres sont bien connus dans les cours de mathématiques à l'école. Arrêtons-nous brièvement sur leurs propriétés, qui sont assez facilement perçues par chacun de nous. Les nombres réels forment un ensemble d'éléments qui ont les propriétés suivantes.

Propriété de commande

Pour deux nombres %%a%% et %%b%%, la relation d'ordre est définie, c'est-à-dire Deux nombres réels %%a%% et %%b%% satisfont l'une des relations suivantes : %%a< b, a = b%% или %%a >b%%; De plus, si %%a< b%% и %%b < c%%, то %%a < c%%.

Propriétés de l'opération d'addition

montant et noté %%a + b%%, que les propriétés suivantes sont satisfaites.

1. Commutativité: %%a + b = b + a %%.
2. Associativité: %%a + (b + c) = (a + b) + c%% pour tous les nombres %%a, b%% et %%c%%.
3. zéro et noté %%0%% , ce qui signifie %%a + 0 = a%% pour n'importe quel nombre %%a%%.
4. Pour tout numéro %%a%%, il y a un numéro appelé opposé%%a%% et noté %%-a%%, soit %%a + (-a) = 0%%.
5. Si un< b%%, то %%a + c < b + c%% для любого числа %%c%%. Нуль единственен, и для каждого числа единственно противоположное ему число. Для любой пары чисел %%a%% и %%b%% число %%a + (-b) %% называют différence les nombres %%a%% et %%b%% et désignent %%a - b%%.

Propriétés de l'opération de multiplication

Pour toute paire de nombres %%a%% et %%b%%, il existe un numéro unique appelé leur travail et noté %%ab%% (ou %%a \cdot b%%) que les propriétés suivantes sont satisfaites.

1. Commutativité: %%ab = ba%%.
2. Associativité: %%a(bc) = (ab)c%% pour tous les nombres %%a, b%% et %%c%%.
3. Il y a un numéro appelé unité et noté %%1%%, que %%a \cdot 1 = a%% pour tout nombre %%a%%.
4. Pour tout nombre %%a%% non égal à zéro, il existe un nombre appelé inverseà cela et noté %%1 / a%%, soit %%a \cdot (1 / a) = 1%%.
5. Si %%a%% ou %%b%%, ou les deux %%a%% et %%b%% sont nuls, alors %%ab = 0%%.
6. Si un< b%% и %%c >0%%, puis %%ac< bc%%. Единица единственна, и для каждого ненулевого числа существует единственное обратное к нему. Для любой пары чисел %%a%% и %%b (b \neq 0)%% число %%a \cdot (1/b)%% называют privé en divisant %%a%% par %%b%% et noté %%a/b%%.

Propriété de distributivité

Pour tout triplet de nombres %%a, b%% et %%c%% l'égalité %%(a + b)c = ac + bc%% est vraie.

Propriété archimédienne

Quel que soit le nombre %%a%%, il existe un entier %%n \in \mathbb(N)%% tel que %%n > a%%.

Riz. 1. Droite numérique

Avant de formuler la propriété suivante des nombres réels, rappelons que la droite est donnée cadre de réference, si deux points différents sont fixés sur cette ligne (points %%O%% et %%e%% sur la Fig. 1). Celui de gauche (point %%O%%) est appelé l'origine, et la longueur du segment %%Oe%% précise l'unité d'échelle. Une droite avec un système de référence donné s’appelle axe de coordonnées. Il est généralement noté %%Ox%%. Le point %%O%% divise l'axe des coordonnées en deux parties : le demi-axe positif, où se trouve le point %%e%%, et le demi-axe négatif.

Coordonner les points %%M%% sur l'axe %%Ox%% sont la longueur du segment %%OM%%, pris avec le signe %%+%%, si le point %%M%% se situe sur le demi-positif et avec le signe %%-% %, si le point %%M%% se situe sur le demi-axe négatif.

Evidemment, chaque point %%M%% sur l'axe %%Ox%% correspond à un nombre réel %%x%%, à savoir sa coordonnée. Et inversement, chaque nombre réel sur l'axe %%Ox%% correspond à un point dont ce nombre réel est sa coordonnée. Chaque fois que cela sera nécessaire, nous supposerons que ce type de correspondance a été établie entre les nombres réels et les points d'une ligne, avec %%e = 1%%, %%O = 0%%.

Ainsi, l’ensemble de tous les nombres réels peut être considéré comme droite numérique. Parfois, au lieu de la droite numérique, le terme « vraie droite » est également utilisé. Identifier des nombres réels avec des points sur la droite numérique sera extrêmement utile à l'avenir, car cela aide à la compréhension et motive l'introduction de nouveaux concepts.

Le sous-ensemble %%X%% de l'ensemble des nombres réels est appelé entre, si, avec deux nombres %%x_1, x_2%%, ce sous-ensemble contient tout %%x%% compris entre eux. Les types d'espaces suivants sont utilisés :

• %%(a, b) = \(x : une< x < b\}%% - intervalle, ou travée ouverte;
• %% = \(x : a \leq x \leq b\)%% - segment de ligne, ou espace fermé(parfois le terme « segment » est utilisé) ;
• %%(une, b] = \(x : une< x \leq b\}%% и %% \supseteq %%, то отрезок %%%% называют imbriqué dans le segment %%%%.

  Propriété de continuité

  Pour tout système de segments imbriqués $$ \supseteq \supseteq \supseteq \ldots \supseteq \supseteq \ldots $$ il y a au moins un point appartenant à tous les segments de ce système. Cette propriété est aussi appelée principe des segments imbriqués (principe de Cantor).

  À partir des propriétés énumérées des nombres réels, on peut obtenir que 1 > 0, ainsi que les règles pour les opérations avec des fractions rationnelles ; règles de signes pour multiplier et diviser les nombres réels ; des règles pour transformer les égalités et les inégalités ; propriétés de la valeur absolue d'un nombre réel.

  Valeur absolue

  Valeur absolue(ou module) %%|a|%% de tout nombre réel %%a%% est un nombre réel qui satisfait aux conditions : $$ |a| = \begin(cases) a, \text( if ) a \geq 0 \\ -a, \text( if ) a< 0 \end{cases} ~~~~~~~~~~(1) $$

  Il s'ensuit que la valeur absolue de tout nombre réel est non négative %%(|a| \geq 0)%%, ainsi que $$ \begin(array)(l) |a| = |-une|, \\ |une| \geq une, \\ |une| \geq -a, \\ -|a| \leq une \leq |une|. \end(tableau)~~~~~~~~~~(2) $$

  Géométriquement, %%|a|%% correspond à la distance entre les points de la droite numérique représentant les nombres %%0%% et %%a%%.

  Soit l'inégalité %%|a|< \varepsilon%%, где %%\varepsilon%% - некоторое положительное число (%%\varepsilon >0%%) . Alors cette inégalité est équivalente à la double inégalité $$ -\varepsilon< a < \varepsilon. $$ Равносильность рассмотренных неравенств будет сохранена, если строгие неравенства (%%<%%) заменить на нестрогие (%%\leq%%): %%|a| \leq \varepsilon%% равносильно %%-\varepsilon \leq a \leq \varepsilon%%.

  Pour tout nombre réel %%a%% et %%b%% l'égalité $$ |ab| = |une||b| ~~~~~~~~~~(3) $$ et les inégalités suivantes sont vraies : $$ \begin(array)(lr) |a + b| \leq |a| + |b| &~~~~~~~~~~(4),\\ |a - b| \geq \big||a| - |b|\big|&~~~~~~~~~~(5). \end(tableau) $$

  En utilisant (1) et (2), nous prouvons l'inégalité (4) : si %%a + b \geq 0%%, alors $$ |a + b| = une + b \leq |une| + |b| $$ et si %%a + b< 0%%, то $$ |a + b| = -(a + b) = (-a) + (-b) < |a| + |b| $$

  Les propriétés ci-dessus décrivent complètement l’ensemble de tous les nombres réels.

  L'ensemble de tous les nombres réels, ainsi que l'ensemble des points sur la droite numérique, sont généralement notés %%\mathbb R%%.

  Ensemble complet de nombres réels

  Réapprovisionné(ou étendu) l'ensemble des nombres réels est l'ensemble formé de tous les nombres réels %%x \in \mathbb R%% avec l'ajout de deux éléments, notés %%+\infty%% (« plus l'infini ») et %%-\ infty%% ("moins l'infini") On pense que %%-\infty< +\infty%% и для всех чисел %%x \in \mathbb R%% справедливо %%-\infty < x < +\infty%%. Пополненное множество обозначают %%\overline{\mathbb R}%%. Ему соответствует étendu(ou réapprovisionné) droite numérique. Les éléments %%-\infty%% et %%+\infty%% sont appelés points infinis d'une telle ligne.

  Sous-ensembles de l'ensemble %%\mathbb R%% de nombres réels

  1. Ensemble d'entiers$$ \mathbb Z = \(\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots \) ​​​​$$ est un sous-ensemble propre de l'ensemble %%\mathbb R%% (%%\mathbb Z\subset\mathbb R%%).
  2. Ensemble de nombres naturels$$ \mathbb N = \(1, 2, 3, \ldots \) ​​​​$$ est un sous-ensemble approprié à la fois de l'ensemble %%\mathbb Z %% et de l'ensemble %%\mathbb R%% %%( \mathbb N \ subset \mathbb Z \subset \mathbb R)%%.

  L'ensemble de tous les nombres réels qui peuvent être représentés comme le quotient de l'entier %%m \in \mathbb Z%% divisé par l'entier naturel %%n \in \mathbb N%% est appelé l'ensemble nombres rationnels et notons %%\mathbb Q%%, c'est-à-dire $$ \mathbb Q = \left\(\frac(m)(n): m \in \mathbb Z, n \in \mathbb N\right\) $$

  Les ratios %%\frac(m)(n)%% et %%\frac(m"))(n")%% sont considérés comme égaux (représentant le même nombre rationnel %%r \in \mathbb Q%%) , si %%mn" = nm"%%. Ainsi, chaque nombre rationnel %%r = \frac(m)(n)%% peut avoir une infinité d'images %%r = \frac(p m)(p n), p \in \mathbb N%%.

  Il est évident que %%\mathbb N \subset \mathbb Z \subset \mathbb Q \subset \mathbb R%%.

  Des intervalles sans fin

  Sur la droite numérique terminée, il y a des intervalles infinis $$ (b, +\infty) = \(x : x > b\), (-\infty, a) = \(x : x< a\} $$ и бесконечные полуинтервалы $$ = \{x: x \leq a\} $$ По аналогии с бесконечными интервалами множество всех точек на числовой прямой R обозначают часто %%(-\infty, +\infty)%% или просто %%(-\infty, \infty)%%.

  

  Riz. 2. Voisinage d'un point

  Tout intervalle %%(a, b)%% contenant un point %%x_0%% est appelé alentours ce point et notons %%\text(U)(x_0)%%, c'est-à-dire %%\text(U)(x_0) = (a, b)%% si %%x_0 \in (a, b)%%. Le point %%x_0%%, situé au milieu de son voisinage %%(a, b)%%, est appelé dans ce cas le centre du quartier, et la distance %%\varepsilon = \frac((b - a))(2)%% est le rayon du quartier. Puis l'ensemble %%\(x: |x - x_0|< \varepsilon\}%% называют %%\varepsilon%%-окрестностъю точки %%x_0%% и обозначают %%\text{U}(x_0, \varepsilon)%% или %%\text{U}_\varepsilon(x_0)%% (рис. 2).

  Sur la droite numérique étendue, le concept de voisinage est introduit pour les points infinis %%+\infty%% et %%-\infty%%, assimilant ainsi ces points à des points finis lorsque l'on considère de nombreuses questions. Soit %%M%% un nombre positif. Alors %%\text(U)(+\infty) = \(x \in \mathbb(R): x > M\)%% et %%\text(U)(-\infty) = \(x \ dans\mathbb(R): x< -M\}%%, а для объединения бесконечных точек %%\text{U}(\infty) = \{x \in \mathbb{R}: |x| >M\)%%. Il est clair que pour n'importe lequel des points infinis, le voisinage avec une valeur plus petite de %%M%% inclut un voisinage avec une valeur plus grande de %%M%%.

  Ministère de l'Éducation et des Sciences de la Fédération de Russie

  Agence fédérale pour l'éducation

  INSTITUT MUNICIPAL DE NIZHNEKAMSK

  Département d'informatique, de mathématiques et de sciences naturelles -

  disciplines scientifiques

  Groupe 561

  ABSTRAIT

  dans la discipline "Algèbre abstraite"

  Spécialiste du niveau d'éducation

  Sujet : Ensembles commandés

  Chef ___________________ R.M. Munipov

  Étudiant ___________________ A.V. Glazounov

  Nijnekamsk 2007

  INTRODUCTION………………………………………………………………………………..3

  1. Ensembles partiellement commandés……………………………5

  2. Des ensembles bien ordonnés…………………………………..20

  3. Groupoïdes partiels et leurs propriétés……………………………..23

  CONCLUSION………………………………………………………..35

  RÉFÉRENCES………………………………………………………….36

  Introduction

  Actuellement, l'algèbre est principalement comprise comme la théorie générale des opérations et des relations algébriques. Il se caractérise par un grand naturel interne des idées et des tâches initiales, une unité des méthodes et une vaste gamme de concepts de base. Sa zone est délimitée clairement et clairement. Et pourtant, les limites actuelles de la théorie ne peuvent être considérées comme fermement et définitivement établies. L’envie de dépasser ses limites commence à émerger de plus en plus souvent. Il est nécessaire de considérer les opérations non seulement comme complètes, mais aussi comme partielles.

  La théorie des actions partielles doit naturellement continuer la théorie des actions complètes. Cette dernière est actuellement extrêmement étendue, riche et est à son apogée. Naturellement, l’idée se pose de transférer les concepts et les résultats développés dans un nouveau domaine. Ceci est bien entendu nécessaire et, dans de nombreux cas, fructueux. Cependant, dès les premiers pas dans le développement de la théorie des actions partielles, la spécificité importante de cette direction se fait sentir. Souvent, le transfert direct des résultats de la théorie des actions complètes s'avère difficile, voire impossible. Le matériel algébrique habituel doit être soumis à un traitement ou à une refonte important. De plus, des concepts et des problèmes complètement nouveaux apparaissent, spécifiques à la nouvelle direction. Ils nécessitent leur propre méthodologie de recherche.

  Il n'y a pas encore eu de présentation suffisamment complète et cohérente de la théorie des actions algébriques partielles. Il existe une incohérence dans les concepts initiaux et même dans les notations et la terminologie. Il n’y a pas assez de liens entre les œuvres individuelles. L'insuffisance du développement des questions individuelles nécessaires à la construction d'une théorie générale se fait sentir.

  1 . Hensembles ordonnés de manière élastique

  Relation binaire sur un ensemble UN appelé antisymétrique Si:

  (une,c UN) UN? V V? UN

  UN appelé réfléchissant Si:

  ( un UN) un un

  Relation binaire sur un ensemble UN appelé transitif Si:

  (un,V,c UN) un V V c>un Avec

  Exemple 1.

  Relation de divisibilité (entièrement) sur l'ensemble des nombres naturels N antisymétrique. En fait, si UN V, V UN, alors il y a des naturels q1 ,q N, tel que une=bq1 , в=аq où un = unq1 q , c'est q1 q = 1. Mais,

  q1 ,q N,ainsi q1 = q = 1, d'où il résulte que une = b.

  Relation binaire transitive antisymétrique réflexive sur un ensemble UN appelé relation d'ordre (commande partielle) sur le plateau UN.

  Un tas de UN avec une relation d'ordre partiel donnée dessus ? ils appelent ensemble partiellement commandé et désigne< UN; ? >.

  Dans ce qui suit, par commodité, nous utiliserons l'abréviation PESTE , désignant un ensemble partiellement ordonné.

  Exemple 2.

  < N, ? > ? inégalité ordinaire non stricte des nombres (au sens scolaire). Faut-il prouver la transitivité, la réflexivité et l’antisymétrie de cette relation ?

  un)un? un,(2 ? 2) - réflexivité,

  b) si UN? V , V? Avec, Que un ? c, (3 ? 4, 4 ? 5 > 3 ? 5) - transitivité,

  c) si un ? V , V?un, Que un=dans,(3 ? 3, 3 ? 3 > 3=3) - antisymétrie.

  Il s'ensuit que < N, ? > -CHUM.

  Exemple 3.

  < N, > .

  a) Relation de divisibilité sur l'ensemble des nombres naturels N réflexif, car tout nombre est un multiple de lui-même, c'est-à-dire parce que pour n'importe qui UN N Toujours un = un 1 (1 N), ceci, au sens de la relation, on a UN UN. C’est donc réflexif.

  b) Si le premier nombre est divisible par le deuxième (c'est-à-dire un multiple du deuxième) et que le deuxième est un multiple du troisième, alors le premier est un multiple du troisième, ce qui signifie que la relation est transitive, c'est-à-dire Si UN V, V Avec, un,V,c N. Il y a donc de tels q ,q N, Quoi

  un= dansq ,

  dans =c q ,

  un = c (q q ).

  Notons : q = q q N. Nous avons

  Où q N, c'est à dire. UN Avec- un prieuré . La relation est donc transitive.

  c) L'antisymétrie de la relation découle du fait que deux nombres naturels multiples l'un de l'autre sont égaux, c'est-à-dire Si UN V, V UN, alors il y a de tels q1 ,q N, Quoi

  une=bq1 ,

  в=аq ,

  un = unq1 q ,

  c'est q1 q = 1. Mais, q1 ,q N,ainsi q1 = q = 1, d'où il résulte que une = b. Donc antisymétrique.

  Il y a donc une commande partielle et, par conséquent, < N, > - CHUM (ensemble partiellement commandé).

  Éléments un,V Peste UN sont appelés incomparable sont écrits

  UN|| V, Si un? V Et V? UN.

  Éléments un,V Peste UN sont appelés comparable Si un? V ou V? UN.

  Commande partielle ? sur UN appelé linéaire, mais la peste elle-même linéairement - ordonné ou chaîne, si deux éléments de UN comparable, c'est-à-dire pour toute un,V UN, ou un ? V, ou V? un.

  Exemple 4 .

  < N, ? >, < R, ? > - sont une chaîne. Cependant<В(M) ; > ,où B( M) - l'ensemble de tous les sous-ensembles de l'ensemble M ou dans ( M) est appelé Booléen sur un plateau M, n'est pas une chaîne, car pas pour deux sous-ensembles de l'ensemble M l'un est un sous-ensemble de l'autre.

  Laisser < UN, ? > - peste arbitraire.

  Élément m UN appelé minimal, si pour quelque X UN de quoi X ? m devrait X = m.

  La signification de ce concept est que UN ne contient pas d'éléments strictement plus petits que cet élément m. Ils disent ça X strictement moins m et écris X< m, Si X ? m, mais en même temps X ? m. L'élément maximum de ce fléau est déterminé de la même manière. Il est clair que si m , m - différents éléments minimum (maximum) de la peste, puis m || m .

  Dans la théorie des ensembles partiellement ordonnés, la condition un ? V on lit parfois ainsi : élémentUN contenu dans l'élémentV ou élémentV contient un élémentUN .

  Lemme.

  Chaque élément d'une Peste finie contient un élément minimum et est contenu dans un élément maximum de cette Peste.

  Preuve:

  Laisser UN- un élément arbitraire du fléau final S. Si UN -élément minimal, alors, par réflexivité, le lemme est prouvé. Si UN n'est pas minimal, alors il y a un élément UN tel que

  UN < UN(1)

  Si UN est minime, alors tout est prouvé. Si l'élément UN n'est pas

  minime, puis pour certains UN on a

  UN < а (2)

  Si UN est minimal, alors de (1), (2), grâce à la transitivité, on conclut que UN contient l'élément minimum UN . Si UN n'est pas minime, alors

  UN < UN (3)

  pour certains UN S. Et ainsi de suite. Ce processus ne peut pas être infini en raison de la finitude de l'ensemble lui-même. S.

  Ainsi, depuis quelque temps n- à la ème étape du raisonnement le processus se termine, ce qui équivaut au fait que l'élément UN minimal. Où

  UN < а < < а < а < а

  En raison de la transitivité, il s'ensuit que l'élément UN contient l'élément minimum UN . De même, l'élément UN contenu dans l’élément maximum. Le lemme est prouvé.

  Conséquence.

  Le fléau final contient au moins un élément minimal.

  Nous introduisons maintenant le concept qui est important pour une présentation ultérieure diagrammes le fléau ultime S.

  Nous prenons d’abord tous les éléments minimaux m , m , m V S. D'après l'enquête, de telles personnes existeront. Puis dans l'ensemble partiellement ordonné

  S = S \ {m , m , m },

  qui, comme S, est fini, on prend les éléments minimaux,

  , , et considérons l'ensemble

  = S \ {, , }

  Éléments du « premier rang » m , m , m représenté par des points. Un peu plus haut on marque les éléments de la « deuxième rangée » avec des points, , et reliez les points avec des segments dans ce cas et seulement dans ce cas si m <

  Ensuite, nous trouvons les éléments minimaux de la Peste, les représentons avec les points de la « troisième rangée » et les connectons avec les points de la « deuxième rangée » de la manière indiquée ci-dessus. Nous continuons le processus jusqu'à ce que tous les éléments de cette peste soient épuisés S. Le processus est fini en raison de la finitude de l'ensemble S. L’ensemble résultant de points et de segments est appelé diagramme PESTE S. En même temps un < в si et seulement si du « point » UN tu peux aller dans "points" V le long d’une ligne brisée « ascendante ». De ce fait, toute plaie finie peut être identifiée grâce à son diagramme.

  Exemple 5 .

  Ici donné par le diagramme CHUM S = {m , m , , ), dans lequel m < , m < , m < m < , m < m < , m < .

  Élément m appelé le plus petitélément de la PESTE, si pour quelqu'un X UN Toujours m ? X.

  Il est clair que le plus petit élément est minimal, mais l’inverse n’est pas vrai : tout élément minimal n’est pas le plus petit. Il n'y a qu'un seul plus petit élément (le cas échéant). Le plus grand élément est déterminé de la même manière.

  Exemple 6.

  · · · ·

  Il s'agit d'un fléau dont les éléments sont incomparables par paires. Ce sont en partie

  les ensembles ordonnés sont appelés antichaînes.

  Exemple 7 .

  C'est la chaîne avec le plus petit et le plus grand élément. Où 0 est le plus petit élément et 1 est le plus grand élément.

  Laisser M- un sous-ensemble d'un ensemble ordonné partiel UN. Élément UN UN appelé bord inférieur ensembles M, Si UN? X pour tout le monde X M.

  Le plus grand de tous les infimums de l'ensemble M, s'il existe, s'appelle bord inférieur exact ensembles M et désigne inf M.

  Laisser < UN, ? > - peste arbitraire. Élément Avec UN appelé bord inférieur exactéléments un,V UN, Si Avec= inf( un,V}.

  Note 1.

  Dans chaque fléau, il n’existe pas un minimum exact pour deux éléments.

  Montrons cela avec un exemple.

  Exemple 8 .

  Pour ( un;c},{d;e) il n'y a pas de bord inférieur,

  info( un;V}=d, inf( V;c}=e.

  Exemple 9 .

  Donnons un exemple de peste, qui a un minimum exact pour tous les éléments.

  info( un;V}=d, inf( un;d}=d, inf( un;0 }=0 , inf( un;c}=0 , inf( un;e}=0 ,

  info( V;c}=e, inf( V;e}=e, inf( V;d}=d,

  info( c;e}=c, inf( c;0 }=0 , inf( c;d}=0 ,

  info( d;e}=0 , inf( d;0 }=0 ,

  info( e;0 }=0 .

  Définition: Un ensemble partiellement ordonné dans lequel pour deux éléments quelconques il y a un minimum est appelé semi-treillis.

  Exemple 10 .

  Donnons un exemple de peste, qui n'est pas un semi-treillis.

  Laisser < N, ? > - ensemble de nombres naturels ordonnés linéairement et e ,e N. Sur le plateau N = N { e ,e ) définir une relation binaire ? , en admettant que X ? oui, Si X, oui N, Où X ? oui, ou si X N, oui { e ,e ). On considère également par définition : e ? e ,e ? e .

  Le schéma de ce fléau est le suivant :

  Tout nombre naturel n ? e et n? e , mais en N il n'y a donc pas de plus grand élément, N - CHUM, mais pas un demi-treillis.

  Ainsi, par sa définition même, un semi-treillis est un modèle (comme un ensemble avec une relation ?). Comme nous allons le voir maintenant, une autre approche du concept de semi-treillis est possible, à savoir qu'un semi-treillis peut être défini comme une certaine algèbre.

  Pour ce faire, nous introduisons quelques concepts algébriques supplémentaires. Comme on le sait, semi-groupe est un ensemble non vide sur lequel est définie une opération algébrique binaire associative.

  Un semi-groupe arbitraire est généralement noté S(semi-groupe).

  Définition.Élément eS appelé idempotent, Si

  e = e, c'est e · e = e.

  Exemple 11 .

  Semi-groupe< N; · > ? n'a qu'un seul idempotent 1.

  Semi-groupe< Z; + > ? a un seul 0 idempotent.

  Semi-groupe< N; + > ? n'a pas d'idempotent, car 0 N.

  Pour tout ensemble non vide X, comme d'habitude, désigne l'ensemble de tous les sous-ensembles de l'ensemble X - le booléen de l'ensemble X.

  Semi-groupe<В;>- est tel que chacun de ses éléments est idempotent.

  UN DANS, UN = UN UN.

  Le semigroupe s'appelle semi-groupe idempotent ou bouquet, si chacun de ses éléments est idempotent. Ainsi, un exemple de connecteur est n'importe quel booléen relatif à une union.

  Exemple 12 .

  Laisser X- ensemble arbitraire.

  B- l'ensemble de tous les sous-ensembles de l'ensemble X.

  B- est appelé un booléen sur le plateau X.

  Si X= (1,2,3) , alors

  B = (O,(1),(2),(3),(1,2),(2,3),(1,3),(1,2,3)).

  Depuis l'intersection de deux sous-ensembles de l'ensemble X est encore une fois un sous-ensemble de X, alors nous avons un groupoïde< В;>, de plus, c'est un semigroupe et même un connecteur, puisque UN Dans et UN = UN UN=UN.

  De la même manière, nous avons la connexion<; В > .

  Le connecteur commutatif s’appelle semi-treillis.

  Exemple 13 .

  Laisser X= (1,2,3), construisons un diagramme< В ; >.

  Donnons des exemples de pestes, mais pas de semi-treillis.

  Exemple 14 .

  CHUM à deux faces inférieures e Et d , qui ne sont pas comparables entre eux : e|| d. Donc inf( un;Avec) n'existe pas.

  Exemple 15.

  CHUM à deux faces inférieures Avec Et d, qui sont incomparables les uns avec les autres : Avec|| d. Donc inf( un;V) n'existe pas.

  Donnons des exemples de semi-treillis.

  Exemple 16 .

  Diagramme:

  UN

  info( un;V}=V, inf( un;Avec}=Avec, inf( un;d}=d,

  info( V;c}=d, inf( V;d}=d,

  info( c;d}=d.

  Exemple 17 .

  C'est un semi-treillis, car pour deux éléments quelconques, il existe un minimum, c'est-à-dire

  info( un;V}=V, inf( un;Avec}=Avec, inf( V;c}=Avec.

  Théorème 1.

  Laisser<S ; ? > - semi-treillis. Alors<S ; > connecteur commutatif, où

  un V=inf( un,V} (*).

  Preuve:

  Il faut prouver que dans<S ; > les identités suivantes sont détenues :

  (1) X y = y X

  (2) (X oui) z = x (oui z)

  (3) X X = X

  1) Selon l'égalité(*)

  X y= info( X,oui) = inf ( oui,X) = oui X

  2) Notons UN = (X oui) z, dans =X ( oui z)

  Prouvons que UN = V.

  Pour ce faire, il suffit de prouver que

  UN ? V (4)

  V ? UN(5) (en raison de l'antisymétrie)

  Notons

  Avec = X oui , d = oui z

  Au sens de, UN la limite inférieure exacte entre Avec Et z

  UN? Avec , UN ? z , c ? X, donc, en raison de la transitivité un ? X.

  De même, UN? oui, c'est à dire. UN- limite inférieure commune pour oui Et z. UN d- leur limite inférieure exacte.

  Ainsi, un ? d, Mais V=inf( X, d}.

  Des inégalités un ? X , un ? d il s'ensuit que UN X Et d, UN V est leur minimum exact, donc,

  UN? V(4) prouvé.

  (5) se prouve de la même manière.

  De (4) et (5), compte tenu de l’antisymétrie, nous concluons que

  une = b.

  Avec cela, nous avons prouvé l'associativité de l'opération ().

  3) Nous avons X X=inf( X,X} = X.

  L’égalité s’obtient par la réflexivité : X? X.

  Que. algèbre construite<S ; > sera un semi-groupe commutatif idempotent, c'est-à-dire lien commutatif.

  Théorème 2.

  Laisser<S ; · > est-ce un semigroupe idempotent commutatif, donc une relation binaire ? sur S, défini par l'égalité

  ? = un·в = а,

  est une commande partielle. En même temps, LA PESTE<S ; ? > est un semi-treillis.

  Preuve:

  1) réflexivité ?.

  Par condition<S ; · > satisfait trois identités :

  (1) X = X

  (2)x y = y x

  (3) (xy)· z = x(oui· z)

  Alors xx = x =x- en vertu de (1). C'est pourquoi X? X.

  2) antisymétrie ? .

  Laisser X? à Et ouais ? X, alors par définition,

  (4) xy = x

  donc, grâce à la commutativité, nous avons x = y.

  3) transitivité ?.

  Laisser X? à Et ouais ?z alors, par définition,

  (6) xy = x

  (7) oui z= oui

  Nous avons X· z = (X· oui)· z X· (oui· z) xy X

  Donc, X· z = X, c'est X?z.

  On a donc CHUM<S ; ? >. Il reste à montrer que pour tout ( UN,V)S existe inf( une,c}.

  Nous prenons arbitraire UN,V S et prouver que l'élément c = un b est inf( une,c), c'est à dire. Avec= inf( une,c}.

  En effet,

  c une =(ac · c)·UN UN·(ac · c) (a·a)· V a·b = c,

  Que. Avec? UN.

  De même, s·v =(ac · c)·V UN·(dans · dans) a·b = c,

  ceux. Avec? V.

  Donc, Avec- borne inférieure commune ( une,c}.

  Prouvons son exactitude.

  Laisser d- une limite inférieure commune pour UN Et V:

  (8) d? un

  (9)d? V

  (10) ré une = ré

  (11)d dans =d

  d· c = d· (ac · c) (d·UN)· V d·V d,

  d· c = d, ainsi, d ? c.

  Conclusion: c = info( un,V}.

  Les théorèmes 1 et 2 démontrés nous permettent d'examiner les semi-réseaux sous deux points de vue : en tant que CUM, et en algèbre (semigroupes commutatifs idempotents).

  2. Des ensembles bien ordonnés

  La théorie des ensembles ordonnés a été créée par G. Chantre . Chatounovski . Hausdorff (1914).

  Des ensembles bien ordonnés - Un ensemble ordonné est dit bien ordonné si chacun de ses sous-ensembles possède un premier élément (c'est-à-dire un élément suivi de tous les autres). Tous les ensembles finis ordonnés sont complètement ordonnés. La série naturelle, ordonnée par ordre croissant (ainsi que d'autres manières), forme un ensemble complètement ordonné. L'importance des ensembles complètement ordonnés est déterminée principalement par le fait que le principe d'induction transfinie est valable pour eux.

  Les ensembles ordonnés qui ont le même type ordinal ont également la même cardinalité, nous pouvons donc parler de la cardinalité d'un type ordinal donné. D'un autre côté, les ensembles ordonnés finis de même cardinalité ont le même type ordinal, de sorte que chaque cardinalité finie correspond à un certain type ordinal fini. La situation change lorsqu'on passe à des ensembles infinis. Deux ensembles ordonnés infinis peuvent avoir la même cardinalité mais des types d’ordre différents.

  3. Groupoïdes partiels et leurs propriétés

  Comme on le sait, une opération algébrique binaire sur un ensemble S est une cartographie à partir d'un carré cartésien S?S. Dans ce cas, l’action est dite définie sur S. Dans ce paragraphe, nous l'appellerons plein effet.

  Tout mappage d'un sous-ensemble S?S V S appelé effet partiel sur S. En d’autres termes, une action partielle sur S est une fonction de S?S > S.

  On peut dire que sur S une action partielle (multiplication partielle) est spécifiée si pour des éléments une,c S travail ac · c soit indéfini, soit défini sans ambiguïté. En termes simples, tous les éléments ne sont pas ici multipliés.

  Un tas de S avec une multiplication partielle qui y est spécifiée est appelé groupoïde partiel et est noté ( S ; · ) contrairement à un groupoïde complet< S ; · >.

  Si pour un groupoïde complet on peut parler d'une table de Cayley, alors pour un groupoïde partiel on peut parler d'un analogue de la table de Cayley, à savoir une table où certaines cellules sont vides - c'est le cas lorsque le produit des éléments est indéfini.

  Exemple 1.

  	un

  UN· dans = dans, Mais V· UN non défini, c'est-à-dire V· UN= Ô. Symbole " Ô" n'appartient pas S, c'est à dire. n'est pas un élément de S.

  Exemple 2.

  Considérez la peste ( S ; ? ).

  S = {un,V,c, d), Où UN? UN, V? V, Avec? Avec, d ? d, Avec? UN, Avec? V, d? UN, d? V.

  Dans une peste arbitraire ( S ; ? ) on convient de désigner :

  UN V= inf( un,V}.

  Alors la peste indiquée dans l'exemple par rapport à cette action partielle est un groupoïde partiel ( S;), dont le tableau de Cayley est le suivant

  				d
  un
  				d
  	c
  			-

  Dans cette section, nous examinerons trois types d'associativité : l'associativité forte, l'associativité moyenne et l'associativité faible.

  Définition 1.

  Groupoïde partiel ( S ; · ) est appelé faiblement associatif , Si

  (X,y,z S) (X· oui)· z Ô X·( oui· z) > (X· oui)· z= X·( oui· z) (*)

  Définition 2.

  Groupoïde partiel ( S ; · ) est appelé modérément associatif , Si

  (X,y,z S) (X· oui)· z Ô oui· z > (X· oui)· z= X·( oui· z)

  Définition 3.

  Groupoïde partiel ( S ; · ) est appelé fortement associatif , Si

  (X,y,z S) [(X· oui)· z Ô X·( oui· z) Ô> (X· oui)· z= X·( oui· z)] (*)

  Un groupoïde partiel fortement associatif satisfait aux propriétés d’associativité modérée et faible. Mais l’inverse n’est en aucun cas nécessaire.

  Exemple 3.

  Donné UN = {un, dans, avec). Réglons-le sur UN opération partielle de multiplication par « table de Cayley partielle ».

  Nous obtenons un groupoïde partiel. Vérifions si le groupoïde est fortement associatif.

  Laisser ( X· oui)· z Ô parce que X UN, alors soit x = c x = b

  1) laissez x = c, Alors y = dans y = c

  a) laisser y = dans, Alors z = un

  (Avec· V)· UN Ô Avec·( V· UN) défini

  (Avec· V)· une = c·( V· UN) l'égalité est satisfaite

  b) laisser y = c, Alors z= dans z=c

  et si z= dans, Alors

  (Avec· Avec)· V Ô Avec·( Avec· V) défini

  (Avec· Avec)· dans = c·( Avec· V) l'égalité est satisfaite

  b") si z=c, Alors

  (Avec· Avec)· Avec Ô Avec·( Avec· Avec) défini

  (Avec· Avec)· c = c·( Avec· Avec) l'égalité est satisfaite

  2) laissez x = b, Alors y = une, UN z= dans z = c

  et si y = une Et z= dans

  (V· UN)· V Ô= dans·( UN· V) indéfini

  (V· UN)· V V·( UN· V) l'égalité n'est pas satisfaite

  b) laisser y = une Et z=c

  (V· UN)· Avec Ô= dans·( UN· Avec) indéfini

  (V· UN)· Avec V·( UN· Avec) l'égalité n'est pas satisfaite

  Ainsi, par définition, un groupoïde partiel n’est pas fortement associatif. Mais cela ne veut pas dire que ( S ; · ) n'est pas faiblement associatif.

  Découvrons-le.

  Laisser (X· oui)· z Ô X·( oui· z) Ô .

  À X UN, à UN, à savoir quand

  x = b x = c

  y = dans y = c

  ce groupoïde partiel est faiblement associatif.

  Exemple 4.

  Laisser UNE ={un, dans, avec), peut être réglé sur UN le tableau de Cayley suivant. Nous obtenons un groupoïde partiel. Vérifions si ce groupoïde est modérément associatif.

  Laisser ( X· oui)· z Ô parce que X V, Alors x = un x = c

  1) laissez x = un, Alors y = une y = dans

  a) laisser y = une, Alors z = un, z= dans

  et si z= un, Alors

  (UN· UN)· UN Ô UN· un défini

  (UN· UN)· UN UN·( UN· un) l'égalité n'est pas satisfaite

  b") si z= dans, Alors

  (UN· UN)· V Ô UN· V défini

  (UN· UN)· V UN·( UN· V) l'égalité n'est pas satisfaite

  Nous voyons donc que le groupoïde n’est pas moyennement associatif. Découvrez s’il est faiblement associatif.

  Laisser ( X· oui)· z Ô X·( oui· z) Ô, parce que X V, Alors x = un x = c

  1) laissez x = un, Alors y = une y = dans

  a) laisser y = une, Alors z = un, z= dans

  et si z= un, Alors

  (UN· UN)· UN Ô= un·( UN· un) indéfini

  (UN· UN)· UN UN·( UN· un)

  b") si z= dans, Alors

  (UN· UN)· V Ô UN·( UN· V) défini

  (UN· UN)· dans = un·( UN· V) l'égalité est satisfaite

  b) laisser y = dans, Alors z = un, z= dans

  et si z= un, Alors

  (UN· V)· UN Ô= un·( V· un) indéfini

  (UN· V)· UN UN·( V· un)

  b") si z= dans, Alors

  (UN· V)· V Ô UN·( V· V) indéfini

  (UN· V)· V UN·( V· V) l'égalité n'est pas satisfaite

  2) laissez x = c, Alors y = une,y = dans

  a) laisser y = une, Alors z = un, z= dans

  et si z= un, Alors

  (Avec· UN)· UN Ô=c·( UN· un) indéfini

  (Avec· UN)· UN Avec·( UN· un) l'égalité n'est pas satisfaite

  b") si z= dans, Alors

  (Avec· UN)· V Ô Avec·( UN· V) défini

  (Avec· UN)· dans = c·( UN· V) l'égalité est satisfaite

  On voit donc qu’un groupoïde partiel est faiblement associatif pour x = un Et z= dans ou lorsque x = c Si y = une Et z= dans.

  Définition 4.

  Groupoïde partiel ( S ; · ) est appelé commutatif , Si

  (X,oui S) X· oui = oui· X

  Définition 5.

  Groupoïde partiel ( S ; · ) est appelé caténaire , Si

  (X,y,z S) (X· oui Ô oui· z) > [(X· oui)· z Ô X·( oui· z)]

  Définition 6.

  Groupoïde partiel ( S ; · ) est appelé idempotent , Si

  (X S) X = X

  Donnons un exemple de groupoïde partiel non caténaire.

  Exemple 5.

  				d
  un
  				d
  	c
  			-

  Nous avons Avec une = c Ô, UN d = d Ô. Cependant, ( Avec UN) d = c d Ô. Par conséquent, le CG donné n’est pas une caténaire.

  Il est clair ce que nous entendons par le terme « limite supérieure commune » des éléments UN Et V une certaine peste.

  Définition 7.

  Ça s'appelle une peste catégorique , si deux de ses éléments qui ont une limite supérieure ont une limite inférieure exacte.

  Exemple 6.

  Exemple 7.

  Un ensemble partiellement ordonné défini par une table de Cayley :

  Exemple 8.

  Ensemble partiellement commandé

  ayant la table de Cayley suivante :

  				-
  				-
  				-

  Il est clair que tout semi-treillis est un fléau catégorique (mais pas l'inverse), car deux éléments quelconques ont un minimum exact. En d’autres termes, la classe de toutes les plaies catégorielles contient la classe de tous les semi-réseaux, mais ne coïncide pas avec elle. Que. toute proposition prouvée pour les plaies catégoriques entraîne comme conséquence évidente un certain théorème concernant les semi-réseaux.

  Donnons des exemples de semi-treillis.

  Exemple 9.

  Diagramme:

  appelé diamant

  				d
  un
  			d
  	c

  Exemple 10.

  Diagramme:

  appelé Pentagone, et est défini par un semi-treillis ayant la table de Cayley suivante :

  Exemple 11.

  Le semi-treillis défini par la table de Cayley :

  a un schéma :

  Théorème 1.

  Laisser ( S ; ? ) - peste catégorique, alors ( S;) - groupoïde partiel caténaire idempotent commutatif faiblement associatif.

  Preuve:

  Pour tout le monde UN S Toujours

  UN UN= inf( un, un} = un donc groupoïde partiel S idempotent.

  Nous avons UN V= inf( un,V) = inf( V,un} = V UN, et donc S commutatif

  Vérifions la faible associativité.

  Laisser ( UN V) Avec Ô UN (V Avec) , dénoter

  UN V = d, V Avec = e, (UN V) Avec= d Avec = F, UN (V Avec) = UN e= g

  Prouvons que F = g.

  Par définition nous avons F ? d ? un F ? un,

  F ? d? V F? V (1)

  F ? c (2)

  Parce que e= inf( dans, avec), puis de (1), (2) il résulte que F ? e. Que. F - une limite inférieure commune pour UN Et e, UN g est leur minimum exact, donc

  F ? g (3)

  De même,

  g ? F (4)

  Inégalité (3), (4) et antisymétrie de la relation ? fournir F = g. Une faible associativité a été prouvée.

  Vérifions la caténaire S.

  Laisser UN V Ô V Avec, dénoter UN b = x, V Avec = oui, d'ici X? V, ouais ? V, c'est à dire.

  V- limite supérieure commune X Et à. Parce que PESTE S catégoriquement, alors il existe inf( x,y), c'est à dire. existe dans S X à. Notons X y = z, nous allons montrer que

  UN (V Avec) = X Avec= z. Nous avons z ? X, z ? oui (parce que z = info( x,y}), oui ? z z ? X, z ? c,

  z - bord inférieur pour X Et Avec.

  Nous garantirons l’exactitude.

  Laisser t ? X , t ? c (t- toute borne inférieure), car t ? X , Que t ? un, t? V, par condition t? Avec, c'est à dire. t- limite inférieure commune pour V Et Avec. Il s'ensuit par définition à, t ? oui.

  Donc, t ? X, t? à ainsi t ? z (un prieuré z).

  La caténaire a fait ses preuves.

  Théorème 2.

  Si ( S ; · ) est un groupoïde partiel commutatif idempotent caténaire faiblement associatif, alors la relation

  ? = (une,c) S?S (2)

  Est une relation d'ordre. En même temps, LA PESTE<S ; ? > - est une caténaire.

  Preuve:

  Prouvons la réflexivité de la relation ? . Parce que groupoïde partiel S idempo-tenten, alors un· un = un donc, par définition (2) UN? UN.

  Vérifions l'antisymétrie.

  Si UN? dans, dans ? UN, Que а·в = а, в·а = в, les côtés gauches sont égaux en raison de la commutativité, ce qui signifie que les côtés droits sont égaux, donc une = b.

  Reste à prouver la transitivité.

  Laisser UN? V, V? Avec, Alors ab = a, v s = dans, а·с =(ac · c)· Avec. En raison de la caténaire, nous avons ( UN· V)· Avec Ô , UN·( V· Avec) Ô, donc en raison d'une faible associativité

  (ac · c)·c = une ·(contre), et donc, a·c = a·(contre) = ab = a.

  Donc, a·c = a, c'est à dire. UN? Avec.

  Que. nous avons une peste<S ; ? > .

  Laisser z- limite supérieure commune pour X Et à. Ainsi, X?z, oui ? z, d'ici X·z = X, oui· z = oui, Alors z· oui = oui. En raison de la caténaire ( X· oui)· z Ô X· oui Ô.

  Notons x y =s, prouvons que s bord inférieur exact.

  Nous avons s· X = (X· oui)· X = X· (X· oui) = (X· X)· oui = X· oui = s (en raison de la caténaire et de la faible associativité), donc, s ? X, c'est à dire. s- borne inférieure commune.

  De ces théorèmes découlent deux corollaires bien connus dans la théorie des semi-réseaux.

  Corollaire 1.

  Si<S ; · > est un semigroupe commutatif idempotent, alors la relation ? , défini par l'égalité (2), est un ordre partiel. De plus, pour deux éléments quelconques de S il existe une limite inférieure exacte.

  Corollaire 2.

  Si<S ; · > est un ensemble partiellement ordonné dans lequel il y a un minimum de deux éléments quelconques, alors par rapport à l'opération

  UN V= inf( un,V} (3)

  un tas de S est un semi-groupe commutatif idempotent.

  CONCLUSION

  En conclusion, on peut noter que la théorie des ensembles ordonnés a été créée par G. Chantre . En 1883, il a introduit le concept d'un ensemble complètement ordonné et d'un nombre ordinal, et en 1895, le concept d'un ensemble ordonné et d'un type ordinal. En 1906-07, S.O. Chatounovski formulé les définitions d'un ensemble dirigé (dans Shatunovsky - un complexe localisé) et la limite sur un ensemble dirigé (par les mathématiciens américains E . G. Moore et G. L. Smith ont considéré ces mêmes concepts indépendamment de Shatunovsky, mais beaucoup plus tard - en 1922). Le concept général d’ensemble partiellement ordonné appartient à F. Hausdorff (1914).

  Ainsi, la théorie des actions algébriques partielles, étant une continuation de la théorie des actions complètes, tirant parti de ses réalisations, des idées et de l'expérience d'applications en dehors de l'algèbre qui y sont associées, devrait encore prendre forme comme une direction indépendante dans le vaste domaine de algèbre moderne.

  À ce jour, des centaines d'ouvrages ont été publiés spécifiquement consacrés à l'étude des actions partielles. Quant aux ouvrages dans lesquels certaines actions partielles interviennent au cours de l'étude, leur nombre ne peut être estimé. Les actions partielles sont également abordées dans certains ouvrages algébriques généraux, mais toujours très brièvement.

  Bibliographie

  A.K. Clifford, G. Preston. Théorie algébrique des semigroupes. 1972.

  Greitzer. Théorie générale des treillis Moscou.-284 p.

  Kojevnikov O.B. Ensembles partiellement ordonnés de groupoïdes partiels Moscou, 1998. - 680.

  E.S. Lyapine. Semi-groupes. Moscou : Fizmat, 1960.- 354 p.

  Lyapine E.S. Algèbre et théorie des nombres. Moscou, 1980.-589 p.

  Lors de l'introduction d'opérations avec des surensembles, nous n'avons pas pris en compte le fait que les ensembles eux-mêmes peuvent avoir leur propre structure interne, c'est-à-dire que nous avons supposé que tous les éléments de l'ensemble étaient égaux. Cependant, en mathématiques, de tels ensembles « purs » présentent peu d'intérêt, et on étudie beaucoup plus souvent des ensembles entre les éléments desquels il existe certains relation . L'une des relations les plus importantes entre les éléments d'un ensemble est relation d'ordre .

  Relation d'ordre n'est rien d'autre que, en règle générale, l'établissement de l'ordre de « séquence » des éléments de l'ensemble.

  Laisser UN- certains réglés, réglés UN appelé ensemble commandé , si pour deux de ses éléments un B l'un des éléments suivants est installé relations de commande :

  ou une ≤ b (UN ne dépasse pas b),

  ou b ≤ une (b ne dépasse pas UN),

  ayant les propriétés suivantes :

  1) réflexivité:

  aucun élément n'est supérieur à lui-même ;

  2) antisymétrie :

  Si UN ne dépasse pas b, UN b ne dépasse pas UN, alors les éléments UN Et b correspondre;

  3) transitivité :

  Si UN ne dépasse pas b, un b ne dépasse pas Avec, Que UN ne dépasse pas Avec.

  Il a été convenu que l'ensemble vide était considéré comme commandé. Dans la définition ci-dessus d'un ensemble ordonné, dont les éléments peuvent être des objets de toute nature, le signe ≤ se lit « ne dépasse pas ». Ce signe (comme le signe « inférieur ou égal ») acquiert sa lecture et sa signification habituelles dans le cas où les éléments de l'ensemble UN- Nombres.

  Deux ensembles composés des mêmes éléments, mais avec des relations d'ordre différentes, sont considérés comme des ensembles ordonnés différents.

  Le même ensemble peut être ordonné de différentes manières, obtenant ainsi des ensembles ordonnés différents.

  Exemple

  Considérons un ensemble dont les éléments sont divers polygones convexes : triangle, quadrilatère, pentagone, hexagone, etc. Une façon de former un ensemble ordonné à partir d'un ensemble non ordonné donné pourrait, par exemple, être de prendre un triangle comme premier élément de l'ensemble ordonné. , le deuxième est un quadrilatère, le troisième est un pentagone, etc., c'est-à-dire que nous classons l'ensemble par ordre croissant du nombre d'angles internes des polygones. L'ensemble des polygones peut être ordonné d'une autre manière, par exemple en listant les polygones par ordre croissant de superficie, lorsque le polygone avec la plus petite superficie est sélectionné comme premier, le polygone dont la superficie n'excède pas la superficie de tous les autres sauf celui déjà sélectionné est sélectionné comme deuxième, etc.

  Les ensembles ordonnés (finis ou dénombrables) sont souvent écrits en disposant leurs éléments dans un ordre donné entre parenthèses.

  Exemple

  Les notations (1 ; 2 ; 3) et (2 ; 1 ; 3) représentent différents ensembles ordonnés finis qui peuvent être obtenus à partir du même ensemble (1 ; 2 ; 3) en l'ordonnant de deux manières différentes.

  Pour écrire un ensemble ordonné dénombrable, vous devez indiquer le premier élément de l'ensemble ordonné et indiquer l'ordre (règle) de la disposition des éléments suivants.