Реферат: Вивчення поняття відносин залежності

--PAGE_BREAK--Зауваження.

Поняття простору залежності можна й зручно визначати через базу залежності. Саме, множина B всіх мінімальних залежних множин простору залежності <img width=«28» height=«28» src=«ref-1_1513594725-182.coolpic» v:shapes="_x0000_i1169"> Z<img width=«19» height=«28» src=«ref-1_1513594907-90.coolpic» v:shapes="_x0000_i1170"> назвемо його базою. Ясно, що множини з B не порожні, кінцеві й не втримуються друг у другу. Крім того, будь-яка незалежна множина містить деяка множина бази B. Простір <img width=«28» height=«28» src=«ref-1_1513594725-182.coolpic» v:shapes="_x0000_i1171"> Z<img width=«19» height=«28» src=«ref-1_1513594907-90.coolpic» v:shapes="_x0000_i1172"> має єдину базу й однозначно визначається їй. Тому простору залежності можна задавати базами.

Легко бачити, що вірно наступне твердження:

Непуста множина B підмножин множини <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1173"> задає на <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1174"> відношення залежності тоді й тільки тоді, коли множини з B не порожні, кінцеві й не включений друг у друга.

У термінах бази B можна сформулювати умова транзитивності відповідного простору залежності.
2. Простір залежності



Теорема 1.

Нехай <img width=«28» height=«28» src=«ref-1_1513594725-182.coolpic» v:shapes="_x0000_i1175"> Z<img width=«19» height=«28» src=«ref-1_1513594907-90.coolpic» v:shapes="_x0000_i1176"> — довільний простір залежності. Розглянемо наступні три твердження:

X — базис в A;

X — максимальна незалежна підмножина в A;

 X — мінімальна множина, що породжує, в A.

Тоді <img width=«71» height=«24» src=«ref-1_1513625346-351.coolpic» v:shapes="_x0000_i1177"> й <img width=«79» height=«24» src=«ref-1_1513625697-351.coolpic» v:shapes="_x0000_i1178">.

Доказ:

(i) <img width=«20» height=«16» src=«ref-1_1513626048-91.coolpic» v:shapes="_x0000_i1179"> (ii)     Якщо X – базис, то по визначенню 6 X – незалежна підмножина, що породжує. Доведемо від противного, що воно максимальне. Нехай існують незалежні множини <img width=«56» height=«19» src=«ref-1_1513626139-196.coolpic» v:shapes="_x0000_i1180">. Візьмемо <img width=«73» height=«20» src=«ref-1_1513626335-245.coolpic» v:shapes="_x0000_i1181">, тоді <img width=«60» height=«24» src=«ref-1_1513626580-313.coolpic» v:shapes="_x0000_i1182"> незалежно, тому що будь-яка підмножина незалежної множини незалежно. Тому по визначеннях 3 і 5 <img width=«60» height=«28» src=«ref-1_1513626893-259.coolpic» v:shapes="_x0000_i1183">, звідки <img width=«64» height=«28» src=«ref-1_1513627152-224.coolpic» v:shapes="_x0000_i1184">, одержали протиріччя з умовою. Тому X є максимальною незалежною підмножиною в A.

(ii) <img width=«20» height=«16» src=«ref-1_1513626048-91.coolpic» v:shapes="_x0000_i1185"> (i)     Доведемо від противного, нехай <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1186"> не базис в <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1187">, тобто <img width=«64» height=«28» src=«ref-1_1513627152-224.coolpic» v:shapes="_x0000_i1188">. Тоді <img width=«96» height=«28» src=«ref-1_1513627887-330.coolpic» v:shapes="_x0000_i1189"> таке, що <img width=«64» height=«24» src=«ref-1_1513628217-316.coolpic» v:shapes="_x0000_i1190">незалежно й лежить в <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1191">, одержали протиріччя з максимальністю <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1192">.

(ii) <img width=«20» height=«16» src=«ref-1_1513626048-91.coolpic» v:shapes="_x0000_i1193"> (iii) Якщо X — максимальна незалежна множина в A, те всякий елемент в<img width=«15» height=«15» src=«ref-1_1513628820-141.coolpic» v:shapes="_x0000_i1194"> A або належить X, або такий, що <img width=«63» height=«25» src=«ref-1_1513628961-325.coolpic» v:shapes="_x0000_i1195">залежно, а тому <img width=«55» height=«27» src=«ref-1_1513629286-168.coolpic» v:shapes="_x0000_i1196"> в тім і іншому випадку, тобто <img width=«67» height=«28» src=«ref-1_1513629454-257.coolpic» v:shapes="_x0000_i1197"> Оскільки <img width=«67» height=«28» src=«ref-1_1513629711-257.coolpic» v:shapes="_x0000_i1198">, те X - множина, що породжує. Виходить, <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1199">  — базис простору <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1200">.

Доведемо тепер, що воно мінімально. Нехай множина <img width=«55» height=«19» src=«ref-1_1513630164-194.coolpic» v:shapes="_x0000_i1201">. Доведемо, що воно не є породжує для A. Візьмемо <img width=«48» height=«20» src=«ref-1_1513630358-192.coolpic» v:shapes="_x0000_i1202">, але <img width=«44» height=«21» src=«ref-1_1513630550-132.coolpic» v:shapes="_x0000_i1203">. Тоді <img width=«53» height=«24» src=«ref-1_1513630682-277.coolpic» v:shapes="_x0000_i1204"> незалежно, як підмножина множини X. Тому по визначеннях 3 і 5 <img width=«55» height=«27» src=«ref-1_1513630959-256.coolpic» v:shapes="_x0000_i1205"> і <img width=«60» height=«28» src=«ref-1_1513631215-218.coolpic» v:shapes="_x0000_i1206">, а це значить, що Y не є множиною, що породжує. Висновок: X – мінімальна множина, що породжує, в A.

(i) <img width=«20» height=«16» src=«ref-1_1513626048-91.coolpic» v:shapes="_x0000_i1207"> (iii) Справедливо, по доведеним вище твердженнях (i)<img width=«20» height=«16» src=«ref-1_1513626048-91.coolpic» v:shapes="_x0000_i1208"> (ii) і (ii) <img width=«20» height=«16» src=«ref-1_1513626048-91.coolpic» v:shapes="_x0000_i1209">(iii). :


Визначення — позначення 10.

