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

Приветствую Вас, уважаемые Читатели! Пару недель назад я уже писал о таком понятии как “отношение эквивалентности”. Ознакомьтесь с этим материалом, потому что это – ключевой момент к теоретико-множественному пониманию определения “фактормножество”.

Формул в этом материале не будет, так что смело листайте дальше. Материал на понимание.

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

Источник: https://youdn.ru/files/uploades/5cc0d167eb14f.jpg

Итак, для начала определим на множестве людей “отношение эквивалентности” в виде согражданства. Мы называем его эквивалентностью потому, что оно удовлетворяет трем свойствам:

1. Симметричность. Если первый человек согражданин второго, то и второй – согражданин первого.

2. Рефлексивность. Любой человек является согражданином для самого себя

3. Транзитивность. Если первый и второй, второй и третий – сограждане, то первый и третий – тоже сограждане.

Вот еще одно разбиение по эквивалентности : касты древней Индии. Источник: https://avatars.mds.yandex.net/get-zen_doc/1712263/pub_5e1833411febd400ae3b5691_5e1839b511691d00ae970445/scale_1200

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

Давайте будем считать, что каждый человек может иметь только одно гражданство.

Классы эквивалентности – названия стран

Множество самих классов эквивалентности называется фактормножеством по отношению эквивалентности для данного множества и обозначается X/~.

Отображение X –> X/~ называется каноническим отображением и является сюръекцией (отображением “на”). Иными словами у каждого элемента фактормножества X/~ есть хотя бы один прообраз в множестве X.

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

Применения и примеры[править | править код]

Если задано сюръективное отображение , тогда на множестве задаётся отношение . Можно рассмотреть фактормножество X/!sim . Функция задаёт естественное взаимно-однозначное соответствие между X/!sim и .

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

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

Проективную плоскость $mathbb{R} P^{2}$ можно определить как факторпространство двумерной сферы, задав отношение эквивалентности .

Бутылку Клейна можно представить как факторпространство цилиндра $S^{1}times [0,;1]$ по отношению эквивалентности ( — угловая координата на окружности).

Свойства[править | править код]

Факторотображения q : X → Y описывается среди сюръективных отображений следующим свойством: если Z является каким-либо топологическим пространством и f : Y → Z является какой-либо функцией, то f является непрерывным тогда и только тогда, когда f ∘ q непрерывна.

Факторпространство X/~ вместе с факторотображением q : X → X/~ описывается следующим универсальным свойством: если g : X → Z является непрерывным отображением, таким что если из a ~ b следует g(a) = g(b) для всех a и b из X, то существует единственное отображение f : X/~ → Z, такое что g = f ∘ q. Мы говорим, что g спускается до факторотображения.

Непрерывные отображения, определённые на X/~ поэтому являются в точности такими отображениями, которые возникают из непрерывных отображений, определённых на X, которые удовлетворяют отношению эквивалентности (в смысле, что они переводят эквивалентные элементы в один и тот же образ). Этот критерий обширно используется при изучении факторпространств.

Если дана непрерывная сюръекция q : X → Y, полезно иметь критерий, по которому можно определить, является ли q факторотображением. Два достаточных условия — q является открытым^[en] или закрытым отображением^[en]. Заметим, что эти условия являются лишь достаточными, но не необходимыми. Легко построить примеры факторотображений, которые не являются ни открытыми, ни закрытыми. Для топологических групп факторотображение является открытым.

Совместимость с другими топологическими понятиями[править | править код]

Отделимость
- В общем случае факторпространства плохо себя ведут относительно аксиом отделимости. Свойства отделимости множества X не обязательно наследуются при X/~ и X/~ могут иметь свойства отделимости, не существующие в X.
- X/~ является пространством T₁^[en] тогда и только тогда, когда любой класс эквивалентности ~ замкнут в X.
- Если факторотображение открыто^[en], то X/~ является хаусдорфовым пространством тогда и только тогда, когда ~ является замкнутым подмножеством произведения пространств X×X.
Связность
- Если пространство связно или линейно связно, то таковыми являются все его факторпространства.
- Факторпространство односвязного или стягиваемого пространства не обязательно будет обладать этими свойствами.
Компактность
- Если пространство компактно, таковыми будут и все его факторпространства.
- Факторпространство локально компактного пространства не обязательно локально компактно.
Размерность пространства
- Топологическая размерность факторпространства может быть больше (а может быть и меньше) размерности исходного пространства; заполняющие пространство кривые дают такие примеры.

Источник

Отношения эквивалентности на множестве

Разбиение множества

Пусть — произвольное множество. Семейство $(B_i)_{iin I}$ непустых и попарно не пересекающихся множеств называют разбиением множества , если объединение множеств семейства $(B_i)_{iin I}$ равно , то есть

$bigcuplimits_{iin I}B_i=A,.$

Сами множества B_i называют элементами (или членами) разбиения $(B_i)_{iin I}$ .

Например, множества $left[0;tfrac{1}{3}right)!,, left[tfrac{1}{3};tfrac{2}{3}right)$ и $left[tfrac{2}{3};1right]$ образуют разбиение отрезка [0;1] . Тривиальными разбиениями являются, по определению, разбиение {A} , состоящее только из самого , и разбиение, состоящее из всех одноэлементных подмножеств множества .

Пусть rho — эквивалентность на множестве и xin A . Множество всех элементов , эквивалентных , т.е. множество {ycolon, y,rho,x} , называют классом эквивалентности по отношению rho и обозначают $[x]_{rho}$ . Отметим, что в силу рефлексивности для любого элемента xin A класс эквивалентности не пуст, так как $xin[x]_{rho}$ .

Теорема 1.4. Для любого отношения эквивалентности на множестве множество классов эквивалентности образует разбиение множества . Обратно, любое разбиение множества задает на нем отношение эквивалентности, для которого классы эквивалентности совпадают с элементами разбиения.

Покажем, что отношение эквивалентности rho на множестве определяет некоторое разбиение этого множества. Убедимся вначале, что любые два класса эквивалентности по отношению rho либо не пересекаются, либо совпадают.

Пусть два класса эквивалентности $[x]_{rho}$ и $[y]_{rho}$ имеют общий элемент $zin[x]_{rho}cap[y]_{rho}$ . Тогда z,rho,x и z,rho,y . В силу симметричности отношения rho имеем x,rho,z , и тогда x,rho,z и z,rho,y . В силу транзитивности отношения rho получим x,rho,y . Пусть $hin[x]_{rho}$ , тогда h,rho,x . Так как x,rho,y , то h,rho,y и, следовательно, $hin[y]_{rho}$ .

Обратно, если $hin[y]_{rho}$ , то в силу симметричности rho получим h,rho,y,~ y,rho,x и в силу транзитивности — h,rho,x , то есть $hin[x]_{rho}$ . Таким образом, $[x]_{rho}=[y]_{rho}$ .

Итак, любые два не совпадающих класса эквивалентности не пересекаются. Так как для любого xin A справедливо $xin[x]_{rho}$ (поскольку x,rho,x ), т.е. каждый элемент множества принадлежит некоторому классу эквивалентности по отношению rho , то множество всех классов эквивалентности по отношению rho образует разбиение исходного множества . Таким образом, любое отношение эквивалентности однозначно определяет некоторое разбиение.

Теперь пусть $(B_i)_{iin I}$ — некоторое разбиение множества . Рассмотрим отношение rho , такое, что x,rho,y имеет место тогда и только тогда, когда и принадлежат одному и тому же элементу B_i данного разбиения:

x,rho,y~ Leftrightarrow~ (exists iin I)(xin B_i)~ land~ (yin B_i).

Очевидно, что введенное отношение рефлексивно и симметрично. Если для любых x,y и имеет место x,rho,y и y,rho,z , то x,y и в силу определения отношения rho принадлежат одному и тому же элементу B_i разбиения. Следовательно, x,rho,z и отношение rho транзитивно. Таким образом, rho — эквивалентность на .

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

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

