Задачі та вправи

І. Які з відношень завдань І-ІІІ до розділу «Види бінарних відношень» є відношеннями: 1) часткового порядку, 2) строгого порядку, 3) передпо-рядку, 4) лінійного порядку, 5) повного порядку.

ІІ. Побудувати частково упорядковану множину, яка має:

1) найменший елемент, максимальний елемент й не має найбільшого елементу;

2) мінімальний елемент й не має найменшого елемента;

3) два мінімальних та два максимальних елемента.

ІІІ. Побудувати відношення часткового порядку на множині:

1) мешканців одного міста;

2) трикутників на площині;

3) поліномів порядку n від однієї змінної;

4) спектаклів з репертуару одного театру;

5) назв населених пунктів України;

6) літаків, приписаних до одного аеропорту;

7) Z².

IV. Побудувати:

1) на множині літер українського алфавіту частковий порядок, який не є лінійним;

2) відношення строгого порядку на множині студентів однієї групи;

3) передпорядок на множині студентів одного університету,

4) передпорядок на множині N².

V. Побудувати відношення лінійного порядку на множині:

1) {+,-,,,!},

2) P({а,b,cd}),

3) N²,

4) NN²,

5) комплексних чисел,

6) A², де A={u,v,w,z,x},

7) слів орфографічного словника,

8) учнів школи,

9) країн світу.

VІ. Побудувати такий лінійний порядок R на множині натуральних чи-сел, що існує найбільший елемент відносно R.

VІІ. Побудувати повний порядок на множині:

1) вулиць Києва,

2) цілих від’ємних чисел,

3) цілих чисел Z.

VІІІ. Довести, що i_A є частковий порядок на множині А.

ІХ. Нехай _B, _A – часткові порядки на множинах B та A відповідно. Довести, що <a₁,b₁>  <a₂,b₂>  a₁ _A a₂ й b₁ _B b₂ – частковий порядок на AB.

Х. Показати, що якщо відношення R на множині А іррефлексивне та транзитивне, то відношення R₁ на А, таке що xR₁y  xRy або x=y, є частковим порядком на А.

ХІ. Нехай A – непорожня частково упорядкована множина, що має n елементів. Довести, що А містить мінімальний елемент.

ХІІ. Нехай задано відображення f: AAA таке, що для будь-яких елементів 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  xy й xy. Довести, що 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 (теорема про трансфінітну індукцію). Нехай <А,>– повністю упорядкована множина, а₀ – найменший елемент А, Р – деяка властивість (унарний предикат) на А. Нехай Р(а₀)=1 та для довільного елементу а множини А з того, що Р(х)=1 для усіх х<а, випливає Р(а)=1. Тоді Р(х)=1 для усіх х з А.

Доведення. Припустимо, що твердження теореми не правильне. Тоді існує така непорожня підмножина В множини А (ВА), що Р(у)=0 для кожного у з В. Позначимо через b₀ найменший елемент множини В. За нашим припущенням Р(b₀)=0, тому а₀b₀ й а₀<b₀. За побудовою множини В Р(х)=1 для усіх тих елементів х множини А, для яких х<b₀. Тоді за умовою теореми має бути Р(b₀)=1, отже, маємо суперечність. Таким чином, теорему доведено.

Опишемо метод трансфінітної індукції. Нехай є повністю упоряд-кована множина <А,> й задана властивість Р на А.

Базис індукції. Перевірити, чи виконується Р(а₀)=1 для найменшо-го елементу а₀ множини А. Якщо Р(а₀)=1, перейти до наступного кроку, інакше завершити роботу (властивість Р не має місця для усіх елементів множини А).

Індукційний крок. Нехай а (аа₀) – деякий елемент множини А. Перевірити, чи випливає Р(а)=1 з того, що Р(х)=1 для усіх тих елементів х, що ха (хА).

Якщо виконуються умови базису та індукційного кроку, то, спираючись на теорему про трансфінітну індукцію, можна зробити висновок, що Р(х)=1 для будь-якого елементу х множини А.

Метод математичної індукції, що використовується для доведення тверджень, котрі стосуються елементів множини N (або її підмножини), повністю упорядкованої відношенням  (менше або дорівнює), є спеці-альним випадком методу трансфінітної індукції. Суть методу така. Нехай є повністю упорядкована множина <А,> (АN,  – природний порядок на N) й задана властивість Р на А.

Базис індукції. Переконатися, що для найменшого елементу n₀ множини А виконується Р(n₀)=1.

Індукційний крок. Нехай k (kn₀) – деякий елемент множини А. Перевірити, чи випливає Р(k+1)=1 з того, що Р(k)=1.

Наведемо приклад застосування методу математичної індукції. Покажемо, що для будь-якого цілого додатного числа n виконується: 1+…+n=n(n+1)/2. У даному випадку розглядається властивість, подана у вигляді рівності, на повністю упорядкованій множині <N⁺,>. Наймен-шим елементом цієї множини є число 1. Отже, маємо.

Базис індукції. Перевіряємо, чи виконується задана рівність для n=1, тобто чи правильна рівність 1=(1(1+1))/2. Легко перевірити, що рівність виконується.

Індукційний крок. Припустимо, що задана рівність виконується для деякого цілого додатного числа k, k1, тобто 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⁺» доведено.