Строга връзка на реда. Строга релация на ред Строго линейна релация на ред има свойствата

Думата "ред" често се използва в най-разнообразни въпроси. Офицерът дава команда: „Изчисли по реда на числата“, аритметичните операции се извършват в определен ред, спортистите стават на височина, всички водещи шахматисти се подреждат в определен ред според така наречените Ело коефициенти (американски професор който е разработил коефициентите на системата, която позволява да се вземат предвид всички успехи и неуспехи на играчите), след първенството всички футболни отбори са подредени в определен ред и т.н. засадено магаре не "!).

Като подреждаме елементите на определен набор един след друг, ние ги подреждаме или установяваме някаква връзка между тях. подред.Най-простият пример е естественият ред на естествените числа. Неговата естественост се състои в това, че за всеки две естествени числа знаем кое от тях следва другото или кое от тях е по-голямо от другото, така че можем да подредим естествените числа в последователност, така че да се намира по-голямото число, за например вдясно от по-малката: 1, 2, 3, ... . Разбира се, последователността от елементи може да бъде написана във всяка посока, а не само отляво надясно. Самата концепция за естествени числа вече съдържа идеята за ред. Установявайки някакво относително подреждане на елементите на всяко множество, ние по този начин задаваме върху него някакво двоично отношение на реда, което във всеки конкретен случай може да има собствено име, например "бъдете по-малко", "бъдете по-стари", "съдържа се в " , "следвай" и др. Символите за подреждане също могат да бъдат различни, например Í и др.

Основната отличителна черта на отношението на ред е, че то притежава свойството транзитивност. Така че, ако имаме работа с последователност от някои обекти x 1, x 2, ..., x n,... , подредени, например, по отношение на , след това от това, което се изпълнява х 1х 2... x n..., трябва да следва това за всеки чифт x i, x jелементи от тази последователност също се изпълняват x ixj:

За чифт елементи x iйв графиката на връзката рисуваме стрелка отгоре x iдо горе xj, т.е. от по-малък елемент към по-голям.

Графикът на връзката на поръчката може да се опрости чрез използване на т.нар Диаграми на Хасе.Диаграмата на Хасе се изгражда по следния начин. По-малките елементи са поставени отдолу, а големите са отгоре. Тъй като едно такова правило не е достатъчно за изображението, се чертаят линии, показващи кой от двата елемента е по-голям и кой е по-малък от другия. В този случай е достатъчно да начертаете само линии за непосредствено следващи елементи. Примери за диаграми на Хасе са показани на фигурата:

Стрелките могат да бъдат пропуснати в диаграма на Хасе. Диаграмата на Хасе може да се върти в равнината, но не произволно. При завъртане е необходимо да се поддържа относителната позиция (горе - долу) на върховете на диаграмата:

Поведение Рв множество хНаречен отношение на строг ред,ако е преходен и асиметричен.

Извиква се множество, в което е дефинирана строга релация на ред подреден.Например множеството от естествени числа е подредено чрез отношението "по-малко от". Но същото множество е подредено и от друга връзка - „е разделено на“ и „по-голямо“.

Графиката на връзката "по-малко от" в множеството от естествени числа може да бъде представена като лъч:

Поведение Рв хсе нарича релация нестрог (частичен) ред, ако е транзитивна и антисиметрична. Всяко отношение от нестрог ред е рефлексивно.

Епитетът "частичен" изразява факта, че може би не всички елементи на набор са сравними в това отношение.

Типични примери за отношение на частичен ред са "не повече", "не по-малко", "не по-старо". Частицата "не" в названията на отношенията служи за изразяване на тяхната рефлексивност. Отношението „не повече“ съвпада с отношението „по-малко или равно на“, а отношението „не по-малко“ е същото като „по-голямо или равно на“. В тази връзка се нарича и частичният ред отпуснатв ред. Често частична (нестрога) връзка на реда се обозначава със символа "".

Връзката на включване U между подмножества на някакво множество също е частичен ред. Очевидно не две подмножества са сравними в това отношение. Фигурата по-долу показва частичен ред чрез включване в множеството на всички подмножества на множеството (1,2,3). Стрелките на графиката, които трябва да сочат нагоре, не са показани.