Множество всех классов эквивалентности по данному отношению эквивалентности rho на множестве называют фактор-множеством множества по отношению rho и обозначают A/rho .

Пример 1.14. а. На множестве целых чисел mathbb{Z} определим отношение равенства по модулю , где kin mathbb{N} . Положим $x=_{(operatorname{mod}k)}y$ , если и только если (x-y) делится на .

Легко проверяется, что это отношение эквивалентности. Действительно, рефлексивность следует из того, что для любо min mathbb{Z}m-m=0 и делится на ; симметричность — из того, что если (m-n) делится на , то и (n-m) делится на . Для доказательства транзитивности заметим, что если (m-n) делится на и (n-p) делится на , то и их сумма (m-n)+(n-p)=m-p делится на . Другими словами, для любых целых m,n,p из $m=_{(operatorname{mod}k)}n$ и $n=_{(operatorname{mod}k)}p$ следует $m=_{(operatorname{mod}k)}p$ , что доказывает транзитивность отношения $=_{(operatorname{mod}k)}$ .

Равенство чисел и по модулю означает, что при делении на эти числа дают одинаковые остатки. Действительно, для каждого xinmathbb{Z} имеем x=mcdot k+r , где — остаток от деления на . Следовательно, x-r=mcdot k , то есть $x=_{(operatorname{mod}k)}r$ . Таким образом, каждое число попадает в тот же класс эквивалентности по отношению $=_{(operatorname{mod}k)}$ , что и остаток от деления его на . Поскольку всего различных остатков может быть ровно kcolon, 0,1,ldots,k-1 , получаем ровно попарно различных классов эквивалентности по данному отношению:

$[0]=_{(operatorname{mod}k)},quad [1]=_{(operatorname{mod}k)},quad ldots,quad [k-1]=_{(operatorname{mod}k)},$

где класс $[r]=_{(operatorname{mod}k)}$ состоит из всех целых чисел, дающих при делении на остаток .

Отметим, что мы установили взаимно однозначное соответствие между фактор-множеством $mathbb{Z}/=_{(operatorname{mod}k)}$ и множеством $mathbb{Z}_k$ , состоящим из чисел 0,1,ldots,k-1 .

Второе множество дает нам как бы wнаглядный образ” построенного фактор-множества. Нельзя считать, что фактор-множество $mathbb{Z}/=_{(operatorname{mod}k)}$ равно множеству {0,1,ldots,k-1} . Нет, указанное фактор-множество состоит из элементов, каждый из которых есть не число, а множество всех целых чисел, при делении на дающих фиксированный остаток. Но каждому такому классу эквивалентности однозначно сопоставляется целое число от 0 до k-1 , и, наоборот, каждому целому числу от 0 до k-1 соответствует единственный класс эквивалентности по отношению $=_{(operatorname{mod}k)}$ . Заметим, что в математике часто используется прием сопоставления фактор-множеству такого находящегося с ним во взаимно однозначном соответствии множества, которое легко представить и описать.

б. На множестве mathbb{R} действительных чисел зададим отношение $a=_{(operatorname{mod}1)}b$ , полагая, что числа и равны по модулю 1 тогда и только тогда, когда число a-b является целым. Из определения следует, что каждое число по модулю 1 равно своей дробной части.

Примечание. Под дробной частью <a> числа понимается число из полуинтервала [0;1) , такое, что a=n+<a> для некоторого целого . Поэтому дробной частью отрицательного числа (-a) , где a>0 , будет число (1-<a>) . Так, Дробной частью (-1,!23) будет не 0,!23 , а 0,!77=1-0,!23 .

Так как отношение $=_{(operatorname{mod}1)}$ определено через равенство, то легко понять, что все свойства отношения эквивалентности для него выполняются. Каждый класс эквивалентности будет содержать числа с равными дробными частями. Это значит, что каждый класс эквивалентности по данному отношению однозначно определяет некоторое число из полуинтервала [0;1) и, наоборот, каждому числу gammain[0;1) однозначно сопоставляется класс эквивалентности, состоящий из всех действительных чисел, дробная часть которых равна gamma . Таким образом, фактор-множество $mathbb{R}/=_{(operatorname{mod}1)}$ и полуинтервал [0;1) на числовой прямой находятся во взаимно однозначном соответствии. Этот полуинтервал можно рассматривать как представление определенного выше фактор-множества.

Связь между понятиями эквивалентности и отображения

Установим теперь связь между понятиями эквивалентности и отображения. Заметим, что для любого отношения эквивалентности rho на множестве можно определить отображение $f_{rho}colon Ato A/rho$ , положив $f_{rho}(x)=[x]_{rho}$ , т.е. сопоставив каждому xin A содержащий его класс эквивалентности. Это отображение сюръективно, так как каждый элемент множества принадлежит некоторому классу эквивалентности, т.е. для каждого $[x]_{rho}in A/rho$ справедливо $[x]_{rho}=f_{rho}(x)$ .

Отображение $f_{rho}$ определенное таким образом, называют канонической сюръекцией множества .

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

Теорема 1.5. Пусть fcolon Ato B — произвольное отображение. Отношение rho_f на множестве , для которого x,rho_f,y , если и только если f(x)=f(y) , является отношением эквивалентности, причем существует биекция фактор-множества A/rho_f на множество f(A) .

Доказательство. Рефлексивность, симметричность и транзитивность отношения rho_f следуют непосредственно из его определения, т.е. rho_f — эквивалентность.

Зададим отображение varphi фактор-множества A/rho_f в множество f(A) следующим образом: $varphi([x]_{rho_f})=f(x)$ . Из способа задания отношения rho следует, что отображение определено корректно, т.е. каждому классу эквивалентности поставлен в соответствие единственный элемент yin f(A) .

Докажем, что varphi — биекция, для чего убедимся в том, что это инъекция и сюръекция одновременно. Пусть классы эквивалентности $[x]_{rho_f}$ и $[y]_{rho_f}$ не совпадают. В силу теоремы 1.4 это означает, что они не пересекаются, т.е. не эквивалентно . Из определения отношения rho_f следует, что f(x)ne f(y) . Таким образом, varphi — инъекция. Если элемент uin f(A) , то найдется такой элемент xin A , что $u=f(x)=varphi([x]_{rho_f})$ , то есть varphi — сюръекция фактор-множества $A/rho_{f}$ на множество f(A) . Итак, varphi — биекция.

Следовательно, в силу доказанных теорем 1.4 и 1.5 существует связь между тремя понятиями — отображением множества, отношением эквивалентности на множестве и разбиением множества. Но неверно, что существует взаимно однозначное соответствие между отображениями и отношениями эквивалентности (заметим, что теорема 1.5 этого и не утверждает). Два разных отображения могут определять одно и то же разбиение отображаемого множества, тем самым задавая на нем одно и то же отношение эквивалентности. Так, например, любое биективное отображение fcolon Ato B задает на одно и то же разбиение — тривиальное разбиение на одноэлементные множества.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Кнопка "Поделиться"

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

Источник

2.1. Отношения
(См. также [4], §§1.2, 1.5; [5], §1.5).
n–местным
отношением
или n–местным
предикатом
P
на множествах
A₁,
A₂,
…, A_n
называется любое подмножество прямого
произведения A₁A₂…,A_n.
При этом, если (a₁,
a₂,
…, a_n)P,
то говорят что a₁,
a₂,
…, a_n
находятся
в отношении
Р.
Отношение РAⁿ
называется n–местным
отношением
(или n–местным
предикатом)
на множестве
А.

При n=1
отношение называется унарным
или свойством.
При n=2
отношение называется бинарным
или соответствием.
При этом если РAB,
то говорят о соответствии между
множествами A
и B,
причем, если (a,
b)Р,
то говорят, что элементу
a
ставится
в соответствие элемент
b.
В этом случае также пишут aРb.

