Relations d'ordre. Relation d'ordre stricte Relation d'ordre sur l'ensemble des nombres naturels

Le dernier exemple introduit le concept d'ordre alphabétique.

Alphabet est un tuple de caractères distincts deux à deux appelés lettres de l'alphabet. Un exemple est l'alphabet de n'importe quelle langue européenne, ainsi que l'alphabet des chiffres arabes 10. Dans un ordinateur, le clavier et certaines aides déterminent l'alphabet des caractères valides.

Mot dans l'alphabetMAIS - tuple de caractères alphabétiques MAIS. Le mot s'écrit avec des caractères alphabétiques d'affilée, de gauche à droite, sans espaces Un nombre naturel est un mot de l'alphabet numérique Une formule n'est pas toujours un mot du fait de la disposition non linéaire des caractères la présence d'exposants (exposants ) et indices (indices de variables, bases de logarithmes) caractères, barre fractionnaire, signes radicaux, etc. ; cependant, selon certaines conventions, il peut être écrit dans une chaîne, qui est utilisée, par exemple, dans la programmation informatique (par exemple, le signe d'exponentiation s'écrit sous la forme de 2 signes de multiplication consécutifs : 5**3 signifie la troisième puissance de le chiffre 5.

Ordre lexico-graphique (alphabétique) - pour divers mots de l'alphabet avec ordre

ordre du jeu de caractères : si

présentation éventuelle , auquel soit

(le sous-mot peut être vide), ou - sous-mot vide

Dans cette définition - un préfixe (sous-mot initial) qui est le même pour les deux mots - ou le premier d'affilée à gauche sont différents

caractères, ou - le dernier caractère du mot - queue

sous-mots.

Ainsi, l'ordre alphabétique des mots est déterminé par le premier caractère qui les distingue de la gauche (par exemple, le mot KONUS précède le mot COSINUS, puisqu'ils diffèrent d'abord par la troisième lettre, et H précède C dans l'alphabet russe). On considère également que le caractère espace précède tout caractère de l'alphabet - pour le cas où l'un des mots est un préfixe de l'autre (par exemple, KOH et CONE)

L'exercice. Vérifiez que l'ordre alphabétique des nombres naturels qui ont le même nombre de chiffres en notation décimale est le même que leur ordre de grandeur.

Laisser être MAIS - ensemble partiellement ordonné. L'élément s'appelle maximum dans MAIS, s'il n'y a pas d'élément pour lequel mais< b. Élément mais appelé le plus grand dans MAIS, si pour autre chose que maisélément terminé b<а-

sont définis symétriquement minimum et moinséléments. Les concepts des éléments les plus grands et les plus maximaux (respectivement les plus petits et les plus minimaux) sont différents - voir. exemple sur la Fig.14. L'ensemble de la Fig. 14a a le plus grand élément R, c'est aussi le maximum, il y a deux éléments minimum : s et t il n'y a pas de plus petit. Sur la Fig. 14b, au contraire, l'ensemble ayant deux éléments maximum / et j, il n'y a pas de plus grand, de minimum, c'est le plus petit - un : T

