Имеет множество положительных факторов его. Отношение эквивалентности и фактор-множество

Если отношение R обладает свойствами: рефлексивное симметричное транзитивное, т.е. является отношением эквивалентности (~ или ≡ или Е) на множестве M , то множество классов эквивалентности называется фактор множеством множества M относительно эквивалентности R и обозначается M/R

Здесь есть подмножество элементов множества M эквивалентных x , называемых классом эквивалентности .

Из определения фактор-множества следует, что оно является подмножеством булеана: .

Функция называется отождествлением и определяется следующим образом:

Теорема. Фактор-алгебра F n /~ изоморфна алгебре булевых функций B n

Доказательство .

Искомый изоморфизм ξ : F n / ~ → B n определяется по следующему правилу: классу эквивалентности ~(φ) сопоставляется функция f φ , имеющая таблицу истинности произвольной формулы из множества ~(φ) . Поскольку разным классам эквивалентности соответствуют различные таблицы истинности, отображение ξ инъективно, а так как для любой булевой функции f из В п найдется формула , представляющая функцию f, то отображение ξ сюръективно. Сохранение операций , 0, 1 при отображении ξ проверяется непосредственно. ЧТД.

По теореме о функциональной полноте каждой функции , не являющейся константой 0 , соответствует некоторая СДНФ ψ , принадлежащая классу ~(φ) = ξ -1 (f) формул, представляющих функцию f . Возникает задача нахождения в классе ~(φ) дизъюнктивной нормальной формы, имеющей наиболее простое строение.

Конец работы -

Эта тема принадлежит разделу:

Курс лекций по дисциплине дискретная математика

Московский государственный строительный университет.. институт экономики управления и информационных систем в строительстве.. иэуис..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Твитнуть

Все темы данного раздела:

Предмет дискретной математики
Предмет дискретная (финитная, конечная) математика – направление математики, изучающее свойства дискретных структур, в то время как классическая (непрерывная) математика изучает свойства объ

Изоморфизм
Наука, изучающая алгебраические операции называется алгеброй. Это понятие по мере изучения курса будет конкретизироваться и углубляться. Алгебру интересует только вопрос, КАК действуе

Упражнения
1. Докажите, что изоморфное отображение всегда изотонно, а обратное утверждение неверно. 2. Запишите на языке множеств свою группу. 3. Запишите на языке множеств предметы, которые

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

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

Мощность множества
Мощность для конечного множества равна числу его элементов. Например, мощность универсума В(A) множества A мощностью n

А1A2A3| + … + |А1A2A3| + … + |А1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…An|
Конечное множество А имеет мощность k, если оно равномощно отрезку 1.. k;:

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

Символический язык содержательных теорий множеств
В процессе изучения курса будем различать объектный язык теории множеств и метаязык, средствами которого изучается объектный язык. Под языком теории множеств будем понимать реляцион

Доказательство
Множество В бесконечно, значит,

Добавление и удаление элементов
Если А - множество, а х - элемент, причем, то элемент

Ограниченные множества. Границы множеств
Пусть на некотором множестве X задана числовая функция f(х). Верхней гранью (границей) функции f(х) называется такое число

Точная верхняя (нижняя) граница
Совокупность всех верхних границ Е обозначается через Еs, всех нижних границ - через Еi. В случа