Пример
2.1. Пусть А=1,
2, 3, 4, 5.
Определим бинарное отношение P
на А:
Р=(a,
b)|
a
меньше b.
Тогда Р=(1,
2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5),
(4, 5).
Обратно, задав множество Р
перечислением, мы задаём отношение
«быть меньше» на множестве А.

Пример
2.2. Пусть А=1,
2, 3, 4, 5,
B={a,
b}.
Определим бинарное отношение P
на множествах А
и B:
Р=(1,
a),
(2, b),
(3, a),
(4, b),
(5, a).
При этом бинарном отношении каждому
нечётному числу из А
ставится в соответствие буква a,
а чётному числу 
буква b.

Бинарные отношения
на А
и B
можно изобразить графически.

Первый способ
графического изображения назовём
декартовым.
Он заключается в том, что на двух взаимно
перпендикулярных осях отмечаются
элементы А
и B:
на горизонтальной 
оси Ох,

элементы А,
на вертикальной 
оси Оy,

элементы B.
Отметив точки с координатами (a,
b)
такими, что (a,
b)Р,
получим графическое декартово изображение
отношения Р.

Второй способ
основан на диаграммах Эйлера-Венна, и
заключается в том, что если (a,
b)Р,
то из a
к b
проводится стрелка. При этом условимся,
что если одновременно (a,
b)Р
и (b,
a)Р,
то две стрелки из a
к b
и из b
к a
изображать в виде одной двойной (то есть
стрелка идёт в обе стороны) (см. рис. 8
ниже)

На рисунках 6 и 7
приведены графические изображения
отношений из примеров 2.1 и 2.2.

Тождественным
отношением
на множестве А
называется отношение id_A=(х,
х)
хА.
Универсальным
отношением
называется отношение U_A=A².

Областью
определения
бинарного отношения Р
называется множество _Р=х(х,
y)Р
для некоторого у.
Областью
значений
бинарного отношения Р
называется множество _Р=у(х,
y)Р
для некоторого х.

Обратным
отношением к
бинарному отношению
Р называется
множество
=(у,
х)(х,
y)Р.

Образом
множества Х
относительно предиката Р
называется множество Р(Х)=у(х,
y)Р
для некоторого хХ.
Прообразом
множества Y=Р(Х)
относительно предиката Р
называется множество
(Y)=х(х,
y)Р
для некоторого уР(Х).

Пример
2.3. Пусть Р

бинарное отношение примера 2.1. Тогда
_Р=1,
2, 3, 4=А{5},
_Р=2,
3, 4, 5=А{1},
=(2,
1), (3, 1), (4, 1), (5, 1), (3, 2), (4, 2), (5, 2), (4, 3), (5, 3),
(5, 4).
Пусть Х=3,
4, 5.
Тогда Р(Х)=4,
5.
Прообразом множества 2,
3
является
(2,
3)=1,
2.

Произведением
бинарных
отношений PAB
и QBC
(или композицией)
называется множество PQ={(x,
z)|
xA,
zC,
и существует такой элемент уB
что (x,
y)P
и (y,
z)Q}.
Произведение PQ
также обозначается через PQ.

Пример
2.4. Пусть
А=1,
2, 3, 4, 5,
B={a,
b,
с},
С=,
,
,
,
Р=(1,
a),
(2, b),
(3, a),
(4, b),
(5, a),
Q
=(a,
),
(b,
).
Тогда
PQ
=(1,
),
(2, ),
(3, ),
(4, ),
(5, ).

Для любых бинарных
отношений
PAB,
QBC,
RCD
выполняются
следующие свойства:

1) PQAC;

2)
=P;

3) (PQ)=QP;

4) (PQ)R=P(QR)
(ассоциативность
произведения);

5) id_AP
=P;

6) Qid_BQ
=Q;

7)
PP=id_A.

Свойство 4) обобщается
на произведение любого числа предикатов.
Именно, если Р₁А₁А₂,
Р₂А₂А₃,
…, Р_nА_nА_n₊₁

предикаты, то в произведении вида
(…((Р₁Р₂)
Р₃)…)Р_n
скобки можно проставлять произвольным
образом, это произведение не зависит
от расстановки скобок. В связи с этим в
произведениях вида (PQ)R
и (…((Р₁Р₂)Р₃)…)Р_n
скобки принято опускать: (PQ)R=PQR,
(…((Р₁Р₂)Р₃)…)Р_n=Р₁Р₂Р₃…Р_n.

Пусть даны два
множества А=a₁,
a₂,
…, a_n,
B=b₁,
b₂,
…, b_m
и бинарное отношение PAB.
Свяжем с Р
матрицу [Р]=(p_ij)_m__n,
элементы которой определены по следующему
правилу:

(p_ij)_m__n=

Эта матрица
называется матрицей
бинарного отношения
Р.
Она однозначно определяет бинарное
отношение.

Пример
2.5. Матрицы бинарных отношений Р
и Q
из примера 2.4 следующие:

[Р]=,
[Q]=.

Матрица бинарного
отношения обладает следующими свойствами:

1. Если
Р,
QAB,
[Р]=(p_ij)_m__n,
[Q]=(q_ij)_m__n,
то
[РQ]=[Р][Q]=(p_ijq_ij)_m__n
и
[РQ]=[Р]+[Q],
где сложение производится по правилам
0+0=0, 1+0=0+1=1+1=1, а умножение 
по обычным правилам 00=10=01=0,
11=1
(Здесь и далее XY
будет означать матрицу, полученную
умножением соответствующих элементов
матриц X
и Y).

2. Если
PAB,
QBC,
то
[РQ]=[Р][Q].
Здесь умножение матриц производится
по обычным правилам, а произведение и
сумма элементов матриц 
по правилам, определённым в пункте 1.

3.
=[Р]^Т.

4. Если
PQ,
[Р]=(p_ij)_m__n,
[Q]=(q_ij)_m__n,
то
[Р][Q]
(то есть p_ijq_ij
для всех i=1,
…, m
и j=1,
…, n).

5. [id_А]=Е

единичная
матрица.

2.2. Свойства
отношений. Отношение эквиваленции.
Фактор-множество
(См. также [4], §§1.5,
1.6; [5], §1.7).
Пусть Р

бинарное отношение на А:
РА².
Отношение называется рефлексивным,
если (х,
х)Р
для всех хА.
Это означает, что id_АР,
а диагональные
элементы матрицы такого отношения равны
1: [Р]=.

Отношение называется
симметричным,
если для любых х,
yА
из (х,
y)Р
следует (y,
х)Р.
Это означает, что P=Р,
то есть [Р]^Т=Р
(матрица
отношения является симметричной).

Отношение называется
антисимметричным,
если из (х,
y)Р
и (y,
х)Р
следует х=y.
Это означает, что РPid_А,
то есть в матрице [РP]=[Р][P]^T
все элементы,
стоящие вне
главной диагонали являются нулевыми.

Отношение называется
транзитивным,
если из (х,
y)Р
и (y,
z)Р
следует (х,
z)Р.
Это означает, что РРР,
то есть [РР]=[Р][Р][Р].

Пример
2.6. Отношение Р
из примера 2.1 не является ни рефлексивным,
ни симметричным, ни антисимметричным,
но является транзитивным. Докажем
последнее. Так как Р=(1,
2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5),
(4, 5),
то из (1, 2)Р
и (2, 3)Р
следует (1, 3)Р,
из (1, 3)Р
и (3, 4)Р
следует (1, 4)Р,
из (1, 4)Р
и (4, 5)Р
следует (1, 5)Р,
из (2, 3)Р
и (3, 4)Р
следует (2, 4)Р,
из (2, 4)Р
и (4, 5)Р
следует (2, 5)Р,
из (3, 4)Р
и (4, 5)Р
следует (3, 5)Р.

Это можно увидеть
и из соответствующих свойств матрицы
отношения. Имеем

[Р]=.

Как видим, не все
диагональные элементы равны 1 (точнее,
равных 1 среди них вообще нет), что
означает не рефлексивность отношения.
Далее, матрица отношения не является
симметричной, то есть отношение
несимметрично. Так как не все элементы
вне главной диагонали равны 0, то отношение
не является антисимметричным. Наконец,

[РР]=[Р][Р]==,

то есть [РР][Р],
и отношение транзитивно.

Отношение, обладающее
одновременно свойствами рефлексивности,
симметричности и транзитивности,
называется отношением эквивалентности
(или эквивалентностью).
Отношение эквивалентности будем
обозначать также через 
(знак «тильда»). При этом, если xy,
то будем говорить, что x
и y
эквивалентны.

Пример
2.7. Отношение равенства на множестве
чисел является отношением эквивалентности.
Действительно, это отношение рефлексивно
(для любого хR
х=х),
симметрично (для любых x,
yR
из x=y
следует y=x)
и транзитивно (из x=y
и y=z
следует x=z).

Пусть на множестве
А
введено отношение эквивалентности .
Тогда множество
А
разбивается
на непересекающиеся между собой
подмножества,
каждое из
которых состоит из эквивалентных между
собой элементов,
причем неэквивалентные
между собой элементы попадают в разные
подмножества.
Эти подмножества называются классами
эквиваленции.
Множество всех классов эквиваленции
множества А
относительно отношения эквивалентности

называется фактор–множеством
множества А
по 
и обозначается через А/.
Если отношение эквиваленции обозначить
через Р,
то соответствующее фактор-множество
обозначается через А/Р.
Класс, содержащий элемент х,
будем обозначать через
.

Пример
2.8. Определим на множестве Z
целых чисел бинарное отношение по
правилу для x,
yZ
положим x~y
тогда и только тогда, когда x
и y
имеют одинаковую чётность. Это отношение
является отношением эквиваленции
(проверьте!),
и множество Z
разбивается на два класса целых чисел

класс четных чисел и класс нечётных
чисел.

Если А

множество с конечным числом элементов,
на котором введено отношение эквиваленции
~, то элементы А
можно пронумеровать таким образом, что
матрица отношения ~ будет иметь
блочно-диагональный вид с блоками,
состоящими из единиц:

[~]=.

Пример
2.9. Рассмотрим отношение Р
на множестве А=1,
2, 3, 4, 5,
изображённое на рисунке 8: Р=(1,
1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3),
(4, 4), (4, 5), (5, 4), (5, 5).
Оно является одновременно рефлексивным,
симметричным и транзитивным (проверьте!),
то есть отношение Р

эквиваленция. Её матрица отношений 
блочно-диагональноая с двумя блоками
из 1:

[Р]=.

2.3. Отношения
порядка (См. также [4], §1.7;
[5], §1.8).
Бинарное отношение РА²=A×A,
обладающее свойством рефлексивности
и транзитивности, называется отношением
предпорядка.
Бинарное отношение РА²,
обладающее свойством рефлексивности,
транзитивности и антисимметричности,
называется отношением частичного
порядка.
Таким образом, отношение частичного
порядка 
это антисимметричный предпорядок. Как
правило, отношение частичного порядка
обозначается через .
Непустое множество А,
на котором определён частичный порядок,
называется частично
упорядоченным.

Частичный порядок
А²
(напоминаем, что если отношение P

это отношение ,
то А²
означает PА²)
называется линейным
порядком,
если для любых х,
yА
либо хy,
либо yх
(то есть любые два элемента х
и y
из А
сравнимы).
Непустое множество А,
на котором определён линейный порядок,
называется линейно
упорядоченным.
Частично упорядоченное и линейно
упорядоченное множества сокращённо
обозначаются соответственно через ЧУМ
и ЛУМ.

Пример
2.10. Отношение P={(a,
a),
(b,
b),
(c,
c),
(a,
b),
(b,
a),
(b,
c),
(a,
c)}
на множестве a,
b,
c
обладает свойствами рефлексивности и
транзитивности (проверьте!).
Значит, это P
отношение предпорядка.

Пример
2.11. Отношение P={(a,
a),
(b,
b),
(c,
c),
(b,
c)}
на множестве А=a,
b,
c
обладает свойствами рефлексивности и
транзитивности (проверьте!). Далее,
одновременно условия (х,
у)Р
и (у,
х)Р
выполняются только для пар (a,
a),
(b,
b),
(c,
c).
Поэтому, если (х,
у)Р
и (у,
х)Р,
то х=у.
Это означает, что Р
удовлетворяет условию антисимметричности.
Таким образом, Р
рефлексивно, транзитивно и антисимметрично,
то есть Р

отношение частичного порядка. При этом
оно не является отношением линейного
порядка, так как не все элементы множества
А
сравнимы, а именно, элементы a
и b,
и элементы a
и c.
Отношение P={(a,
a),
(b,
b),
(c,
c),
(a,
b),
(a,
c),
(b,
c)}
является отношением линейного порядка.

Пример
2.12. Линейным порядком является любое
подмножество действительных чисел
относительно обычного отношения .
Отношение 
на булеане P(А)
является частичным порядком, но не
линейным (почему?).

Отношение <,
определённое по правилу: a<b
тогда и только тогда, когда a≤b
и a≠b,
называется строгим
порядком.

Элемент a
частично упорядоченного множества A
называется максимальным,
если для всех xA,
сравнимых с a,
из a≤x
следует, что x=a.
Аналогично, элемент a
частично упорядоченного множества A
называется минимальным,
если для всех xA,
сравнимых с a,
из x≤a
следует, что x=a.

Элемент a
частично упорядоченного множества A
называется наибольшим,
если a
сравним со всеми элементами из А,
и для любого xA
имеет место x≤a.
Элемент a
частично упорядоченного множества A
называется наименьшим,
если a
сравним со всеми элементами из А,
и для любого aA
имеет место a≤x.

Разница между
максимальным и наибольшим элементами
(соответственно, между минимальным и
наименьшим элементами) очевидна:
наибольший
элемент является также максимальным,
а максимальный
элемент, в
силу того, что он не обязан быть сравнимым
со всеми элементами множества А,
вообще говоря, не
обязательно наибольший в
А.
Он является
наибольшим только в
некотором подмножестве B
из A,
а именно, в
подмножестве тех
(и только
тех) элементов
из A,
которые
сравнимы с данным максимальным.
Ясно, что наибольший
элемент во множестве обязан быть
единственным:
если a
и b

наибольшие в A,
то с одной стороны, a≤b
(так как b

наибольший в A),
с другой стоороны b≤a
(так как a

наибольший в A),
то есть одновременно выполнены условия
a≤b
и b≤a;
но отношение ≤ обладает свойством
антисимметричности, и поэтому a=b.

Аналогично,
наименьший
элемент является минимальным,
но обратное,
вообще говоря, неверно,
и наименьший
элемент в частично упорядоченном
множестве единствен
(докажите!).

Ясно, что в
линейно упорядоченном множестве
максимальный и наибольший элементы
совпадают
(соответственно, минимальный
и наименьший элементы совпадают).

Максимальный и
минимальный элементы не обязательно
единственны
(почему?).

Максимальный и
минимальный элементы множества A
будем обозначать через maxA,
minA,
соответственно. Если их по несколько,
то через max₁A,
max₂A,
…, min₁A,
min₂A,
….

Пусть A

ЧУМ и BA.
Элемент aA
называется верхней
гранью
множества B,
если b≤a
для всех bB.
Элемент aA
называется нижней
гранью
множества B,
если a≤b
для любого bB.
Из определений верхней и нижней граней
множества следует, что они не обязаны
принадлежать самому множеству.

Наименьшая из
верхних граней множества называется
точной
верхней гранью
(супремумом)
данного множества. Наибольшая из нижних
граней множества называется его точной
нижней гранью
(инфимумом).
Точная верхняя и нижняя грани множества
B
обозначаются через supB
и infB,
соответственно.

Пример
2.13. Рассмотрим интервал [a,
b)
(a<b)
на числовой прямой. Тогда inf
[a,
b)=a,
sup
[a,
b)=b.
Кроме того, для любого c<a
имеем, что c

нижняя грань интервала, и для любого d
c
условием b<d
d

верхняя грань.

Пример
2.14. Рассмотрим множество A={,
{1}, {2}, {1, 2}} (множество всех подмножеств
множества {1, 2}, то есть A=P({1,
2}). Отношение ≤ между элементами введём
по правилу a≤b
тогда и только тогда, когда ab.
Тогда 
и {1, 2} 
соответственно наименьший и наибольший
элементы. В подмножестве B={,
{1}, {2}} существует наименьший элемент 
это ,
наибольшего нет; minB=,
max₁B={1}
и max₂B={2},
то есть в B
имеется два максимальных элемента;
наконец, infB=,
supB={1,
2}.

Аналогично можно
рассмотреть minC,
maxC,
infC,
supC,
наибольший и наименьший элементы
подмножества A={{1},
{2}, {1, 2}} (что предоставляется читателю
в качестве несложного упражнения).

2.4.
Упражнения.
1. Пусть А=a
aN,
1a20.
Задать отношение PA²
перечислением элементов:

а) (х,
у)Р
тогда и только тогда, когда х
делит у;

б) (х,
у)Р
тогда и только тогда, когда у=х²;

в) (х,
у)Р
тогда и только тогда, когда х+у=20;

г) (х,
у)Р
тогда и только тогда, когда ху
делится на 3;

д) (х,
у)Р
тогда и только тогда, когда ху
делится на 5;

е) (х,
у)Р
тогда и только тогда, когда х+3=у.

Решение.
б) В Р
включаются такие пары (х,
у),
что у=х².
Например, 4=2².
Поэтому (2, 4)P.
Так как 83²,
то (3, 8)P.
Окончательно имеем P={(1,
1), (2, 4), (3, 9), (4, 16)}.

Ответ:
б) P={(1,
1), (2, 4), (3, 9), (4, 16)}.

2.
Пусть A={a,
b,
c},
B={1,
2, 3, 4}. Изобразить отношения PAB
и QB²
графически. Найти _Р,
_Q,
_Р,
_Q
и РQ:

а)
P={(b,
1), (b,
3), (c,
1), (c,
2), (c,
3), (c,
4)}, Q={(1,
1), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3),
(4, 4)};

б)
P={(a,
1), (a,
2), (a,
4), (b,
3), (c,
1), (c,
4)}, Q={(1,
3), (1, 2), (2, 3), (3, 2), (3, 4), (4, 1)};

в) P={(a,
1),(a,
4), (b,
2), (b,
3), (c,
1), (c,
4)}, Q={(1,
1), (1, 4), (2, 1), (3, 4), (4, 3), (4, 1)}.

3.
Найти матрицы отношений P,
Q
из упражнения 2, а также (PQ),
и по матрице отношений найти (PQ).
С помощью матрицы отношения проверить,
является ли отношение Q
рефлексивным, симметричным, транзитивным,
антисимметричным.

Решение.
а) Имеем

[Р]=,
[Q]=.

Поэтому по свойствам
композиций отношений и их матриц получаем

[(PQ)]=[QP]=[Q][P]=[Q]^T[P]^T==.

В частности,
(PQ)=(1,
b),
(2, b),
(3, b),
(4, b),
(1, с),
(2, с,
(3, с),
(4, с).

Матрица [Q]
отношения Q
обладает тем свойством, что по главной
диагонали стоят единицы. Следовательно,
отношение Q
рефлексивно.

Далее, матрица [Q]
симметрична, [Q]^Т=[Q].
Поэтому отношение Q
симметрично.

Так как

[Q][Q]===[Q]

(напоминаем, что
умножение матриц и чисел производится
обычным образом, а сложение чисел 
по правилу 0+0=0, 1+0=0+1=1+1=1, см. свойства
матриц бинарных отношений, стр. 12), то
отношение Q

транзитивно.

Наконец, вне главной
диагонали [Q]
имеются ненулевые элементы. Поэтому
отношение Q
не является антисимметричным.

Таким образом,
отношение Q
рефлексивно, симметрично, транзитивно
(в частности, Q

эквиваленция), не антисимметрично.

Ответ:
[Р]=,
[Q]=,
[(PQ)]=.
ОтношениеQ
является рефлексивным, симметричным,
транзитивным, но не является
антисимметричным. (PQ)=(1,
b),
(2, b),
(3, b),
(4, b),
(1, с),
(2, с,
(3, с),
(4, с).

4.
Проверить отношения из упражнения 1 на
рефлексивность, симметричность,
транзитивность, антисимметричность.
Если на множестве А
отношение Р
является эквиваленцией, то найти
фактор-множество .

Решение.
г) Так как 0=хх
делится на 3 для любого х,
то для любого х
(х,
х)Р,
и отношение
Р
рефлексивно. Далее, для любых х,
у
из того, что ху
делится на 3 следует, что ух=(ху)
делится на 3. Поэтому из (х,
у)Р
следует (у,
х)Р,
и отношение симметрично. Пусть ху
делится на 3 и уz
делится на 3. Тогда (в силу того, что сумма
чисел, делящихся на 3 тоже делится на 3)
хz
=(ху)+(уz)
делится на 3. Поэтому из (х,
y)Р
и (y,
z)Р
следует (х,
z)Р,
и отношение транзитивно. Следовательно,
отношение Р
рефлексивно, симметрично, транзитивно,
и Р

эквиваленция.

Из того, что ху
делится на 3 и ух
делится на 3 не следует, что х=у.
Поэтому отношение не является
антисимметричным.

Найдем фактор-множество
по отношению Р.
Классами эквиваленции являются
=1,
4, 7, 10, 13, 16, 19,
=2,
5, 8, 11, 14, 17, 20,
=3,
6, 9, 12, 15, 18.
Поэтому А/Р=,,.

Ответ:
Отношение Р
является рефлексивным, симметричным,
транзитивным, но не является
антисимметричным. А/Р=,,.

5.
Найдите область определения, область
значений отношения РR².
Является ли отношение Р
рефлексивным, симметричным, антисимметричным,
транзитивным?

а) (x,
y)P
тогда и только тогда, когда y=|x|;

б) (x,
y)P
тогда и только тогда, когда xy>1;

в) (x,
y)P
тогда и только тогда, когда x²+y²=1.

Решение.
а) Элемент х
может принимать любое действительное
значение, то есть хR,
и _Р=R.
Так как y=|x|0,
то _Р=R₊=у
уR,
у0

множество всех неотрицательных чисел.
Вообще говоря, х|x|
(например, 1|1|,
и отношение нерефлексивно. Далее, из
y=|x|
не следует, что х=|у|
(это не так, если х

отрицательно), и поэтому отношение
несимметрично. Из y=|x|
и z=|у|
следует z=|x|,
так как z=|у|=у=|x|
(|у|=у
так как y=|x|≥0).
Поэтому отношение транзитивно. Наконец,
из y=|x|
и х=|у|
следует х=у,
то есть отношение антисимметрично.

Ответ:
_Р=R,
_Р=R₊=у
уR,
у0.
Отношение нерефлексивно, несимметрично,
транзитивно, антисимметрично.

6.
Пусть
a,
b,
c,
d,
e,
f

такие
числа,
что
a<b<c<d<e<f,
A=[c,
d),
B=[c,
d)(e,
f
), C=[a,
b)[c,
d),
D=[c,
d)(e,
+),E=(,d)[c,
d).
Найти (в
случае наличия) minX,
maxX,
infX,
supX,
наименьшее и наибольшее значения
множеств X=A,
B,
C,
D,
E.

Решение.
Решим упражнение для X=B.

Покажем, что minB=с,
maxB
не существует. Действительно,

B=[c,
d)(e,
f
)={x|c≤x<d}{x|e<x<f
}.

Поэтому для xB
из x≤c
следует, что x=c,
так как x
удовлетворяет системе неравенств

Следовательно,
c=minB.
Далее, так как для любого xB
имеет место неравенство x<d,
то нет такого aB,
что для любого xB
имело бы место x≤a.
Действительно, aB
означает, что a<d
и тогда существует x
такой, что a<x<d,
то есть xB
и a<x.
Следовательно, maxB
не существует.

Покажем, что infB=с
и supB=f.
Будем рассматривать B
как подмножество R:
BR.
Тогда для любого xR
с условием x≤y,
где y

произвольный элемент из B,
является нижней гранью B.
Из нижних граней B
наибольшим является c,
то есть infB=с.
Аналогично, любой xR
с условием y≤x,
где yB,
является верхней гранью B.
Наименьшая из них 
это d,
то есть supB=f.

Наконец, в ЛУМ minX
и maxX
являются одновременно наибольшим и
наименьшим элементами, соответственно.
Так как B

ЛУМ (как числовое множество) и minB=c,
a
c=maxB
не существует, то наименьшим элементом
B
является c,
а наибольшего элемента не существует.

7.
Пусть A={1,
2, 3} (A={1,
2, 3, 4}) и P(A)

его булеан.

а) Доказать, что
P(A)
имеет наименьший и наибольший элементы
относительно отношения .
Найти все минимальные и максимальные
элементы в P(A).