Набори, на които е даден частичен ред, се наричат частично поръчан,или просто подреденкомплекти.

Елементи хи причастично подредено множество се наричат сравнявам,ако хприили приХ.Иначе не са сравними.

Нарича се подредено множество, в което всеки два елемента са сравними линейно подредени, а редът е линеен ред. Линейният ред се нарича още перфектен ред.

Например множеството от всички реални числа с естествен ред, както и всички негови подмножества, е линейно подредено.

Могат да се поръчват обекти от най-разнообразен характер йерархично.Ето няколко примера.

Пример 1: Частите на книга са подредени така, че книгата да съдържа глави, главите съдържат раздели, а разделите се състоят от подраздели.

Пример 2. Папките във файловата система на компютъра са вложени една в друга, образувайки разклонена структура.

Пример 3. Връзката родители – деца може да се изобрази под формата на т.нар семейно дърво,което показва кой чий е прародител (или потомък).

Нека на снимачната площадка НОдадена частична поръчка. елемент хНаречен максимум (минимум)елемент от множеството А, ако от факта, че хпри(приХ),следва равенството х= г.С други думи, елементът хе максимумът (минимумът), ако за всеки елемент приили това не е вярно хпри(прих), или се извършва х=г.По този начин максималният (минималният) елемент е по-голям (по-малък) от всички други елементи, с които е във връзка.

елемент хНаречен най-голям (най-малък),ако има приÎ НОизпълнени при< х (х< у).

Едно частично подредено множество може да има множество минимални и/или максимални елементи, но не може да има повече от един минимален и максимален елемент. Най-малкият (най-големият) елемент също е минимален (максимален), но обратното не е вярно. Фигурата отляво показва частичен ред с два минимални и два максимални елемента, а отдясно - частичен ред с най-малкия и най-големия елемент:

В крайно частично подредено множество винаги има минимални и максимални елементи.

Нарича се подредено множество, което има най-големия и най-малкия елемент ограничен .Фигурата показва пример за безкрайно ограничено множество. Разбира се, невъзможно е да се изобрази безкраен набор върху крайна страница, но е възможно да се покаже принципът на неговото изграждане. Тук не са показани примки близо до върховете, за да се опрости чертежа. По същата причина не се показват дъгите, които осигуряват показване на свойството транзитивност. С други думи, фигурата показва диаграма на Хасе на връзката на реда.

Безкрайните набори може да нямат максимум, минимум или и двете. Например наборът от естествени числа (1,2, 3, ...) има най-малък елемент 1, но няма максимум. Множеството от всички реални числа с естествен ред няма нито най-малък, нито най-голям елемент. Въпреки това, неговото подмножество, състоящо се от всички числа х< 5 има най-голям елемент (номер 5), но няма най-малък елемент.

Нека R е двоично отношение в множество A.

ОПРЕДЕЛЕНИЕ. двоична релация R върху множество A се нарича отношение на ред върху A или ред върху A, ако е транзитивно и антисиметрично.

ОПРЕДЕЛЕНИЕ. Отношение на ред R върху множество A се нарича нестриктно, ако е рефлексивно върху A, т.е. за всяко от A.

Отношението на реда R се казва, че е строго (върху A), ако е антирефлексивно върху A, т.е. за което и да е от A. Въпреки това, антисиметрията на транзитивно отношение R следва от факта, че то е антирефлексивно. Следователно можем да дадем следното еквивалентно определение.

ОПРЕДЕЛЕНИЕ. Бинарно отношение R върху множество A се нарича строг ред върху A, ако е транзитивно и антирефлексивно върху A.

Примери. 1. Нека е множеството от всички подмножества на множеството M. Отношението на включване върху множеството е нестрого отношение на ред.

2. Отношенията върху множеството от реални числа са съответно отношение от строг и нестрог ред.

3. Релацията на делимост в множеството от естествени числа е релация от нестрог ред.

ОПРЕДЕЛЕНИЕ. Бинарна релация R върху множество A се нарича релация на предварителен ред или преднаредба на A, ако е рефлексивна и транзитивна.

Примери. 1. Отношението на делимост в множеството от цели числа не е порядък. Той обаче е рефлексивен и транзитивен, което означава, че е предварителен.

2. Отношението на логическото следствие е предварителен ред върху множеството от пропозиционални логически формули.

Линеен ред. Важен специален случай на поръчка е линейната поръчка.

ОПРЕДЕЛЕНИЕ. Отношение на ред върху множество се нарича линейно отношение на ред или линеен ред на ако е свързано на , т.е. за всяко x, y от A

Отношение на реда, което не е линейно, обикновено се нарича отношение на частичен ред или частичен ред.

Примери. 1. Отношението "по-малко от" върху множеството от реални числа е отношение от линеен ред.

2. Отношението на реда, прието в речниците на руския език, се нарича лексикографско. Лексикографският ред на набора от думи в руския език е линеен ред.

Думата "ред" често се използва в различни въпроси. Офицерът дава команда: „Изчислете по ред на числата“, аритметичните операции се извършват в определен ред, спортистите стават на височина, има ред за извършване на операции при производството на част, ред на думите в изречение.

Какво е общото във всички случаи, когато става дума за ред? Фактът, че думата „ред“ има такова значение: означава кой елемент от този или онзи набор следва кой (или кой елемент предхожда кой).

Поведение " хследва при» преходно: ако « хследва при" и " приследва z", тогава " хследва z". Освен това това съотношение трябва да бъде антисиметрично: за две различни хи при, ако хследва при, тогава прине следва х.

Определение.Поведение Рна снимачната площадка хНаречен строго отношение на реда, ако е транзитивна и антисиметрична.

Нека да разберем характеристиките на графиката и графиката на строги отношения на ред.

Помислете за пример. На снимачната площадка х= (5, 7, 10, 15, 12) отношението Р: « х < при". Ние дефинираме тази връзка чрез изброяване на двойки
Р = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.

Нека изградим неговата графика. Виждаме, че графиката на тази връзка няма цикли. На графиката няма двойни стрелки. Ако от хстрелката отива към при, и от при- в z, след това от хстрелката отива към z(фиг. 8).

Построената графа ви позволява да подредите елементите на множеството хв този ред:

{5, 7, 10, 12, 15}.

На фиг. 6 (§ 6 от тази глава) колони VII, VIII са графики на отношения в строг ред.

Нестрога връзка на реда

Отношението "по-малко от" в множеството от реални числа е противоположно на отношението "не по-малко". Вече не е строг ред. Въпросът е, при х = при, отношения х ³ прии при ³ х, т.е. отношението "не по-малко" е рефлексивно.

Определение.Поведение Рна снимачната площадка хНаречен нестрога връзка на реда, ако е рефлексивен, антисиметричен и транзитивен.

Такива отношения са обединения на отношение на строг ред с отношение на идентичност.

Помислете за отношението "не повече" (£) за множеството

х= (5, 7, 10, 15, 12). Нека построим неговата графика (фиг. 9).

Графът на нестрога релационна връзка, за разлика от графа на строга релационна връзка, има цикли във всеки връх.

На фиг. 6 (§ 6 от тази глава) графики V, VI са графики на отношения от нестрог ред.

Поръчани комплекти

Едно множество може да се окаже подредено (те също така казват напълно подредено) от някакво отношение на реда, докато друго може да бъде неподредено или частично подредено от такова отношение.

Определение.Много хНаречен подреденнякакво отношение на реда Рако за всеки два елемента x, yот х:

(х, при) Î Рили ( y, x) Î Р.

Ако Ре строга релация на ред, тогава множеството хподредени от тази връзка при условие: ако х, привсеки два неравни елемента от множество х, тогава ( х, при) Î Рили ( y, x) Î Р, или произволни два елемента x, yкомплекти хса равни.

От училищния курс по математика е известно, че множествата на числата н , З , Q , Р подредени по съотношението „по-малко от“ (<).

Множеството от подмножества на определено множество не е подредено чрез въвеждането на релация на включване (U) или стриктна релация на включване (T) в горния смисъл, тъй като има подмножества, нито едно от които не е включено в другото. В този случай се казва, че даденото множество е частично подредено от релацията Í (или Ì).

