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

  • Просмотров 5682
  • Скачиваний 76
  • Размер файла 765
    Кб

элемент М; в силу максимальности каждый элемент множества Y либо принадлежит М, либо зависит от М, откуда . Этим доказано, что М — базис в A. Так как , то М имеет вид , где удовлетворяет условиям .■ Определение 11. Пространство зависимости Z называется конечномерным, если любое его независимое множество конечно. Теорема 3. Пусть Z - транзитивное пространство зависимости. Тогда любые два базиса в этом пространстве равномощны.

Доказательство: Рассмотрим сначала случай конечномерного пространства . Пусть В, С — любые два базиса в А, их существование обеспечивается теоремой 2, и , , , где различные элементы обозначены различными буквами или снабжены различными индексами. Применим индукцию по max (r, s). Если r = 0 или s = 0, то или , и . Поэтому можно предполагать, что r ≥ 1, s ≥ 1, без ограничения общности будем считать, что r > s, так что на самом деле r > 1. Предположим,

что базисы будут равномощными для любого t < r По лемме о замене множество можно дополнить до базиса D элементами базиса С, скажем , t ≤ s < r. Теперь пересечение D c В состоит из n + 1 элемента, и D содержит, кроме того, еще t (< r) элементов, тогда как В содержит, кроме этого пересечения, еще r - 1 элементов, так что по предположению индукции , то есть . Поскольку r > 1, отсюда вытекает, что t ≥ 1, и поэтому пересечение D с С содержит не меньше чем

n+1 элементов. Используя еще раз предположение индукции, находим, что и, следовательно, r = s и базисы В и С равномощны. Далее, пусть В - конечный базис в . Тогда и любой другой базис С пространства будет конечным. Действительно, В выражается через конечное множество элементов в силу транзитивности будет порождающим и независимым множеством в , то есть . Наконец, если базисы В и С бесконечны. Каждый элемент из В зависит от некоторого

конечного подмножества базиса С, и наоборот. Мощность множества всех конечных подмножеств всякого бесконечного множества равна мощности самого множества. Поэтому мощности В и С совпадают.■ Теорема 4. Пусть Z - произвольное пространство зависимости, тогда следующие условия эквивалентны Z транзитивно; для любого конечного ; конечных и Z Z; для любого конечного . Доказательство: (i) (ii) Справедливо по теореме 3 и примеру 7. (ii) (iii)

Возьмем , так что - независимы и . Допустим, что утверждение Z неверно. Тогда Z. Рассмотрим . Имеем . Но Z, поэтому Z . По (ii) имеем. Но - противоречие. (iii) (ii) Докажем от противного. Пусть . Можно считать, что . Тогда по (iii) независимо. Получили противоречие с максимальностью (iii) (i) Нужно доказать равенство для произвольного . Возьмем и покажем, что Так как , то Пусть существует , тогда независимо и существует Z и Z . Расширяя в можно предположить,