Точная верхняя (нижняя) граница множества
Если элемент z принадлежит пересечению множества E и множеству всех его верхних границ Es (соответственно нижних г

Основные свойства верхних и нижних границ
Пусть X - частично упорядоченное множество. 1. Если, то

Множество с атрибутивной точки зрения
Агрегатная точка зрения, в отличие от атрибутивной, является логически несостоятельной в том плане, что она приводит к парадоксам типа Рассела и Кантора (см. ниже). В рамках атрибутивной т

Структура
Частично упорядоченное множество X называется структурой, если в нем любое двухэлементное множество

Покрытие и разбиение множеств
Разбиением множества А называется семейство Аi

Бинарные отношения
Последовательность длины п, члены которой суть а1, .... аn, будем обозначать через {а1, .... а

Свойства бинарных отношений
Бинарное отношение R на множестве Хобладает следующими свойствами: (а) рефлексивно, если хRх

Тернарные отношения
Декартовым произведением XY

N-арные отношения
По аналогии с декартовым произведением двух множеств X,Y можно построить декартово произведение X

Отображения
Отображения – это некоторые связи между элементами множеств. Простейшими примерами отношений являются отношения принадлежности х

Соответствие
ПодмножествоSдекартового произведения называетсяn-арным соответствиeмэлементов множествMi. Формально

Функция
В основе всех разделов дискретной математики лежит понятие функции. Пусть Х -

Представление функции в терминах отношений
Функцией называется бинарное отношение f, если из и

Инъекция, сюръекция, биекция
При использовании термина «отображение» различают отображение ХвY и отображение Х на Y

Обратная функция
Для произвольных, определим

Частично упорядоченные множества
Множество S называется частично упорядоченным (ЧУМ), если на нем задано рефлексивное, транзитивной и антисимметричное бинарное отношение частичного порядка

Минимизации представления множества
Используя эти законы, рассмотрим задачу минимизации представления множества М с помощью операций

Перестановки
Дано множество A. Пусть A – конечное множество, состоящее из n элементов A = {a1, a2, …, a

Перестановки с повторениями
Пусть в множестве A имеются одинаковые (повторяющиеся) элементы. Перестановкой с повторениями состава (n1, n2, … ,nk

Размещения
Кортежи длины k (1≤k≤n), состоящие из различных элементов n-элементного множества A (кортежи отличаются од

Размещения с повторениями
Пусть во множестве A имеются одинаковые (повторяющиеся) элементы. Размещениями с повторениями из n элементов по k назы

Упорядоченное размещение
Разместим п объектов по m ящикам так, чтобы каждый ящик содержал бы последовательность, а не множество, как прежде, помещенных в нем объектов. Два

Сочетания
Из m-элементного множества A построим упорядоченное множество длины n, элементы которого являются размещениями с одними и тем

Сочетания с повторениями
Полученные формулы справедливы только, когда в множестве A нет одинаковых элементов. Пусть имеются элементы n видов и из них составляется кортеж из

Метод производящий функций
Этот метод используется для перечисления комбинаторных чисел и установления комбинаторных тождеств. Исходным пунктом являются последовательность {ai} комбинатор

Алгебраическая система
Алгебраической системой A называется совокупность ‹M,O,R›, первая составляющая которой M есть непустое множество, вторая компонента O – множество

Замыкание и подалгебры
Подмножество называется замкнутым относительно операции φ, если

Алгебры с одной бинарной операцией
Пусть на множестве М задана одна бинарная операция. Рассмотрим порождаемые ею алгебры, но предварительно рассмотрим некоторые свойства бинарных операций. Бинарная о

Группоид
Алгебра вида <М, f2>называется группоидом. Если f2 - операция типа умножения (

Целые числа по модулю m
Дано кольцо целых чисел . Напомним. Алгебра <М,

Конгруэнции
Конгруэнцией на алгебре A = (Σ – сигнатура алгебры состоит только из функциональных символов) называется такое отношение эквивалентности

Элементы теории графов
Графы - математические объекты. Теория графов применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электротехника, машиностроение, архитектура, исследование о

Граф, вершина, ребро
Под неориентированным графом (или короче графом) будем понимать такую произвольную пару G = , что

Соответствие
Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, ко

Неориентированный граф
Если ребра не имеют ориентации, то граф называется неориентированным (неориентированный дубликат или неориен

Инцидентность, смешанный граф
Если ребро е имеет вид {и, v } или <и, v>, то будем говорить, что ребро е инцидентно вер

Обратное соответствие
Поскольку представляет собой множество таких вершин

Изоморфизм графов
Два графа G1 = и G2 = изоморфны (G

Путь, ориентированный маршрут
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в котор

Смежные дуги, смежные вершины, степень вершины
Дуги а = (хi, хj), хi ≠ хj, имеющие общие концевые вершины, н

Связность
Две вершины в графе называются связным, если существует соединяющая их простая цепь. Граф называется связным, если все его вершины связны. Теорема.

Граф со взвешенными дугами
Граф G = (N, A) называется взвешенным, если на множестве дуг A определена некоторая функция l: A → R, которую на

Матрица сильной связности
Матрица сильной связности: по диагонали ставим 1; заполняем строку X1 - если вершина достижима из X1 и X1 д

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

В любом нетривиальном дереве имеются по крайней мере две висячие вершины
Доказательство Рассмотрим дерево G(V, Е). Дерево - связный граф, следовательно,

Теорема
Центр свободного дерева состоит из одной вершины или из двух смежных вершин: Z(G) = 0&k(G) = 1 → С(G) = К1

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

Доказательство
1. Каждая дуга входит в какой-то узел. Из п. 2 определения 9.2.1 имеем: v

Упорядоченные деревья
Множества Т1,.. ., Тk в эквивалентном определении ордерева являются поддеревьями. Если относительный порядок поддеревьев Т1,.. .,

Бинарные деревья
Бинарное (или двоичное) дерево - это конечное множество узлов, которое либо пусто, либо состоит из корня и двух непересекающихся бинарных деревьев - левого и правого. Бинарное дерево не яв

Представление свободных деревьев
Для представления деревьев можно использовать те же приёмы, что и для представления графов общего вида - матрицы смежности и инциденций, списки смежности и другие. Но используя особенные свойства д

End for
Обоснование Код Прюфера действительно является представлением свободного дерева. Чтобы убедиться в этом, покажем, что если Т" - дерево

Представление бинарных деревьев
Всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Для потомков одного узла (братьев) упорядоченного ордерева определено отно

Основные логические функции
Обозначим через E2 = {0, 1} – множество, состоящее из двух чисел. Числа 0 и 1 являются основными в дискретной мате

Булева функция
Булевой функцией от n аргументов x1, x2, … ,xn, называется функция f из n-ой степени множества

Двухэлементная булева алгебра
Рассмотрим множество Во = {0,1} и определим на нем операции, согласно таблицам ист

Таблицы булевых функций
Булева функция от n переменных может быть задана таблицей, состоящей из двух столбцов и 2n строк. В первом столбце перечисляются все наборы из B

F5 – повторение по y
f6 – сумма по модулю 2 f7

Порядок выполнения операций
Если в сложном выражении скобок нет, то операции надо выполнять в следующем порядке: конъюнкция, дизъюнкция, импликация, эквивалентность, отрицание. Соглашения относительно расстановки скоПервая теорема Шеннона
Для решения задачи нахождения СДНФ и СКНФ, эквивалентных исходной формуле φ, предварительно рассмотрим разложения булевой функции f(x1, х2

Вторая теорема Шеннона
В силу принципа двойственности для булевых алгебр справедлива Теорема 6.4.3 (вторая теорема Шеннона). Любая булева функция f(x1, х2,...

Функциональная полнота
Теорема(о функциональной полноте). Для любой булевой функции f найдется формула φ, представляющая функцию f

Алгоритм нахождения сднф
Для нахождения СДНФ данную формулу нужно привести сначала к ДНФ, а затем преобразовать ее конъюнкты в конституенты единицы с помощью следующих действий: а) если в конъюнкт входит некоторая

Метод Квайна
Рассмотрим метод Квайна для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие триоперации: - операция полного склеивания -

Каноническое представление логических функций
Каноническими формами логических (формул) функций называются выражения, имеющие стандартную форму булевой формулы такой, которая однозначно представляет логическую функцию. В алгебр

Системы булевых функций
Пусть даны булевы функции f(g1, g2, …, gm) и g1(x1, x2, …, xn), g2(x1

Базис Жегалкина
Примерю Рассмотрим систему. Она является полной, так как любая функция из стандартного базиса выражается чере

Теорема Поста
Теорема Поста устанавливает необходимые и достаточные условия полноты системы булевых функций. (Post E.L. The two-valued interactive systems of mathematical logic. – Annals of Math. Stu

Доказательство
Необходимость. От противного. Пусть и

Алгебра Жегалкина
Сумма по модулю 2, конъюнкция и константы 0 и 1 образуют функционально полную систему, т.е. образуют алгебру - алгебру Жегалкина. A =

Логика высказываний
Математическая логика изучает базовые понятия синтак­сиса (формы) и семантики (содержания) естественного языка. Рассмотрим три крупных направления исследований в матема­тической логике - логику

Определение предиката
Пусть Х1, Х2, ..., Хп произвольные переменные. Эти переменные будем называть предметными. Пусть наборы переменных вы

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

Булева алгебра предикатов
Так как к предикатам можно применять логические операции, то для них справедливы основные законы булевой алгебры. Теорема. (Свойства логических операций для предикатов). Мн

F↔G=(F→G)(G→F), F→G=неFG
2. Использовать закон ненеF=F, законы де Моргана: не(F

Исчисление предикатов
Исчисление предикатов называют еще теорий первого порядка. В исчислении предикатов, так же как и в исчислении высказываний, на первом по важности месте стоит проблема разрешимост

Следование и эквиваленция
Высказывательная форма Q2 следу­ет из высказывательной формы Q1, если импликация Q1→Q2 об­ращается в истинное выс

Принятые обозначения
Символы «порядка не более». При сравнении скорости роста двух функций f(n) и g(n) (с неотрицательными значениями) очень удобны следующи

Метаобозначения
Обозна-чения Содержание Пример ИЛИ

Фактор множества

Множества.

Отношением частичного порядка на множестве x называется бинарное отношение, которое является антисимметричным, рефлексивным и транзитивным и обозначается в
виде пары:

Бинарное отношение называется толерантностью, если оно рефлексивно и симметрично.

Бинарное отношение называется квазипорядком, если оно иррефлексивно, антисимметрично и транзитивно (предпорядок).

Бинарное отношение называется строгим порядком, если оно рефлексивно и транзитивно.

Энарной алгебраической операцией на множестве М называется функция

– унарная операция;

– бинарная операция;

– триарная операция.

Бинарная алгебраическая операция –

– операция, ставящая в соответствие каждой упорядоченной паре из множества М некоторые элемент множества М.

Свойства:

1) Коммутативность:

2) Ассоциативность:

Нейтральный элемент

Множества М для бинарной алгебраической операции

Называется элемент:

• 
  Фактор множества – совокупность классов эквивалентности этого множества . Отношением частичного порядка на множестве x называется бинарное отношение...


• 
  Следующий вопрос ». Фактор множества . Фактор множества – совокупност. Мультипликативные и аддитивные формы.


• 
  Фактор множества – совокупност.
  Множество – совокупность определённых и различных между собой объектов мыслимых как единое целое.


• 
  Мультипликативная функция ― а... подробнее ». Фактор множества . Фактор множества – совокупность классов эквивалентности этого множества .


• 
  В реальной действительности процесс производства протекает сложнее, а его продукт результат использования множества факторов .


• 
  Качество управленческих решений зависит от множества факторов , наиболее значимыми из которых можно н.


• 
  Оптимизация решений по привлечению капитала – это процесс исследования множества факторов , воздействующих на ожидаемые результаты...

∼ {\displaystyle \sim } . Тогда множество всех классов эквивалентности называется фактормножеством и обозначается . Разбиение множества на классы эквивалентных элементов называется его факторизацией .

Отображение из X {\displaystyle X} в множество классов эквивалентности X / ∼ {\displaystyle X/\!\sim } называется факторотображением . Благодаря свойствам отношения эквивалентности, разбиение на множества единственно. Это означает, что классы, содержащие ∀ x , y ∈ X {\displaystyle \forall x,\;y\in X} , либо не пересекаются, либо совпадают полностью. Для любого элемента x ∈ X {\displaystyle x\in X} однозначно определён некоторый класс из X / ∼ {\displaystyle X/\!\sim } , иными словами существует сюръективное отображение из X {\displaystyle X} в X / ∼ {\displaystyle X/\!\sim } . Класс, содержащий x {\displaystyle x} , иногда обозначают [ x ] {\displaystyle [x]} .

Если множетво снабжено структурой, то часто отображение X → X / ∼ {\displaystyle X\to X/\!\sim } можно использовать чтобы снабдить фактормножество X / ∼ {\displaystyle X/\!\sim } той же структурой, например топологией. В этом случае множество X / ∼ {\displaystyle X/\!\sim } с индуцированной структурой называется факторпространством .

Энциклопедичный YouTube

1 / 4

✪ 3. Классы эквивалентности

✪ Теория множеств Лекция 3 Часть 1

✪ Теория множеств Лекция 3 Часть 2

✪ Теория множеств Лекция 3 Часть 3

Субтитры

Факторпространство по подпространству

Часто отношение эквивалентности вводят следующим образом. Пусть X {\displaystyle X} - линейное пространство , а L {\displaystyle L} - некоторое линейное подпространство. Тогда два элемента x , y ∈ X {\displaystyle x,\;y\in X} таких, что x − y ∈ L {\displaystyle x-y\in L} , называются эквивалентными . Это обозначается x ∼ L y {\displaystyle x\,{\overset {L}{\sim }}\,y} . Получаемое в результате факторизации пространство называют факторпространством по подпространству L {\displaystyle L} . Если X {\displaystyle X} разлагается в прямую сумму X = L ⊕ M {\displaystyle X=L\oplus M} , то существует изоморфизм из M {\displaystyle M} в X / ∼ L {\displaystyle X/\,{\overset {L}{\sim }}} . Если X {\displaystyle X} - конечномерное пространство , то факторпространство X / ∼ L {\displaystyle X/\,{\overset {L}{\sim }}} также является конечномерным и dim ⁡ X / ∼ L = dim ⁡ X − dim ⁡ L {\displaystyle \dim X/\,{\overset {L}{\sim }}=\dim X-\dim L} .

Примеры

. Можно рассмотреть фактормножество X / ∼ {\displaystyle X/\!\sim } . Функция f {\displaystyle f} задаёт естественное взаимноднозначное соответствие между X / ∼ {\displaystyle X/\!\sim } и Y {\displaystyle Y} .

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

Если для факторизации линейного пространства вводится некоторое его подпространство и считается, что если разность двух элементов исходного пространства принадлежит этому подпространству, то эти элементы эквивалентны, то фактормножество является линейным пространством и называется факторпространством.

Пусть G={p 0 =e, p 1 , …, p r } есть некоторая группа подстановок, определенная на множестве X = {1, 2, …, n} с единицей e=p 0 тождественной подстановкой. Определим отношение x~y, положив x~y равносильно, что существует p принадлежащее G(p(x)=y). Введенное отношение есть отношение эквивалентности, то есть оно удовлетворяет трем аксиомам:

1) x~x;
2) x~y→y~x;
3) x~y&y~z→x~z;

Пусть А – произвольное множество.
Определение : Бинарное отношение δ=A*A есть отношение эквивалентности (обозначается a ~ b), если они удовлетворяет следующим аксиомам:
∀ a, b, c ∈ A
1) a ~ a – рефлексивность;
2) a ~ b ⇒ b ~ a – коммутативность;
3) a ~ b & b ~ c → a ~ c — транзитивность

обозначается a ~ b, σ(a,b), (a,b) ∈ σ, a σ b

Определение : Разбиение множества А есть семейство попарно не пресекающихся подмножеств из А, в объединении (в сумме) дающих все А.
А= ∪А i , А i ∩А j = ∅, ∀i ≠ j.

Подмножества А i называются смежными классами разбиения.

Теорема : каждое отношение эквивалентности, определенное на А, соответствует некоторому разбиению множества А. Всякое разбиение множества А соответствует некоторому отношению эквивалентности на множестве А.

Коротко: между классами всех определенных на множестве А отношений эквивалентностей и классом всех разбиений множества А существует взаимнооднозначное соответствие.

Доказательство : пусть σ — есть отношение эквивалентности на множестве А. Пусть а ∈ А.

Построим множество: К a ={x ∈ A,: x~a } – всех элементов, эквивалентных а. Множество (обозначение) называется классом эквивалентности относительно эквивалентности σ. Заметим, что если b принадлежит K a , то b~a. Покажем, что a~b⇔K a =K b . В самом деле, пусть a~b. Возьмем произвольный элемент c принадлежит K a . Тогда c~a, a~b, c~b, c принадлежит K b и потому K b принадлежит K a . То, что K a принадлежит K b , показывается аналогично. Следовательно, K b =K a .
Пусть теперь K b =K a . Тогда a принадлежит K a = K b , a принадлежит K b , a~b. Что и требовалось показать.

Если 2 класса K a и K b имеют общий элемент с, то K a = K b . В самом деле, если с принадлежит K a и K b , то b~c, c~a, b~a => K a = K b .

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

Обратное: Пусть А = сумма по или A i – есть разбиение А. Введем на А отношение a~b, как a~b ⇔ a,b принадлежат одному и тому же классу разбиения. Это отношение удовлетворяет следующим аксиомам:

1) a ~ a (лежат в одном классе);
2) a ~ b → b ~ a;
3) a ~ b & b ~ c → a ~ c, т.е. введенное отношение ~ есть отношение эквивалентности.

Замечание :
1) разбиение множества А на одноэлементные подмножества и разбиение А, состоящие только из множества А, называется тривиальными (несобственным) разбиением.