Помислете за комплекта х= (1, 2, 3, 4, 5, 6) и има две отношения „по-малко от“ и „делимо на“. Лесно е да се провери, че и двете отношения са отношения на ред. Графиката на отношението по-малко от може да бъде представена като лъч.

Графиката на връзката "е разделена на" може да бъде представена само на равнина.

Освен това има върхове на графиката на втората релация, които не са свързани със стрелка. Например, няма стрелка, свързваща числата 4 и 5 (фиг. 10).

Първата връзка х < при' се нарича линеен. Като цяло, ако връзката на поръчката Р(строги и нестроги) на снимачната площадка хима свойството: за всякакви х, приÎ хили xRy, или yRx, тогава се нарича линейно отношение на реда, а множеството хе линейно подредено множество.

Ако наборът хразбира се, и се състои от нелементи, след това линейното подреждане хсвежда до изброяване на елементите си с числа 1,2,3, ..., н.

Линейно подредените множества имат редица свойства:

1°. Позволявам a, b, c– множество елементи х, подредени по отношение Р. Ако се знае, че aRvи vRc, тогава казваме, че елементът влежи между елементите аи с.

2°. Много х, линейно подредени от релацията Р, се нарича дискретно, ако между всеки два негови елемента лежи само краен набор от елементи на това множество.

3°. Линейно подредено множество се нарича плътно, ако за всеки два различни елемента от това множество има елемент от множеството, разположен между тях.

Важен тип бинарни отношения са отношенията на ред. Строга връзка на реда -бинарна връзка, която е антирефлексивна, антисиметрична и транзитивна:

обозначаване - (апредшестван б).Примери са

отношения "по-голям от", "по-малко от", "по-стар" и др. За числата обичайната нотация е знаците "<", ">".

Нестрога връзка на реда -бинарна рефлексивна, антисиметрична и транзитивна връзка. Наред с естествените примери за нестроги неравенства за числата, пример е отношението между точки в равнина или пространство „да бъде по-близо до началото“. Нестрогото неравенство, за цели числа и реални числа, може също да се разглежда като дизюнкция на равенство и отношения на строг ред.

Ако спортен турнир не предвижда разделяне на местата (т.е. всеки участник получава определено, само яде / присъдено място), тогава това е пример за строг ред; в противен случай не е строг.

Отношенията на реда се установяват върху множество, когато за някои или всички двойки от неговите елементи, отношението

предимство . Настройка - за набор се извиква някакво отношение на реда неговото "нареждане,и „себе си.задават в резултат на това става подреден.Отношенията на реда могат да бъдат въведени по различни начини. За крайно множество, всяка пермутация на неговите елементи "специфицира някакъв строг ред. Едно безкрайно множество може да бъде подредено по безкраен брой начини. Само онези подреждания, които имат смислено значение, представляват интерес.

Ако за отношението на поръчката Рна снимачната площадка .Ми някои различни елементи, поне една от връзките е спазена

aRbили b Ra,след това елементите аи bНаречен сравнимив противен случай - несравним.

Напълно (или линейно) подредено множество М -

множество, на което е дадено отношението на реда, и всеки два елемента от множеството Мсъпоставим; частично подреден набор- еднакви, но се допускат двойки несравними елементи.

Линейно подредено множество е множество от точки на права линия с отношението "надясно", набор от цели, рационални, реални числа по отношение на "по-голямо от" и т.н.

Пример за частично подредено множество са триизмерни вектори, ако редът е даден така, сякаш

Тоест, ако предимството е изпълнено и в трите координати, векторите (2, 8, 5) и (6, 9, 10) са сравними, а векторите (2, 8, 5) и (12, 7, 40) ) не са сравними. Този начин на подреждане може да се разшири до вектори с произволно измерение: вектор

предшества вектора if

И готово

Други примери за подреждане могат да бъдат разгледани върху множеството от вектори.

1) частична поръчка: , ако

Тези. по дължината на векторите; вектори с еднаква дължина са несравними.

2) линеен ред: , ако а ако а-г,тогава b< е ; ако jed \u003d c? u6 \u003d e, тогава