Відносини порядку. Відношення суворого порядку Відношення порядку на множині натуральних чисел

Останній приклад є поняття алфавітного порядку.

Алфавіт- Це кортеж попарно різних символів, званих буквами алфавіту. Прикладом є алфавіт будь-якої європейської мови, а також алфавіт з 10 арабських цифр У комп'ютері клавіатура та деякі допоміжні засоби визначають алфавіт допустимих символів.

Слово в алфавітіА -кортеж із символів алфавіту А.Слово записується символами алфавіту поспіль, зліва направо, без пробілів Натуральне число є словом в цифровому алфавіті радикалів та ін; однак, шляхом деяких угод вона може бути приведена до запису в рядок, що й застосовується, наприклад, у комп'ютерному програмуванні (так, знак зведення у ступінь записується як 2 знаки множення поспіль: 5**3 означає третій ступінь числа 5).

Лексико-графічне (алфавітне) впорядкування -для різних слів в алфавіті з упорядкованими

символами встановлюється впорядкування: , якщо

можливе уявлення , при якому або

(підслів може бути порожнім), або - порожнє підслівне

У цьому визначенні - префікс (початкове підслів), однаковий у обох слів - або перші за рахунком зліва різні

символи, або - останній символ у слові-хвостові

підслів.

Таким чином, алфавітне впорядкування слів визначається першим ліворуч символом, що розрізняє їх (наприклад, слово КОНУС передує слову КОСИНУС, оскільки вони вперше різняться в третій букві, і Н передує С в російському алфавіті). Вважається також, що символ пробілу передує будь-якому символу алфавіту – для випадку, коли одне зі слів є префіксом іншого (наприклад, КОН та КОНУС)

Вправа.Перевірте, що алфавітне впорядкування натуральних чисел, що мають однакове число розрядів у десятковому записі, співпадає з упорядкуванням їх за величиною.

Нехай А -частково впорядковане безліч. Елемент називається максимальнимв А,якщо не існує елемента для якого а< b. Елемент аназивається найбільшимв А,якщо для будь-якого відмінного від аелемента виконано Ь<а-

Симетричним чином визначаються мінімальний та найменшийелементів. Поняття найбільшого та максимального (відповідно, найменшого та мінімального) елементів різні -див. приклад на рис.14. Безліч на рис. 14,а має найбільший елемент р,він же є максимальним, мінімальних елементів два: s та t,найменшого немає. На рис.14,б, навпаки, безліч, що має два максимальні елементи / і jнайбільшого немає, мінімальний, він найменший - один: т.е.

Взагалі, якщо у множини є найбільший (відповідно, найменший) елемент, то тільки один (може не бути жодного).

