Корректность определения операции

[loser228]

Есть множество классов вычетов по модулю $ m: \mathbb{Z}_m = \left\lbrace \bar{0}, \bar{1}, ..., \overline{m-1} \right\rbrace$. Задаем бинарную операцию на данном множестве $\bar{a} + \bar{b}= \overline{a+b}$. В учебнике пишут, что надо проверить сперва корректность операции (то есть как я понял, надо чтобы результат действия попадал опять в множество $\mathbb{Z}_m$), а в чем может быть некорректность ? То есть если мы (при $m=5$ применим $\bar{3}+ \bar{4} \overset{def} = \overline{3+4}$, то $\overline{7}\notin \mathbb{Z}_5$. Получается , что нужно $a , b $ заменить $c $ и $d$, такими что $a \equiv c \pmod m $, и $b \equiv d \pmod m$ , $c+d \leqslant m-1$, и тогда $\bar{a}+ \bar{b} = \bar{c}+\bar{d} = \overline{c+d}$, а результат правой части уже лежит в $\mathbb{Z}_5$. Правильно я понял ? Если да, то как доказать сей факт ? Не совсем понятно.

a \equiv c \pmod m

[mihaild]

loser228 в сообщении #1187576 писал(а):

а в чем может быть некорректность ?

В том, что могут существовать такие $a_1, a_2, b_1, b_2: \overline{a_1} = \overline{a_2}, \overline{b_1} = \overline{b_2}$, что $\overline{a_1 + b_1} \neq \overline{a_2 + b_2}$. Тогда из нашего определения мы получили бы $\overline{a_1 + b_1} = \overline{a_1} + \overline{b_1} = \overline{a_2} + \overline{b_2} = \overline{a_2 + b_2} \neq \overline{a_1 + b_1}$. Нам нужно доказать, что так не бывает, т.е. $\overline{a_1} = \overline{a_2}, \overline{b_1} = \overline{b_2} \rightarrow \overline{a_1 + b_1} = \overline{a_2 + b_2}$.

$\overline{7}$ конечно лежит в $\mathbb{Z}_5$ - это $\{5k + 2 | k \in \mathbb{Z}\}$.

[loser228]

То есть, как я понял, формально, чтобы посчитать $\bar{3}+\bar{4}$ , мы заменяем $4 \to -1$, и $\bar{3} + \bar{4} = \bar{3} + \overline {-1} = \overline {3-1} = \bar{2}$ ?

[mihaild]

Нет. Формально мы складываем $3$ и $4$, и смотрим, в какой класс попали.

Как у вас определялось кольцо классов вычетов? (что является его элементами?)

[loser228]

Кольцо классов вычетов по модулю $m$ - это множество , состоящее из классов вычетов по модулю $m$(то есть $\bar{0}$ - это множество целых чисел, дающих при делении на $m$ остаток $0$, $\bar{1}$ - остаток $1$ , и так далее до остатка $m-1$ ) ($m>0$)

[Otta]

Ну и хорошо, что будет, если мы к числам с остатком 3 при делении на 5 (это какой элемент?) будем прибавлять числа с остатком 4 при том же делении?

[loser228]

Otta в сообщении #1187588 писал(а):

Ну и хорошо, что будет, если мы к числам с остатком 3 при делении на 5 (это какой элемент?) будем прибавлять числа с остатком 4 при том же делении?

Мы получим числа с остатком $2$ при делении на $5$, то есть элемент класса $\bar{2}$

[ewert]

loser228 в сообщении #1187576 писал(а):

Задаем бинарную операцию на данном множестве $\bar{a} + \bar{b}= \overline{a+b}$

А как именно задаём? Можно ведь делать это разными (эквивалентными) способами.

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

А можно сказать, что сумма вычетов -- это остаток от суммы остатков. Тогда доказывать корректность не надо, но зато придётся возиться с проверкой аксиом.

Первый способ проще и универсальнее.

[loser228]

Судя по всему, задаем именно первым способом. Вообще, принцип доказательства корректности станет для меня понятным, если прояснится одна вещь: $\bar{a} = \bar{b} \Leftrightarrow a \equiv b \pmod m$

[Otta]

loser228 в сообщении #1187589 писал(а):

Мы получим числа с остатком $2$ при делении на $5$, то есть элемент класса $\bar{2}$

А класс $\bar{2}$ включает в себя в том числе и 7. А поскольку обозначаются классы по любому представителю (и понятно, что без разницы по какому), то $\bar{2}$ и $\bar{7}$ это один и тот же класс. То есть неправда, что

loser228 в сообщении #1187576 писал(а):

то $\overline{7}\notin \mathbb{Z}_5$.

По существу основного вопроса Вам уже и без меня хорошо ответили. :)

-- 26.01.2017, 22:31 --

loser228 в сообщении #1187591 писал(а):

если прояснится одна вещь: $\bar{a} = \bar{b} \Leftrightarrow a \equiv b \pmod m$

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

[ewert]

loser228 в сообщении #1187591 писал(а):

если прояснится одна вещь: $\bar{a} = \bar{b} \Leftrightarrow a \equiv b \pmod m$

А что тут прояснять? Это же определение.

Точнее так. Класс вычетов -- это класс эквивалентности по некоторому отношению эквивалентности. Так вот справа ровно определение этого отношения и стоит.

[arseniiv]

Кстати (если это интересует ТС), определение суммы может быть и прямым: $A+B = \{a + b : a\in A, b\in B\}$. Тогда не нужно доказывать корректность, зато нужно вместо этого будет показать, что это действительно класс эквивалентности (что выше, наоборот, выходило по определению), т. е. для всех $c\in A + B$, $c'\in\mathbb Z$ верно $c'\in A+B \Leftrightarrow c\equiv c'\pmod m$ (вправо — в $A+B$ нет ничего лишнего, влево — там есть всё нужное).

-- Сб янв 28, 2017 02:02:15 --

(И мне кажется, с прямым определением жить проще и возни меньше.)

[knizhnik]

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

что это действительно класс эквивалентности

Что именно есть класс эквивалентности?

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

для всех $c\in A + B$, $c'\in\mathbb Z$ верно $c'\in A+B \Leftrightarrow c\equiv c'\pmod m$

Для всех это неверно. Пусть $c \in \bar{0}$ и $c'$ не делится на $m$.

[mihaild]

knizhnik в сообщении #1187880 писал(а):

Что именно есть класс эквивалентности?

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

$\{a + b : a\in A, b\in B\}$.

knizhnik в сообщении #1187880 писал(а):

Пусть $c \in \bar{0}$ и $c'$ не делится на $m$.

Тогда, в зависимости от того, равны ли $A$ и $-B$, будет либо неверно $c \in A+B$, либо $c' \in A+B$.

[knizhnik]

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