Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Елементи теорії множин I
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2003
Тип роботи:
Методичні вказівки
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти і Науки України
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
Елементи теорії множин I
Методичні вказівки до практичних занять та самостійної роботи з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія”
Затверджено на засіданні кафедри Електронних Обчислювальних Машин Протокол № 6 від 21 січня 2003 року
Львів – 2003
Елементи теорії множин I : Методичні вказівки до практичних занять та самостійної роботи з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” / Укладачі: І. Мороз, Р. Попович – Львів: Національний університет “Львівська політехніка”, 2003, 18 с.
Укладачі: І. Мороз, ст.викл.
Р. Попович, к.т.н., доцент
Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри ЕОМ
Рецензенти: Ємець В. Ф., професор кафедри ЕОМ, д. фіз.-мат. н.
Юрчак І. Ю., доцент кафедри САПР, к. т. н.
Елементи теорії множин I
Вступ
Дискретна математика є розділом математики, що зародилася в давні часи. Її головною відмінністю є дискретність, тобто антипод неперервності. Дискретна математика включає традиційні розділи математики, які вже сформувалися (математичну логіку, алгебру, теорію чисел), і нові, що інтенсивно розвиваються.
У більш як двотисячорічній історії дискретної математики сучасний період є одним із найінтенсивніших періодів її розвитку: дуже швидко розширюється сфера застосування, інтенсивно зростають обсяги нової інформації та кількість нових результатів. Якщо ще порівняно недавно ця наука була сферою інтересів лише вузького кола фахівців, то тепер вона перетворюється на наукову дисципліну, дуже важливу й потрібну для багатьох, а у сфері сучасної освіти – для всіх.
Масове використання обчислювальної техніки та інформаційних технологій значно розширює сферу прикладних досліджень, у яких все більше застосовується апарат дискретної математики.
Базовим розділом як дискретної математики, так і взагалі всієї математики, є теорія множин.
Відповісти на питання “Що таке множина ?” не так просто, як це здається на перший погляд. У повсякденному житті та практичній діяльності часто доводиться говорити про деякі сукупності різних об’єктів: предметів, понять, чисел, символів тощо. Наприклад, сукупність деталей механізму, сукупність сторінок у книзі, сукупність книг у бібліотеці, стадо овець, група студентів.
На підставі інтуїтивних уявлень про такого роду чітко визначені сукупності об’єктів сформувалося математичне поняття множини як об’єднання об’єктів у єдине ціле. Саме такої точки зору дотримувався засновник теорії множин німецький математик Г. Кантор.
Множина належить до категорії найзагальніших, основоположних понять математики. Так, група математиків, які працювали під псевдонімом Н.Бурбакі, стверджувала: “Множина утворюється з елементів, що мають певні властивості, знаходяться у певних відношеннях між собою чи з елементами інших множин” або ж “Логічно кажучи, майже всю сучасну математику можна вивести з єдиного джерела: теорії множин”.
Математичне поняття множини пов’язане з абстракцією, яку називають абстракцією множини. Суть її полягає в тому, що існуючі зв’язки предметів, які об’єднуються між собою та з іншими предметами, ігноруються, а замість них предметам, що об’єднуються, приписують нові зв’язки одного з одним, які виражають їх належність множині. При цьому вважається, що два предмети, які нічим не різняться, є одним і тим самим предметом.
Способи задання множин
Об’єкти, що утворюють множину, називаються її елементами, або членами. Прикладами множин можуть бути: множина сторінок книги (кожна сторінка є елементом цієї множини); множина всіх дійсних чисел, більших від 0 і менших від1; множина студентів певного учбового закладу тощо.
Множина є визначеною. Коли можна встановити, чи є будь-який об’єкт її членом чи ні.
Для позначення конкретних множин, як правило, використовують великі літери A, S, X,… або великі літери з індексами A1, A2 і т.д.
Для позначення елементів множин загалом застосовують малі літери a, s, x,…або малі літери з індексами a1, a2 і т.д.
Для позначення того, що х є елементом (тобто х належить), застосовують запис x(S, а запис x(S означає, що елемент x не належить множині S. Символ ( називається символом належності. Записом x1, x2,…,xn(S користуються як скороченням для запису x1(S, x2(S,…,xn(S.
Є кілька способів задання множин.
1. Словесний (вербальний) за допомогою опису характеристичних властивостей , які повинні мати елементи множини. Наприклад,
множина натуральних чисел N;
множина цифр десяткової системи числення;
множина цифр двійкової системи числення;
множина парних чисел.
2. Список (перелік) усіх елементів у фігурних дужках. Стосовно зазначених вище прикладів маємо:
N={1, 2, 3,…};
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
{0, 1};
{2, 4 ,6,…}.
3. Висловлювальний (предикатний, породжувальний) за допомогою предиката, тобто множина задається у вигляді {x | P(x)}, де P(x) набуває значення «істина» для елементів множини. Приклади предикатного задання:
{1, 2, 3,…}={x | x – натуральне число};
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}={x | x – цифра десяткової системи числення};
{0, 1}={x | x – цифра двійкової системи числення};
{2, 4 ,6,…}={x | x – парне число}={x | ( n(N, x=2n}.
4. Аналітичний.
Із наведених прикладів випливає, що множини бувають скінченними та нескінченними. Множину називають скінченною, якщо число її елементів скінченне, тобто існує натуральне число n, яке є числом елементів множини. Множину називають нескінченною, якщо вона містить нескінченне число елементів.
Введені вище поняття теорії множин з успіхом можуть бути використані в основах аналізу, алгебрі, математичній логіці та ін. Однак при більш строгому розгляді такі інтуїтивні уявлення можуть виявитися незадовільними. Недосконалість інтуїтивних уявлень про множини, їх недостатність ілюструється, наприклад, відомим парадоксом Б.Рассела, який формулюється так. Розглянемо множину А всіх таких множин Х, що Х не є елементом Х. Тоді, якщо А не є елементом А, то за означенням А також є елементом А. З іншого боку, якщо А є елементом А, то А – одна з тих множин Х, які не є елементами самих себе, тобто А не є елементом А. У будь-якому випадку А є елементом А й А не є елементом А.
Цей парадокс свідчить про те, що теорія множин, яка широко використовується в її інтуїтивному, “наївному” викладі, є суперечливою. Формалізація теорії множин, пов’язана, зокрема, з усуненням парадоксів, сприяла розвитку не тільки методів теорії множин, а й математичної логіки.
Операції над множинами
У теорії множин використовується поняття порожньої множини. Вона позначається символом (.
Множина може взагалі не містити елементів, наприклад
S={x | x – непарне число, що ділиться на 2}=(;
K={x | x(R, x2+1=0}=(.
Для позначення цього факту вводиться поняття порожньої множини.
Це поняття відграє дуже важливу роль при заданні множин за допомогою опису. Так, без поняття порожньої множини не можна говорити про множину відмінників студентської групи або про множину дійсних коренів квадратного рівняння, не пересвідчившись заздалегідь, чи є в студентській групі відмінники або чи має задане рівняння дійсні корені. Поняття порожньої множини дає змогу оперувати множиною відмінників групи, не турбуючись про те, чи є відмінники в групі, яка розглядається. Порожню множину умовно відносять до скінченних множин. Число елементів у ній рівне 0.
Таким чином, уведення порожньої множини дає можливість оперувати будь-якою множиною без попереднього застереження, існує вона чи ні.
Розглянемо дві множини А і В та введемо кілька операцій над ними. Для графічної ілюстрації використовують діаграми (кола) Ейлера. Для зображення множини на площині креслять замкнену лінію із заштрихованою внутрішньою областю (найчастіше – це коло, звідси й назва відповідного інструмента, що широко застосовується в теорії множин).
Об’єднання А і В – множина, що складається з усіх елементів множини А, всіх елементів множини В і не містить ніяких інших елементів (рис.1), тобто
А(В={x | x(А або x(В}.
Переріз А і В – множина, що складається з тих і тільки з тих елементів, які належать одночасно множині А та множині В (рис.2), тобто
А(В={x | x(А і x(В}.
Різниця А і В (відносне доповнення) – множина, що складається з тих і тільки тих елементів, які належать множині А й не належать множині В (рис.3), тобто
А\В={x | x(А і x(В}.
Симетрична різниця А і В (диз’юнктивна сума) – множина, що складається усіх елементів А, які не належать множині В, й усіх елементів В, які не належать множині А, та яка не містить ніяких інших елементів (рис.4), тобто
А(В={x | (x(А і x(В) або (x( В і x( А)}.
Очевидно, що А(В=(А\В) ((В\А).
Доповнення множини.
Звичайно, вже в означенні конкретної множини явно або неявно обмежується сукупність об’єктів, що є допустимими. (Слони – серед тварин, натуральні числа – серед цілих або дійсних залежно від контексту). Зручно сукупність допустимих об’єктів зафіксувати явно та вважати, що множини, які розглядаються, складаються з елементів цієї сукупності. Її називають основною множиною (універсумом) і позначають U. Універсум U арифметики – числа, універсум U зоології – тварини і т.д. Будь-яку множину розглядатимемо у зв’язку з універсамом, який на діаграмах Ейлера асоціюватимемо з прямокутником на площині, всередині якого зображатимемо множини (рис.5).
Доповнення множини А – це множина, що містить усі елементи універсуму, за винятком елементів А (рис.6), тобто .
Множина А називається підмножиною множини В, якщо кожен елемент А є елементом В. Для позначення цього факту вводиться знак ( - символ строгого включення (або ( - символ нестрогого включення) (рис.7). Якщо необхідно підкреслити, що множина В містить також інші елементи, крім елементів множини А, то використовують символ строгого включення А(В.
Дві множини рівні, якщо вони складаються з одних і тих самих елементів. Справджується таке: А=В тоді і тільки тоді, коли А(В і В(А.
Множину, елементами якої є всі підмножини множини А, називають множиною підмножин множини А і позначають Р(А). Так, для триелементної множини А={a,b,c} маємо P(A)={(,{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}}. У разі скінченної множини А з n елементів, множина підмножин Р(А) містить 2n елементів.
Алгебра множин
Операції над множинами, як і операції над числами, мають деякі властивості (табл.). Останні виражаються сукупністю тотожностей незалежно від конкретного вмісту множин, що входять у ці тотожності та є підмножинами деякого універсуму U.
Таблиця
Комутативний закон
1а) А(В=В(А
1б) А(В=В(А
Асоціативний закон
2а) А((В(С)=(А(В)(С
2б) А((В(С)=(А(В)(С
Дистрибутивний закон
3а) А((В(С)=(А(В)((А(С)
3б) А((В(С)=(А(В)((А(С)
Властивості ( та U
4а) А((=A
4б) А(U=A
5а)
5б)
6а) А(U=U
6б) А((=(
7а)
7б)
Закон самопоглинання (ідемпотентності)
8а) А(A=A
8б) А(A=A
Закон поглинання
9а) А((А(В)=А
9б) А((А(В)=А
Теорема де Моргана
10а)
10б)
Властивості доповнення, різниці та рівності
11) А(В=U і А(В=( (
12)
13)
14)
15) А(В=В(А
16) А((В(С)=(А(В)(С
17) А((=(( A=A
18) А(В ( А(В=А ( А(В=В (
19)
Основний метод доведення тотожностей в алгебрі множин ґрунтується на згаданому раніше такому факті: А=В тоді і тільки тоді, коли А(В і В(А. Доведемо, наприклад, тотожність 3а) А((В(С)=(А(В)((А(С).
Доведемо, що А((В(С)((А(В)((А(С). Для цього візьмемо будь-яке x(А((В(С), тоді за означенням операцій ( та ( маємо x(А або (x(В і x(С). За законом дистрибутивності “або” відносно “і” (x(А або x(В) і (x(А або x(С), тобто x(А(В і x(А(С або x((А(В)((А(С), що й треба було довести.
Доведемо тепер, що (А(В)((А(С)(А((В(С). Для цього візьмемо будь-яке x((А(В)((А(С). Звідси (x(А або x(В) і (x(А або x(С) або x(А або (x(В і x(С), тобто x(А((В(С), що й потрібно було довести.
Таким чином, А((В(С)=(А(В)((А(С).
Із властивості асоціативності операції об’єднання множин випливає, що об’єднання кількох множин можна виконати, послідовно об’єднуючи їх, причому порядок входження множин не впливає на результат: А((В(С)=(А(В)(С= А(В(С. Отже, об’єднання сукупності множин можна подати співвідношенням: .
Аналогічно на n множин узагальнюється операція перерізу: .
Використовуючи узагальнення операцій об’єднання та перерізу на n множин, можна узагальнити також інші співвідношення, наприклад закон де Моргана, який в узагальненому вигляді записується так: і .
Операція прямого добутку множин узагальнюється на будь-яку їх кількість і записується у вигляді , причому елементом прямого добутку n множин є впорядкована послідовність із n елементів (a1,a2,…,an), яка називається ще вектором або кортежем завдовжки n, а також n-кою. Якщо як співмножник декартового добутку n множин використовується одна множина А, то це записується так: .
Сукупність підмножин A1,A2,…,An множини A називається розбиттям множини A, якщо :
1. ;
2. Ai ( Aj=(, i(j.
Відображення
Визначення і приклади
Нехай задано дві множини Х і Y. Відображення f з областю визначення Х та областю значень Y кожному елементу х з множини Х ставить у відповідність деякий елемент f(х) з множини Y. У випадку Y=Х кажуть ще про перетворення f множини Х в себе. Символічно відображення записується наступним чином: f: Х(Y чи XY.
Варто розрізняти відображення f і елемент f(x) , що відповідає елементу х при цьому відображенні. Наприклад, неправильно (але зручно) казати "функція sin х ", правильно - "функція sin". Цю неточність звичайно виправляють, вказуючи, що задано функцію x→sin x, чи, що функція f визначена рівністю f(x)=sin x.
Приклади відображень:
1) f(x)= є відображенням множини відмінних від нуля елементів множини дійсних чисел R в R. Було б неточно казати, що область визначення відображення співпадає з множиною R, оскільки х не може приймати всі дійсні значення. Але цілком можна розглядати відображення з R в R типу: g(x)= для x≠0 і g(0)=2 або відображення з R в R1: h(x)= для x≠0 і h(0) =+∞, де множина R1 утворена об’єднанням R i деякого додаткового елемента +∞.
2) Якщо Х - множина дійсних функцій φ(х), визначених та інтегрованих на інтервалі [a,b], тo інтеграл є відображенням з Х в R.
3) Якщо X - множина кривих скінченної довжини на площині, то можна визначити відображення з Х в множину R+ додатніх дійсних чисел, яке кожній кривій ставить у відповідність її довжину.
Деякі часткові випадки
1. Відображення f множини Х в множину Х, визначене рівністю f (х)=х, називається тотожним.
2. Якщо Х є підмножиною Y , то відображення Х в Y , визначене рівністю f (х)=х, називається канонічною ін’єкцією Х в Y.
3. Ще раз повернемося до поняття "проекція на якусь множинy", введене, коли ми розглядали прямий добуток множин, тобто Х х Y . Тоді відображення Х х Y в X, що ставить у відповідність кожній парі (x,y)(Х х Y елемент х(Х, називається проекцією на X. Аналогічно визначається проекція на Y .
4. Нехай Х , Y , Z - три множини. Відображення f множини Х х Y в множину Z кожній парі (x,y)(Х х Y ставить у відповідність деякий елемент із Z , що позначається через f(z)=f(x,y))=f(x,y). Кажуть, що f є функцією двох змінних. Наприклад, якщо Х є множиною дійсних функцій дійсної змінної, інтегрованих на будь-якому скінченному інтервалі, то інтеграл визначає деяке відображення X x R x R в R, оскільки це відображення є функцією трьох змінних: φ ( Х, а ( R і b ( R.
5. Якщо розглядати відображення з X в Y x Z , то воно має вигляд х→(f(x), g(x)), де f (відповідно g) є відображенням X в Y (відповідно в Z ). Задання такого відображення еквівалентно заданню системи двох функцій.
6. У загальному випадку задання відображення деякого декартового добутку Х1 х Х2 х... х Хn у декартовий добуток Y1 х Y2 х ... х Ym рівносильне завданню системи m функцій від n змінних.
7. Відображення f множини X в множину Y називають постійним, якщо для всіх х(Х елемент f (х) рівний тому самому елементу з Y.
Ін’єкції, сюр’єкції, бієкції
Відображення f множини Х в множину Y називають ін’єктивним, чи ін'єкцією, якщо два різних елементи з Х мають образами при відображенні f два різних елементи з Y. Канонічна ін'єкція деякої підмножини в саму множину є ін’єктивним відображенням.
Відображення f називають сюр’єктивним, чи сюр’єкцією, якщо кожен елемент з Y є образом при відображенні f принаймні одного елемента з X.
Відображення f називається бієктивним, чи бієкцією, якщо кожен елемент із Y є образом при відображенні f деякого, і при цьому єдиного, елемента з X . Відображення бієктивне тоді і тільки тоді, коли воно одночасно ін’єктивнe й сюр’єктивнe. Бієкція множини на себе називається також перестановкою чи перетворенням.
Визначивши поняття ін'єкції, сюр’єкції та бієкції, введемо поняття образу і прообразу підмножини, а потім ще раз повернемося до властивостей ін'єкції, сюр’єкції та бієкції. Розглянемо два відображення:
f :X →Y i f`:x`→y`
1. Вони рівні, якщо X=X' , Y=Y` і f (х)= f `(х) дляєХ.
2. Відображення f``:X`→Y— називається звуженням або обмеженням на X' відображення f`:X→Y. якщо X`X і f``(x)= f `(x)= f (x) для хX'.
3. Множина f--1(у){x|y=f(x),xєX} називається повним прообразом елемента y при відображенні f.
Якщо Х ={x1, x2,…, xn} тo відображення f : Х → Y, може бути подане у вигляді двохрядкового запису f=, де f(хi) ( Y, i =1,2,…,n. Наприклад, f :Х→Y , Х={l,2,3,4,5}, Y={а,b,c}, f= .
Тоді повні прообрази - це f--1 (a)={1,2,5}, f--1 (b)={3}, f--1(c)={4}.Якщо X’ = {l,2,3,4,5}, то звуження X’ відображення f має вид f’=
4. Сукупність образів елементів множини X’Х при відображенні f :X→Y називається образом x' i позначається f(x’).
Наприклад: для відображення f= маємо f({1,3,4})={Y1,Y3}.
Тепер повернемося знову до властивостей відображень, при цьому з огляду на уведені визначення образа і прообразу множина. Отже, розглядаємо відображення f :x→y(xy).
Можна сказати, що це відображення сюр’єктивне, якщо будь-який елемент yєY має хоча б один прообраз при цьому відображенні, порівняєте раніше сказане. Іншими словами, yєY існує х є Х такий, що y= f (х) і тоді f (х)=Y i для yєY справедливо умова f--1(y)≠Ø. Для скінченних множин Х и Y сюр’єктивнiсть відображення f :X→Y означає, що |Х|≤|У| Наприклад; f : {1,2,3,4}→{y1,y2,y3}, f=сюр’єктивне, a f=не сюр’єктивнe.
Відображення f : X→Y ін’єктивне, якщо для будь-якого yєY його f--1(у) повний прообраз містить не більш одного елемента (порівняєте раніше сказане). Іншими словами f:X→Y ін”єктивно, якщо для будь-яких x≠x’, x,x’єx, f(x)≠f(x’).Якщо Х i Y скінченні, то ін’єктивність відображення означає, що |Х|≤|Y|. Наприклад, х = {l,2,3}, Y={y1 y2 y3 y4} I якщо f(I)=Y1, f(2)=Y2, f(3)=Y3, то f :X→Y ін’єктивнe.
Дійсно, із сюр’єктивності випливає, що | f--1 (y)|≥I для будь-якого yєY , а з ін’єктивності випливає, що | f -1(y)| ≤I для кожного yєY. Отже, бієктивність f означає, що| f -1(y)|=I для будь-якого yєY, тобто умова y=f(x)для кожного yєY однозначно визначає єдине значення xєХ. Кажуть, що бієктивне відображення встановлює взаємно однозначну відповідність між X i Y . При скінченних X і Y в цьому випадку |X|=|Y|. Наприклад, X = (1,2,3). Y={У1,У2,У3} , тo f =
Повернемося знову до введеного раніше поняттям "образ" і "прообраз" і розглянемо поняття образа і прообразу підмножини.
Образ і прообраз підмножини
Нехай маємо відображення f: X→Y та A - підмножина Х. Позначимо через f(A) підмножинy Y, утворену зі всіх елементів f (x), x(A, тобто f(A)={f(x)|x(A}. Очевидно, що f(Ø)=Ø. Виходячи з відображення f , ми тим самим визначаємо деяке відображення A→f(A) множини Р(Х) у множину Р(Y). Це відображення зберігає символи,, у тому сенсі, що коли А B, то f(A)f(B), f(AB)=f(A)f(B). Однак символи ,C при цьому відображенні не зберігаються, тому що має місце лише включення, тобто f (AB) f (A)f (B). Дійсно, нехай f - постійне відображення, тобто f(x)=b для всіх x(X , A i B – підмножини множини Х, що не перетинаються. Оскільки AB=Ø, то f(AB)= Ø і це не збігається з f(A)f (B)={b}
Підмножина f(A) називається образом підмножини А нри відображенні f.
Нехай тепер В є деякою підмножиною множини Y . Будемо позначати через f -1(В) підмножину множини Х , утворену з усіх таких елементів х , що f(х)(В, тобто f--1(B)={x| f(x)(B}. Очевидно, f -1(Ø)=Ø. Може виявитися, що f--1(B)=Ø при B≠Ø, наприклад, f : х→х2 відображення множини R в R , тоді f--1({-1})= Ø. Тим самим ми зв'язали з відображенням f відображення B→f--1(B) множини Р(Y) в множину Р(X). Це відображення зберігає п'ять символів ,,, ,С в тому сенсі, що коли АВ , то f--1(A)f--1(B), f--1(AB)=f--1(A)f--1(B), f--1(A)f--1(B)=f--1(A)f--1(B), f-1(СA)=С(f--1(А)).Таким чином, відображення f'-1 простіше. ніж відображення f.
Підмножина f--1(B) називається прообразом підмножини В при відображенні f.
Це визначення зовсім не припускає бієктивності f . У всякому разі, якщо yєY , тo можна говорити про f--1 ({У}), але ця деяка частина Х , а не елемент X . Ця частина може містити більше одного елемента, якщо f не ін’єктивне, а може виявитися і порожній, якщо f не сюр’єктивне. Якщо f бієктивне, то f--1({y})={ f--1(Y)}. Символ f--1(B) крім того, може мати два можливих однакових значення: це прообраз B при відображенні f чи образ множини В при бієктивному зворотному відображенні f -1. Природно, якщо f бієктивне, то образ також зберігає п'ять символів ,,, ,С , і, крім того, маємо f -1(f(А)) А для АєР(Х) , f (f--1(В)) В для ВєР(Y). Ми розглянули множини X , Y і говорили про відображення одного в інше, позначаючи подібне відображення f (чи f--1 ). Але самих відображень також може бути множина, до розгляду якого ми і переходимо.
Множина відображень. Сім’ї. Послідовності
Якщо Х i Y довільні множини, то можна говорити про деяку нову множину - множину відображень X в Y . Наприклад, якщо Х={x1,x2}, то множина відображень X в Y може бути бієктивно відображене на квадрат У2 , тому що кожне відображенням в Y цілком визначається парою (y1,y2)є У2 образів y1,y2 елементів , x1, x2 з Х.
Далі, якщо Х= {x1, x2,….,xk} тo множина відображень X в Y можна бієктивнe відобразити на Yk , тому що кожне таке відображення еквівалентне завданню системи (у1, y2,..., уk) є Yk образів х1 x2,….,xk при цьому відображенні.
Тому множина відображень Х в Y прийнято позначати Yx. Далі приведені різні підмножини множини Y x
1) множина безупинних відображень Х в Y , якщо Х и Y метричні простори;
2) множина лінійних відображень Х в Y , якщо X і Y векторні простори;
3) сімейство (xj)jєJ елементів з X , постачених індексами з множини J , можна розглядати як відображення J у Х. Множина сімейств елементів з X , постачених індексами з J , є не чим іншим, як множиною Х відображень J у X ;
4) послідовність елементів з Х можна визначити як сімейство елементів з X , постачених індексами з множини цілих чисел ≥ 0, чи ж як відображення N в Х. Множина усіх послідовностей елементів з Х є множиною Х n
5) можна говорити про послідовності з індексами з множини N цілих чисел ≥. I чи про кінцеву послідовність, постаченої індексами з кінцевої множини цілих чисел 1,2,..., к. Завжди слід уточнювати зміст вираження "послідовність" при розбіжності множини індексів з множиною цілих чисел.
Композиція відображень
Нехай f:X→Y, а g:Y→Z. Тоді композицією відображень f і g , що позначається gоf будемо називати відображення, визначене формулою gоf (x)=g(f(x)). Іншими словами - це відображення X в Z gоf |xyz.. Прийнято правило, відповідно до якого в композиції gоf треба починати з відображення f , розташованого праворуч.
Нехай AX, тоді gоf (А) = g(f(A)) , де f(А) підмножина y , утворене з всіх елементів f(x),х є A. Якщо BZ, тo (gоf)-1(B)=f--1(g-1(B)). Композиція відображень асоціативна, тобто якщо f: Х→У , g:Y→Z , h:Z→W, то (hog)of=ho(gоf)=hogоf.
Якщо f--1 є бієкцією, зворотної до бієкції f- множини X на Y, то fo-1 f=Ix, fo f--1=Iy, де Ix - тотожне відображення X , Iy- тотожне відображення Y. I навпаки, якщо відображення f:X→Y і g:Y→X такі, що gоf =Ix,fog=Iy, тo f- бієкція, а g - його зворотня бієкція. Якщо f:X→Y бієкція і g:Y→Z бієкція, то gоf - бієкція Х на Z , а її зворотна бієкція буде fo-1 g-1 .
Нехай f:X→Y, a AX тоді відображення fA :A→Х , визначене формулою fA (х)=f (x) для x є А , називається звуженням
f на А и позначається через f /А. Говорять також, що f є продовженням на X відображення fA множини А в множину Y. Найчастіше в цьому випадку продовжують писати f замість fA . Точно так само, якщо f :Х → Y i f(x) В. те f/ визначає деяке відображення fB :Х → B, що задається формулою fB (х) = f (х) . Практично завжди замість f B пишуть f .
Заміна змінних і заміна функцій
Нехай f - функція, визначена на Х , зі значеннями в Y. Якщо і U:X1 → X , тo можна побудувати нову функцію f1=fo u :x1 →y
i тоді говорять, що тим самим зроблена заміна змінної U чи заміна вихідної множини х1 х і що f1 є прообразом f при цій заміні змінної. Підставивши х = u(х1) у вираження f(x)i одержують f1(x1) . Часто, якщо не вказується сама заміна змінної U , функція f позначається через u* f чи навіть через f*. Таким чином, u*f(x1)=f(u(x1)) або f *(x1)=f(u(x1)).
Якщо тепер V:Y→Y , то можна визначити функцію f 2= Vo f: X→Y2. При цьому говорять, що зроблено заміну V чи функції заміна множини значень у , тобто YY2 і що f2 є образом f при цій заміні. Можна одночасно замінити змінну і функцію, розглядаючи f3 =Vo fo u і. , де f3 є образом f при заміні змінної u і заміні функції V.
Назвемо для будь-якої множини А відображення IA: А → А як iA(x)=x для x є А. Функцію f будемо називати I-І-функцією, якщо для будь-яких х1, х2, y із того, що у=f(x1) i у=f(x2) випливає x1=x2. Взаємно однозначна відповідність f А→А називається підстановкою множини.
Література
1. Дискретна математика: Підручник/ Ю.М.Бардачов, Н.А.Соколова, В.Є.Ходаков; за ред. В.Є.Ходакова. – К.: Вища школа, 2002. – 287с.
2. Основи дискретної математики: Підручник/ Ю.В.Капітонова, С.Л.Кривий, О.А.Летичевський, Г.М.Луцький, М.К.Печурін. – К.: Наукова думка, 2002. – 568с.
3. Луцький Г.М., Кривий С.Л., Печурін М.К. Основи дискретної математики. – К.: ВІПОЛ, 1995. – 252с.
4. Бородін О.I., Потьомкін Л.В., Сліпенко А.К. Основні поняття сучасної алгебри.- К.:Вища школа,1993.-112 с.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора