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

[Vladimir Pliassov]

Пусть нам дано множество $X=\{t, a, b, c\}$. Имеем множество $P=X\times X$, которое состоит из всех пар, помещенных в правой нижней четверти таблицы

$$\begin{tabular}{1|1111} &t&a&b&c\\ \hline t&\langle t, t \rangle&\langle t, a \rangle&\langle t, b \rangle&\langle t, c \rangle\\ a&\langle a, t \rangle&\langle a, a \rangle&\langle a, b \rangle&\langle a, c \rangle \\ b&\langle b, t \rangle&\langle b, a \rangle&\langle b, b \rangle&\langle b, c \rangle\\ c&\langle c, t \rangle&\langle c, a \rangle&\langle c, b \rangle&\langle c, c \rangle\\ \end{tabular} \eqno (1) $$

В той же четверти таблицы

$$\begin{tabular}{1|1111} &t&a&b&c\\ \hline t&&&&\\ a&&\langle a, a \rangle&\langle a, b \rangle&\langle a, c \rangle \\ b&&\langle b, a \rangle&\langle b, b \rangle&\langle b, c \rangle\\ c&&\langle c, a \rangle&\langle c, b \rangle&\langle c, c \rangle\\ \end{tabular} \eqno (2) $$

помещены все элементы множества $P'=\{\langle a, a\rangle, \langle a, b\rangle, \langle a, c\rangle, \;\; \langle b, a\rangle, \langle b, b\rangle, \langle b, c\rangle, \;\; \langle c, a\rangle, \langle c, b\rangle, \langle c, c\rangle\} \;\; P'\subset P$.

Является ли подмножество $P'$ множества $P$ отношением эквивалентности на множестве $X$?

Если является, то как это сообразуется с определением

Цитата:

Бинарное отношение $R$ на множестве $X$ называется отношением
эквивалентности, если выполнены следующие свойства:
• (рефлексивность) $xRx$ для всех $x \in X$;
• (симметричность) $xRy \Rightarrow yRx$ для всех $x, y \in X$;
• (транзитивность) $xRy$ и $yRz \Rightarrow xRz$ для всех $x, y, z \in X$.

https://www.mccme.ru/free-books/shen/sh ... art1-2.pdf стр. 42

Цитата:

Напомним, что бинарным отношением на множестве $X$ называется подмножество $R \subset X\times X$; вместо $\langle x_1, x_2 \rangle \in R$ часто пишут $x_1Rx_2$.

Там же.

? Я имею в виду первый пункт (рефлексивность): по определению $xRx$ для всех $x \in X$, значит, и для $x=t$ тоже, то есть, поскольку $P'$ является отношением эквивалентности на множестве $X$, пара $\langle t, t \rangle$ должна принадлежать $P'$, а она не принадлежит.

[mihaild]

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

Vladimir Pliassov в сообщении #1576799 писал(а):

то есть, поскольку $P'$ является отношением эквивалентности на множестве $X$, пара $\langle t, t \rangle$ должна принадлежать $P'$, а она не принадлежит

Это чуть лучше сформулировать как "если бы $P'$ было отношением эквивалентности, то пара принадлежала бы".

А у вас что-то в вашем рассуждении вызывает сомнение?

[Vladimir Pliassov]

mihaild в сообщении #1576801 писал(а):

Это чуть лучше сформулировать как "если бы $P'$ было отношением эквивалентности, то пара принадлежала бы".

Я имел в виду: "Если является, то, поскольку является, ..."

mihaild в сообщении #1576801 писал(а):

В терминах таблицы, рефлексивность означает, что отношение должно содержать диагональ.

Значит, $R=\{\langle t, t \rangle\}\cup P'$ это отношение эквивалентности на множестве $X$, и $\{a, b, c\}$ (без $t$) -- класс эквивалентности по отношению $R$? (В этом классе $a\sim b, a\sim c, b\sim c$?)

[mihaild]

Vladimir Pliassov в сообщении #1576810 писал(а):

Значит, $R=\{\langle t, t \rangle\}\cup P'$ это отношение эквивалентности на множестве $X$, и $\{a, b, c\}$ (без $t$) -- класс эквивалентности по отношению $R$?

Да, всё так.

[Vladimir Pliassov]

Берем произвольное непустое подмножество $X'$ множества $X$, возводим его в декартов квадрат: $X'\times X'$, -- объединяем $X'\times X'$ с множеством $D=\{\langle x_i, x_i \rangle \} \;\; i\in I$ всех пар, каждая из которых состоит из одного и того же элемента $x_i\in X$, взятого два раза, и получаем множество $R$, которое называется отношением эквивалентности на множестве $X$: $R=D\cup (X'\times X')$.

(Здесь $I$ -- некоторое множество индексов, конечное или бесконечное).

При этом $X'$ -- это класс эквивалентности по отношению $R$.

При таком понимании отношения эквивалентности (то есть когда под бинарным отношением понимается множество) каждому $R$ соответствует единственный класс эквивалентности.

Всего же при этом классов эквивалентности по всевозможным $R$ для множества $X$ существует $(2^{\vert X\vert}-1)-(\vert X\vert-1)=2^{\vert X\vert}-\vert X\vert$ (то есть столько, сколько существует непустых подмножеств $X$ минус число элементов $X$ за вычетом одного -- для отношений $R$, состоящих из одних только пар $\langle x_i, x_i \rangle $, этим отношениям соответствуют одноэлементные классы эквивалентности).

Однако, по-моему, под отношением $R$ понимается не только множество, но и нечто другое (и это может сбивать с толку), а именно, в следующих предложениях:

1) для выбранного $R$ классы эквивалентности это блоки (части) соответствующего разбиения множества $X$ (при этом каждому блоку соответствует единственное подмножество множества $X\times X$);

2) для $X$ существует всего столько $R$, сколько существует разбиений $X$;

3)

Цитата:

Множество классов эквивалентности называют фактор-множеством множества $X$ по отношению эквивалентности $R$.

https://www.mccme.ru/free-books/shen/sh ... art1-2.pdf, стр. 43

Другое $R$ (другая эквивалентность) -- другое фактор-множество.

Очевидно, что в этих трех предложениях под отношением $R$ имеется в виду не множество, а некое условие, по которому каждому блоку разбиения (каждому классу эквивалентности) взаимно-однозначно соответствует подмножество множества $X\times X$, причем каждое из этих подмножеств (множества $X\times X$) также называется отношением $R$. По-моему, это неудачно -- называть разные вещи одним и тем же именем.

Если, конечно, я все правильно понял.

[warlock66613]

Отношение на $\lbrace a, b \rbrace$, заданное множеством $\lbrace\langle a, a \rangle, \langle b, b \rangle\rbrace$, разбивает множество на два класса эквивалентности: $\lbrace a \rbrace$ и $\lbrace b \rbrace$.

[mihaild]

warlock66613 в сообщении #1576840 писал(а):

и получаем множество $R$, которое называется отношением эквивалентности на множестве $X$

Для этого нужно, чтобы $x_i$ пробегали, как минимум, $X \setminus X'$, и не выходили за пределы $X$.
Потому что иначе возьмите просто $X = \{1\}$, $X' = \varnothing$, и либо $I = \varnothing$ либо $I = \{42\}$, $x_42 = 666$ - какие отношения в этом случае получатся? будут ли они отношениями эквивалентности на $X$?

Vladimir Pliassov в сообщении #1576833 писал(а):

При таком понимании отношения эквивалентности (то есть когда под бинарным отношением понимается множество) каждому $R$ соответствует единственный класс эквивалентности.

Это тоже нужно уточнять. Вы построили по $X'$ отношение эквивалентности, и в принципе можете сказать, что "запомнили", какое было $X'$ - и оно действительно будет классом эквивалентности. Но восстановить $X'$ по $R$ в общем случае нельзя.
Ну и естественно в $R$ могут быть и другие классы эквивалентности.

Vladimir Pliassov в сообщении #1576833 писал(а):

Всего же при этом классов эквивалентности по всевозможным $R$ для множества $X$ существует $(2^{\vert X\vert}-1)-(\vert X\vert-1)=2^{\vert X\vert}-\vert X\vert$

Поясните подробнее, что вы тут считали - число всех множеств, которые являются классами эквивалентности для какого-то $R$? Их, естественно, столько же, сколько непустых подмножеств $X$.

Vladimir Pliassov в сообщении #1576833 писал(а):

под отношением $R$ имеется в виду не множество, а некое условие, по которому каждому блоку разбиения (каждому классу эквивалентности) взаимно-однозначно соответствует подмножество множества $X\times X$

Под $R$ понимается именно множество. По этому множеству можно построить разбиение на классы эквивалентности, а по разбиению на классы эквивалентности - обратно множество.

Vladimir Pliassov в сообщении #1576833 писал(а):

причем каждое из этих подмножеств (множества $X\times X$) также называется отношением $R$

Нет, не называется.

[Vladimir Pliassov]

mihaild в сообщении #1576849 писал(а):

Под $R$ понимается именно множество. По этому множеству можно построить разбиение на классы эквивалентности, а по разбиению на классы эквивалентности - обратно множество.

warlock66613 в сообщении #1576840 писал(а):

Отношение на $\lbrace a, b \rbrace$, заданное множеством $\lbrace\langle a, a \rangle, \langle b, b \rangle\rbrace$, разбивает множество на два класса эквивалентности: $\lbrace a \rbrace$ и $\lbrace b \rbrace$.

Пусть дано множество $X=\{t, a, b, c\}$. Имеем множество

$R=\{\langle t, t \rangle, \;\; \langle a, a\rangle, \langle a, b\rangle, \langle a, c\rangle, \;\; \langle b, a\rangle, \langle b, b\rangle, \langle b, c\rangle, \;\; \langle c, a\rangle, \langle c, b\rangle, \langle c, c\rangle\}$,

которое состоит из всех пар, помещенных в правой нижней четверти таблицы

$$\begin{tabular}{1|1111} &t&a&b&c\\ \hline t&\langle t, t \rangle&&&\\ a&&\langle a, a \rangle&\langle a, b \rangle&\langle a, c \rangle \\ b&&\langle b, a \rangle&\langle b, b \rangle&\langle b, c \rangle\\ c&&\langle c, a \rangle&\langle c, b \rangle&\langle c, c \rangle\\ \end{tabular} \eqno (3) $$

Попытаюсь найти все классы эквивалентности, на которые отношение $R$ разбивает множество $X$. Их всего два: $\lbrace t\rbrace$ и $\lbrace a, b, c\rbrace$. Правильно?

[mihaild]

Vladimir Pliassov в сообщении #1576882 писал(а):

Правильно?

Да, правильно.
Попробуйте доказать, что следующий метод позволяет найти все классы эквивалентности, причем каждый ровно по одному разу:
1. Выписываем на листок все элементы множества.
2. Берем первый выписанный невычеркнутый элемент.
3. Берем все элементы, ему эквивалентные, записываем это как новый класс.
4. Вычеркиваем все элементы, взятые на предыдущем шаге. Если остались невычеркнутые - возвращаемся к 1, иначе говорим, что закончили.

[Vladimir Pliassov]

mihaild в сообщении #1576888 писал(а):

Попробуйте доказать, что следующий метод позволяет найти все классы эквивалентности, причем каждый ровно по одному разу:
1. Выписываем на листок все элементы множества.
2. Берем первый выписанный невычеркнутый элемент.
3. Берем все элементы, ему эквивалентные, записываем это как новый класс.
4. Вычеркиваем все элементы, взятые на предыдущем шаге. Если остались невычеркнутые - возвращаемся к 1, иначе говорим, что закончили.

Сначала надо выяснить, что такое эквивалентность элементов.

Вот какая картина у меня сложилась.

Пусть имеем множество $X$. Тогда $R\subset (X\times X)$ это отношение между $X$ и $X$ (отношение множества с самим собой).

Если взять произвольный элемент $x\in X$, то о нем нельзя сказать, что он рефлексивен или нерефлексивен, симметричен или несимметричен с самим собой, транзитивен или нетранзитивен с самим собой, то есть нельзя сказать, что он эквивалентен самому себе или что он не эквивалентен самому себе. Но если пара $\langle x, x\rangle\in R$, то говорят, что $x$ рефлексивен по отношению $R$.

Из рефлексивности элемента следует его симметричность с самим собой. В самом деле, представим $x$ в двух видах: $x_1$ и $x_2$, то есть подмножество $\lbrace x\rbrace$ множества $X$ представим в виде $\lbrace x_1, x_2\rbrace$, где $x_1=x_2=x$, и тогда $x_1Rx_2\Rightarrow x_2Rx_1$.

Из рефлексивности элемента следует также его транзитивность с самим собой. В самом деле, представим $x$ в трех видах: $x_1$, $x_2$ и $x_3$, то есть подмножество $\lbrace x\rbrace$ множества $X$ представим в виде $\lbrace x_1, x_2, x_3\rbrace$, где $x_1=x_2=x_3=x$, и тогда $x_1Rx_2\wedge x_2Rx_3\Rightarrow x_1Rx_3$.

