- •Поняття множини. Способи подання множин
- •Задачі та вправи
- •Включення та рівність множин
- •Задачі та вправи
- •Операції над множинами
- •Задачі та вправи
- •Властивості операцій над множинами
- •Тепер доведемо, що
- •Задачі та вправи
- •Булеан множини
- •Задачі та вправи
- •Покриття та розбиття множини
- •Задачі та вправи
- •Декартів добуток множин
- •Задачі та вправи
- •Відношення
- •Задачі та вправи
- •Операції над відношеннями
- •Задачі та вправи
- •Відображення
- •Задачі та вправи
- •Види відображень
- •Задачі та вправи
- •Види бінарних відношень
- •Задачі та вправи
- •Відношення еквівалентності
- •Задачі та вправи
- •Фактор-множина
- •Задачі та вправи
- •Замикання відношень
- •Задачі та вправи
- •Відношення порядку
- •Задачі та вправи
- •Трансфінітна індукція
- •Задачі та вправи
- •Потужність множини
- •Задачі та вправи
- •Список використаної та рекомендованої літератури
- •Символи та позначення
- •Предметний покажчик
- •Слова іншомовного походження
Задачі та вправи
І. Які з відношень завдань І-ІІІ до розділу «Види бінарних відношень» є відношеннями: 1) часткового порядку, 2) строгого порядку, 3) передпо-рядку, 4) лінійного порядку, 5) повного порядку.
ІІ. Побудувати частково упорядковану множину, яка має:
1) найменший елемент, максимальний елемент й не має найбільшого елементу;
2) мінімальний елемент й не має найменшого елемента;
3) два мінімальних та два максимальних елемента.
ІІІ. Побудувати відношення часткового порядку на множині:
1) мешканців одного міста;
2) трикутників на площині;
3) поліномів порядку n від однієї змінної;
4) спектаклів з репертуару одного театру;
5) назв населених пунктів України;
6) літаків, приписаних до одного аеропорту;
7) Z2.
IV. Побудувати:
1) на множині літер українського алфавіту частковий порядок, який не є лінійним;
2) відношення строгого порядку на множині студентів однієї групи;
3) передпорядок на множині студентів одного університету,
4) передпорядок на множині N2.
V. Побудувати відношення лінійного порядку на множині:
1) {+,-,,,!},
2) P({а,b,cd}),
3) N2,
4) NN2,
5) комплексних чисел,
6) A2, де A={u,v,w,z,x},
7) слів орфографічного словника,
8) учнів школи,
9) країн світу.
VІ. Побудувати такий лінійний порядок R на множині натуральних чи-сел, що існує найбільший елемент відносно R.
VІІ. Побудувати повний порядок на множині:
1) вулиць Києва,
2) цілих від’ємних чисел,
3) цілих чисел Z.
VІІІ. Довести, що iA є частковий порядок на множині А.
ІХ. Нехай B, A – часткові порядки на множинах B та A відповідно. Довести, що <a1,b1> <a2,b2> a1 A a2 й b1 B b2 – частковий порядок на AB.
Х. Показати, що якщо відношення R на множині А іррефлексивне та транзитивне, то відношення R1 на А, таке що xR1y xRy або x=y, є частковим порядком на А.
ХІ. Нехай A – непорожня частково упорядкована множина, що має n елементів. Довести, що А містить мінімальний елемент.
ХІІ. Нехай задано відображення f: AAA таке, що для будь-яких елементів x,y,z множини A f(x,y)=f(y,x), f(x,f(y,z))=f(f(x,y),z), f(x,x)=x. Визначимо xRy f(x,y)=x. Довести, що R – частковий порядок на А.
ХІІІ. 1) Нехай – частковий порядок на множині А. Визначимо на А відношення R: xRy xy й xy. Довести, що R – строгий порядок на А.
2) Нехай < – строгий порядок на множині А. Визначимо на А відношен-ня R: xRy x<y або x=y. Довести, що R – частковий порядок на А.
3) Нехай Q – передпорядок на множині А. Визначимо на А відношення R: xRy хQу та <y,x>Q. Довести, що R – строгий порядок на А.
4) Нехай Q – передпорядок на множині А. Визначимо на А відношення R: xRy хQу й yQx. Довести, що R – відношення еквівалентності на А.
ХІV. Довести, що будь-яка підмножина частково упорядкованої множини частково упорядкована.
Трансфінітна індукція
Твердження, що стосуються елементів деякої повністю упорядко-ваної множини, можна доводити, використовуючи метод трансфінітної індукції, який є узагальненням методу математичної індукції й грунту-ється на теоремі про трансфінітну індукцію. Далі позначаємо відношен-ня повного порядку через , а вираз a<b означатиме, що аb, але аb.
Теорема 15 (теорема про трансфінітну індукцію). Нехай <А,>– повністю упорядкована множина, а0 – найменший елемент А, Р – деяка властивість (унарний предикат) на А. Нехай Р(а0)=1 та для довільного елементу а множини А з того, що Р(х)=1 для усіх х<а, випливає Р(а)=1. Тоді Р(х)=1 для усіх х з А.
Доведення. Припустимо, що твердження теореми не правильне. Тоді існує така непорожня підмножина В множини А (ВА), що Р(у)=0 для кожного у з В. Позначимо через b0 найменший елемент множини В. За нашим припущенням Р(b0)=0, тому а0b0 й а0<b0. За побудовою множини В Р(х)=1 для усіх тих елементів х множини А, для яких х<b0. Тоді за умовою теореми має бути Р(b0)=1, отже, маємо суперечність. Таким чином, теорему доведено.
Опишемо метод трансфінітної індукції. Нехай є повністю упоряд-кована множина <А,> й задана властивість Р на А.
Базис індукції. Перевірити, чи виконується Р(а0)=1 для найменшо-го елементу а0 множини А. Якщо Р(а0)=1, перейти до наступного кроку, інакше завершити роботу (властивість Р не має місця для усіх елементів множини А).
Індукційний крок. Нехай а (аа0) – деякий елемент множини А. Перевірити, чи випливає Р(а)=1 з того, що Р(х)=1 для усіх тих елементів х, що ха (хА).
Якщо виконуються умови базису та індукційного кроку, то, спираючись на теорему про трансфінітну індукцію, можна зробити висновок, що Р(х)=1 для будь-якого елементу х множини А.
Метод математичної індукції, що використовується для доведення тверджень, котрі стосуються елементів множини N (або її підмножини), повністю упорядкованої відношенням (менше або дорівнює), є спеці-альним випадком методу трансфінітної індукції. Суть методу така. Нехай є повністю упорядкована множина <А,> (АN, – природний порядок на N) й задана властивість Р на А.
Базис індукції. Переконатися, що для найменшого елементу n0 множини А виконується Р(n0)=1.
Індукційний крок. Нехай k (kn0) – деякий елемент множини А. Перевірити, чи випливає Р(k+1)=1 з того, що Р(k)=1.
Наведемо приклад застосування методу математичної індукції. Покажемо, що для будь-якого цілого додатного числа n виконується: 1+…+n=n(n+1)/2. У даному випадку розглядається властивість, подана у вигляді рівності, на повністю упорядкованій множині <N+,>. Наймен-шим елементом цієї множини є число 1. Отже, маємо.
Базис індукції. Перевіряємо, чи виконується задана рівність для n=1, тобто чи правильна рівність 1=(1(1+1))/2. Легко перевірити, що рівність виконується.
Індукційний крок. Припустимо, що задана рівність виконується для деякого цілого додатного числа k, k1, тобто 1+…+k=k(k+1)/2. Покажемо, що тоді задана рівність виконується й для числа k+1, тобто 1+…+k+(k+1)=((k+1)((k+1)+1))/2. Маємо:
1+…+k+(k+1)=(1+…+k)+(k+1)=(k(k+1))/2+(k+1)=(k+1)((k+2)/2)= =((k+1)((k+1)+1))/2.
Отже, твердження «1+…+n=n(n+1)/2 для будь-якого n з N+» доведено.