Абстрактное отношение зависимости

дипломная работа

§1.Определения и примеры

Определение 1.

Множество Z подмножеств множества A назовем отношением зависимости на A, если выполняются следующие аксиомы:

Z1: Z ;

Z2: Z Z ;

Z3: Z ( Z - конечно).

Подмножество множества A называется зависимым, если оно принадлежит Z, и независимым в противном случае.

Легко убедиться в независимости аксиом Z1 - Z3..

Модель 1: . Полагаем Z = B (А) для любого множества .

Модель 2: . Пусть Z = при .

Модель 3:. Пусть Z = для бесконечного множества .

Определение 2.

Пространством зависимости назовем пару Z, где Z - отношение зависимости на A.

Определение 3.

Элемент называется зависимым от множества , если а X или существует такое независимое подмножество Y множества X, что зависимо, т.е. Z Z ).

Из определения 1 вытекает, что если элемент зависит от множества , то он зависит от некоторого конечного подмножества .

Определение 4.

Множество всех элементов, зависящих от X, называется оболочкой множества X и обозначается через .

Ясно, что и включение влечет включение их оболочек: .

Определение 5.

Если = A, то X называется порождающим множеством множества A.

Определение 6.

Независимое порождающее подмножество множества A называется базисом множества A.

Определение 7.

Множество зависит от , если любой элемент из зависит от , то есть .

Определение 8.

Отношение зависимости Z на A будем называть транзитивным отношением зависимости, если .

Определение 9.

Транзитивным пространством зависимости назовем пространство зависимости, в котором отношение зависимости обладает свойством транзитивности.

В качестве теоретико-множественного постулата будем использовать следующий принцип, эквивалентный известной аксиоме выбора.

Лемма Цорна.

Непустое упорядоченное множество, в котором каждое линейно упорядоченное подмножество обладает верхней гранью, имеет максимальный элемент.

Далее целесообразно рассмотреть некоторые примеры отношения зависимости:

Пример 1.

Понятие линейной зависимости в векторном пространстве V над полем . Система векторов векторного пространства V называется линейно зависимой, если существует конечная линейно зависимая ее подсистема, в противном случае - линейно независимой.

Понятие линейной зависимости в конечномерных векторных пространствах дается в курсе алгебры. Конечная система векторов V называется линейно зависимой, если существуют элементы поля одновременно не равные нулю и такие, что линейная комбинация. Множество линейных комбинаций множества векторов векторного пространства V с коэффициентами из поля P называется линейной оболочкой этих векторов и обозначается . При этом - является подпространством в пространстве V, порожденным . Получаем транзитивное отношение зависимости.

Пример 2.

Пусть поле является расширением основного поля Р, а минимальное подкольцо содержащее элементы и поле Р. Подкольцо состоит из всех элементов поля , которые выражаются через элементы и элементы поля Р при помощи сложения, вычитания и умножения: это будут всевозможные многочлены от с коэффициентами из поля Р. Тогда, если для всякого элемента существует единственная запись в виде многочлена от как неизвестных с коэффициентами из поля Р, то есть если различные многочлены от будут различными элементами подкольца , то система элементов , будет называться алгебраически независимой над полем Р, в противном случае алгебраически зависимой. Произвольное множество элементов поля Р называется зависимым, если оно содержит конечное зависимое подмножество. В первом случае кольцо изоморфно кольцу многочленов . Отношение алгебраической зависимости над полем Р является транзитивным отношением зависимости.

Пример 3.

Пусть на множестве A задано рефлексивное и симметричное бинарное отношение (называемое отношением сходства). Подмножество X множества A будем считать зависимым, если оно содержит два различных элемента, находящихся в отношении .

Оболочкой множества служит множество

В этом случае можно усилить аксиому отношения зависимости следующим образом:

Z Z.

Тогда оболочкой множества будет множество всех элементов, находящихся в отношении сходства хотя бы с одним элементом из множества .

Введенное отношение зависимости будет транзитивным тогда и только тогда, когда соответствующее бинарное отношение будет транзитивно, то есть является отношением эквивалентности на .

В случае, когда - отношение эквивалентности будет независимым тогда и только тогда, когда множество содержит не более одного элемента. Любое максимальное независимое подмножество будет содержать ровно по одному элементу из каждого класса эквивалентности .

Пример 4.

Рассмотрим четырехэлементное множество .

Назовем подмножество множества зависимым тогда и только тогда, когда или .

Z .

Рассмотрим подмножество множества , по введенному определению оно будет независимо. Рассмотрим оболочку множества и найдем оболочку оболочки нашего множества . Таким образом, мы получили , то есть рассмотренное нами отношение зависимости не является транзитивным.

Пример 5.

Рассмотрим произвольное множество и . Множество будем считать зависимым, если B (А) B (В), то есть , но . Таким образом, получили следующее транзитивное пространство зависимости: B (А) B (В. Оболочкой будет множество .

В частности можно рассмотреть 2 случая:

1. , то есть все множества независимы, тогда .

2. B (А), то есть все множества, кроме пустого, будут зависимыми, в этом случае .

Пример 6.

Рассмотрим произвольное множество и его непустое конечное подмножество . Введем на множестве А следующее отношение зависимости

Z B (А).

Таким образом, зависимыми будут все надмножества множества .

Если , то .

Если , то .

Если , то .

Получаем транзитивное пространство зависимости.

Пример 7.

Подпространство пространства зависимости Z. Рассмотрим , где действует то же отношение зависимости Z. Тогда получим индуцированное пространство зависимости Z B . В этом случае зависимыми будут только те подмножества множества , которые были зависимы в пространстве Z. И если пространство Z транзитивно, то транзитивным будет и подпространство .

Пример 8.

Пусть и Z = . Такое пространство зависимости Z не транзитивно, так как и . Пространство А имеет два базиса и , которые являются и единственными минимальными порождающими множествами в .

Этот пример показывает, что существуют не транзитивные пространства зависимости, в которых минимальные порождающие множества независимы, то есть являются базисами.

Пример 9.

Зададим на множестве N натуральных чисел следующее отношение зависимости:

Z.

Получаем бесконечную строго возрастающую цепочку оболочек в Z. При получаем

.

Таким образом, имеем .

Замечание.

Понятие пространства зависимости можно и удобно определять через базу зависимости. Именно, множество B всех минимальных зависимых множеств пространства зависимости Z назовем его базой. Ясно, что множества из B непусты, конечны и не содержатся друг в друге. Кроме того, любое независимое множество содержит некоторое множество базы B. Пространство Z имеет единственную базу и однозначно определяется ей. Поэтому пространства зависимости можно задавать базами.

Легко видеть, что верно следующее утверждение:

Непустое множество B подмножеств множества задает на отношение зависимости тогда и только тогда, когда множества из B непусты, конечны и не включены друг в друга.

В терминах базы B можно сформулировать условие транзитивности соответствующего пространства зависимости.

Делись добром ;)