Таким образом, из рефлексивности элемента следует его эквивалентность самому себе.

Или я зря все это доказывал? Может быть, если пара $\langle x, y\rangle$ принадлежит $R$, то элементы $x$ и $y$ -- именно на этом основании -- называются эквивалентными друг другу (по отношению $R$)? А если $\langle x, y\rangle\notin R$, то $x$ и $y$ не эквивалентны друг другу (по отношению $R$)?

И если $\langle x, x\rangle\in R$, то элемент $x$ -- именно на этом основании -- называется эквивалентным самому себе (по отношению $R$)? А если $\langle x, x\rangle\notin R$, то $x$ не эквивалентен себе (по отношению $R$)?

[mihaild]

Vladimir Pliassov в сообщении #1577008 писал(а):

Но если пара $\langle x, x\rangle\in R$, то говорят, что $x$ рефлексивен по отношению $R$.

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

Vladimir Pliassov в сообщении #1577008 писал(а):

Из рефлексивности элемента следует его симметричность с самим собой.

Vladimir Pliassov в сообщении #1577008 писал(а):

Из рефлексивности элемента следует также его транзитивность с самим собой.

А вот что это значит понять уже сложнее.

Vladimir Pliassov в сообщении #1577008 писал(а):

Таким образом, из рефлексивности элемента следует его эквивалентность самому себе.

Тут понятно, что имеется в виду, но лучше так не говорить: про эквивалентность стоит говорить только если у нас уже есть отношение эквивалентности, а если отношение не абы какое, а эквивалентности, то оно автоматически рефлексивно.

Vladimir Pliassov в сообщении #1577008 писал(а):

Может быть, если пара $\langle x, y\rangle$ принадлежит $R$, то элементы $x$ и $y$ -- именно на этом основании -- называются эквивалентными друг другу (по отношению $R$)? А если $\langle x, y\rangle\notin R$, то $x$ и $y$ не эквивалентны друг другу (по отношению $R$)?

Именно так. Только, повторюсь, говорит об "эквивалентности по отношению $R$" можно только если уже сказано, что $R$ - отношение эквивалентности.

[Vladimir Pliassov]

mihaild в сообщении #1576888 писал(а):

Попробуйте доказать, что следующий метод позволяет найти все классы эквивалентности, причем каждый ровно по одному разу:
1. Выписываем на листок все элементы множества.
2. Берем первый выписанный невычеркнутый элемент.
3. Берем все элементы, ему эквивалентные, записываем это как новый класс.
4. Вычеркиваем все элементы, взятые на предыдущем шаге. Если остались невычеркнутые - возвращаемся к 1, иначе говорим, что закончили.

Каждый класс эквивалентности множества $X$ является классом эквивалентности по любому из своих элементов и потому может быть найден по описанному методу.

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

mihaild в сообщении #1577047 писал(а):

говорить об "эквивалентности

элементов

mihaild в сообщении #1577047 писал(а):

по отношению $R$" можно только если уже сказано, что $R$ - отношение эквивалентности.

То есть эквивалентность элементов $X$ определяется через эквивалентность $R$, а не наоборот. Определение

Цитата:

Бинарное отношение $R$ на множестве $X$ называется отношением
эквивалентности, если выполнены следующие свойства:
• (рефлексивность) $xRx$ для всех $x \in X$;
• (симметричность) $xRy \Rightarrow yRx$ для всех $x, y \in X$;
• (транзитивность) $xRy$ и $yRz \Rightarrow xRz$ для всех $x, y, z \in X$.

https://www.mccme.ru/free-books/shen/sh ... art1-2.pdf стр. 42

мне, кажется, теперь понятно, и понятно, как по нему находить классы эквивалентности. Но есть другое определение отношения эквивалентности, в котором эквивалентность $R$ определяется через эквивалентность элементов $X$:

Цитата:

Отношение эквивалентности ($\sim$) на множестве $X$ — это бинарное отношение, для которого при любых $a,b,c$ из $X$ выполнены следующие условия:

1. рефлексивность: $a\sim a$;
2. симметричность: если $a\sim b$, то $b\sim a$;
3. транзитивность: если $a\sim b$ и $b\sim c$, то $a\sim c$.

и, для того, чтобы пользоваться этим определением, надо сначала определить, что такое эквивалентность элементов. Как это сделать, если не через эквивалентность $R$?

[mihaild]

Vladimir Pliassov в сообщении #1577088 писал(а):

