Степінь відношення. Поняття про замикання відношень.

Означення: Степенем , n = 1,2,…, відношення R називається його n-кратна композиція, тобто .

За означенням примається, що

Теорема: Розглянемо на множині А транзитивне відношення R. Тоді

Означення: Замиканням відношення R на проміжку А за властивістю Р називається найменша за включенням відношення , що володіє властивістю P, і містить відношення R.

Очевидно, що .

Зауваження. Якщо відношення R володіє властивістю P, то замикання його за властивістю P дорівнює самому R.

Введемо позначення - об`єднання всіх додатніх, - об`єднання всіх невідємних степенів деякого відношення R на множині А.

Мають місце такі теореми:

Теорема: Відношення є замиканням відношення R за властивістю транзитивності.

Теорема: Відношення є рефлексивним і транзитивним замиканням відношення R.

Функціональні відношення. Відображення та функції.

Означення: розглянемо бінарне відношення R між множинами А та В. R – функціональне, якщо

Для функціональних відношень або . Для другого випадку можна записати і в цьому випадку говорять, що елементи а та b є функціонально залежні.

Означення: Функціональне відношення називають відображенням множини А в множину В, якщо =А (позначається , або ).

У цьому випадку множина є областю визначення відображення R, a, - множиною (областю) значень цього відображення.

Означення: Якщо R є відображенням і , то елемент b називається образом елемента а при відображенні R, а елемент а – прообразом елемента b.

Означення: Розглянемо відношення і . Образом множини А₁ при відображенні R називається множина , а сама множина А₁ називається прообразом множини R(A₁).

Безпосередньо з означення випливають такі рівності:

1. ;

2. ;

3. ;

Означення: Функцією називається таке відображення, область визначення та множина значень якого є числовими множинами.

Класифікація відображень

Означення: Відображення називається:

1. Сюр’єктивним, якщо (на множину В);

2. Ін’єктивним (взаємно однозначним), якщо ;

3. Бієктивним, якщо воно є одночасно сюр’єктивним та ін’єктивним;

Теорема: Якщо є бієктивним відображенням, то також є бієктивним відображенням.

Теорема: Композиція двох довільних відображень є відображенням.

Теорема: Композиція бієктивних відображень є бієктивним відображенням.

Комп’ютерне зображення відношень та функцій

Розглянемо довільне відношення . Пронумеруємо елементи множини А: . Тоді відношення R можна зобразити за допомогою мулевої матриці (двовимірного масиву) , де

Загальним зображенням функції є також масив, що є ефективним за швидкістю, оскільки реалізація масивів забезпечує отримання значення функції за постійний час, що мало залежить від розмірності масиву та значення індекса.

Для великих скінченних або нескінченних множин зображення функції масивом є неефективним способом або взагалі неможливим. У цьому випадку використовуються підпрограми-функції, які визначають для заданого значення аргументу єдине значення функції.

2.6 Потужність множин

Означення. Дві множини А та В наживаються рівнопотужними (рівночисельними), якщо між ними можна встановити взаємно однозначну відповідність (бієктивне відображення) (позначають ).

Відношення рівнопотужності є відношенням еквівалентності. Тому рівнопотужні множини називають еквівалентними (записують ).

Приклади.

1)

2)

3)

Означення. Непорожня множина Х є скінченною, якщо вона еквівалентна деякій множині . У протилежному випадку вона є нескінченною.

У цьому випадку . Зрозуміло, що |Ø| = 0.

Означення. Множина А називається зчисленною, якщо , тобто .