Для довільної множини <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1210"> простору залежності <img width=«28» height=«28» src=«ref-1_1513594725-182.coolpic» v:shapes="_x0000_i1211"> Z<img width=«19» height=«28» src=«ref-1_1513594907-90.coolpic» v:shapes="_x0000_i1212"> позначимо <img width=«48» height=«24» src=«ref-1_1513632078-259.coolpic» v:shapes="_x0000_i1213"> множину всіх максимальних незалежних підмножин, а через <img width=«51» height=«24» src=«ref-1_1513632337-269.coolpic» v:shapes="_x0000_i1214">  — множину всіх мінімальних підмножин, що породжують, цієї множини.

З теореми 1 випливає, що <img width=«45» height=«24» src=«ref-1_1513632606-267.coolpic» v:shapes="_x0000_i1215"> збігається із множиною всіляких базисів простору <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1216"> й <img width=«119» height=«24» src=«ref-1_1513632969-446.coolpic» v:shapes="_x0000_i1217"> для кожного <img width=«55» height=«21» src=«ref-1_1513611357-148.coolpic» v:shapes="_x0000_i1218">.

Наступний приклад показує, що зворотне включення <img width=«119» height=«24» src=«ref-1_1513633563-447.coolpic» v:shapes="_x0000_i1219"> вірно не завжди.

Приклад 10.

Розглянемо дев'яти елементну множину <img width=«65» height=«28» src=«ref-1_1513634010-313.coolpic» v:shapes="_x0000_i1220">, що записана у вигляді матриці <img width=«164» height=«84» src=«ref-1_1513634323-891.coolpic» v:shapes="_x0000_i1221">. Залежнимибудемо вважати підмножини множини <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1222">, що містять «прямі лінії»: стовпці, рядки або діагоналі матриці <img width=«19» height=«24» src=«ref-1_1513635310-163.coolpic» v:shapes="_x0000_i1223">.

Розглянемо множини <img width=«156» height=«25» src=«ref-1_1513635473-478.coolpic» v:shapes="_x0000_i1224"> й <img width=«188» height=«25» src=«ref-1_1513635951-529.coolpic» v:shapes="_x0000_i1225">, вони буде максимальними незалежними, тому що не містять прямих і при додаванні будь-якого елемента з <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1226">, що не лежить у них, стають залежними. Тут максимальні незалежні множини містять різна кількість елементів.

Розглянемо ще одну множину <img width=«219» height=«25» src=«ref-1_1513636576-584.coolpic» v:shapes="_x0000_i1227">, вона є мінімальним що породжує, тому що якщо виключити з нього хоча б один елемент, то воно вже не буде множиною, що породжує. Легко помітити, що <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1228"> залежно, тому не є базисом. Даний приклад ілюструє, що (iii)<img width=«23» height=«17» src=«ref-1_1513637260-92.coolpic» v:shapes="_x0000_i1229"> (i) не вірно в загальному випадку, тобто для довільних просторів залежності.

Для будь-якого простору залежності <img width=«28» height=«28» src=«ref-1_1513594725-182.coolpic» v:shapes="_x0000_i1230"> Z<img width=«19» height=«28» src=«ref-1_1513594907-90.coolpic» v:shapes="_x0000_i1231"> виконуються наступні властивості:

Заміщення.Якщо <img width=«311» height=«28» src=«ref-1_1513637624-836.coolpic» v:shapes="_x0000_i1232">

Доказ:

Нехай <img width=«61» height=«28» src=«ref-1_1513638460-267.coolpic» v:shapes="_x0000_i1233">, <img width=«104» height=«28» src=«ref-1_1513638727-416.coolpic» v:shapes="_x0000_i1234">. Тому що <img width=«16» height=«20» src=«ref-1_1513639143-92.coolpic» v:shapes="_x0000_i1235"> залежить від <img width=«63» height=«24» src=«ref-1_1513639235-309.coolpic» v:shapes="_x0000_i1236">, те <img width=«16» height=«20» src=«ref-1_1513639143-92.coolpic» v:shapes="_x0000_i1237"> залежить від незалежної підмножини <img width=«16» height=«19» src=«ref-1_1513597563-92.coolpic» v:shapes="_x0000_i1238"> множини <img width=«63» height=«24» src=«ref-1_1513639235-309.coolpic» v:shapes="_x0000_i1239">, тобто <img width=«61» height=«25» src=«ref-1_1513640037-288.coolpic» v:shapes="_x0000_i1240"> залежно. Тепер, якби <img width=«43» height=«21» src=«ref-1_1513640325-129.coolpic» v:shapes="_x0000_i1241">, те <img width=«16» height=«19» src=«ref-1_1513597563-92.coolpic» v:shapes="_x0000_i1242"> було б підмножиною множини <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1243"> й тому <img width=«61» height=«28» src=«ref-1_1513640646-247.coolpic» v:shapes="_x0000_i1244">, що суперечило б нашому припущенню. Тому <img width=«43» height=«19» src=«ref-1_1513640893-182.coolpic» v:shapes="_x0000_i1245">. Візьмемо <img width=«125» height=«28» src=«ref-1_1513641075-415.coolpic» v:shapes="_x0000_i1246">. Тоді <img width=«149» height=«29» src=«ref-1_1513641490-476.coolpic» v:shapes="_x0000_i1247"> незалежно, тому що <img width=«63» height=«33» src=«ref-1_1513641966-208.coolpic» v:shapes="_x0000_i1248">. Але <img width=«195» height=«29» src=«ref-1_1513642174-695.coolpic» v:shapes="_x0000_i1249"> залежно. Звідки <img width=«199» height=«33» src=«ref-1_1513642869-613.coolpic» v:shapes="_x0000_i1250">.

Вкладеність.Об'єднання будь-якої системи вкладених друг у друга незалежних множин є незалежною множиною, тобто <img width=«76» height=«32» src=«ref-1_1513643482-273.coolpic» v:shapes="_x0000_i1251">  — незалежно, де <img width=«53» height=«27» src=«ref-1_1513643755-261.coolpic» v:shapes="_x0000_i1252"> також незалежні й <img width=«228» height=«28» src=«ref-1_1513644016-665.coolpic» v:shapes="_x0000_i1253">


Доказ:

Доведемо від противного. Припустимо, що <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1254"> залежно, тоді в ньому найдеться кінцева залежна підмножина <img width=«136» height=«25» src=«ref-1_1513644781-427.coolpic» v:shapes="_x0000_i1255">:<img width=«67» height=«28» src=«ref-1_1513645208-252.coolpic» v:shapes="_x0000_i1256">. Маємо <img width=«131» height=«43» src=«ref-1_1513645460-418.coolpic» v:shapes="_x0000_i1257">, одержали протиріччя з незалежністю <img width=«27» height=«28» src=«ref-1_1513645878-115.coolpic» v:shapes="_x0000_i1258">.