б) Для B=P(A){{2,
3}, {1, 2, 3}} найти наибольший и наименьший
элементы, minB,
maxB,
infB,
supB
(если указанные элементы существуют).

в) Изобразить
графически отношение 
на A,
B.

Источник

Прочие статьи цикла

Отношения. Часть I
Отношения. Часть II
Количественные характеристики отношений

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

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

Понятие отношения

Думаю, что термин отношение знаком каждому читателю, но просьба дать определение поставит большинство в тупик. Причин для этого много. Они чаще всего в преподавателях, которые, если и использовали отношения в процессе преподавания, внимания на этом термине не заостряли, запоминающихся примеров не приводили. Некоторые комментаторы статьи отнесли замечания на свой счет и насыпали минусов. Но шила в мешке не утаишь. Серьезных публикаций как не было, так и нет. Задайте себе вопрос, работали ли Вы с каким-либо пространством отношений? И честно себе ответьте. Что об этом пространстве можете миру поведать, для начала хотя-бы перечислить его элементы и указать свойства. Даже на СУБД Вы смотрите глазами их создателей, а они ведь тоже не все видят, или не все показывают, как, например, в микросхемах.

Здесь сделаю небольшой повтор. Начинать следует с абстрактного множества А ={a1,a2,a3,…, an}. О нем почитать можно здесь. Для лучшего понимания сократим множество до 3 элементов, т.е. А ={a1, a2, a3}. Теперь выполним декартово умножение А×А =А² и явно перечислим все элементы декартова квадрата
А×А={(a1, a1),(a1, а2),(a1, a3),(a2, а1),(a2, a2),(a2, a3),(a3, a1),(a3, a2),(a3, a3)}.
Получили 9 упорядоченных пар элементов из А×А, в паре первый элемент из первого сомножителя, второй — из второго. Теперь попробуем получить все подмножества из декартова квадрата А×А. Подмножества будут содержать разное количество пар: одну, две, три и так до всех 9 пар, включаем в этот список и пустое множество ∅. Сколько же получилось подмножеств? Много, а именно 2⁹ = 512 элементов.

Определение. Подмножество декартова квадрата множества называется бинарным отношением. Если декартов квадрат из двух сомножителей отношение бинарное, если из 3-х -тернарное, из 4-х — тетрарное, из n — n-арное. Арность — число мест в элементе отношения.
Определение. Множество всех подмножеств множества А называется булеаном. Булеан состоит из 2^|A| элементов, здесь |A| — мощность множества.

Отношения можно задавать в разном представлении:

перечислением элементов; R1 ={(a2,a2),(a2,a3),(a3,a1)}; R2 ={(a3,a3)}
двоичным вектором; <000011100>; <000000001>
матрицей;
графом и др. способами.

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

Пространства бинарных отношений

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

Пространством бинарных отношений с множеством-носителем называется произвольное подмножество множества бинарных отношений заданных на. Рассмотрим основные пространства для отношений предпочтений (рис. 2.15).

Р – пространство всех отношений слабого предпочтения, удовлетворяют условию рефлексивности и полноты.
QT – слабые предпочтения, удовлетворяющие условию квазитранзитивности.
QO – пространство линейных квазипорядков, т. е. отношения из QT, которые являются транзитивными.
ТО – пространство всех совершенных порядков, т. е. отношения из QO, которые являются антисимметричными.
SP – пространство всех отношений строгого предпочтения, удовлетворяют свойствам антирефлексивности и антисимметричности.
РО – отношения строгого частичного порядка, или транзитивные строгие предпочтения. Так как отношения строгого частичного порядка транзитивны, естественно пользоваться, для их представления сокращенными графами, то есть такими, в которых опущены дуги, реализующие транзитивность. Такие сокращенные графы называются диаграммами Хассе.
QS – пространство квазисерий, т. е. строгие частичные порядки, для которых отношение I=¬(PUP^-1) – эквивалентность.
TSO – пространство строгих линейных порядков, т. е. тех частичных порядков, для которых выполняется свойство полноты.
Необходимо отметить, всего таких отношений n!.. Например, для n = 3, число совершенных отношений равно 6 и все они приведены на рис. 2.13.
Т – пространство всех отношений толерантности (безразличия), они обладают свойствами симметричности и рефлексивности.
ТОТ – пространство транзитивно ориентируемых отношений толерантности, т. е. такие отношения, что дополнение к I представляется в виде объединения взаимно обратных транзитивных отношений, т. е.
¬I =R∩R^-1.
I – пространство всех отношений эквивалентности, т. е. симметричных, рефлексивных и транзитивных отношений.
Е – пространство отношений равенства, состоит из одного отношения представленного диагональной матрицей. Между пространствами R, P и I имеется взаимно-однозначная связь, определяемая отображением отношений предпочтения.

Рисунок 2.15 Схема пространств бинарных отношений

Выявленные связи между пространствами используются для переноса задач принятия решений (ЗПР) из одних пространств в другие, где они могут быть решены более простым путем, а затем полученное решение возвращают в исходное пространство, где была сформулирована ЗПР.
Эти отношения представлены диаграммой на рис. 2.14. Пространства бинарных отношений (типы отношений) представлены рис. 2.15.

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

Определение. Бинарное отношение σ ⊆ А×А, обладающее тремя свойствами рефлексивности, симметричности, транзитивности, называется, бинарным отношением эквивалентности (БОЭ). Обозначается отношение эквивалентности σ(х, у), (х, у)∊σ, хσу, х≈у. Удобно использовать матричное (табличное) представление отношения. Ниже на рис 2.24 приведено как раз матричное представление. Над множеством из 4-х элементов существует 15 БОЭ, которые все изображены.

Представление и анализ структуры отношений эквивалентности (n = 4)
Эквивалентность из бинарных отношений, пожалуй, самое распространенное БО. Редкая наука обходится без этого понятия, но даже тогда, когда эквивалентности используются в изложении каких-либо вопросов, бывает трудно понять, что в виду имел автор. Даже при корректном определении и перечислении свойств, присущих этому бинарному отношению – трудности восприятия остаются.

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

Пример 1. Пусть имеется три кубика. Составим список свойств, которыми наделены кубики и практическое использование которых (свойств кубиков) делает их как бы взаимозаменяемыми. Кубикам присвоим номера, а их свойства представим таблицей 1.

По каждому из свойств возникает БОЭ и классы эквивалентности. Продолжая список свойств, мы новых отношений эквивалентности не получим. Будут только повторы уже построенных, но для других признаков. Покажем связь БОЭ с множествами.

Рассмотрим множество из трех элементов А ={1,2,3} и получим для него все возможные разбиения на все части. ①1|2|3; ②12|3; ③13|2; ④ 1|23; ⑤123. Последнее разбиения на одну часть. Номера разбиений и БО в кружках.

