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

І. Які з відношень завдань XXVIІ-XXІX до попереднього розділу є відношен-нями: 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 елементів. Довести, що А містить мінімальний та максимальний елементи.

ХІІ. 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 – відношення еквівалентності на А.

ХІІІ. Довести, що будь-яка підмножина частково упорядкованої множини частково упорядкована.