Максимальність.Будь-яка незалежна множина втримується в максимальній незалежній множині.

Доказ:

Нехай <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1259">  — довільна незалежна множина в. <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1260"> Утворимо множину <img width=«65» height=«24» src=«ref-1_1513646189-283.coolpic» v:shapes="_x0000_i1261"> Z :<img width=«60» height=«24» src=«ref-1_1513646472-262.coolpic» v:shapes="_x0000_i1262">всіх незалежних множин, що містять <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1263">. Відносно <img width=«19» height=«17» src=«ref-1_1513646834-91.coolpic» v:shapes="_x0000_i1264"> множина <img width=«16» height=«20» src=«ref-1_1513646925-95.coolpic» v:shapes="_x0000_i1265"> є впорядкованою множиною, що задовольняє по властивості вкладеності, умові леми Цорна. Тоді по лемі Цорна в <img width=«16» height=«20» src=«ref-1_1513646925-95.coolpic» v:shapes="_x0000_i1266"> існує максимальний елемент <img width=«56» height=«21» src=«ref-1_1513647115-143.coolpic» v:shapes="_x0000_i1267">.

Теорема 2.

Будь-який простір залежності має базис.

Доказ:

Візьмемо порожню множину, вона незалежне. По властивості максимальності воно повинне втримуватися в деякій максимальній незалежній множині, що по теоремі 1 є базисом.




3. Транзитивність

Особливий інтерес представляють транзитивні простори залежності. Важливим результатом є доказ інваріантності розмірності будь-якого транзитивного простору залежності.

Доведемо деякі властивості, справедливі для транзитивних просторів залежності <img width=«28» height=«28» src=«ref-1_1513594725-182.coolpic» v:shapes="_x0000_i1268"> Z<img width=«19» height=«28» src=«ref-1_1513594907-90.coolpic» v:shapes="_x0000_i1269"> .

Властивість 1: <img width=«16» height=«19» src=«ref-1_1513597563-92.coolpic» v:shapes="_x0000_i1270"> залежить від<img width=«123» height=«28» src=«ref-1_1513647622-389.coolpic» v:shapes="_x0000_i1271">.

Доказ:

<img width=«23» height=«17» src=«ref-1_1513637260-92.coolpic» v:shapes="_x0000_i1272"><img width=«16» height=«19» src=«ref-1_1513597563-92.coolpic» v:shapes="_x0000_i1273"> залежить від <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1274">, тобто <img width=«56» height=«24» src=«ref-1_1513648295-258.coolpic» v:shapes="_x0000_i1275"> <img width=«61» height=«28» src=«ref-1_1513640646-247.coolpic» v:shapes="_x0000_i1276">, і <img width=«65» height=«28» src=«ref-1_1513648800-252.coolpic» v:shapes="_x0000_i1277">. Розглянемо <img width=«80» height=«28» src=«ref-1_1513649052-295.coolpic» v:shapes="_x0000_i1278">, тоді <img width=«60» height=«21» src=«ref-1_1513649347-156.coolpic» v:shapes="_x0000_i1279"><img width=«16» height=«15» src=«ref-1_1513649503-121.coolpic» v:shapes="_x0000_i1280"><img width=«17» height=«19» src=«ref-1_1513614307-93.coolpic» v:shapes="_x0000_i1281">  — незалежно й <img width=«60» height=«24» src=«ref-1_1513649717-302.coolpic» v:shapes="_x0000_i1282">  — залежно, а <img width=«100» height=«28» src=«ref-1_1513650019-306.coolpic» v:shapes="_x0000_i1283">, одержуємо, що <img width=«120» height=«31» src=«ref-1_1513650325-373.coolpic» v:shapes="_x0000_i1284">, тому <img width=«79» height=«28» src=«ref-1_1513650698-287.coolpic» v:shapes="_x0000_i1285">. Маємо <img width=«112» height=«28» src=«ref-1_1513650985-343.coolpic» v:shapes="_x0000_i1286">.

<img width=«23» height=«17» src=«ref-1_1513651328-91.coolpic» v:shapes="_x0000_i1287">По визначенню 8 будь-яка підмножина <img width=«65» height=«28» src=«ref-1_1513648800-252.coolpic» v:shapes="_x0000_i1288"> залежить від <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1289"> 

Властивість 2: Якщо <img width=«17» height=«19» src=«ref-1_1513651771-94.coolpic» v:shapes="_x0000_i1290"> залежить від <img width=«16» height=«19» src=«ref-1_1513597563-92.coolpic» v:shapes="_x0000_i1291">, а <img width=«16» height=«19» src=«ref-1_1513597563-92.coolpic» v:shapes="_x0000_i1292"> залежить від <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1293">, те <img width=«17» height=«19» src=«ref-1_1513651771-94.coolpic» v:shapes="_x0000_i1294"> залежить від <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1295">.

Доказ:

Запишемо умову, використовуючи властивість 1 <img width=«75» height=«28» src=«ref-1_1513652343-279.coolpic» v:shapes="_x0000_i1296">, а <img width=«79» height=«28» src=«ref-1_1513650698-287.coolpic» v:shapes="_x0000_i1297">, тоді очевидно, що <img width=«124» height=«28» src=«ref-1_1513652909-382.coolpic» v:shapes="_x0000_i1298">.


Властивість 3: Якщо X — мінімальна множина, що породжує, в A, те X — базис в A.

Доказ:

Нехай X — мінімальна множина, що породжує, в A. Покажемо, що воно не може бути залежним, тому що в цьому випадку його можна було б замінити власною підмножиною, що усе ще породжує A. Дійсно, у силу транзитивності відносини залежності, будь-яка множина, що породжує множина X, буде так само породжувати й множина A. Отже, X — незалежна множина, що породжує, що по визначенню 6 є базисом.

Властивість 4: <img width=«116» height=«24» src=«ref-1_1513653291-422.coolpic» v:shapes="_x0000_i1299"> для кожного <img width=«55» height=«21» src=«ref-1_1513611357-148.coolpic» v:shapes="_x0000_i1300">.

Доказ: Потрібне із властивості 3.

Властивість 5 (про заміну.):

Якщо X — незалежна множина й Y —множина, що породжує, в A, то існує така <img width=«20» height=«20» src=«ref-1_1513653861-102.coolpic» v:shapes="_x0000_i1301"> підмножина множини Y, <img width=«80» height=«23» src=«ref-1_1513653963-191.coolpic» v:shapes="_x0000_i1302"> що <img width=«48» height=«23» src=«ref-1_1513654154-150.coolpic» v:shapes="_x0000_i1303"> й — базис для A.