Определение. Разбиением множества А называют семейство Аi, i = 1(1)I, непустых попарно непересекающихся подмножеств из А, объединение которых образует все исходное множество А=UАi, Аi∩Аj =∅, ∀ i ≠ j. Под-множества Аi называют классами эквивалентности разбиения исходного множества.

Это все разбиения множества (5 штук). Анализ БО показывает, что различных отношений эквивалентности тоже только 5 штук. Случайно ли это совпадение? Мы можем каждому разбиению сопоставить матрицу из девяти ячеек (3×3 = 9), в каждой из которых либо размещается упорядоченная пара элементов из множества А, либо ячейка остается пустой, если для соответствующей пары нет объекта. Строки и столбцы матрицы размечаются элементами множества А, а пересечению строка – столбец соответствует упорядоченная пара (i, j). В ячейку матрицы вписывается не пара, а просто единица или нуль, впрочем, нуль часто не пишут совсем.

Нет, совпадение не случайное. Оказывается, каждому разбиению множества взаимно однозначно соответствует БОЭ, при этом мощность множества может быть любой |A| = n.

Это отношение едва ли не самое частое по использованию в научном обороте, но совокупность свойств, реализуемых в этом отношении, сильно ограничивает его распространенность.
Так среди всех абстрактных бинарных отношений над множеством из трех элементов (всего их 2⁹ = 512 отношений) только пять являются эквивалентностями — носителями требуемых свойств, менее одного процента.

Для |A| = 4 отношений существует 2¹⁶ = 65536, но эквивалентностей лишь 15 штук. Это весьма редкий тип отношений. С другой стороны, отношения эквивалентности широко распространены в прикладных задачах. Везде, где имеются и рассматриваются множества самых различных объектов и различные разбиения таких множеств (не чисел) на части возникают отношения эквивалентности. Их можно назвать математическими (алгебраическими) моделями таких разбиений, классифицирующими множества объектов по различным признакам.

Минимальное разбиение множества А, образованное из одноэлементных подмножеств А= U{a} и разбиение А, состоящее из самого множества {А}, называются тривиальными (несобственными) разбиениями.

Решетка Р(4): все разбиения множества А = {a1,a2,a3,a4} = {1,2,3,4}

Минимальному разбиению соответствует отношение эквивалентности П15, которое называется равенством или единичным отношением. В каждом классе эквивалентности — единственный элемент. Разбиению множества А, включающему лишь само множество А, соответствует отношение эквивалентности, содержащее все элементы декартова квадрата А×А.

Ближайший тип к отношениям эквивалентности – отношения толерантности. Множество отношений толерантности содержит в себе все отношения эквивалентности. Для носителя А из трех элементов толерантностей 8. Все они обладают свойствами рефлексивности и симметричности.

При выполнении свойства транзитивности пять из восьми толерантностей преобразует в эквивалентности (рис. 2.24 и 2.25).

Определение. Совокупность классов [a]σ эквивалентности элементов множества А называется фактор-множеством (обозначается А/σ) множества А по эквивалентности σ.

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

Отношения толерантности и их анализ

Об этих БО ранее уже упоминалось, а здесь рассмотрим их подробнее. Всем известны понятия сходство, похожесть, одинаковость, неразличимость, взаимозаменяемость объектов. Они кажутся близкими по содержанию, но при этом не одно и то же. Когда для объектов указано только сходство, то невозможно разбить их на четкие классы так, что внутри класса объекты похожи, а между объектами разных классов сходства нет. В случае сходства возникает размытая ситуация без четких границ. С другой стороны, накапливание несущественных различий у сходных объектов может привести к совершенно непохожим объектам.

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

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

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

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

В самом деле, будем рассматривать множество точек (х, у) на плоскости. Пусть величина d имеет значение меньшее порога разрешимости глаза, т. е. d – такое расстояние, при котором две точки, находящиеся на этом расстоянии, сливаются в одну, т.е. визуально неразличимы (при выбранном удалении плоскости от наблюдателя). Рассмотрим теперь n точек, лежащих на одной прямой и отстоящих (каждая от соседних) на расстоянии d. Каждая пара
соседних точек неразличима, но, если n достаточно велико, первая и последняя точки будут отстоять друг от друга на большое расстояние и заведомо будут различимы.

Традиционный подход к изучению сходства или неразличимости состоит в том, чтобы сначала определить меру сходства, а затем исследовать взаимное расположение сходных объектов. Английский математик Зиман, изучая модели зрительного аппарата, предложил аксиоматическое определение сходства. Тем самым свойства сходства стало возможным изучать независимо от того, как конкретно оно задано в той или иной ситуации: расстоянием между объектами, совпадением каких-то признаков или субъективным мнением наблюдателя.
Введем экспликацию понятия сходства или неразличимости.

Определение. Отношение Т на множестве M называется отношением толерантности или толерантностью, если оно рефлексивно и симметрично.

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

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

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

Рассмотрим примеры, где толерантность задается разными способами.

Пример 2. Множество M состоит из четырехбуквенных русских слов — нарицательных существительных в именительном падеже. Будем называть такие слова сходными, если они отличаются не более чем на одну букву. Известная задача «Превращение мухи в слона» в точных терминах формулируется так. Найти последовательность слов, начинающуюся словом «муха» и кончающуюся словом «слон», любые два соседних слова в которой сходны в смысле только что данного определения. Решение этой задачи:

муха — мура — тура — тара — кара — каре — кафе — кафр — каюр — каюк — крюк — крок — срок — сток — стон — слон.

Пример 3. Пусть p — натуральное число. Обозначим через Sp совокупность всех непустых подмножеств множества М = {1, 2, …, p}. Отношение «иметь хотя бы один общий элемент» на множестве Sp – это отношение толерантности. Тогда два таких подмножества назовем толерантными, если у них есть хотя бы один общий элемент. Легко видеть, что рефлексивность и симметричность отношения выполнены.

Множество Sp называется (p –1) -мерным симплексом. Это понятие обобщает понятие отрезка, треугольника и тетраэдра на многомерный случай. Числа 1, 2, 3, …, p интерпретируются как вершины симплекса. Двухэлементные подмножества – как ребра, трехэлементные – как плоские (двумерные) грани, прочие k-элементные подмножества – как (k –1)-мерные грани. Число всех элементов (подмножеств) из Sp равно 2^р −1.

Толерантность подмножеств (граней) означает наличие у них общих вершин.

Определение. Множество M с заданным на нем отношением толерантности τ называется пространством толерантности. Таким образом, пространство толерантности есть пара (M, τ).

Пример 4. Пространство толерантности Sp допускает обобщение на бесконечный случай. Пусть H — произвольное множество. Если SH – совокупность всех непустых подмножеств множества H, то отношение толерантности Т на SH задается условием: X Т Y, если X∩Y ≠ ∅. Симметричность и рефлексивность этого отношения очевидны. Пространство SH обозначается <Н, Т> и называется «универсальным» пространством толерантности.

Пример 5. Пусть p — натуральное число. Обозначим Bp множество всех точек p-мерного пространства, координаты которых равны 0 или 1. Толерантность в Bp задается правилом: xτy, если x и y содержат хотя бы одну совпадающую компоненту (координату). Общее количество элементов в Bp равно 2^р. Для каждого элемента x = (a1, a2, …,ap) из множества Bp существует только один не толерантный ему элемент y = (1−a1, 1−a2, …, 1−ap ).
Очевидно, что Bp состоит из всех вершин p-мерного куба.

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

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

При других значениях p пространство можно интерпретировать как множество точек p-мерного пространства. В частности, каждый элемент x можно считать числовой функцией, заданной на множестве натуральных чисел {1, 2, 3, …}, которая каждому натуральному числу i: 1 ≤ i ≤ p сопоставляет действительное число ai (конечная числовая последовательность). Тогда толерантность двух функций x и y означает, что они хотя бы в одной точке равны.