Максимальних і мінімальних елементів може бути кілька (може не бути зовсім – у нескінченній множині; в кінцевому випадку – обов'язково є).

Розберемо ще два приклади. - відношення на безлічі N:

"Yділить X",або "Xє дільником числа Y"(наприклад,

) є рефлексивним та транзитивним. Розглянемо його на кінцевій множині дільників числа 30.

Ставлення є відношенням часткового порядку (не суворого)

та зображується наступною матрицею порядку 8, що містить 31 знак

Відповідна схема з 8 вершинами має містити 31 зв'язку. . Однак вона буде більш зручною для огляду, якщо виключити 8

зв'язок-петель, що зображають рефлексивність відношення (діагональні елементи матриці) та транзитивні зв'язки, тобто. зв'язки

Якщо є проміжне число Z таке, що

(Наприклад, зв'язку , оскільки ). Тоді у схемі

залишиться 12 зв'язок (рис.15); відсутні ланки маються на увазі "по транзитивності". Число 1 є найменшим, а число 30

найбільшим елементами у . Якщо виключити з числа 30 і

розглянути той самий частковий порядок на безлічі ,

найбільшого елемента немає, але є 3 максимальні елементи: 6, 10, 15

Тепер побудуємо таку ж схему для відношення на булеані

(Большості всіх підмножин) триелементної множини

Містить 8 елементів:

Перевірте, якщо порівняти елементам а,Ь,с,відповідно числа 2, 3, 5, а операції об'єднання множин - множення відповідних чисел (тобто, наприклад, підмножина відповідає

добуток 2 5 = 10), то матриця відношення буде точно такою

ж, як для відношення; схеми цих двох відносин із описаними

скороченнями петель та транзитивних зв'язок з точністю до позначень збігаються (див. рис.16). Найменшим елементом є

А найбільшим –

Бінарні відносини Rна безлічі Аі Sна безлічі Вназиваються ізоморфними,якщо між А і Вможна встановити взаємно однозначне відповідність Р, у якому, якщо (тобто.

елементи знаходяться у відношенні R),то (образи

цих елементів знаходяться у відношенні S).

Так, частково впорядковані множини та ізоморфні.

Розглянутий приклад припускає узагальнення.

Ставлення на булеані є частковим порядком. Якщо

Тобто. безліч Емістить пелементів , то кожному

підмножині відповідає п-мірний вектор з

компонентами , де - характеристична функція

множини Л/. Сукупність всіх таких векторів можна розглядати як безліч точок. п-мірного арифметичного простору з координатами 0 або 1, або по-іншому, як вершини п-мірного

одиничного куба, що позначається, тобто. куба з ребрами одиничної довжини. Для п = 1, 2, 3 зазначені точки є відповідно кінці відрізка, вершини квадрата і куба - звідси загальна назва. Для /7=4 графічне зображення цього відношення – на рис.17. Біля кожної вершини 4-мірного куба вказано відповідне

підмножина 4-елементної множини та чотиривимірна

вектор, що представляє характеристичну функцію цього підмножини. З'єднані між собою вершини, що відповідають підмножинам, які різняться присутністю рівно одного елемента.

На рис.17 чотиривимірний куб зображено так, що на одному

рівні розташовані попарно не порівняні елементи, що містять однакове число одиниць у записі (від 0 до 4), або, по-іншому, однакове число елементів у подмножествах, що представляються.

На рис.18а,б - інші наочні уявлення 4-мірного куба;

на рис.18а вісь першої змінної ОХспрямована вгору (навмисне відхилення від вертикалі, щоб не зливалися різні ребра куба):

при цьому 3-мірний підкуб, відповідний X= 0 розташований нижче, а для X= 1 – вище. На рис. 186 та сама вісь ОХспрямована зсередини куба назовні внутрішній підкуб відповідає X= О, а зовнішній - X = 1.

В
файлі матеріалів наведено зображення 5-мірного одиничного куба (стор.134).

2) відношення на множині Х називається ставленням строго порядкуякщо воно антисиметричне і транзитивне. Ставлення називається антисиметричним, якщо з того, що а знаходиться у відношенні з в не випливає, що у знаходиться у відношенні з а (а, в ∈ Х, а R в → в R а) R – перебувати у відношенні.Ставлення називається транзитивним, якщо для будь-яких елементів а, в, з того, що а R в і R з → що а R с, а, в, з ∈ Х. Наприклад: відношення «більше, менше». Багато, на якому поставлено ставлення строгого порядку, називається упорядкованимбезліччю.

3) відношення на множині Х називається ставленням не суворого порядкуякщо воно рефлексивне, асиметричне і транзитивне. Наприклад: відношення ≥ ≤. Якщо відношення порядку має властивість зв'язності, то кажуть, що воно є відношенням лінійного порядку. Ставлення називається пов'язанимна множині Х, якщо для будь-яких елементів х і у виконується умова: з того, що х ≠ у слід, що х R у або у R х. Якщо на безлічі задано ставлення лінійного порядку, воно лінійно впорядковує це безліч.

5. Безліч дійсних чисел. Його властивості. До розширення безлічі раціональних чисел призвела необхідність виміру довжин відрізків, площ тощо. В основі будь-якого виміру лежить той самий принцип: вимірюваний об'єкт порівнюється з еталоном (предметом або явищем), величина якого має чисельне значення, рівне 1, але не одиничний відрізок вкладається в об'єкті, що вимірювається. Тому при вимірі роблять 2 припущення, які в математиці визначилися як аксіоми: 1) Одиничний еталон можна розділити на будь-яку кількість рівних між собою часток або частин. 2) Вибраним стандартом можна вимірювати будь-який великий об'єкт. Для відрізків ці аксіоми сформулював Архімед: Яким би малим відрізок АВ і хоч би як був великий відрізок СД, існує таке натуральне число N, що N*AB>CD, якщо у вимірюваному відрізку CD вклалося рівне число відрізків АВ, то довжина відрізка CD виражається натуральним числом. Якщо у вимірюваному відрізку CD відрізок АВ укладається нерівне число разів, то АВ розбиваємо на 10 однакових відрізків, званих десятою часткою еталонів. За потреби десята частка може розбиватися на 10 рівних частин тощо. Якщо у відрізок CD укладається рівне число 10, 100 тощо. часткою відрізків АВ, то довжина відрізка CD виражається раціональним числом. Однак не завжди довжина відрізка може виражатися натуральним чи раціональним числом. Існують непорівнянні відрізки, тобто. відрізки, довжина яких виражається раціональним числом. (теореми дивись питання 32)