Но есть другое определение отношения эквивалентности, в котором эквивалентность $R$ определяется через эквивалентность элементов $X$:

На самом деле то же самое, просто $\langle x, y\rangle \in R$ в первом варианте записывается как $xRy$, а во втором - как $x \sim y$. На уровне множеств (если помнить, что отношение - это множество, подмножество декартова квадрата) различий нет.

[Vladimir Pliassov]

Мне кажется, что в статье, из которой я привел эту цитату (Википедия "Отношение эквивалентности "), все же другой взгляд. Там не начинают с того, с чего начинают Верещагин и Шень, то есть с определения $R$, а сразу говорят о природе элементов:

Цитата:

Отношение эквивалентности — бинарное отношение между элементами данного множества, свойства которого сходны со свойствами отношения равенства.

и, вообще, много говорят об эквивалентности элементов множества через их природу:

Цитата:

Равенство («$=$»), тривиальное отношение эквивалентности на любом множестве, в частности, вещественных чисел.
Сравнение по модулю: $a\equiv b\pmod n$.
В евклидовой геометрии
Отношение конгруэнтности («$\cong$ »).
Отношение подобия («$\sim$»).
Отношение параллельности прямых («$\|$») (если считать каждую прямую параллельной самой себе).

и т. д..

Наверное, авторы имеют в виду, что эквивалентность или неэквивалентность элементов друг другу определяется исходя из их природы, например, из равенства или неравенства чисел или из параллельности или непараллельности прямых, а без знания природы элементов нельзя определить эквивалентны они или нет (если не исходить из определения отношения как множества $R\subset (X\times X)$).

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

Всякий раз, когда два объекта рассматриваются вместе, мы смотрим, состоялось между ними определенное отношение или не состоялось, например, если прямые непараллельны, то отношение "параллельность" не состоялось.

Если отношение состоялось, мы говорим, что объекты эквивалентны, и если полагаем их элементами множества, говорим, что и элементы эти эквивалентны.

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

При этом:

1) если элемент $a$ (по своей природе) эквивалентен самому себе: $a\sim a$, -- мы можем сказать, что он рефлексивен ("рефлексивность" это синоним слов "эквивалентность самому себе"?), например, прямая $a$ параллельна самой себе -- в этом ее эквивалентность самой себе (рефлексивность) (по отношению "параллельность"),

а если элемент $a$ (по своей природе) неэквивалентен самому себе: $a\not\sim a$, -- мы можем сказать, что он нерефлексивен, например, прямая $a$ не перпендикулярна самой себе -- в этом ее неэквивалентность самой себе (нерефлексивность) (по отношению "перпендикулярность");

2) что касается отношения двух элементов $a$ и $b$, то может быть так, что $a\sim b$, но $b\not \sim a$, например, по отношению "больше".

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

[mihaild]

Vladimir Pliassov в сообщении #1577114 писал(а):

Наверное, авторы имеют в виду, что эквивалентность или неэквивалентность элементов друг другу определяется исходя из их природы, например, из равенства или неравенства чисел или из параллельности или непараллельности прямых, а без знания природы элементов нельзя определить эквивалентны они или нет (если не исходить из определения отношения как множества $R\subset (X\times X)$).

Примеры, которые вы процитировали - это разные способы задать отношение (которое окажется отношением эквивалентности). Например, для параллеьности: у нас есть множество $M$ прямых, и есть отношение $\|$ на нём, причем $\langle a, b\rangle \in \|$ если $a$ параллельно $b$.
Это определение некоторого конкретного множества.

Никакой "природы" тут нет. Более того, на одном и том же множестве могут задаваться разные отношение эквивалентности. Например для прямых - для любого $n$ можно задать отношение $R_n$, относительно которого прямые параллельны, если угол между ними кратен $\frac{\pi}{n}$. Или для чисел - можно задавать сравнения сразу по разным модулям.
И глядя чисто на элементы, сказать, какое именно отношение эквивалентности нам понадобится, нельзя.

Vladimir Pliassov в сообщении #1577114 писал(а):

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

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

-- 14.01.2023, 23:19 --

Vladimir Pliassov в сообщении #1577114 писал(а):

а если элемент $a$ (по своей природе) неэквивалентен самому себе: $a\not\sim a$, -- мы можем сказать, что он нерефлексивен, например, прямая $a$ не перпендикулярна самой себе -- в этом ее неэквивалентность самой себе (нерефлексивность) (по отношению "перпендикулярность")

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