3. Відношення

Приклади розв’язання типових задач

Задача 1. Нехай . Вказати властивості відношення, заданого на множині.

Розв’язання. Відношення не є рефлексивним, оскільки діагональна пара не належить . Дане відношення містить діагональні пари і , тому воно не є іррефлексивним. Безпосередньою перевіркою встановлюємо, що з кожною парою виду відношення містить пару виду (у нашому випадку до пари у відношенні є обернена пара і навпаки; пари і збігаються зі своїми оберненими). Отже, відношення є симетричним. Воно не антисиметричне, оскільки , але. Відношенняне є транзитивним, оскільки містить париі, але не містить пари.

Задача 2. Класифікувати відношення та– особи одного року народження} на множині людей.

Розв’язання. Відношення рефлексивне (адже твердження “ та – особи одного року народження” істинне для будь-якого з множини людей, отже, містить усі діагональні пари),симетричне (якщо , то це означає, що та – особи одного року народження, але тодіта також є особами одного року народження, звідки ), транзитивне (якщо та , тобто та – особи одного року народження йта– особи одного року народження, то йта– особи одного року народження, отже, ). Таким чином, дане відношення є відношенням еквівалентності.

Задача 3. Нехай , та– бінарні відношення на множині. Довести, що:a) ; b) .

Розв’язання.

1. Використовуючи означення доповнення відношення та означення відношення, оберненого до даного, маємо: . Отже, . Покажемо, що. Маємо: . Це і означає, що.

2. Використовуючи означення відношення, оберненого до даного, та означення добутку відношень, маємо: існує такий елементз множини, що та . Отже, . Покажемо, що. Маємо: існує такий елементз множини, що та , Отже, доведено, що .

Задача 4. Нехай та– часткові порядки на. Довести, що– частковий порядок на.

Розв’язання. Покажемо, що відношення є рефлексивним, антисиметричним та транзитивним. Оскількита– часткові порядки на, то відношеннятає рефлексивними, тобто і відношеннярефлексивне. Нехайта. Тоді і , звідки з антисиметричності випливає, що. Отже, відношення– антисиметричне. Доведемо транзитивність. Нехайта. Тоді . З транзитивності відношень тавипливає, що та , тобто . Таким чином,є частковим порядком на.

Задача 5. З’ясувати, чи будуть відношення , та, задані на множинах та , відображеннями (або частковими відображеннями).

Розв’язання. Відношення є відображенням множиниу, тому щофункціональне та його область визначення , оскільки ,Ø,,,Ø. Відношенняне є відображенням, оскільки воно не є функціональним (елемент 3 з множинизустрічається двічі, тобто більше одного разу, на першому місці у парах, які належать). Відношенняє частковим відображенняму, тому щофункціональне та його область визначення .

Задача 6. З’ясувати, чи будуть сюр’єктивними відображення ,, та ,, де та .

Розв’язання. Для кожного елемента з множиниобчислимо повний прообраз:, , . Таким чином, Ø для кожного , отже, є сюр’єктивним відображенням (відображеннямна). В той же час для відображеннямаємоØ, тому не є сюр’єктивним.

Задача 7. З’ясувати, чи будуть ін’єктивними відображення ,, та ,, де та .

Розв’язання. Відображення єін’єктивним, оскільки різні елементи з області визначення мають різні образи. В той же час у відображенні різні елементитамають однаковий образ 2, томуне єін’єктивним.

Задача 8. З’ясувати, чи будуть бієктивними (взаємно однозначними) відображення ,, та ,, де , та .

Розв’язання. Відображення є сюр’єктивним, оскільки кожен елемент множини має прообраз; крім того, різні елементи множинимають різні образи, отже, є ін’єктивним. Таким чином, є бієкцією.Відображення не є ін’єктивним, хоча є сюр’єктивним. Отже, не є бієктивним.

A3

1. Навести приклади унарних відношень на множині натуральних чисел та на множині людей.

2. Навести приклад тернарного відношення на множині відрізків.

3. Скільки унарних та тернарних відношень можна побудувати на множині , якщо вона міститьелементів?

4. На множині побудувати відношення тотожності:.

5. На множині побудувати відношення:“мати спільний дільник, що не дорівнює 1”. Задати це відношення графіком, матрицею та стрілковою діаграмою.

6. Нехай та– відношення на множині, , . Знайти , , .

7. Нехай – множина людей,,є дитиною. Яким буде відношення ?

8. Відношення задане на множині дійсних чисел. Побудувати.

9. Визначити властивості відношень ,, якщо:

a) ;

b) .