Числа, які можуть бути представлені у вигляді нескінченних десяткових неперіодичних дробів називається ірраціональними. Об'єднання безлічі раціональних чисел і множини ірраціональних чисел є безліч дійсних чисел ().

Властивості безлічі дійсних чисел. 1). Безліч точок числової осі рівномірно безлічі дійсних чисел.

0 М 1 Візьмемо на відрізку від 0 до 1 будь-яку точку М,

Д проведемо півколо з центром в

Середині цього відрізка та радіусом

К О С дорівнює половині його. Проведемо перпендикуляр із М до перетину з півколом. Отримаємо Д. Ця точка єдина, оскільки півколо і пряма перетинаються лише у одній точці. З середини даного відрізка через Д проведемо пряму до перетину з числовою віссю. Отримаємо До, яка визначається єдиним чином, так як прямі перетинаються тільки в одній точці. Вибираючи іншу довільну точку на заданому відрізку та повторюючи весь процес отримаємо, що будь-якій точці відрізка від0 до 1 відповідає єдина точка числової прямої. Розмірковуючи в зворотному порядкуможна показати, що будь-якій точці числової прямої також відповідає єдина точка від 0 до 1. Якщо довільна точка Е належить числової прямої, то через точки М і Е можна провести тільки одну пряму, яка перетне півколо. З півкола можна опустити перпендикуляр на заданий відрізок. Отже, між точками відрізка від 0 до 1 і точками числової прямої встановлюється взаємно однакове відображення, тобто. вони рівносильні.

2) безліч дійсних чисел є рахунковим, тобто. воно не дорівнює безлічі натуральних чисел.

3). Багато дійсних чисел є безперервним безліччю. Безперервність безлічі дійсних чисел полягає в тому, що між будь-якими двома дійсними числами знаходиться безліч тільки дійсних чисел

6. Розбиття множини на класи. Приклад класифікації. Відношення еквівалентності, його властивості. Взаємозв'язок відносини еквівалентності з розбиттям множини на класи. Розглянемо з прикладу. Нехай задано безліч М (множина опуклих багатокутників), утворюємо всі підмножини даної множини: А 1 – безліч трикутників; А2 – безліч чотирикутників; А3 – безліч п'ятикутників; Ак – безліч до-кутників. Безліч М вважається розбитим на класи, якщо виконуються такі умови:

1. кожне підмножина А не пусто
2. перетину будь-яких двох підмножин є порожньою множиною
3. об'єднання всіх підмножин є ця безліч М

Розбиття множини на класи називається класифікацією.

Ставленняна множині Х називається еквівалентним якщо воно рефлексивне, симетричне і транзитивне. Ставлення називається рефлексивним, якщо будь-який елемент із множини Х знаходиться у відношенні сам із собою а ∈ Х, а R а (R – перебувати у відношенні). Ставлення називається симетричним, якщо для будь-яких двох елементів множини Х (а і в) з того, що а знаходиться у відношенні з в, буде слідувати, що знаходиться у відношенні з а (а, в ∈ Х, а R в → в R а). Ставлення називається транзитивним, якщо для будь-яких елементів а, в, з того, що а R в і R з → що а R с, а, в, с ∈ Х. На графі відношення еквівалентності є петлі, взаємно зворотні стрілки і трикутні стрілки. Відношення еквівалентності, і тільки воно, пов'язане з розбиттям множини на класи. Це твердження можна сформулювати як теореми: Якщо на множині Х поставлено відношення еквівалентності, то це відношення розбиває безліч Х на класи, і навпаки, якщо безліч Х розбито на класи, то на заданій множині виконується відношення еквівалентності. Наприклад. Нехай ставиться ставлення – жити в одному будинку. Покажемо, що багато мешканців у будинку буде розбите на класи. А кожен клас – це окрема квартира. Для цього поділу виконуватимуться всі необхідні умовирозбиття множини на класи: а) кожен клас не порожній, т.к. у кожному квартирі хоча б 1 людина, але прописаний, б) класи не перетинаються (1 людина не прописаний у різних квартирах), в) об'єднання всіх класів, тобто. мешканців кожної квартири, і складає безліч мешканців будинку.