Отношения частичного порядка и их анализ

Упорядоченные множества – это множества с введенным на нем отношением порядка. Определение. Множество А и бинарное отношение порядка R на нем (≤) называется частично упорядоченным, если для отношения выполнены (как и в БОЭ) три условия (одно условие другое):

рефлексивность ∀ х ∊ А (хRx); (антирефлексивность ∀ х ∊ А ¬(хRx));
антисимметричность ∀ х, y ∊ А (хRy yRx→x = y);
транзитивность ∀ х, у, z ∊ А (хRy& yRz →xRz).

При антирефлексивном отношении возникает строгий частичный порядок. Множество В(А) всех подмножеств множества А, упорядоченное по включению элементов является частично упорядоченным множеством (ЧУМ). Частично упорядоченное множество (В(А), ⊆) часто называют булеаном.

Элемент х∊А ЧУМ А покрывает элемент у∊А, если х > y и не существует z∊А такого, что х > z > y. Пара элементов х, у∊А называется сравнимой, если х ≥ у или х ≤ у.

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

Если же некоторое ЧУМ В состоит лишь из несравнимых друг с другом элементов, то множество В называют антицепью. Цепь в ЧУМ А называется насыщенной, если она не может быть вложена ни в какую другую цепь, отличную от себя.

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

Элемент m ЧУМ А называется минимальным, если в А нет элемента х∊А, отличного от m и такого, что х≤m. Элемент M ЧУМ А называется максимальным, если в А нет элемента х «большего», чем M, отличного от M и такого, что х ≥ M.

Элемент у∊А ЧУМ А называется наибольшим, если ∀ х∊ А х ≤ у. Элемент у∊ А ЧУМ А называется наименьшим, если ∀ х∊А х ≥ у. Для наибольшего и наименьшего элементов принято использовать обозначения 1 и 0 соответственно. Их называют универсальными границами. Всякое ЧУМ А имеет не более одного наименьшего и не более одного наибольшего элементов. В ЧУМ А допустимо несколько минимальных и несколько максимальных элементов
Изображать конечное ЧУМ А удобно диаграммой Хассе, которая представляет собой ориентированный граф, его вершины распределены по уровням диаграммы и соответствуют элементам из А, а каждая дуга направляется вниз и рисуется тогда и только тогда, когда элемент х∊А покрывает элемент у∊А.

Транзитивные дуги не изображаются. Уровни диаграммы Хассе содержат элементы одинакового ранга, т.е. связанные с минимальными элементами ЧУМ путями равной длины (по числу дуг).
Пусть В непустое подмножество ЧУМ А, тогда элемент х∊А называется точной верхней гранью (обозначается sup_AB) множества В, если х ≥ у для всех у∊В и, если из истинности соотношения z ≥ у для всех у∊В вытекает, что z ≥ х.

Точной нижней гранью (обозначается inf_AB) множества В называется элемент х∊А, если х ≤ у для всех у∊В и, если из условия z ≤ у для всех у∊ В вытекает, что z ≤ х.

Пример 7. Заданы два конечных числовых множества
А = {0,1,2,…,21} и B = {6,7,10,11}.

ЧУМ (А, ≤) представлено рис. 2.26.

Совокупность В^Δ всех верхних граней для В называется верхним конусом для множества В. Совокупность В^∇ всех нижних граней для В называется нижним конусом для В.

Всякое подмножество ЧУМ также является ЧУМ относительно наследованного порядка. Если в множестве существуют наибольший и/или наименьший элементы, то они являются максимальным (минимальным соответственно). Обратное неверно. Булеан обладает единственным наименьшим (Ø) и единственным наибольшим элементами.

В приведенном множестве наименьший элемент нуль (0) и он совпадает с единственным минимальным элементом, а наибольшего элемента не существует. Максимальными элементами являются {19, 20, 21}. Точная верхняя грань для B = {6,7,10,11} есть элемент 21 (это наименьший элемент в верхнем конусе).

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

Частичные порядки отличаются от строгих частичных порядков только тем, что содержат в своем составе дополнительные элементы (в матричном представлении – диагональные) (аi, ai ) = 1, i = 1(1)n, а число тех и других порядков в полном множестве отношений одинаково. До настоящего времени не найдены зависимости (формула, алгоритм), которые позволяли бы подсчитывать и перечислять при любом n число частичных порядков.

Разными авторами непосредственным подсчетом определены и опубликованы следующие результаты (табл. 2.12).

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

В таблице 2.12 показаны: n = |A| – мощность множества-носителя; вторая строка – количество всех бинарных отношений на множестве А; и далее

|Ин(n)| – количество классов неизоморфных отношений;
|Г(n)| – количество отношений частичного порядка;
|Гн(n)| – количество классов неизоморфны отношений частичного порядка;
|Гл(n)| = n! – количество отношений линейного порядка.

Как видим, в таблице для небольших n, например, Г(n=4) имеется всего 219, приводятся данные, значения которых с увеличением n очень быстро растут, что существенно усложняет их количественный (и качественный) непосредственный анализ даже с помощью ЭВМ.

Таблица ниже иллюстрирует возможность порождения Г(n=4) всех частичных порядков из пересечения каждого с каждым линейных частичных порядков. Но в этой ситуации возникают избыточные (повторяющиеся), которые при малых n можно отсечь вручную (пересчитать). Получаются 300 матриц, но ЧУМ среди них лишь 219. Общие формулы так и не были получены. На мировом уровне ситуация аналогичная, хотя мне не довелось видеть публикаций о перечислениях ЧУМ западных авторов. Наши алгоритмы вполне оригинальны и пионерские.

Приведу возможную схему решения задачи перечисления элементов пространства частичных порядков (n=4).

Множество строгих частичных порядков при лексикографическом упорядочении линейных порядков (n=4) порождается при их взаимном пересечении.

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

Определение. Замкнутый интервал – это множество вида {x: a ≤ x ≤ b}; открытый интервал не замкнут, и полуоткрытый интервал, т. е. множество вида {x: a < x ≤ b}, где а < b, или вида {x: a ≤ x < b} не открыт и не замкнут.

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

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

Определение. Семейство R называется цепью (иногда башней, гнездом) тогда и только тогда, когда для любых его элементов А и В либо А ⊂ В, либо В ⊂ А. Это условие равносильно утверждению, что семейство R линейно упорядочено по включению или – в принятой терминологии – что семейство R вместе с отношением включения является цепью.

П р и н ц и п м а к с и м а л ь н о с т и Х а у с д о р ф а. Для любого семейства множеств A и любого гнезда R, образованного элементами семейства A существует максимальное гнездо M в A, содержащее R.

Важная теорема о множествах и их семействах (Дж.Л.Kелли «Общая топология» стр.55).
Теорема. (а) П р и н ц и п м а к с и м а л ь н о г о э л е м е н т а. Максимальный элемент в семействе A множества существует, если для каждого гнезда, лежащего в A, в A найдется элемент, который содержит произвольный элемент этого гнезда.

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

(в) Л е м м а Т ь ю к и. В каждом семействе множеств конечного характера есть максимальный элемент.

(г) Л е м м а К у р а т о в с к о г о. Каждая цепь в (частично) упорядоченном множестве содержится в некоторой максимальной цепи.

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

(е) А к с и о м а в ы б о р а. Пусть Хα – непустое множество для каждого элемента а из множества индексов А. Тогда на А существует функция с такая, что с(а)∊ Хα для каждого а из А.

(ж) П о с т у л а т Ц е р м е л о. Для любого семейства A непересекающихся непустых множеств существует такое множество С, что АUС для каждого А из A состоит ровно из одной точки.

(з) П р и н ц и п в п о л н е у п о р я д о ч е н и я. Каждое множество можно вполне упорядочить.

Источник

Читайте также:

Применения и примеры[править | править код]

Свойства[править | править код]

Совместимость с другими топологическими понятиями[править | править код]

Отношения эквивалентности на множестве

Разбиение множества

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