En général, si un ensemble a un élément le plus grand (respectivement le plus petit), alors un seul (il peut n'y en avoir aucun).

Il peut y avoir plusieurs éléments maximum et minimum (peut-être pas du tout - dans un ensemble infini ; dans le dernier cas, il doit y en avoir).

Regardons deux autres exemples. - relation sur le plateau N:

"O divise X", ou "X est le diviseur du nombre Y"(par exemple,

) est réflexive et transitive. Considérez-le sur un ensemble fini de diviseurs du nombre 30.

La relation est une relation d'ordre partiel (non strict)

et est représenté par la matrice suivante d'ordre 8, contenant 31 caractères

Le schéma correspondant à 8 sommets doit contenir 31 faisceaux. . Cependant, il sera plus pratique pour la visualisation si nous excluons 8

des liens-boucles représentant la réflexivité de la relation (éléments diagonaux de la matrice) et des liens transitifs, c'est-à-dire liasses

S'il existe un nombre intermédiaire Z tel que

(par exemple, un tas parce que ). Puis dans le schéma

il y aura 12 ligaments (Fig. 15) ; les chaînons manquants sont sous-entendus "par transitivité". Le chiffre 1 est le plus petit et le chiffre 30

les plus grands éléments de . Si nous excluons du nombre 30 et

considérons le même ordre partiel sur l'ensemble , alors

il n'y a pas d'élément le plus grand, mais il y a 3 éléments maximum : 6, 10, 15

Construisons maintenant le même schéma pour la relation booléenne

(ensemble de tous les sous-ensembles) d'un ensemble de trois éléments

Contient 8 éléments :

Vérifiez que si vous faites correspondre les éléments un, b, c, les nombres 2, 3, 5, respectivement, et les opérations d'union d'ensembles sont la multiplication des nombres correspondants (c'est-à-dire, par exemple, un sous-ensemble correspond à

produit 2 5 = 10), alors la matrice de relation sera exactement

comme pour la relation ; schémas de ces deux relations avec les

les abréviations des boucles et des connecteurs transitifs coïncident jusqu'à la notation (voir Fig. 16). Le plus petit élément est

Et le plus grand -

relations binaires R sur le plateau MAIS Et S sur le plateau DANS appelé isomorphe si entre A et B il est possible d'établir une correspondance biunivoque Г, dans laquelle, si (c'est-à-dire

les éléments sont liés R), alors (images

ces éléments sont liés S).

Ainsi, les ensembles partiellement ordonnés et sont isomorphes.

L'exemple considéré admet une généralisation.

La relation booléenne est un ordre partiel. Si

Celles. beaucoup de E contient Péléments, alors chacun

le sous-ensemble correspond P-vecteur dimensionnel avec

composants , où est la fonction caractéristique

fixe A/ . L'ensemble de tous ces vecteurs peut être considéré comme un ensemble de points P espace arithmétique dimensionnel avec les coordonnées 0 ou 1, ou, en d'autres termes, comme sommets P-dimensionnel

cube unité, noté , c'est-à-dire cube dont les arêtes ont une unité de longueur. Pour n = 1, 2, 3 points indiqués représentent respectivement les extrémités du segment, les sommets du carré et du cube - d'où le nom commun. Pour /7=4, une représentation graphique de cette relation est sur la Fig.17. Près de chaque sommet du cube à 4 dimensions, le correspondant

sous-ensemble d'un ensemble à 4 éléments et à quatre dimensions

un vecteur représentant la fonction caractéristique de ce sous-ensemble. Les sommets sont connectés les uns aux autres, correspondant à des sous-ensembles qui diffèrent par la présence d'exactement un élément.

Dans la Fig. 17, un cube à quatre dimensions est représenté de telle manière que sur un

niveau il y a des éléments deux à deux incomparables contenant le même nombre d'unités dans l'enregistrement (de 0 à 4), ou, en d'autres termes, le même nombre d'éléments dans les sous-ensembles représentés.

Dans Fig.18a,b - d'autres représentations visuelles d'un cube à 4 dimensions ;

dans la Fig.18a l'axe de la première variable OH dirigé vers le haut (déviation intentionnelle de la verticale pour que les différentes arêtes du cube ne se confondent pas) :

tandis que le sous-cube tridimensionnel correspondant à X= 0 est situé en dessous, et pour X= 1 - supérieur. Sur la fig. 186 même essieu OH dirigé de l'intérieur du cube vers l'extérieur, le sous-cube intérieur correspond à X= Oh, et externe - X= 1.

DANS
Le fichier de matériau montre une image d'un cube unité à 5 dimensions (p. 134).

2) la relation sur l'ensemble X est appelée la relation commander strictement, s'il est antisymétrique et transitif. La relation s'appelle antisymétrique, si de ce que a est par rapport à c en il ne s'ensuit pas que in est par rapport à a (a, dans ∈ X, et R dans → dans R a) R - être en relation. La relation s'appelle transitif, si pour tout élément a, b, c du fait que a R dans et dans R c → que a R c, a, c, c ∈ X. Par exemple : la relation "plus, moins". Un ensemble sur lequel une relation d'ordre stricte est donnée est appelé ordonné de nombreux.

