10.9. Максимальні і мінімальні елементи
Не змішуйте перший елемент з мінімальним, а останній з максимальним. Це справедливо тільки в тому випадку, коли множина впорядкована по величині.
Означення 6. Елемент a ( (A, R) називається мінімальним якщо він не має попередніх.
Означення 7. Елемент a ( (A, R) називається максимальним, якщо він не має наступних.
Приклад. Нехай множина (A,R) = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} є впорядкована таким чином, що x ( y тоді і тільки тоді, коли y ділиться на х. Представимо бінарне відношення перечисленням всіх його елементів:
R = {(2, 4), (2, 6), (2, 8), (2, 10), (2, 12), (3, 6), (3, 9), (3, 12), (4, 12), (5, 10), (6,12)}.
Звертаємо вашу увагу, що порядок є частковим (тобто, не всі елементи A є порівняльні), і строгим (виключаються випадки коли число ділиться само на себе – рефлексивність).
Множина А не має ні першого, ні останнього елемента ( не змішуйте множину A саму по собі з впорядкованою множиною (A,R)). Але 2, 3, 5, 7, 11 є мінімальними, а 7, 8, 9, 10, 11, 12 максимальними елементами. Як бачимо, один елемент – 7, є і мінімальним, і максимальним одночасно.
10.10. Нижня і верхня грані
Означення 7. Нехай B є підмножина частково впорядкованої множини (A, R). Елемент m(A називається нижньою гранню B, якщо для ( x ( B
m ( x,
тобто, m передує будь якому елементу B. Сама більша з нижніх граней B, якщо вона існує, називається точною нижньою гранню і позначається
inf(B).
Взагалі, B може не мати жодної нижньої грані, а може мати й багато їх. Але точна нижня грань inf(B), якщо вона існує, може бути лише одна.
Означення 8. Нехай B є підмножина частково впорядкованої множини (A, R). Елемент m(A називається верхньою гранню B, якщо для ( x ( B
x ( m,
тобто, будь якому елемент B передує m. Найменша з верхніх граней B, якщо вона існує, називається точною верхньою гранню і позначається
sup(B).
Взагалі, B може не мати жодної верхньої грані, а може мати й багато їх. Але точна верхня грань sup(B), якщо вона існує, може бути лише одна.
Приклад 1. Нехай V = {a, b, c, d, e} впорядкована наступною діаграмою
a
b
c
d
e
f g
і нехай B = {c, d, e}. Тоді, a, b, c є верхні грані, але тільки c = sup(B) e c ( B. f є єдиною нижньою гранню, тому f = inf(B) e f ( B. Зверніть увагу, що g не є нижньою гранню, тому що не всі елементи B слідують за ним.
Приклад 2. Нехай B = {x: x ( Q, 2 < x2 < 3}. Іншими словами, B складається з усіх раціональних чисел між (2 і (3. Тоді B має нескінчену множину як верхніх, так і нижніх граней, але не має ні inf(B) ні sup(B) ((2 і (3 не належать Q і тому не можуть служити як inf(B) або sup(B), з іншого боку, між будь якими раціональним і ірраціональними числами існує як завгодно багато раціональних чисел).
10.11. Подібні множини
Означення 9. Дві впорядковані множини називаються подібними, якщо існує бієктивна аплікація однієї з них на іншу, яка зберігає відношення порядку. Іншими словами,
A ( B
якщо існує бієктивна функція f: A ( B з властивостями : для будь яких a ( A, b ( A,
a ( b тоді і тільки тоді, коли f(a) ( f(b).
Приклад. Нехай V = {1, 2, 6, 8} впорядковане відношенням “ у ділиться на х “ і нехай W = {a, b, c, d} впорядкована діаграмою
a
b
c
d
Замітимо, що порядок у V також можна зобразити діаграмою
8 6
2
1
Тоді V ( W, тому що аплікація f = {(1, d), (2, c), (8, a), (6, b)} зберігає відношення порядку.
Теорема 1. Якщо A тотально впорядкована і A ( B, то B також є тотально впорядкованою.
Доведення. Якщоe A є тотально впорядкована, то для будь яких x ( A і y ( A
x ( y або x ( y.
Але так як A ( B, існує f: A ( B така, що f(x) ( f(y) або f(x) ( f(y). Так як f є бієктивною, то будь які два елементи В єсть образами певних елементів А і тому є порівняльні. Це значить, що множина В також є тотально впорядкована.
Теорема 2. Якщо A ( B, то A ( B.
Доведення. Щоб довести еквівалентність двох множин досить знайти бієктивну аплікацію однієї з них на другу. Але така аплікація існує по самому визначенню подібних множин.
Теорема 3. Відношення подібності двох множин є еквівалентність.
Доведення.
A ( A – функція f в цьому випадку є ідентичністю IA – відношення рефлексивне.
Якщо A( B то B( A (так як f є бієктивна, існує обернена функція f -1: B(A , що зберігає відношення порядку) – відношення симетричне.
Якщо A( B e B( C, існують f: A ( B і g: B ( C. Але в цьому випадку функція g(f: A ( C зберігає відношення порядку , значить A ( C – відношення транзитивне.
Отже, відношення подібності множин задовольняє всім умовам еквівалентності.
Вправи на закріплення.
Відношення x ( y в N визначено як “ у ділиться на х ”.
Довести, що x ( y є частковий порядокl;
b) Поставте символи ( , ( або I (непорівняльні) між елементами кожної пари чисел:
(2, 8), (18, 24), (9, 3), (5, 15)
с) Чи є кожна із наступних підмножин N тотальним порядком?
{24, 2, 6}; {3, 15, 5}; {15, 5, 30}; {2, 8, 32, 4}; {1, 2, 3,…}; {5}.
Нехай V = {a, b, c, d} впорядкована наступною діаграмою
a
b
c
d e
a) Поставте символи ( , ( або I (не порівняльні ) між елементами кожної пари:
(a, e); (b, c); (d, a); (c, d);
b) Побудуйте діаграму оберненого відношення.
3. Нехай N N впорядковане лексикографічно. Поставте символи ( , ( ou I (не порівняльні) між вказаними нижче парами:
a) (5, 78) і (7, 1); b) (4, 6) і (4, 2); c) (5, 5) і (4, 23); d) (1, 3) і (1, 2).
Nota. Лексикографічний порядок вживають для впорядкування множин, елементами яких є пари, трійки або, взагалі, набори n елементів. Ідея цього методу полягає в порівнянні спочатку перших елементів набору, потім других і т. д., аж до кінця. Такий порядок вживають в словниках, звідси і його назва. Наприклад,
Дерево ( Залізо,
Дача ( Дерево.
В першому випадку порівняння робиться по першій літері, в другому випадку – по другій літері.
4. Нехай A = (N, <) натуральні числа упорядковані в зростаючому порядку і B = (N, >) – ті ж самі числа, але впорядковані в зворотному порядку. Поставте символи ( , ( або I (не порівняльні) між парами:
(3, 8) і (1, 1); b) (2, 1) і (2, 8); c) (3, 3) і (3, 1); d) (4, 9) і (7, 15).
5. Нехай B = {1, 2, 3, 4, 5} впорядковане таким чином:
1
2 3
4 5
Знайти всі мінімальні і максимальні елементи;
Знайти перший і останній елемент;
Нехай T(B) множина всіх тотально впорядкованих підмножин B, що містять два або більше елементи. Нехай множина T(B) частково впорядковано відношенням включення. Побудувати діаграму T(B).
Нехай A = {2, 3, 4, 5, … } впорядковане x ( y відношенням “ у ділиться на х ”. Знайти максимальні і мінімальні елементи А.
Відповіді
a) Що відношення подільності є частковий порядок, було показано в одному з прикладів цієї лекції. Відшукайте.
b) (2 ( 8), (18 I 24), (9 ( 3), (5 ( 15).
c) {24, 2, 6}, {15, 5, 30}, {2, 8, 32, 4}, {5} тотально впорядковані;
{3, 15, 5}, {1, 2, 3,…} частково впорядковані.
2. a) (a ( e); (b I c); (d ( a); (c I d);
b)
a
b c
d e
3. a) (5, 78) ( (7, 1); b) (4, 6) ( (4, 2); c) (5, 5) ( (4, 23); d) (1, 3) ( (1, 2).
4. a) (3, 8) ( (1, 1); b) (2, 1) ( (2, 8); c) (3, 3) ( (3, 1); d) (4, 9) ( (7, 15).
5. a) Мінімальні елементи 3, 4, 5; максимальні 1;
b) Останній елемент 1, першого елемента немає;
c) T(B) = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (1, 2, 4), (1, 2, 5)}
(1, 2, 4) (1, 2, 5)
(1, 2) (1, 4) (1, 5) (2, 4) (2, 5)
Всі прості числа максимальні, тому що за ними не слідує жодне число – вони ні на що не діляться. Не існує мінімальних елементів – кожному числу передує його кратне.
Текст 3.
Дискретна Математика
Лекція 9. Функції
Аплікація
Множина потенція
Ін’єкція
Сур’єкція
Бієкції.
Композиція функцій
Обернена функція
Графік функції
Спеціальні функції
Перестановки