Доказ:

Розглянемо систему J таких незалежних підмножин Z множини A, що <img width=«108» height=«20» src=«ref-1_1513654304-213.coolpic» v:shapes="_x0000_i1304">.

Тому що X незалежно, те такі множини існують; крім того, якщо <img width=«33» height=«24» src=«ref-1_1513654517-202.coolpic» v:shapes="_x0000_i1305">— деяке лінійно впорядкована множина множин з J, те його об'єднання <img width=«60» height=«24» src=«ref-1_1513654719-156.coolpic» v:shapes="_x0000_i1306"> знову належить J, оскільки Z задовольняє умові <img width=«108» height=«20» src=«ref-1_1513654304-213.coolpic» v:shapes="_x0000_i1307">, і якщо Z залежне, те деяка кінцева підмножина множини Z повинне було б бути залежним; ця підмножина втримувалося б у деякій множині <img width=«33» height=«24» src=«ref-1_1513654517-202.coolpic» v:shapes="_x0000_i1308"> в суперечності з тим фактом, що всі <img width=«33» height=«24» src=«ref-1_1513654517-202.coolpic» v:shapes="_x0000_i1309"> незалежні.

По лемі Цорна Jмає максимальний елемент М; у силу максимальності кожний елемент множини Y або належить М, або залежить від М, звідки <img width=«108» height=«28» src=«ref-1_1513655492-264.coolpic» v:shapes="_x0000_i1310">. Цим доведено, що М — базис вA. Тому що <img width=«115» height=«20» src=«ref-1_1513655756-230.coolpic» v:shapes="_x0000_i1311">, те М має вигляд <img width=«80» height=«23» src=«ref-1_1513655986-195.coolpic» v:shapes="_x0000_i1312">, де <img width=«75» height=«20» src=«ref-1_1513656181-172.coolpic» v:shapes="_x0000_i1313"> задовольняє умовам <img width=«128» height=«24» src=«ref-1_1513656353-250.coolpic» v:shapes="_x0000_i1314">.■

Визначення 11.

Простір залежності <img width=«28» height=«28» src=«ref-1_1513594725-182.coolpic» v:shapes="_x0000_i1315"> Z<img width=«19» height=«28» src=«ref-1_1513594907-90.coolpic» v:shapes="_x0000_i1316"> називається кінцеве мірним, якщо будь-яке його незалежна множина кінцева.

Теорема 3.

Нехай <img width=«28» height=«28» src=«ref-1_1513594725-182.coolpic» v:shapes="_x0000_i1317"> Z<img width=«19» height=«28» src=«ref-1_1513594907-90.coolpic» v:shapes="_x0000_i1318"> — транзитивний простір залежності. Тоді будь-які два базиси в цьому просторі рівно потужні.


Доказ:

Розглянемо спочатку випадок кінцеве мірного простору <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1319">.

Нехай В, З — будь-які два базиси в А, їхнє існування забезпечується теоремою 2, і <img width=«133» height=«31» src=«ref-1_1513657243-451.coolpic» v:shapes="_x0000_i1320">, <img width=«164» height=«29» src=«ref-1_1513657694-478.coolpic» v:shapes="_x0000_i1321">, <img width=«165» height=«29» src=«ref-1_1513658172-458.coolpic» v:shapes="_x0000_i1322">, де різні елементи позначені різними буквами або постачені різними індексами. Застосуємо індукцію по max (r, s).

Якщо r = 0 або s = 0, то <img width=«53» height=«21» src=«ref-1_1513658630-142.coolpic» v:shapes="_x0000_i1323">або <img width=«53» height=«21» src=«ref-1_1513658772-141.coolpic» v:shapes="_x0000_i1324">, і <img width=«48» height=«20» src=«ref-1_1513658913-130.coolpic» v:shapes="_x0000_i1325">. Тому можна припускати, що r ≥ 1, s ≥ 1, без обмеження спільності будемо вважати, що r > s, так що насправді r > 1.

Припустимо, що базиси будуть рівне потужними для будь-якого t < r

По лемі про заміну множина <img width=«100» height=«31» src=«ref-1_1513659043-404.coolpic» v:shapes="_x0000_i1326"> можна доповнити до базису D елементами базису З, скажемо
<img width=«203» height=«49» src=«ref-1_1513659447-636.coolpic» v:shapes="_x0000_i1327">, t ≤ s < r.
Тепер перетинання D c У складається з n + 1 елемента, і D містить, крім того, ще t (< r) елементів, тоді як У містить, крім цього перетинання, ще r — 1 елементів, так що по припущенню індукції <img width=«64» height=«28» src=«ref-1_1513660083-201.coolpic» v:shapes="_x0000_i1328">, тобто <img width=«63» height=«20» src=«ref-1_1513660284-170.coolpic» v:shapes="_x0000_i1329">.

Оскільки r > 1, звідси випливає, що t ≥ 1, і тому перетинання D із Із містить не менше ніж n+1 елементів. Використовуючи ще раз припущення індукції, знаходимо, що <img width=«63» height=«20» src=«ref-1_1513660454-172.coolpic» v:shapes="_x0000_i1330"> й, отже, r = s і базиси В и С рівне потужні.

Далі, нехай В — кінцевий базис в. <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1331"> Тоді й будь-який інший базис Із простору <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1332"> буде кінцевим. Дійсно, У виражається через кінцеву множину елементів <img width=«57» height=«23» src=«ref-1_1513660818-220.coolpic» v:shapes="_x0000_i1333"> у силу транзитивності <img width=«23» height=«21» src=«ref-1_1513661038-101.coolpic» v:shapes="_x0000_i1334"> буде що породжує й незалежною множиною в <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1335">, тобто <img width=«55» height=«21» src=«ref-1_1513661235-136.coolpic» v:shapes="_x0000_i1336">.

Нарешті, якщо базиси В и С нескінченні. Кожний елемент із У залежить від деякої кінцевої підмножини базису З, і навпаки. Потужність множини всіх кінцевих підмножин усякої нескінченної множини дорівнює потужності самої множини. Тому потужності В и С збігаються.

    продолжение
--PAGE_BREAK--Теорема 4.

Нехай <img width=«28» height=«28» src=«ref-1_1513594725-182.coolpic» v:shapes="_x0000_i1337"> Z<img width=«19» height=«28» src=«ref-1_1513594907-90.coolpic» v:shapes="_x0000_i1338"> — довільний простір залежності, тоді наступні умови еквівалентні