18 . Теоретико-множинний підхід до побудови теорії цілих негативних чисел. Відносини рівності, більші (менші). Дві множини А і В називаються еквівалентними або рівносильними, якщо між ними можна встановити взаємнооднозначну відповідність, тобто якщо кожному елементу множини А ставиться у відповідність єдиний елемент множини В і навпаки. Потужність або кардинальне число – це така властивість, яка притаманна будь-якій множині В, рівносильній множині А і не притаманна жодній іншій множині не рівнопотужній множині А. А~В n(А)=а – це потужність. Ставлення рівноваги є ставленням еквівалентності, тобто. для нього виконуються властивості рефлексивності, симетричності та транзитивності. Ставлення рівнопотужності розбиває безліч усіх множин на класи еквівалентності. Для визначення поняття натурального числа та нуля розглянемо розбиття всіх кінцевих множин.

Нехай М це безліч усіх кінцевих множин. М = К 0 Ка Кв, де Ко - це клас порожніх множин, Ка - це безліч, що містить рівносильні множини а 1, а 2, а 3 і т.д., Кв - це безліч. Що містить рівносильні множини в 1, 2, 3 і т.д. Безліч М може містити й інші підмножини різної природи, які складаються з рівносильних множин. У кожного класу еквівалентності є спільне те, що вони складаються з однакової кількості елементів, інших загальних властивостей немає. Ціле невід'ємне число з теоретико-множинної точки зору є загальна властивість класу кінцевих рівносильних множин. Натуральне число є загальною властивістю класу не порожніх кінцевих рівносильних множин. Кожному класу приписується кардинальне число (потужність). Класу порожня множина приписується координальне число 0. Класу, що складається з множин, що мають 1 елемент, приписується число1. Класу, що складається з множин, що мають 2 елементи, приписується число 2. (n(К 0)=0, n(К 1)=1, n(К 2)=2, n(Ка)=а).

Відношення рівності. Цілі невід'ємні числа а і в називаються рівними, якщо множини А і В, чисельність яких вони виражають, рівносильні (А; n(А)=а, n(В)=в, ~ ~ n(А)=n(В) а = в).

Теорема: відношення рівності у багатьох цілих невід'ємних чисел є відношенням еквівалентності Доведення. Доведемо, що відношення рівності має властивості симетричності, транзитивності та рефлексивності.

Т.к. характеристики рефлексивності, симетричності, транзитивності виконуються, то відношення рівності є ставленням еквівалентності.

Ставлення менше. Ціле невід'ємне число а<в, если множество А равномощно собственному подмножеству В 1 множества В. а<в; n(А)=а; n(В)=в; В 1 В n(В 1)

Теорема: відношення менше в багатьох цілих невід'ємних чисел є ставленням строго порядку. Доказ: Доведемо, що відношення менше має властивості антисиметричності і транзитивності.

З 2 З 1 З 2 ~В 1 З 2 ~А n(А)=n(З 2) n(З 2)

А В С 1 С

В 1 З 2

19 . Додавання та віднімання в кількісній теорії цілих невід'ємних чисел. Їхні властивості. Сумоюдвох цілих неотрицательных чисел а і називається ціле неотрицательное число з, що є потужністю об'єднання двох непересічних множин А і В, потужності яких відповідно рівні а і в. а+в=с, n(С)=n(АUВ), n(АUВ)=n(А)+n(В).

Властивості додавання. 1. Додавання у безлічі цілих невід'ємних чисел завжди існує і визначається єдиним чином. Доведемо, що сума завжди є. Розглянемо А і В, такі, що їх перетин порожня множина і число елементів А є а, а потужність В є - в. знайдемо об'єднання А і У. Оскільки об'єднання двох непересекающихся множин завжди існує, отже є і сума, та якщо з визначення суми слід, що додавання завжди існує.

Доведемо, що сума визначається єдиним чином. Існує З 1 і З 2 – невід'ємні цілі числа. З 1 = а + в і З 2 = а + в. Сума чисел а і в не залежить від того, які множини А і В ми вибрали з класу рівносильних множин, а отже і об'єднання А і В, взятих з класу рівносильних множин не залежить від вибору множин А і В, тому що потужності в кожному класі однакові, то С1 = С2.

2. Камутотивність додавання. Для будь-яких цілих невід'ємних чисел а і виконується властивість а+в=в+а. З теорії множин знаємо, що для АUВ = ВUА. Якщо рівні множини, рівні їх чисельні значення. n(АUВ) = n(ВUА). З теорії множин знаємо, що потужність об'єднання дорівнює сумі потужностей. N(А)+n(B)=n(B)+n(A).