2) Разбиение А на одноэлементные подмножества соответствует отношению эквивалентности которое есть равенство.

3) Разбиение А, состоящие из одного класса А, соответствует отношению эквивалентности, содержащему A x A.

4) a σ b → [a] σ = [b] σ — всякое отношение эквивалентности определенное на некотором множестве разбивает это множество на попарно не пересекающиеся классы называемые классами эквивалентности.

Определение : Совокупность классов эквивалентности множества А называется фактор-множеством A/σ множества А по эквивалентности σ.

Определение : Отображение p:A→A/σ, при котором p(A)=[a] σ , называется каноническим (естественным) отображением.

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

Пусть R – бинарное отношение на множестве X. Отношение R называется рефлексивным , если (x, x) Î R для всех x Î X; симметричным – если из (x, y) Î R следует (y, x) Î R; транзитивным числу 23 соответствует вариант 24 если (x, y) Î R и (y, z) Î R влекут (x, z) Î R.

Пример 1

Будем говорить, что x Î X имеет общее с элементом y Î X, если множество
x Ç y не пусто. Отношение иметь общее будет рефлексивным и симметричным, но не транзитивным.

Отношением эквивалентности на X называется рефлексивное, транзитивное и симметричное отношение. Легко видеть, что R Í X ´ X будет отношением эквивалентности тогда и только тогда, когда имеют место включения:

Id X Í R (рефлексивность),

R -1 Í R (симметричность),

R ° R Í R (транзитивность).

В действительности эти три условия равносильны следующим:

Id X Í R, R -1 = R, R ° R = R.

Разбиением множества X называется множество А попарно непересекающихся подмножеств a Í X таких, что UA = X. С каждым разбиением А можно связать отношение эквивалентности ~ на X, полагая x ~ y, если x и y являются элементами некоторого a Î A.

Каждому отношению эквивалентности ~ на X соответствует разбиение А, элементами которого являются подмножества, каждое из которых состоит из находящихся в отношении ~. Эти подмножества называются классами эквивалентности . Это разбиение А называется фактор-множеством множества X по отношению ~ и обозначается: X/~.

Определим отношение ~ на множестве w натуральных чисел, полагая x ~ y, если остатки от деления x и y на 3 равны между собой. Тогда w/~ состоит из трёх классов эквивалентности, соответствующих остаткам 0, 1 и 2.

Отношение порядка

Бинарное отношение R на множестве X называется антисимметричным , если из x R y и y R x следует: x = y. Бинарное отношение R на множестве X называется отношением порядка , если оно рефлексивно, антисимметрично и транзитивно. Легко видеть, что это равносильно выполнению следующих условий:

1) Id X Í R (рефлексивность),

