Задачі та вправи. І. Які з відношень завдань XXVIІ-XXІX до попереднього розділу є відношен-нями: 1) часткового порядку

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

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