10. Визначити властивості відношень, побудованих чи наведених у задачах № 4, 5, 6, 7.

11. Вказати властивості відношення, заданого на множині людей : та мають спільного предка.

12. На множині побудувати відношення, яке є

    1. рефлексивним, не симетричним, транзитивним;

    2. іррефлексивним, не антисиметричним, транзитивним.

13. Класифікувати відношення:

1. 

2. .

Для відношень еквівалентності побудувати класи еквівалентності.

14. З’ясувати, чи є наведені відношення відношеннями еквівалентності:

1. “вчитись в одній групі” на множині студентів КПІ;

2. “мати таку ж парність, як …” на множині ;

3. “мати стільки ж знаків, скільки …” на множині ;

4. на множині прямих;

5. на множині прямих.

Для відношень еквівалентності побудувати класи еквівалентності.

15. Відношення еквівалентності на множині задано розбиттям на класи Представити це відношення множиною впорядкованих пар, матрицею та графом.

16. На множині різнокольорових кульок різного діаметра побудувати відношення еквівалентності.

17. Нехай – скінченна множина. Які відношення еквівалентності породжують найбільшу та найменшу кількість класів еквівалентності?

18. Класифікувати відношення, , задане на множині . Побудувати матрицю цього відношення та діаграму Хаасе. Вказати мінімальний, максимальний, найбільший та найменший елементи.

19. На булеані множини задане відношення. Побудувати діаграму Хаасе, вказати елементи, які не можна порівняти за цим відношенням. Вказати мінімальний, максимальний, найбільший та найменший елементи.

20. Скільки різних відношень часткового порядку можна побудувати на трьохелементній множині. Побудувати діаграми Хаасе.

21. Чи може один і той же елемент частково впорядкованої множини бути одночасно мінімальним і максимальним?

22. Якщо впорядкована множина має найменший елемент, то він єдиний. Довести.

23. Класифікувати відношення , задане на множині. Побудувати матрицю цього відношення та діаграму Хаасе.

24. З’ясувати тип порядку (частковий, строгий, лінійний):

1. на множині співробітників банку задане відношення “підлеглий – начальник”;

2. на множині офіцерських звань задане відношення “бути молодшим за званням”;

3. на множині деталей задане відношення “бути важчим”.

25. Розташувати у лексикографічному порядку елементи множини:

a) деb) де

26. Бінарне відношення є одночасно симетричним і антисиметричним. Довести, що– транзитивне.

27. Довести, що об’єднання двох рефлексивних відношень є рефлексивним.

28. Нехай – бінарні відношення, задані на множині. Довести:

1. 

2. 

3. –транзитивне .

29. Нехай Побудувати приклади відношенькожне з яких є:

1. повністю визначене на і не функціональне;

2. не повністю визначене на і не функціональне;

3. не повністю визначене на і функціональне;

4. повністю визначене на і функціональне.

30. Нехай – відношення між елементами множин таВ яких випадкахможна розглядати як відображення, якщо:

1. –множина студентів, – множина навчальних дисциплін; вивчає;

2. –множина спортсменів, – множина дійсних чисел; має зріст;

3. –множина деталей, – їх маса; має масу?

31. З’ясувати властивості відображення , якщо

1. с)

2. d)

32. Вибрати множини та побудувати на них відображення, яке є:

a) довільним; b) сюр’єктивним, але не ін’єктивним; c) ін’єктивним, але не сюр’єктивним; d) бієктивним; e) тотожним.

33. Чи є рівнопотужними множини:

1. та ; с)та;

2. та ;d) та?

34. Множини і– скінченні. Якщо ці множини еквівалентні, то вони містять однакову кількість елементів. Довести.

35. Чи будуть множини і еквівалентними, якщо

1. ; b) ?

36. Чи будуть еквівалентними множини точок на будь-яких двох відрізках і?

37. Нескінченна підмножина зліченної множини зліченна. Довести.

B3

1. На множині студентів навести приклади повного та порожнього бінарного відношення.

2. На множині побудувати відношення: . Задати його різними способами.

3. Задати відношення координатним способом:

   1. ; b) та).

4. Нехай на множинах тазадано відношення і . Побудувати.

5. Нехай на множині людей задані такі відношенняє батькомтає донькою. Описати такі відношення:.

6. Відношення задане на множині, вказати його властивості, якщо:

   1. ;

   2. ;

   3. ;

   4. ;

e) .

7. З’ясувати, які властивості мають відношення, задані на множині натуральних чисел:

a) тавзаємно прості;

b) є дільником;

c) ;

d) .