2) R Ç R -1 (антисимметричность),

3) R ° R Í R (транзитивность).

Упорядоченная пара (X, R), состоящая из множества X и отношения порядка R на X, называется частично упорядоченным множеством .

Пример 1

Пусть X = {0, 1, 2, 3}, R = {(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (3, 3)}.

Поскольку R удовлетворяет условиям 1 – 3, то (X, R) – частично упорядоченное множество. Для элементов x = 2, y = 3, неверно ни x R y, ни y R x. Такие элементы называют несравнимыми . Обычно отношение порядка обозначают £. В приведенном примере 0 £ 1 и 2 £ 2, но неверно, что 2 £ 3.

Пример 2

Пусть < – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.

Элементы x, y Î X частично упорядоченного множества (X, £) называются сравнимыми , если x £ y либо y £ x.

Частично упорядоченное множество (X, £) называется линейно упорядоченным или цепью , если любые два его элемента сравнимы. Множество из примера 2 будет линейно упорядоченным, а из примера 1 – нет.

Подмножество A Í X частично упорядоченного множества (X, £) называется ограниченным сверху , если существует такой элемент x Î X, что a £ x для всех a Î A. Элемент x Î X называется наибольшим в X, если y £ x для всех y Î X. Элемент x Î X называется максимальным, если нет отличных от x элементов y Î X, для которых x £ y. В примере 1 элементы 2 и 3 будут максимальными, но не наибольшими. Аналогично определяются ограничение снизу подмножества, наименьший и минимальный элементы. В примере 1 элемент 0 будет и наименьшим и минимальным. В примере 2 этими свойствами также обладает 0, но в (w, £) нет ни наибольшего, ни максимального элемента.