АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Отношения порядка и эквивалентности

Читайте также:
  1. I Классификация кривых второго порядка
  2. I.Диагностика самоотношения.
  3. II ОБЩИЕ НАЧАЛА ПУБЛИЧНО-ПРАВОВОГО ПОРЯДКА
  4. II. САКРАЛЬНАЯ ГЕОМЕТРИЯ: МЕТАФОРА УНИВЕРСАЛЬНОГО ПОРЯДКА
  5. IV.1. Общие начала частной правозащиты и судебного порядка
  6. V2: ДЕ 53 - Способы решения обыкновенных дифференциальных уравнений первого порядка
  7. V2: ДЕ 54 - Дифференциальные уравнения, допускающие понижение порядка
  8. V2: ДЕ 6 - Линейные отображения. Определители второго порядка
  9. А. Блага высшего порядка в своем характере благ обусловлены наличием в нашем распоряжении соответственных комплементарных благ.
  10. Агентские отношения.
  11. Аграрные отношения и формы землевладения. Усиление эксплуатации общинников.
  12. Аграрные отношения феодальной Индии. Крестьянская община

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

Определение 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≤ in. И среди элементов, удовлетворяющих этим неравенствам, она должна быть наибольшим элементом.

При 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, упорядоченное отношением Í?


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)