3) la relation sur l'ensemble X est appelée la relation pas dans un ordre strict, s'il est réflexif, asymétrique et transitif. Par exemple : rapport ≥ ≤. Si une relation d'ordre a la propriété d'être connexe, on dit qu'elle est une relation ordre linéaire. La relation s'appelle en relation sur l'ensemble X, si pour tous les éléments x et y la condition est satisfaite : du fait que x ≠ y il s'ensuit que x R y ou y R x. Si une relation d'ordre linéaire est donnée sur un ensemble, alors elle ordonne linéairement ensemble donné.

5. L'ensemble des nombres réels. Ses propriétés. La nécessité de mesurer les longueurs des segments, des aires, etc. a conduit à l'expansion de l'ensemble des nombres rationnels. Toute mesure est basée sur le même principe : l'objet mesuré est comparé à l'étalon (objet ou phénomène), dont la valeur a une valeur numérique égale à 1, mais pas toujours un seul segment est noyé dans l'objet mesuré. Par conséquent, lors de la mesure, 2 hypothèses sont faites, qui en mathématiques ont été définies comme des axiomes : 1) Une seule norme peut être divisée en un nombre quelconque de parts ou parties égales. 2) La norme choisie peut être utilisée pour mesurer n'importe quel objet arbitrairement grand. Pour les segments, ces axiomes ont été formulés par Archimède : Aussi petit que soit le segment AB et aussi grand que soit le segment CD, il existe un nombre naturel N tel que N*AB>CD, si un nombre égal de segments AB rentrent dans le CD du segment mesuré, alors la longueur du segment CD est exprimée sous la forme d'un nombre naturel. Si dans le segment mesuré CD le segment AB correspond un nombre inégal de fois, alors nous divisons AB en 10 segments identiques, appelés le dixième des normes. Si nécessaire, la dixième part peut être divisée en 10 parts égales, etc. Si un nombre égal de 10, 100, etc. rentre dans le segment CD. fractions de segments AB, alors la longueur du segment CD est exprimée sous la forme d'un nombre rationnel. Cependant, la longueur du segment ne peut pas toujours être exprimée sous forme de nombre naturel ou rationnel. Il existe des segments incommensurables, c'est-à-dire segments dont la longueur n'est pas exprimée par un nombre rationnel. (théorèmes voir question 32)

Les nombres qui peuvent être représentés comme des fractions décimales non récurrentes infinies sont appelés nombres irrationnels. L'union de l'ensemble des nombres rationnels et de l'ensemble des nombres irrationnels est l'ensemble des nombres réels ().

Propriétés de l'ensemble des nombres réels. une). L'ensemble des points de l'axe numérique est équivalent à l'ensemble des nombres réels.

0 M 1 Prendre n'importe quel point M sur le segment de 0 à 1,

Dessinez un demi-cercle centré sur

Le milieu de ce segment et le rayon

K O C égal à la moitié de celui-ci. Tracez une perpendiculaire de M à l'intersection avec le demi-cercle. On obtient D. Ce point est unique, puisque le demi-cercle et la droite se coupent en un seul point. Du milieu de ce segment à travers D, nous traçons une ligne droite jusqu'à l'intersection avec l'axe réel. On obtient K, qui est déterminé de manière unique, puisque les droites se coupent en un seul point. En choisissant un autre point arbitraire sur un segment donné et en répétant tout le processus, on obtient que tout point sur le segment de 0 à 1 correspond à un seul point sur la droite réelle. Se disputer dans ordre inverse on peut montrer que tout point sur la droite numérique correspond également à un seul point de 0 à 1. Si un point arbitraire E appartient à la droite numérique, alors une seule ligne peut être tracée à travers les points M et E qui coupe le demi-cercle . A partir d'un demi-cercle, vous pouvez déposer une perpendiculaire à un segment donné. Ainsi, entre les points du segment de 0 à 1 et les points de la droite numérique, une cartographie mutuellement identique est établie, c'est-à-dire ils sont égaux.

2) l'ensemble des nombres réels n'est pas dénombrable, c'est-à-dire il n'est pas égal à l'ensemble des nombres naturels.

3). L'ensemble des nombres réels est un ensemble continu. La continuité de l'ensemble des nombres réels est qu'entre deux nombres réels, il existe un ensemble infini de nombres réels uniquement