3. Властивість асоціативності. Для будь-яких чисел а, в, з виконується властивість: а+(в+с)=(а+в)+с. З теорії множин відомо, що для об'єднання множин виконується властивість асоціативності: АU(ВUС)=(АUВ)UС, якщо рівні множини, то дорівнюють їх чисельні значення, n(АU(ВUС))=n((АUВ)UС). З теорії множин відомо, що потужність об'єднання дорівнює сумі потужностей цих множин, n(А)+n(ВUС)=n(АUВ)+n(С) n(А)+(n(В)+n(С))= (n(А)+n(В))+n(С) а+(в+с)=(а+в)+с.

Різницяцілих неотрицательных чисел а і називається ціле неотрицательное число з, що є потужністю доповнення множини В до множини А, таких, що належить А, n(А)=а, n(В)=в.

Властивості різниці. 1. Для того щоб різниця цілих невід'ємних чисел існувала, необхідно і достатньо, щоб було більше або дорівнює в.

Доведемо: 1) достатня умова існування різниці. Дано: а – в = с, довести: а в. За визначенням різниці слід, що існує доповнення множини до безлічі А, і це доповнення має потужність, яку можна знайти з рівності, відомого з теорії множин.

n() = n(А)-n(В). З того, що є підмножиною А випливає, що число елементів В менше числа елементів А. n (В) в; Входить у А; n(В)

2). Необхідна умова. Дано а ст. довести існування різниці (а-в). Якщо а>в, за визначенням відношення «менше» існує безліч А 1, таке, що А 1 входить в А і А 1 ~В. Складемо різницю А і А 1. Ця різниця завжди існує (А-А 1 = С), а отже існує З, яке є цією різницею. З цих умов випливає, що є доповненням А 1 до А. С = 1А Потужність С є потужність доповнення А 1 до А. n (С)=n( 1А)=n(А)-n(А 1) , так як А 1 ~ В то n(А 1)=n(В), отже n(С)=n(А)-n(В), отже з=а-в.

2. Різниця цілих неотрицательных чисел знаходиться єдиним чином, оскільки різницю є потужність доповнення підмножин до множини, а доповнення визначається єдиним чином, те й різниця цілих неотрицательных чисел визначається єдиним чином.

3. Для віднімання не виконуються властивості комутативності та асоціативності.

4. Віднімання суми з числа. а-(в+с)=(а-в)-с. З теорії множин відомо А\(ВUС)=(А\В)\С, причому В Ì А; С Ì А; ВУСІЯ.

n (А\(ВUС))=n((А\В)\С)

n(А)-n(ВUС)=n(А\В)-n(С)

n(А)-(n(В)+n(С))=(n(А)-n(В))-n(С)

а-(в+с)=(а-в)-с.

5. Віднімання числа від різниці (а-в)-с=(а-с)-в. Доказ ґрунтується на властивості різниці множин (А\В)\С=(А\С)\В.

6. Віднімання числа із суми (а+в)-с=(а-с)+в. Доказ спирається на властивість множин (АУВ) С = (А С) UВ.

Вимкніть adBlock!
дуже потрібно

Безліч X (\displaystyle X), на якому введено відношення часткового порядку, називається частково впорядкованим. Відношення нестрогого часткового порядку часто позначають знаком ≼ (\displaystyle \preccurlyeq ).

Варіанти

Відношення часткового порядку R (\displaystyle R)називається лінійним порядком, якщо виконано умову

Безліч X (\displaystyle X), на якому введено відношення лінійного порядку, називається лінійно впорядкованим, або ланцюгом.

Ставлення R (\displaystyle R), що задовольняє лише умовам рефлексивності та транзитивності, називається передпорядком , або квазіпорядком.

Суворий порядок

Якщо умову рефлексивності замінити на умову антирефлексивності:

то отримаємо визначення строгого, або антирефлексивного часткового порядку(позначається зазвичай символом ≺ (\displaystyle \prec )).

Зауваження. Одночасна антирефлексивність та транзитивність відношення спричиняє антисиметричність. Тому ставлення є ставленням суворого порядкутоді й лише тоді, коли воно антирефлексивне та транзитивне.

У загальному випадку, якщо R (\displaystyle R)- транзитивне, антисиметричне відношення, то

Приклади

• На безлічі речових чисел відношення «більше» і «менше» є відносинами суворого порядку, а «більше або одно» і «менше або одно» - не суворого.
• Ставлення подільності на безлічі цілих чисел є ставленням не суворого порядку.

Розмірність Душника - Міллера

Історія

Знаки < {\displaystyle <} і > (\displaystyle >)винайдені