Отношение и разбиение

[gogoshik]

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

Задача. Пусть $\mathcal{P}_{\sim}$ - семейство классов эквивалентности по отношению $\sim$ на множестве $S$. Доказать, что $\mathcal{P}_{\sim}$ является разбиением $S$.

Видимо, чего то я не допонимаю. Существенного. Помогите, пожалуйста, разобраться и понять суть.

[arseniiv]

Давайте сначала выпишем определения. Что такое класс эквивалентности по $\sim$? Что такое разбиение множества? Ну и, вероятно, что такое отношение эквивалентности, раз пока неизвестно, где загвоздка.

-- Пт июл 19, 2019 21:10:04 --

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

[gogoshik]

arseniiv

Давайте выпишем. Спасибо за ответ!

Определение 1. Отношением на множестве $S$ называется любое подмножество $R$ прямого произведения $S \times S$.

Определение 2. Отношением эквивалентности на множестве $S$ называется любое отношение $\sim$, удовлетворяющее следующим свойствам:
a) рефлексивность: $(\forall a \in S) ~a \sim a$
b) симметричность: $(\forall a, b \in S) ~a \sim b \Rightarrow b \sim a$
c) транзитивность: $(\forall a, b, c \in S) ~a \sim b ~and ~b \sim c \Rightarrow a \sim c$.

Определение 3. Разбиением множества $S$ называется семейство $\mathcal{P}$ непересекающихся непустых подмножеств $S$, объединение которых совпадает с $S$.

Определение 4. Классом эквивалентости элемента $a \in S$ по отношению $\sim$ называется подмножество множества $S$, определяемое как: $[a]_{\sim} = \{b \in S ~| ~b \sim a\}$.

[arseniiv]

gogoshik
Вам тоже спасибо. Вот, теперь видно, что надо будет доказать две вещи: что разные классы эквивалентности не пересекаются и что объединение их всех будет давать всё множество $S$. Скажите, насколько вы ощущаете то и это. (Если хорошо ощущаете, то сразу доказывайте, пока получается, и где остановитесь, посмотрим.)

Плюс параллельно можно проверить, как срабатаывает конкретный пример. Будем рассматривать множество $\mathbb Z$ и отношение эквивалентности такое: $x\sim y$ в том случае, если $x - y$ кратно четырём. (Проверьте, что это эквивалентность, если недостаточно очевидно.) Какие по нему есть классы эквивалентности? Тоже будет ясно, если появляется проблема, где она.

[gogoshik]

arseniiv в сообщении #1406032 писал(а):

доказать две вещи: что разные классы эквивалентности не пересекаются и что объединение их всех будет давать всё множество $S$. Скажите, насколько вы ощущаете то и это. (Если хорошо ощущаете, то сразу доказывайте, пока получается, и где остановитесь, посмотрим.)

Ощущаю, но скорее всего на банальном уровне.

Докажем, что разные классы эквивалентности не пересекаются. Пусть $[a]_{\sim}, ~[b]_{\sim}$ - классы эквивалентности и $[a]_{\sim} \cap ~[b]_{\sim} \neq \varnothing$. Тогда $\exists ~c \in [a]_{\sim} \cap ~[b]_{\sim}$. Таким образом $a \sim c$ и $c \sim b$ (в силу симметричности). Поэтому $a \sim b$ (в силу транзитивности). Следовательно $[a]_{\sim} и $[b]_{\sim}$ совпадают.

Сейчас я думаю, как правильно сформулировать доказательство утверждения, что объединение непересекающихся классов эквивалентности элементов множества $S$ совпадает с $S$.

[arseniiv]

gogoshik в сообщении #1406129 писал(а):

Докажем, что разные классы эквивалентности не пересекаются. Пусть $[a]_{\sim}, ~[b]_{\sim}$ - классы эквивалентности и $[a]_{\sim} \cap ~[b]_{\sim} \neq \varnothing$. Тогда $\exists ~c \in [a]_{\sim} \cap ~[b]_{\sim}$. Таким образом $a \sim c$ и $c \sim b$ (в силу симметричности). Поэтому $a \sim b$ (в силу транзитивности). Следовательно $[a]_{\sim} и $[b]_{\sim}$ совпадают.

Коротко, понятно и верно.

gogoshik в сообщении #1406129 писал(а):

Сейчас я думаю, как правильно сформулировать доказательство утверждения, что объединение непересекающихся классов эквивалентности элементов множества $S$ совпадает с $S$.

Можете попробовать от противного: пусть объединение меньше $S$ (больше оно быть не может, хотя это тоже можно доказать явно отдельно при желании), тогда есть элемент $S$, не принадлежащий этому объединению, и тогда по свойству объединения…

[gogoshik]

arseniiv в сообщении #1406198 писал(а):

Можете попробовать от противного: пусть объединение меньше $S$ (больше оно быть не может, хотя это тоже можно доказать явно отдельно при желании), тогда есть элемент $S$, не принадлежащий этому объединению, и тогда по свойству объединения…

Этот элемент является представителем одноэлементного класса эквивалентности.

Кажется, чтобы быть честным утверждение нужно доказывать индукцией по числу $n$ элементов $S$ c базой $n = 2$. Тогда утверждение, что объединение непересекающихся классов эквивалентности для двухэлементного множества почти очевидно (множество состоит либо из одного класса, либо ровно из двух). Индукционный переход доказывается рассмотрением тривиального случая, когда $k + 1$ элемент не эквивалентен ни одному из двух и является самостоятельным (новым) одноэлементым классом. Что тоже вроде бы как очевидно. Таким образом мы перебираем все элементы множества.

[arseniiv]

Индукцией вы докажете только для не более чем счётного $S$, а это утверждение верно для любого $S$.

gogoshik в сообщении #1406287 писал(а):

Этот элемент является представителем одноэлементного класса эквивалентности.

Вот по этому пути можно получить простое доказательство даже не от противного. Рассмотрим любой элемент: действительно, он входит в класс элементов, эквивалентных ему (потому что $x\sim x$ из-за рефлексивности $\sim$. И даже не обязательно, входит ли кто-то в тот же класс или нет, мы сразу заткнули все дыры.

Более формально:
Обозначим множество всех классов эквивалентности как $S/{\sim}$. У нас есть отображение $x\mapsto [x]_{\sim}\colon S\to S/{\sim}$, сопоставляющее $x$ класс $[x]_{\sim} := \{y\mid y\sim x, y\in S\}$ из всего ему эквивалентного. Мы видим, что $\{x\}\subset [x]_{\sim}$, тогда если взять слева и справа объединение по всем $x\in S$, то получится $S \subset \bigcup_{x\in S} [x]_{\sim}$. Так как все классы эквивалентности непусты и содержат только элементы $S$, то в правой части объединяются все они, то есть, множество классов $S/{\sim}$ и вправду покрывает $S$.

[gogoshik]

arseniiv в сообщении #1406291 писал(а):

Обозначим множество всех классов эквивалентности как $S/{\sim}$. У нас есть отображение $x\mapsto [x]_{\sim}\colon S\to S/{\sim}$, сопоставляющее $x$ класс $[x]_{\sim} := \{y\mid y\sim x, y\in S\}$ из всего ему эквивалентного. Мы видим, что $\{x\}\subset [x]_{\sim}$, тогда если взять слева и справа объединение по всем $x\in S$, то получится $S \subset \bigcup_{x\in S} [x]_{\sim}$. Так как все классы эквивалентности непусты и содержат только элементы $S$, то в правой части объединяются все они, то есть, множество классов $S/{\sim}$ и вправду покрывает $S$.

Ой! Спасибо! Я как раз к чему-то похожему на Ваше пришел в своих записях, только не осмелился написать.

Кстати, само доказательство, что объединение разных классов эквивалентности образует $S$, я не встречал в книгах. Обычно часто доказывается первое утверждение: разные классы эквивалентности либо не пересекаются, либо совпадают. А потом авторы сразу переходят к понятию факторизации множества, так строго и не обосновав, почему это вдруг фактормножество совпадает с объединением классов эквивалентности. Чтобы спрятать следы бесстыдства, авторы просто приводят следствие из этого факта (может быть и сам факт) в форме определения фактормножества, то есть $S/{\sim} := \mathcal{P}_{\sim}$.

[alcoholist]

фактормножество совпадает с объединением множеством классов эквивалентности

[Connector]

gogoshik в сообщении #1406300 писал(а):

Кстати, само доказательство, что объединение разных классов эквивалентности образует $S$, я не встречал в книгах. Обычно часто доказывается первое утверждение: разные классы эквивалентности либо не пересекаются, либо совпадают. А потом авторы сразу переходят к понятию факторизации множества, так строго и не обосновав, почему это вдруг фактормножество совпадает с объединением классов эквивалентности. Чтобы спрятать следы бесстыдства, авторы просто приводят следствие из этого факта (может быть и сам факт) в форме определения фактормножества, то есть $S/{\sim} := \mathcal{P}_{\sim}$.

А Вы посмотрите
А. Г. Курош, «Лекции по общей алгебре», глава 1, § 3, пункт 2. Там все обстоятельно доказывается.

[gogoshik]

Connector в сообщении #1406304 писал(а):

А. Г. Курош, «Лекции по общей алгебре», глава 1, § 3, пункт 2. Там все хорошо и подробно доказано.

Действительно, на стр. 18 у Куроша всё подробно написано. Чего не читал, того не читал. Я бы не смог так детально выразить доказательство, как это сделал Курош. Спасибо!

[gogoshik]

arseniiv

arseniiv в сообщении #1406032 писал(а):

Плюс параллельно можно проверить, как срабатаывает конкретный пример. Будем рассматривать множество $\mathbb Z$ и отношение эквивалентности такое: $x\sim y$ в том случае, если $x - y$ кратно четырём. (Проверьте, что это эквивалентность, если недостаточно очевидно.) Какие по нему есть классы эквивалентности? Тоже будет ясно, если появляется проблема, где она.

Если я правильно понял, то здесь будет четыре класса эквивалентности. Множество $\mathbb Z$ очевидно разбивается на классы - остатки от деления на четыре: $[0]_{\sim}, ~[1]_{\sim}, ~[2]_{\sim}, ~[3]_{\sim}$.

[Connector]

(Оффтоп)

Извините, что вмешиваюсь в ваш с arseniiv разговор, но тоже хочется помогать решить/разобраться :-)

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

Какому из двух классов принадлежит, по вашему, например, число $6$ ?

UPD. gogoshik
Кстати, эти классы называются классами вычетов по модулю $4$, а само отношение — сравнимостью по модулю $4$

[gogoshik]

Connector
Спасибо. Я ошибся и исправил.