Релация 1

[Гост]

Ще казваме, че една релация на еквивалентност ∼ над
Z е конгруентност, ако за всеки a, x, y ∈ Z, от x ∼ y следва, че
a + x ∼ a + y.
а) За всяко ненулево цяло число q ∈ Z, определяме релацията
≡q над Z, чрез x ≡q y точно тогава, когато q дели x − y.
Докажете, че за всяко ненулево q, релацията ≡q е конгруен-
тност;
б) Докажете, че всички конгруентности в Z се изчерпват с ре-
лациите ≡q и диагоналната релация ∆Z = {(z, z) | z ∈ Z}.

Ако може някой да ми я обесни подробно, защото нищо не разбирам от тези релации.

[Knowledge Greedy]

Определението на релация на еквивалетност над [tex]M[/tex], между елементи на дадено множество [tex]M[/tex], включва изпълнението на свойствата: огледалност (рефлексивност), симетричност и преносимост (транзитивност).
[tex]\sim[/tex] е релация на еквивалентност над [tex]M[/tex] [tex]\Leftrightarrow[/tex] [tex]\left \{\begin{matrix}
x \sim x \\
x \sim y \Leftrightarrow y \sim x \\
x \sim y \wedge y \sim z \Rightarrow x \sim z,
\end{matrix}\right .[/tex]
[tex]\forall x, y, z \in M[/tex]

При това, че [tex]M[/tex] се разбива на класове на еквивалентност[tex]^*[/tex] от релацията [tex]\sim[/tex] еднозначно по следния начин.
Два елемента [tex]a_1[/tex] и [tex]a_2[/tex] принадлежат на един клас [tex]A[/tex] на еквивалентност [tex]\Leftrightarrow[/tex] [tex]a_1
\sim a_2[/tex]
Който и да е елемент [tex]a[/tex] на [tex]M[/tex] принадлежи само на един клас на еквивалентност [tex]A[/tex], [tex]A \subset M/\sim[/tex].
Това означава, че ако [tex]A[/tex] и [tex]B[/tex] са различни класове на еквивалентност от [tex]M/\sim[/tex], то [tex]A \cap B = \varnothing[/tex]
___________
[tex]^*[/tex]Класовете на еквивалентност над [tex]M[/tex] означаваме с [tex]M/\sim[/tex]

Сега към задачата.
а) За всяко ненулево цяло число [tex]q ∈ Z[/tex], определяме релацията
[tex]≡q[/tex] над [tex]Z[/tex], чрез [tex]x ≡q y[/tex] точно тогава, когато [tex]q[/tex] дели [tex]x − y[/tex].
Докажете, че за всяко ненулево [tex]q[/tex], релацията [tex]≡q[/tex] е конгруентост.
Доказателство.
1.1. Правим проверка, че релацията [tex]≡q[/tex] има свойството рефлексивност.
Наистина, ако [tex]m \in \mathbb{Z}[/tex], [tex]m ≡q m[/tex] точно тогава, когато [tex]q[/tex] дели [tex]0 = m − m.[/tex]
1.2. Правим проверка, че релацията [tex]≡q[/tex] има свойството симетричност.
Наистина, ако [tex]m \in \mathbb{Z}[/tex] и [tex]n \in \mathbb{Z}[/tex], то [tex]m ≡q n[/tex] точно тогава, когато [tex]q[/tex] дели [tex]m − n.[/tex] Но последното означава, че [tex]q[/tex] дели и противоположното му, т.е [tex]q[/tex] дели [tex]n − m.[/tex]
Съгласно определението на [tex]≡q[/tex], последното означава, че [tex]n ≡q m,[/tex] Доказано е и второто свойство.
1.3. Правим проверка, че релацията [tex]≡q[/tex] има свойството транзитивност.
Наистина, ако [tex]m \in \mathbb{Z}[/tex], [tex]n \in \mathbb{Z}[/tex] и [tex]p \in \mathbb{Z}[/tex], като [tex]m ≡q n[/tex] и [tex]n ≡q p[/tex].
Съгласно определението [tex]q[/tex] дели [tex]m - n[/tex] и [tex]q[/tex] дели [tex]n - p[/tex]. Това означава, че [tex]q[/tex] дели и техния сбор [tex]m - n + (n - p)= m-p[/tex]. Но щом [tex]q[/tex] дели [tex]m-p[/tex], според определението означава, че [tex]m ≡q p[/tex]. Транзитивността е доказана.
Така доказахме, че [tex]≡q[/tex] е релация на еквивалентност.
Тази релация на еквивалентност поражда разбиване на [tex]\mathbb{Z}[/tex] на класовете на еквивалентност [tex]Z/≡q[/tex]
2. Чрез определящото свойство на релацията [tex]≡q[/tex] доказваме, че тя е конгруентност, за някое [tex]q \ne 0[/tex].
Нека [tex]a \in \mathbb{Z}[/tex].
Да разгледаме произволни два елемента [tex]x[/tex] и [tex]y[/tex] принадлежащи на един и същ клас на еквивалентност, т.е. [tex]x ≡q y[/tex]
Това означава още, че [tex]q[/tex] дели [tex](x - y)[/tex].
Следователно [tex]q[/tex] дели и [tex](x + a - ( y + a))[/tex]. Според определението на [tex]≡q[/tex] следва [tex]x + a ≡q (y+a)[/tex], а това означава, че [tex]≡q[/tex] е конгруентност. (Тук не е задължително [tex]x + a[/tex] и [tex]y+a[/tex] да са от същия клас на еквивалентност, на който принадлежаха [tex]x[/tex] и [tex]y[/tex].)