Z транзитивне;

для будь-якого кінцевого<img width=«55» height=«21» src=«ref-1_1513611357-148.coolpic» v:shapes="_x0000_i1339"><img width=«111» height=«24» src=«ref-1_1513661791-425.coolpic» v:shapes="_x0000_i1340"> <img width=«57» height=«28» src=«ref-1_1513662216-195.coolpic» v:shapes="_x0000_i1341">;

<img width=«51» height=«23» src=«ref-1_1513662411-243.coolpic» v:shapes="_x0000_i1342"> кінцевих і <img width=«81» height=«23» src=«ref-1_1513662654-256.coolpic» v:shapes="_x0000_i1343"><img width=«52» height=«23» src=«ref-1_1513662910-236.coolpic» v:shapes="_x0000_i1344">Z<img width=«204» height=«28» src=«ref-1_1513663146-548.coolpic» v:shapes="_x0000_i1345">

<img width=«77» height=«24» src=«ref-1_1513663694-370.coolpic» v:shapes="_x0000_i1346"> Z;

для будь-якого кінцевого<img width=«55» height=«21» src=«ref-1_1513611357-148.coolpic» v:shapes="_x0000_i1347"><img width=«116» height=«24» src=«ref-1_1513664212-433.coolpic» v:shapes="_x0000_i1348"><img width=«59» height=«28» src=«ref-1_1513664645-196.coolpic» v:shapes="_x0000_i1349">.

Доказ:

(i) <img width=«20» height=«16» src=«ref-1_1513626048-91.coolpic» v:shapes="_x0000_i1350"> (ii)     Справедливо по теоремі 3 і прикладу 7.

(ii) <img width=«20» height=«16» src=«ref-1_1513626048-91.coolpic» v:shapes="_x0000_i1351"> (iii)   Візьмемо <img width=«72» height=«23» src=«ref-1_1513665023-243.coolpic» v:shapes="_x0000_i1352">, так що <img width=«39» height=«23» src=«ref-1_1513665266-186.coolpic» v:shapes="_x0000_i1353">  — незалежно й <img width=«85» height=«28» src=«ref-1_1513665452-266.coolpic» v:shapes="_x0000_i1354">. Допустимо, що твердження <img width=«84» height=«20» src=«ref-1_1513665718-265.coolpic» v:shapes="_x0000_i1355"><img width=«77» height=«24» src=«ref-1_1513663694-370.coolpic» v:shapes="_x0000_i1356"> Z невірно. Тоді <img width=«87» height=«20» src=«ref-1_1513666353-304.coolpic» v:shapes="_x0000_i1357"><img width=«77» height=«24» src=«ref-1_1513666657-347.coolpic» v:shapes="_x0000_i1358"> Z. Розглянемо <img width=«85» height=«20» src=«ref-1_1513667004-237.coolpic» v:shapes="_x0000_i1359">. Маємо <img width=«79» height=«24» src=«ref-1_1513667241-331.coolpic» v:shapes="_x0000_i1360">. Але <img width=«29» height=«21» src=«ref-1_1513667572-114.coolpic» v:shapes="_x0000_i1361"> Z, тому <img width=«32» height=«20» src=«ref-1_1513667686-146.coolpic» v:shapes="_x0000_i1362"> <img width=«103» height=«23» src=«ref-1_1513667832-339.coolpic» v:shapes="_x0000_i1363">Z <img width=«98» height=«25» src=«ref-1_1513668171-332.coolpic» v:shapes="_x0000_i1364">. По (ii) маємо<img width=«65» height=«28» src=«ref-1_1513668503-230.coolpic» v:shapes="_x0000_i1365">. Але <img width=«163» height=«28» src=«ref-1_1513668733-473.coolpic» v:shapes="_x0000_i1366">  — протиріччя.

(iii) <img width=«20» height=«16» src=«ref-1_1513626048-91.coolpic» v:shapes="_x0000_i1367"> (ii) Доведемо від противного. Нехай <img width=«169» height=«28» src=«ref-1_1513669297-582.coolpic» v:shapes="_x0000_i1368">. Можна вважати, що <img width=«81» height=«28» src=«ref-1_1513669879-262.coolpic» v:shapes="_x0000_i1369">. Тоді по (iii) <img width=«176» height=«24» src=«ref-1_1513670141-544.coolpic» v:shapes="_x0000_i1370"> незалежно. Одержали протиріччя з максимальністю <img width=«17» height=«20» src=«ref-1_1513670685-94.coolpic» v:shapes="_x0000_i1371">

(iii) <img width=«20» height=«16» src=«ref-1_1513626048-91.coolpic» v:shapes="_x0000_i1372"> (i)    Потрібно довести рівність <img width=«92» height=«31» src=«ref-1_1513670870-259.coolpic» v:shapes="_x0000_i1373"> для довільного<img width=«55» height=«21» src=«ref-1_1513595188-148.coolpic» v:shapes="_x0000_i1374">.

Візьмемо <img width=«87» height=«25» src=«ref-1_1513671277-321.coolpic» v:shapes="_x0000_i1375"> й покажемо, що <img width=«87» height=«28» src=«ref-1_1513671598-290.coolpic» v:shapes="_x0000_i1376"> Тому що <img width=«63» height=«23» src=«ref-1_1513671888-229.coolpic» v:shapes="_x0000_i1377">, те <img width=«89» height=«28» src=«ref-1_1513672117-316.coolpic» v:shapes="_x0000_i1378"> Нехай існує <img width=«107» height=«28» src=«ref-1_1513672433-371.coolpic» v:shapes="_x0000_i1379">, тоді <img width=«99» height=«24» src=«ref-1_1513672804-372.coolpic» v:shapes="_x0000_i1380"> незалежно й існує <img width=«41» height=«23» src=«ref-1_1513673176-213.coolpic» v:shapes="_x0000_i1381"> Z і <img width=«163» height=«24» src=«ref-1_1513673389-539.coolpic» v:shapes="_x0000_i1382"> Z. Розширюючи <img width=«28» height=«20» src=«ref-1_1513673928-141.coolpic» v:shapes="_x0000_i1383"> в <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1384"> можна припустити, що <img width=«93» height=«25» src=«ref-1_1513674169-332.coolpic» v:shapes="_x0000_i1385"> По (ii) <img width=«76» height=«28» src=«ref-1_1513674501-258.coolpic» v:shapes="_x0000_i1386">, тобто <img width=«92» height=«28» src=«ref-1_1513674759-318.coolpic» v:shapes="_x0000_i1387">. Тому по (iii) <img width=«176» height=«24» src=«ref-1_1513675077-573.coolpic» v:shapes="_x0000_i1388">Z. бачимо, що <img width=«43» height=«20» src=«ref-1_1513675650-162.coolpic» v:shapes="_x0000_i1389">. Виходить, <img width=«88» height=«23» src=«ref-1_1513675812-278.coolpic» v:shapes="_x0000_i1390">. Одержуємо протиріччя з тим, що <img width=«93» height=«25» src=«ref-1_1513674169-332.coolpic» v:shapes="_x0000_i1391"> Отже, <img width=«87» height=«28» src=«ref-1_1513676422-312.coolpic» v:shapes="_x0000_i1392">, те мережа <img width=«84» height=«28» src=«ref-1_1513676734-256.coolpic» v:shapes="_x0000_i1393">.

