|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Отношения порядка и эквивалентностиВ данном параграфе изучаются частично упорядоченные множества и решетки. Рассматривается также отношения эквивалентности и их связь с разбиениями множества. Доказывается, что частично упорядоченное множество отношений эквивалентности на множестве является решеткой. Определение 1. Пусть X – множество. Бинарное отношение R Í X ´ X называется отношением порядка на X, если оно рефлексивно, антисимметрично и транзитивно. Таким образом, R – отношение порядка, если (1) (a,a) ÎR для всех a Î X, (2) aRb & bRa Þ a = b, (3) для всех a, b, c Î X верна импликация aRb & bRc Þ aRc, Пара (X, R), состоящая из множества X и отношения порядка R на X называется частично упорядоченным множеством. Пусть (X, R) – частично упорядоченное множество. Всякое подмножество A Í X будет частично упорядоченным множеством с отношением порядка R Ç(A ´ A). Отношение порядка обычно обозначается символом £. Элемент x частично упорядоченного множества (X,£) называется наибольшим (соответственно наименьшим), если для всякого y Î X верно y £ x (соответственно x £ y). Определение 2. Пусть (X,£) – частично упорядоченное множество. Нижней гранью множества его элементов называется наибольший элемент подмножества . Нижняя грань обозначается через . Двойственно, как наименьший элемент множества , определяется верхняя грань . Заметим, что нижняя грань должна принадлежать множеству , и, значит, удовлетворять неравенствам для всех 1≤ i ≤ n. И среди элементов, удовлетворяющих этим неравенствам, она должна быть наибольшим элементом. При n =2 нижняя грань множества обозначается , а верхняя . Пример 1. Пусть (N+, |) – множество положительных натуральных чисел {1, 2, 3, …}, с отношением делимости: m | n Û n делится на m Û ($ k Î N+) mk = n. Тогда нижняя грань m Ù n равна наибольшему общему делителю, а m Ú n – наименьшему общему кратному. Определение 3. Частично упорядоченное множество (X,£) называется нижней (соответственно верхней) полурешеткой, если для любых множество имеет нижнюю (соответственно верхнюю) грань в X. Если (X,£) является нижней и верхней полурешеткой, то оно называется решеткой. Пример 2. Пусть X – множество. Частично упорядоченное множество (P(X),Í) подмножеств множества X с отношением включения будет решеткой. Пример 3. Частично упорядоченное множество положительных натуральных чисел (N+, |) будет решеткой. Лемма 1. Если конечное частично упорядоченное множество (X,£) является нижней полурешеткой и имеет наибольший элемент, то оно будет решеткой. Доказательство. Пусть . В этом случае множество S= непусто и конечно. Поскольку X – нижняя полурешетка, то существует . Положим . Для всех i=1, …, n имеет место z³ ai. И z – наименьший среди обладающих этим свойством. Стало быть, z = . Определение 4. Пусть X – множество. Бинарное отношение R Í X´X называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Таким образом, R – отношение эквивалентности на X, если (1) (a,a)ÎR для всех a Î X, (2) aRb Þ bRa (3) для всех a, b, c Î X верна импликация aRb & bRc ÞaRc, Определение 5. Разбиением множества X называется множество { Xi: iÎI } попарно непересекающихся подмножеств Xi Í X таких, что . С каждым разбиением { Xi: iÎI } можно связать отношение эквивалентности ~ на X, полагая x ~ y, если x и y являются элементами некоторого Xi. Каждому отношению эквивалентности ~ на X соответствует разбиение { Xi: i Î I }, элементами которого являются подмножества, состоящие из эквивалентных элементов. Эти подмножества называются классами эквивалентности. Множество классов эквивалентности {Xi: iÎI} называется фактор-множеством множества X по отношению эквивалентности ~ и обозначается: X/~. Теорема 1. Пусть X – конечное множество. Множество отношений эквивалентности на X с отношением включения Í является решеткой. Доказательство. Множество отношений эквивалентности является нижней полурешеткой, ибо точной нижней гранью отношений эквивалентностей будет их пересечение. Оно будет иметь наибольший элемент X´X. Стало быть, оно будет решеткой, по лемме 1. Поскольку разбиения множества X взаимно однозначно соответствуют отношениям эквивалентности на X, то множество разбиений легко превратить в частично упорядоченное множество. Отношение порядка между разбиениями определяется как имеющее место тогда и только тогда, когда разбиение P1 мельче чем P2, т.е. когда верна импликация . В этом случае будет верно включение , и, стало быть, отношение эквивалентности, соответствующее разбиению P1, будет содержаться в отношении эквивалентности, соответствующем разбиению P2 . Мы установили биекцию между разбиениями и отношениями эквивалентности на множестве. Эта биекция сохраняет порядок. Получаем Следствие 1. Множество разбиений множества является решеткой. Упражнение 1. Пусть (X, R) – конечное частично упорядоченное множество. Будет ли решеткой множество отношений порядка rÍR, упорядоченное отношением Í? Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.) |