1. Навести приклад відношень, кожне з яких є

1. рефлексивним, симетричним, не транзитивним;

2. не рефлексивним, не симетричним, транзитивним;

3. рефлексивним, антисиметричним, не транзитивним.

1. Довести, що відношення , задане на множині, є відношенням еквівалентності.

2. Чи буде відношенням еквівалентності відношення подібності на множині трикутників?

3. Нехай – множина прямих. З’ясувати, чи будуть наступні відношення відношеннями еквівалентності:

   1. пряма перетинається з прямою;

   2. пряма лежить в одній площині з прямою;

   3. пряма перетинає ті ж самі площини, що і пряма.

4. Нехай на множині задано відношення. З’ясувати, чи буде відношенням еквівалентності, якщо:

1. 

2. 

3. 

4. 

Для кожного відношення еквівалентності побудувати класи еквівалентності..

13. Знайти класи еквівалентності для відношень, заданих на :

a) b) c) .

1. Класифікувати відношення, задані на множині :

1. , ;

2. ділить .

Побудувати матриці відношень та діаграми Хаасе. Вказати мінімальний, максимальний, найбільший та найменший елементи.

15. Нехай . Скільки відношень часткового порядку можна побудувати на цій множині? Вказати їх.

16. З’ясувати, чи будуть наведені відношення відношеннями порядку:

    1. 

    2. 

    3. ділиться на з остачею.

Вказати тип впорядкованості у випадках, коли це можливо. Побудувати діаграми Хаасе.

17. Опишіть симетричні відношення, які є відношеннями часткового порядку.

18. Довести, що перетин двох симетричних відношень є симетричним.

19. Нехай та – іррефлексивні відношення. Чи завжди буде добуток таких відношень іррефлексивним? Навести приклади.

20. Нехай ,та – бінарні відношення, задані на множині . Довести:

    1. ;

    2. ;

    3. 

21. Чи кожна підмножина множиниє графіком певного відображення?

22. На множинах ізадано відношення:

;

;

;

;

.

Які з них: a) всюди визначені; b) функціональні; c) ін’єктивні; d) сюр’єктивні; e) бієктивні (взаємно однозначні)?

23. Чи є відношення

    1. ;

    2. ;

    3. ;

    4. ;

    5. ;

    6. ;

    7. .

відображеннями? Вказати їх властивості.

24. Що можна сказати про множини та, коли відомо, що кожне відображенняє: а) сюр’єкцією; b) ін’єкцією; c) бієкцією?

25. Навести приклад множини , що еквівалентна множині. Скільки взаємно однозначних відображень існує міжта?

26. Чи є зліченною множина ?

27. Чи будуть множини і еквівалентними, якщо:

a) ; b) ?

28. Довести, що декартів добуток двох зліченних множин є множина зліченна.

29. Чи є зліченною множина ?

С3

1. Множина складається зелементів. Скільки різних бінарних відношень можна побудувати на цій множині? Скільки буде серед них:

a) рефлексивних відношень; b) симетричних відношень?

2. Визначити, чи будуть вказані відношення відношеннями еквівалентності:

1. , ;

2. , ;

3. , ;

4. .

Для відношень еквівалентності задати класи еквівалентності.

3. Чи можна стверджувати, що об’єднання двох відношень еквівалентності теж буде еквівалентністю? Відповідь обґрунтувати.

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

5. Якщо – відношення часткового порядку, тотеж відношення часткового порядку. Довести.

6. Нехай ділиться на. Вказати мінімальний, максимальний, найменший, найбільший елементи, якщо:

a) ; b) ; c) .

7. Нехай – сукупність непорожніх власних підмножин множини , впорядкована відношенням включення. Вказати мінімальний, максимальний, найменший, найбільший елементи.

8. Нехай на множині задано відношення . Знайти лінійний порядок , для якого. Скільки існує таких лінійних порядків?

9. Нехай і – бінарні відношення, задані на множині . Довести:

а) ;b) .

10. Довести, що – симетричне відношення тоді і тільки тоді, коли.

11. Довести, що – антисиметричне відношення тоді і тільки тоді, коли.

12. Якщо – відношення еквівалентності, тота. Довести.

13. Нехай та– відношення еквівалентності. Довести, що– відношення еквівалентності тоді і тільки тоді, коли.

14. Нехай . Скільки можна побудувати різних відображень?

15. Нехай . Скільки можна побудувати різних бієкцій?

16. На множинах тазадано відношення. За яких умов відношенняє:a) всюди визначеним; b) функціональним; c) ін’єктивним; d) сюр’єктивним; e) бієктивним?