Тепер досить показати, що <img width=«104» height=«31» src=«ref-1_1513676990-364.coolpic» v:shapes="_x0000_i1394">. Нехай <img width=«124» height=«31» src=«ref-1_1513677354-434.coolpic» v:shapes="_x0000_i1395">, тоді <img width=«164» height=«28» src=«ref-1_1513677788-559.coolpic» v:shapes="_x0000_i1396"> залежно, розширюючи <img width=«21» height=«20» src=«ref-1_1513678347-126.coolpic» v:shapes="_x0000_i1397">в <img width=«37» height=«28» src=«ref-1_1513678473-174.coolpic» v:shapes="_x0000_i1398"> можна припустити, що <img width=«95» height=«28» src=«ref-1_1513678647-392.coolpic» v:shapes="_x0000_i1399">, крім того <img width=«97» height=«28» src=«ref-1_1513679039-397.coolpic» v:shapes="_x0000_i1400">, тоді по (ii) <img width=«69» height=«28» src=«ref-1_1513679436-242.coolpic» v:shapes="_x0000_i1401">. <img width=«99» height=«24» src=«ref-1_1513672804-372.coolpic» v:shapes="_x0000_i1402"> незалежно, тому <img width=«85» height=«28» src=«ref-1_1513680050-302.coolpic» v:shapes="_x0000_i1403">. По (iii) <img width=«163» height=«24» src=«ref-1_1513680352-545.coolpic» v:shapes="_x0000_i1404">Z. бачимо, що <img width=«43» height=«20» src=«ref-1_1513675650-162.coolpic» v:shapes="_x0000_i1405">. Виходить, <img width=«105» height=«28» src=«ref-1_1513681059-339.coolpic» v:shapes="_x0000_i1406">, одержали протиріччя з максимальністю <img width=«21» height=«20» src=«ref-1_1513678347-126.coolpic» v:shapes="_x0000_i1407">. Отже, <img width=«104» height=«31» src=«ref-1_1513676990-364.coolpic» v:shapes="_x0000_i1408">, зворотне включення очевидно, тому <img width=«101» height=«31» src=«ref-1_1513681888-310.coolpic» v:shapes="_x0000_i1409">.

(iv) <img width=«25» height=«17» src=«ref-1_1513682198-97.coolpic» v:shapes="_x0000_i1410">(ii) У силу теорем 1 і 3 і доведена еквівалентності

(i) <img width=«25» height=«17» src=«ref-1_1513682198-97.coolpic» v:shapes="_x0000_i1411">(ii).■

Далі будемо розглядати транзитивний простір залежності <img width=«28» height=«28» src=«ref-1_1513594725-182.coolpic» v:shapes="_x0000_i1412"> Z<img width=«19» height=«28» src=«ref-1_1513594907-90.coolpic» v:shapes="_x0000_i1413">.

Визначення 12.

Потужність максимальної незалежної підмножини даної множини <img width=«54» height=«21» src=«ref-1_1513682664-148.coolpic» v:shapes="_x0000_i1414"> називається рангом цієї множини: <img width=«133» height=«36» src=«ref-1_1513682812-556.coolpic» v:shapes="_x0000_i1415">.

Будемо розглядати кінцеві підмножини <img width=«75» height=«23» src=«ref-1_1513683368-245.coolpic» v:shapes="_x0000_i1416">.

Мають місце наступні властивості.

Властивість 1о: <img width=«35» height=«21» src=«ref-1_1513683613-116.coolpic» v:shapes="_x0000_i1417"> Z <img width=«164» height=«24» src=«ref-1_1513683729-472.coolpic» v:shapes="_x0000_i1418">.

Доказ: <img width=«35» height=«21» src=«ref-1_1513683613-116.coolpic» v:shapes="_x0000_i1419">Z <img width=«275» height=«24» src=«ref-1_1513684317-645.coolpic» v:shapes="_x0000_i1420">.

Властивість 2о: <img width=«35» height=«21» src=«ref-1_1513683613-116.coolpic» v:shapes="_x0000_i1421">Z <img width=«104» height=«28» src=«ref-1_1513685078-391.coolpic» v:shapes="_x0000_i1422">.

Доказ: <img width=«35» height=«21» src=«ref-1_1513683613-116.coolpic» v:shapes="_x0000_i1423">Z, візьмемо <img width=«79» height=«24» src=«ref-1_1513685585-325.coolpic» v:shapes="_x0000_i1424">, тодіпо властивості 1о<img width=«51» height=«19» src=«ref-1_1513685910-132.coolpic» v:shapes="_x0000_i1425"> і <img width=«168» height=«28» src=«ref-1_1513686042-510.coolpic» v:shapes="_x0000_i1426">. Зворотне твердження потрібне з визначення 13.


Властивості 3о – 7о сформульовані для <img width=«84» height=«23» src=«ref-1_1513686552-304.coolpic» v:shapes="_x0000_i1427"><img width=«83» height=«25» src=«ref-1_1513686856-252.coolpic» v:shapes="_x0000_i1428">.

Властивість 3о: <img width=«108» height=«28» src=«ref-1_1513687108-460.coolpic» v:shapes="_x0000_i1429">.

Доказ: Ясно, що <img width=«69» height=«24» src=«ref-1_1513687568-380.coolpic» v:shapes="_x0000_i1430">, і тому що число елементів будь-якої підмножини не більше числа елементів самої множини, то дана властивість виконується.

Властивість 4о: <img width=«164» height=«24» src=«ref-1_1513687948-526.coolpic» v:shapes="_x0000_i1431">.