6. Diviser l'ensemble en classes. Exemples de classement. Relation d'équivalence, ses propriétés. Le rapport de la relation d'équivalence avec la division de l'ensemble en classes. Prenons un exemple. Soit donné l'ensemble M (un ensemble de polygones convexes), on forme tous les sous-ensembles de cet ensemble : A 1 - un ensemble de triangles ; A2 est un ensemble de quadrilatères ; А3 – ensemble de pentagones ; Ak est l'ensemble des k-gons. L'ensemble M est considéré comme divisé en classes si les conditions suivantes sont remplies :

1. chaque sous-ensemble A n'est pas vide
2. l'intersection de deux sous-ensembles est l'ensemble vide
3. l'union de tous les sous-ensembles est l'ensemble donné M

La division d'un ensemble en classes s'appelle classification.

Attitude sur l'ensemble X est appelé équivalent , s'il est réflexif, symétrique et transitif. La relation s'appelle réfléchissant, si tout élément de l'ensemble X est en relation avec lui-même a ∈ X, et R a (R est en relation). La relation s'appelle symétrique, si pour deux éléments quelconques de l'ensemble X (a et c) du fait que a est en relation avec c il s'ensuit que c est en relation avec a (a, c ∈ X, et R c → c R a). La relation s'appelle transitif, si pour tout élément a, b, c du fait que a R dans et dans R c → que a R c, a, c, c ∈ X. Il y a des boucles, des flèches mutuellement inverses et des flèches triangulaires sur le graphe des relation d'équivalence. La relation d'équivalence, et seulement elle, est liée à la division d'un ensemble en classes. Cette affirmation peut être formulée comme théorèmes: Si une relation d'équivalence est spécifiée sur l'ensemble X, alors cette relation divise l'ensemble X en classes, et inversement, si l'ensemble X est divisé en classes, alors la relation d'équivalence est satisfaite sur l'ensemble donné. Par exemple. Que la relation soit donnée - vivre dans la même maison. Montrons que l'ensemble des locataires de la maison sera divisé en classes. Et chaque classe est un appartement séparé. Pour cette division, tous les conditions nécessaires fractionnement de l'ensemble en classes : a) chaque classe n'est pas vide, car chaque appartement compte au moins 1 personne, mais est inscrite, b) les classes ne se chevauchent pas (1 personne n'est pas inscrite dans deux appartements différents), c) l'union de toutes les classes, c'est-à-dire locataires de chaque appartement, et constitue l'ensemble des locataires de la maison.

18 . Approche ensembliste de la construction de la théorie des entiers non négatifs. Relations d'égalité, plus (moins). Deux ensembles A et B sont dits équivalents ou équivalents si une correspondance biunivoque peut être établie entre eux, c'est-à-dire si chaque élément de l'ensemble A est associé à un seul élément de l'ensemble B et inversement. La puissance ou le nombre cardinal est une propriété inhérente à tout ensemble B, qui est égal en puissance à l'ensemble A, et n'est inhérente à aucun autre ensemble, qui n'est pas égal en puissance à l'ensemble A. A~B n (A) =a est la puissance. La relation d'équivalence est une relation d'équivalence, c'est-à-dire il satisfait les propriétés de réflexivité, de symétrie et de transitivité. La relation d'équivalence divise l'ensemble de tous les ensembles en classes d'équivalence. Pour définir le concept d'un nombre naturel et zéro, considérons une partition de tous les ensembles finis.

Soit M l'ensemble de tous les ensembles finis. M=K 0 Ka Kv, où Ko est une classe d'ensembles vides, Ka est un ensemble contenant des ensembles égaux a 1, a 2, a 3, etc., Kv est un ensemble. Contenant des ensembles égaux en 1 , en 2 , en 3 , etc. L'ensemble M peut également contenir d'autres sous-ensembles K de nature différente, constitués d'ensembles de même puissance. Chaque classe d'équivalence K a en commun d'être composée du même nombre d'éléments, il n'y a pas d'autres propriétés communes. Un entier non négatif d'un point de vue de la théorie des ensembles est une propriété générale d'une classe d'ensembles finis égaux. Un nombre naturel est une propriété générale de la classe des ensembles équipotents finis non vides. Chaque classe se voit attribuer un nombre cardinal (puissance). L'ensemble vide de classe se voit attribuer le numéro de coordonnée 0. La classe composée d'ensembles à 1 élément se voit attribuer le numéro 1. La classe constituée d'ensembles à 2 éléments se voit attribuer le numéro 2. (n(K 0)=0, n(K 1)=1, n(K 2)=2, n(Ka)=a).

Relation d'égalité. Les nombres entiers non négatifs a et b sont dits égaux si les ensembles A et B, dont ils expriment le nombre, sont équivalents (A ; n(A)=a, n(B)=b, A ~ B n(A )=n(B)a=c).

Théorème: la relation d'égalité dans l'ensemble des entiers non négatifs est une relation d'équivalence. Preuve. Montrons que la relation d'égalité a les propriétés de symétrie, de transitivité et de réflexivité.

Parce que les propriétés de réflexivité, de symétrie, de transitivité sont satisfaites, alors la relation d'égalité est une relation d'équivalence.

Rapport moins. Un entier non négatif a<в, если множество А равномощно собственному подмножеству В 1 множества В. а<в; n(А)=а; n(В)=в; В 1 В n(В 1)

Théorème : le rapport plus petit que dans l'ensemble des entiers non négatifs est une relation d'ordre strict. Preuve : Montrons que la relation moins que a les propriétés d'antisymétrie et de transitivité.

C 2 C 1 C 2 ~ B 1 C 2 ~ UNE n (A) \u003d n (C 2) n (C 2)

A B C 1 C

B 1 C 2

19 . Addition et soustraction dans la théorie quantitative des nombres entiers non négatifs. Leurs propriétés. somme deux entiers non négatifs a et b est appelé un entier non négatif c, qui est le cardinal de l'union de deux ensembles non sécants A et B, dont les cardinalités sont respectivement égales à a et c. a+b=c, n(C)=n(AUB), n(AUB)=n(A)+n(B).

Propriétés supplémentaires. 1. L'addition dans l'ensemble des entiers non négatifs existe toujours et est définie de manière unique. Montrons que la somme existe toujours. Considérons A et B tels que leur intersection est l'ensemble vide et le nombre d'éléments de A est a, et le cardinal de B est c. on trouve l'union de A et B. Puisque l'union de deux ensembles disjoints existe toujours, donc la somme existe, et de la définition de la somme il suit que l'addition existe toujours.

Montrons que la somme est déterminée de manière unique. Il existe C 1 et C 2 - entiers non négatifs. C 1 \u003d a + b et C 2 \u003d a + c. La somme des nombres a et b ne dépend pas des ensembles A et B que nous avons choisis dans la classe des ensembles équivalents, et donc l'union de A et B pris dans la classe des ensembles équivalents ne dépend pas du choix des ensembles A et B, parce que la puissance dans chaque classe est la même, alors C 1 \u003d C 2.

2. Commutativité de l'addition. Pour tous les entiers non négatifs a et b, la propriété a+b=b+a est remplie. Nous savons par la théorie des ensembles que pour AUB = BUA. Si les ensembles sont égaux, leurs valeurs numériques sont égales. n(AUB)=n(BUA). Nous savons par la théorie des ensembles que la cardinalité d'une union est égale à la somme des cardinalités. N(A)+n(B)=n(B)+n(A).

3. Propriété d'associativité. Pour tous les nombres a, b, c, la propriété suivante est vraie : a+(b+c)=(a+b)+c. De la théorie des ensembles, on sait que pour l'union d'ensembles, la propriété d'associativité est remplie: АU(ВУС)=(АУВ)UС, si les ensembles sont égaux, alors leurs valeurs numériques sont égales, n(АU (ВУС))=n((АУВ)UC). Il est connu de la théorie des ensembles que la cardinalité de l'union est égale à la somme des cardinalités de ces ensembles, n(A) + n (BUC) \u003d n (AUB) + n (C) n (A) + ( n (B) + n (C)) \u003d (n (A) + n (B)) + n (C) une + (b + c) \u003d (a + c) + c.

différence les entiers non négatifs a et b est appelé un entier non négatif c, qui est la puissance du complément de l'ensemble B à l'ensemble A, tel que B appartient à A, n(A)=a, n(B) =C.

Propriétés de différence. 1. Pour qu'il existe une différence d'entiers non négatifs, il faut et il suffit que a soit supérieur ou égal à b.

Prouvons: 1) une condition suffisante pour l'existence d'une différence. Étant donné : a - b = c, prouver : a c. Par la définition de la différence, il s'ensuit qu'il existe un complément de l'ensemble B à l'ensemble A, et ce complément a une cardinalité qui peut être trouvée à partir d'une égalité connue de la théorie des ensembles.