В подусловие б) се изброяват всички възможни конгруентности при фиксирано [tex]q \in \mathbb{Z}[/tex]
Оказва се, че те са точно [tex]q[/tex] на брой.

[Гост]

...В подусловие б) се изброяват всички възможни конгруентности при фиксирано [tex]q \in \mathbb{Z}[/tex]
Оказва се, че те са точно [tex]q[/tex] на брой.

Въобще не е така. Всъщност в б) се твърди следното: Ако имаме една релация на конгруентност, то или това е идентитета, или съществува $q\in \mathbb{Z}$, такова че дадената релация съвпада с $\equiv q$.

[Гост]

Леле колко сте умни и какви умни неща пишете

[Гост]

A, ми не. Просто използваме сложни думички да се правим на по-интелигентни, отколко сме

[Гост]

A, ми не. Просто използваме сложни думички да се правим на по-интелигентни, отколко сме

Не харесвате миризмата на овчи тор?
- Не се приближавайте до кошарата

[Knowledge Greedy]

Дефиниране на конгруентност

...В подусловие б) се изброяват всички ...

Въобще не е така. Всъщност в б) се твърди следното: Ако имаме една релация на конгруентност, то или това е идентитета, или съществува [tex]q∈Z[/tex], такова че дадената релация съвпада с [tex]≡q[/tex].

Съгласен съм. Написал съм нелепост. За да бъде доказано:
"б) Докажете, че всички конгруентности в [tex]Z[/tex] се изчерпват с ре-
лацията [tex]≡q[/tex] и диагоналната релация ∆Z = {(z, z) | z ∈ Z}."
следва да проверим:
- че релацията [tex]∆Z = {(z, z) | z ∈ Z}[/tex] (отговаряща на идентитета) изпълнява условието на конгруентността - това е лесно проверимо;
- че, ако съществува релация на конгруентност [tex]\equiv q[/tex] в [tex]\mathbb{Z}[/tex],тя може да бъде построена с всеки елемент [tex]q \ne 0[/tex], [tex]q\in \mathbb{Z}[/tex] - това направихме в подусловие а);
- друга възможност според зададеното условие няма.

[Гост]

@Knowledge Greedy: Не виждам къде е доказан следния факт:
Ако $\sim$ е релация на еквивалентност и е инвариантна относно транслацията(т.е. според горната терминология е релация на конгруентност), то или $\sim$ e идентитета, или съществува $q\in \mathbb{N}$, такова че $\sim$ съвпада с $\,\equiv \pmod q$.