Доказ: потрібне з того, що незалежна підмножина в <img width=«55» height=«21» src=«ref-1_1513688474-143.coolpic» v:shapes="_x0000_i1432"> можна продовжити до максимальної незалежної підмножини в <img width=«16» height=«19» src=«ref-1_1513597563-92.coolpic» v:shapes="_x0000_i1433">;

Властивість 5о: <img width=«269» height=«25» src=«ref-1_1513688709-733.coolpic» v:shapes="_x0000_i1434">.

Доказ:

Нехай <img width=«167» height=«25» src=«ref-1_1513689442-542.coolpic» v:shapes="_x0000_i1435"> Тоді <img width=«196» height=«28» src=«ref-1_1513689984-635.coolpic» v:shapes="_x0000_i1436"> И потім <img width=«287» height=«28» src=«ref-1_1513690619-799.coolpic» v:shapes="_x0000_i1437">. Маємо <img width=«196» height=«28» src=«ref-1_1513691418-557.coolpic» v:shapes="_x0000_i1438"> <img width=«645» height=«24» src=«ref-1_1513691975-1328.coolpic» v:shapes="_x0000_i1439"><img width=«108» height=«24» src=«ref-1_1513693303-416.coolpic» v:shapes="_x0000_i1440">.

Властивість 6о: <img width=«216» height=«25» src=«ref-1_1513693719-736.coolpic» v:shapes="_x0000_i1441">.

Доказ:випливає із властивості 40;

Властивість 7о: <img width=«432» height=«25» src=«ref-1_1513694455-1193.coolpic» v:shapes="_x0000_i1442">.

Доказ: <img width=«432» height=«25» src=«ref-1_1513695648-1186.coolpic» v:shapes="_x0000_i1443">

<img width=«106» height=«25» src=«ref-1_1513696834-426.coolpic» v:shapes="_x0000_i1444"><img width=«430» height=«25» src=«ref-1_1513697260-1200.coolpic» v:shapes="_x0000_i1445">.
4. Зв'язок транзитивних відносин залежності з операторами замикання
Транзитивне відношення залежності також може бути описане за допомогою алгебраїчного оператора замикання деякого типу. Для початку сформулюємо визначення використовуваних понять.

Визначення 13.

Множина E підмножин множини A називається системою замикань, якщо <img width=«31» height=«19» src=«ref-1_1513698460-172.coolpic» v:shapes="_x0000_i1446"> E і система E замкнута щодо перетинань, тобто ∩D <img width=«13» height=«13» src=«ref-1_1513698632-84.coolpic» v:shapes="_x0000_i1447">E для кожної непустої підмножини D <img width=«19» height=«17» src=«ref-1_1513646834-91.coolpic» v:shapes="_x0000_i1448">E

Визначення 14.

Оператором замиканняна множині A називається відображення J множини B (A) у себе, що володіє наступними властивостями:



J. 1. Якщо <img width=«56» height=«21» src=«ref-1_1513698807-144.coolpic» v:shapes="_x0000_i1449">, то J(X)<img width=«16» height=«16» src=«ref-1_1513698951-89.coolpic» v:shapes="_x0000_i1450"> J(Y);

J. 2. X<img width=«16» height=«16» src=«ref-1_1513698951-89.coolpic» v:shapes="_x0000_i1451"> J(X);

J. 3. JJ(X) = J(X), для всіх X, Y <img width=«13» height=«13» src=«ref-1_1513698632-84.coolpic» v:shapes="_x0000_i1452">B (A).



Визначення 15.

Оператор замикання J на множині A називається алгебраїчним, якщо для будь-яких <img width=«55» height=«21» src=«ref-1_1513595188-148.coolpic» v:shapes="_x0000_i1453"> і <img width=«44» height=«20» src=«ref-1_1513594997-191.coolpic» v:shapes="_x0000_i1454"> <img width=«73» height=«24» src=«ref-1_1513699552-309.coolpic» v:shapes="_x0000_i1455"> тягне <img width=«72» height=«24» src=«ref-1_1513699861-307.coolpic» v:shapes="_x0000_i1456"> для деякої кінцевої підмножини <img width=«20» height=«19» src=«ref-1_1513700168-99.coolpic» v:shapes="_x0000_i1457"> множини <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1458">.

Визначення 16.

Система замикань називається алгебраїчної, якщо тільки відповідний оператор замикання є алгебраїчним

Слід зазначити теорему про взаємозв'язок між системами замикань і операторами замикань.

Теорема 5.

Кожна система замикань E на множині <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1459"> визначає оператор замикання J на <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1460"> за правилом J(X) = ∩{Y <img width=«13» height=«15» src=«ref-1_1513700559-84.coolpic» v:shapes="_x0000_i1461">E | Y<img width=«16» height=«16» src=«ref-1_1513700643-90.coolpic» v:shapes="_x0000_i1462"> X}. Обернено, кожний оператор замикання J на <img width=«17» height=«19» src=«ref-1_1513593296-96.coolpic» v:shapes="_x0000_i1463"> визначає систему замикань E <img width=«80» height=«24» src=«ref-1_1513700829-290.coolpic» v:shapes="_x0000_i1464"> J<img width=«72» height=«24» src=«ref-1_1513701119-316.coolpic» v:shapes="_x0000_i1465"> .

Наступна теорема показує зв'язок транзитивного відношення залежності й алгебраїчного оператора замикання.

Теорема 6.

Для будь-якого транзитивного відношення залежності <img width=«28» height=«28» src=«ref-1_1513594725-182.coolpic» v:shapes="_x0000_i1466"> Z<img width=«19» height=«28» src=«ref-1_1513594907-90.coolpic» v:shapes="_x0000_i1467"> відображення <img width=«67» height=«27» src=«ref-1_1513701707-177.coolpic» v:shapes="_x0000_i1468"> є алгебраїчним оператором замикання наА із властивістю заміщення.

Обернено, будь-який алгебраїчний оператор замикання на А із властивістю заміщення виходить таким способом з деякого транзитивного відношення залежності Z наА.

Доказ:

Будемо називати підмножину Т множини A замкнутим, якщо <img width=«53» height=«27» src=«ref-1_1513701884-159.coolpic» v:shapes="_x0000_i1469">.