n () \u003d n (A) -n (B). Du fait que B est un sous-ensemble de A, il s'ensuit que le nombre d'éléments de B est inférieur au nombre d'éléments de A. n (B) dans; B entre dans A ; n(V)

2). Condition nécessaire. Donné un. prouver l'existence de la différence (a-c). Si a>b, par définition de la relation "inférieur à", il existe un ensemble A 1 tel que A 1 est inclus dans A et A 1 ~B. Composez la différence entre A et A 1. Cette différence existe toujours (A-A 1 \u003d C), et donc il existe C, qui est cette différence. De ces conditions, il s'ensuit que C est le complément de A 1 à A. C \u003d 1A La puissance de C est la puissance du complément de A 1 à A. n (C) \u003d n ( 1A) \u003d n ( A) -n (A 1) , puisque A 1 ~ B, alors n (A 1) \u003d n (B), donc n (C) \u003d n (A) -n (B), donc c \u003d ac .

2. La différence des entiers non négatifs se trouve de manière unique, puisque la différence est la cardinalité du complément des sous-ensembles à un ensemble, et le complément est défini de manière unique, alors la différence des entiers non négatifs est définis de manière unique.

3. Pour la soustraction, les propriétés de commutativité et d'associativité ne sont pas satisfaites.

4. Soustraction de la somme du nombre. a-(b+c)=(a-c)-c. D'après la théorie des ensembles, nous savons A\(BUC)=(A\B)\C, et B Ì A ; C Ì A; VUSÌA.

