Ekvivalence reláció

Ekvivalens állítások

• $A \equiv B\ (\text{mod }C)$A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
• $A \text{ mod } C = B \text{ mod }C$A, start text, space, m, o, d, space, end text, C, equals, B, start text, space, m, o, d, space, end text, C
• $C \ |\ (A - B)$C, space, vertical bar, space, left parenthesis, A, minus, B, right parenthesis (A „|” jel itt azt jelenti: osztója)
• $A = B + K \cdot C$A, equals, B, plus, K, dot, C (ahol $K$K egész szám)

• $13 \equiv 23\ (\text{mod }5)$13, \equiv, 23, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis
• $13 \text{ mod } 5 = 23 \text{ mod }5$13, start text, space, m, o, d, space, end text, 5, equals, 23, start text, space, m, o, d, space, end text, 5
• $5 \ |\ (13 - 23)$5, space, vertical bar, space, left parenthesis, 13, minus, 23, right parenthesis ( $5 \ |\ -10$5, space, vertical bar, space, minus, 10, ami igaz, mert ${5 \times (-2) = -10}$5, times, left parenthesis, minus, 2, right parenthesis, equals, minus, 10 )
• $13 = 23 + K \cdot 5$13, equals, 23, plus, K, dot, 5. Ez teljesülni fog $\bf{K = -2}$K, equals, minus, 2-re: $13 = 23 + (-2) \cdot 5$13, equals, 23, plus, left parenthesis, minus, 2, right parenthesis, dot, 5

A kongruens modulo egy ekvivalencia művelet

• Az egyes szeletekhez tartozó értékpárok között kapcsolat van.
• Nincs olyan érték, ami két szeletben is megtalálható (a szeletek kölcsönösen diszjunktak, vagyis szétválaszthatók).
• Ha egyesítjük az összes szeletet, akkor a kapott halmaz tartalmazni fogja az összes számot.

• A kör: a vizsgált értékek gyűjteménye.
• A körszelet: egy ekvivalencia osztály.
• A körszelet felosztása: ekvivalencia reláció.

• A kör: az összes egész szám.
• A $B$B-vel jelölt körszelet: az az ekvivalencia osztály, ahol $\text{mod } C = B$start text, m, o, d, space, end text, C, equals, B.
• A kör felszeletelése: a kongruens modulo C relációval, $\equiv (\text{mod } C)$\equiv, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis.

Miért fontos az, hogy a kongruens modulo C ekvivalencia reláció ?

• reflexív: A ekvivalens A-val.
• szimmetrikus: ha A ekvivalens B-vel, akkor B ekvivalens A-val.
• tranzitív: ha A ekvivalens B-vel és B ekvivalens C-vel, akkor A ekvivalens C-vel.

• $A \equiv A \ (\text{mod } C)$A, \equiv, A, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
• ha $A \equiv B \ (\text{mod }C)$A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis, akkor $B \equiv A \ (\text{mod }C)$B, \equiv, A, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
• ha $A \equiv \bf{B} \ (\text{mod } C)$A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis és $\bf{B} \equiv D \ (\text{mod } C)$B, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis, akkor $\bf{A \equiv D} \ (\text{mod } C)$A, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis

Példa

• $3 \equiv 3\ (\text{mod } 5)$3, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (reflexivitás)
• ha $3 \equiv 8\ (\text{mod } 5)$3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis, akkor $8 \equiv 3\ (\text{mod }5)$8, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (szimmetria)
• ha $3 \equiv 8\ (\text{mod }5)$3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis és $8 \equiv 18\ (\text{mod }5)$8, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis, akkor $3 \equiv 18\ (\text{mod }5)$3, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (tranzitivitás)