Покажемо спочатку, що замкнуті підмножини утворять систему замикань. Якщо <img width=«68» height=«25» src=«ref-1_1513702043-241.coolpic» v:shapes="_x0000_i1470">, де <img width=«37» height=«25» src=«ref-1_1513702284-231.coolpic» v:shapes="_x0000_i1471">  — сімейство замкнутих множин, то нехай <img width=«24» height=«25» src=«ref-1_1513702515-113.coolpic» v:shapes="_x0000_i1472">  — така незалежна підмножина множини B, що <img width=«68» height=«25» src=«ref-1_1513702628-317.coolpic» v:shapes="_x0000_i1473"> залежно; оскільки <img width=«65» height=«25» src=«ref-1_1513702945-168.coolpic» v:shapes="_x0000_i1474"> для всіх <img width=«16» height=«20» src=«ref-1_1513703113-168.coolpic» v:shapes="_x0000_i1475">, маємо <img width=«104» height=«28» src=«ref-1_1513703281-309.coolpic» v:shapes="_x0000_i1476">, звідки <img width=«97» height=«25» src=«ref-1_1513703590-280.coolpic» v:shapes="_x0000_i1477">, тобто В замкнуто.

Нехай <img width=«61» height=«28» src=«ref-1_1513640646-247.coolpic» v:shapes="_x0000_i1478">, те по визначенню 3 <img width=«65» height=«24» src=«ref-1_1513704117-284.coolpic» v:shapes="_x0000_i1479"><img width=«47» height=«23» src=«ref-1_1513704401-224.coolpic» v:shapes="_x0000_i1480"> Z <img width=«39» height=«23» src=«ref-1_1513704625-263.coolpic» v:shapes="_x0000_i1481"> кінцеве, таке що<img width=«69» height=«28» src=«ref-1_1513704888-325.coolpic» v:shapes="_x0000_i1482"> залежно. У першому випадку <img width=«75» height=«31» src=«ref-1_1513705213-404.coolpic» v:shapes="_x0000_i1483">, а в другому <img width=«69» height=«31» src=«ref-1_1513705617-360.coolpic» v:shapes="_x0000_i1484">. І оскільки <img width=«33» height=«28» src=«ref-1_1513599784-140.coolpic» v:shapes="_x0000_i1485"> замкнуто в силу транзитивності, одержуємо алгебраїчний оператор замикання.

Цим доведено, що замкнуті підмножини утворять алгебраїчну систему замикань.

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

Обернено, нехай <img width=«72» height=«24» src=«ref-1_1513706117-261.coolpic» v:shapes="_x0000_i1486">  — алгебраїчний оператор замикання із властивістю заміщення.

Будемо вважати <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1487"> залежним, якщо <img width=«95» height=«25» src=«ref-1_1513706478-413.coolpic» v:shapes="_x0000_i1488"> для деякого <img width=«49» height=«24» src=«ref-1_1513706891-203.coolpic» v:shapes="_x0000_i1489">, і незалежним у противному випадку.

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

Тепер для будь-яких <img width=«55» height=«21» src=«ref-1_1513595188-148.coolpic» v:shapes="_x0000_i1490">, <img width=«45» height=«24» src=«ref-1_1513707242-201.coolpic» v:shapes="_x0000_i1491"> маємо <img width=«59» height=«25» src=«ref-1_1513707443-193.coolpic» v:shapes="_x0000_i1492"> тоді й тільки тоді, коли <img width=«61» height=«28» src=«ref-1_1513707636-266.coolpic» v:shapes="_x0000_i1493"> для деякої кінцевої підмножини <img width=«24» height=«23» src=«ref-1_1513707902-109.coolpic» v:shapes="_x0000_i1494"> множини <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1495">. Вибираючи <img width=«24» height=«23» src=«ref-1_1513707902-109.coolpic» v:shapes="_x0000_i1496"> мінімальним, можемо припускати, що <img width=«24» height=«23» src=«ref-1_1513707902-109.coolpic» v:shapes="_x0000_i1497"> незалежно. Звідси випливає, що <img width=«116» height=«33» src=«ref-1_1513708329-294.coolpic» v:shapes="_x0000_i1498"> й, отже, <img width=«80» height=«28» src=«ref-1_1513708623-296.coolpic» v:shapes="_x0000_i1499">.

Обернено, якщо <img width=«61» height=«28» src=«ref-1_1513640646-247.coolpic» v:shapes="_x0000_i1500">, те знову <img width=«67» height=«33» src=«ref-1_1513709166-211.coolpic» v:shapes="_x0000_i1501"> для деякої кінцевої незалежної підмножини <img width=«24» height=«23» src=«ref-1_1513707902-109.coolpic» v:shapes="_x0000_i1502"> множини <img width=«21» height=«19» src=«ref-1_1513597655-100.coolpic» v:shapes="_x0000_i1503">. Це означає, що <img width=«69» height=«28» src=«ref-1_1513704888-325.coolpic» v:shapes="_x0000_i1504"> залежно, тобто <img width=«139» height=«28» src=«ref-1_1513709911-570.coolpic» v:shapes="_x0000_i1505"> для якогось <img width=«96» height=«28» src=«ref-1_1513710481-376.coolpic» v:shapes="_x0000_i1506">.

У силу властивості заміщення одержуємо, що <img width=«61» height=«28» src=«ref-1_1513707636-266.coolpic» v:shapes="_x0000_i1507"> й <img width=«72» height=«24» src=«ref-1_1513711123-271.coolpic» v:shapes="_x0000_i1508">, тому <img width=«76» height=«28» src=«ref-1_1513711394-220.coolpic» v:shapes="_x0000_i1509">.

Зауваження.Існують алгебраїчні оператори замикання, що не володіють властивістю заміщення. Для приклада візьмемо нескінченну циклічну напівгрупу <img width=«151» height=«27» src=«ref-1_1513711614-494.coolpic» v:shapes="_x0000_i1510">.

Нехай <img width=«59» height=«23» src=«ref-1_1513712108-273.coolpic» v:shapes="_x0000_i1511"><img width=«51» height=«28» src=«ref-1_1513712381-151.coolpic» v:shapes="_x0000_i1512">і <img width=«41» height=«16» src=«ref-1_1513712532-115.coolpic» v:shapes="_x0000_i1513">. Тоді <img width=«93» height=«28» src=«ref-1_1513712647-431.coolpic» v:shapes="_x0000_i1514">, <img width=«85» height=«28» src=«ref-1_1513713078-284.coolpic» v:shapes="_x0000_i1515">, але <img width=«169» height=«33» src=«ref-1_1513713362-524.coolpic» v:shapes="_x0000_i1516">.
5. Матроїди
Поняття матроїда тісно пов'язане з поняттям відносини залежності, тому ця тема розглядається в даній кваліфікаційній роботі. Однак з іншої сторони воно є теоретичною основою для вивчення й аналізу «жадібних» алгоритмів.

Визначення 17.

    продолжение
--PAGE_BREAK--