n (A\(BUC))=n((A\B)\C)

n(A)-n(BUC)=n(A\B)-n(C)

n(A)-(n(B)+n(C))=(n(A)-n(B))-n(C)

a-(b+c)=(a-c)-c.

5. Soustraire un nombre de la différence (a-c)-c \u003d (a-c)-c. La preuve est basée sur la propriété de différence d'ensemble (A\B)\C=(A\C)\B.

6. Soustraire un nombre de la somme (a+b)-c=(a-c)+c. La preuve est basée sur la propriété des ensembles (AUB)\C=(A\C)UB.

Désactivez adblock !
très nécessaire

Beaucoup de X (\displaystyle X), sur laquelle la relation d'ordre partiel est introduite, est appelée partiellement commandé. Une relation d'ordre partiel non stricte est souvent désignée par le symbole ≼ (\displaystyle \preccurlyeq ).

Choix

Relation d'ordre partiel R (\displaystyle R) appelé ordre linéaire si l'état

Beaucoup de X (\displaystyle X), sur laquelle la relation d'ordre linéaire est introduite, est appelée ordonné linéairement, ou chaîne.

Attitude R (\displaystyle R), qui ne satisfait que les conditions de réflexivité et de transitivité, est appelé précommande ou quasi-commande.

ordre strict

Si la condition de réflexivité est remplacée par la condition d'antiréflexivité :

alors on obtient la définition strict, ou ordre partiel antiréflexif(généralement désigné par le symbole ≺ (\displaystyle \prec )).

Commenter. L'antiréflexivité et la transitivité simultanées d'une relation impliquent l'antisymétrie. Le rapport est donc relation d'ordre stricte si et seulement si elle est antiréflexive et transitive.

En général, si R (\displaystyle R) est une relation transitive et antisymétrique, alors

Exemples

• Sur l'ensemble des nombres réels, les relations "supérieur à" et "inférieur à" sont des relations d'ordre strict, tandis que "supérieur ou égal à" et "inférieur ou égal à" sont des relations d'ordre non strict.
• La relation de divisibilité sur l'ensemble des entiers est une relation d'ordre non strict.

Dimension Dushnik-Miller

Histoire

Panneaux < {\displaystyle <} Et > (\displaystyle>) a inventé