Relations and Equivalence Classes TODO
Concept
A binary relation on a set is defined as a subset of the Cartesian product — it enumerates which pairs of elements are related. A relation that satisfies reflexivity, symmetry, and transitivity all at once is an equivalence relation. An equivalence relation splits a set into disjoint equivalence classes, and conversely any partition defines an equivalence relation, so the two correspond one-to-one. The set of all equivalence classes is called the quotient set, and an operation defined on the quotient set is well-defined only if the result doesn't depend on which representative element you pick. Congruence modulo n on the integers is the canonical equivalence relation, and its equivalence classes are the residue classes.
Deciding what counts as "the same" is the essence of deduplication, cache keys, and replay protection, and if the criterion you pick breaks symmetry or transitivity, that's a bug waiting to happen.
Code & Formula
# 관계와 동치류 — 정수의 "mod n 합동"이 동치관계임을 반사·대칭·추이성으로 검증하고,
# 그 동치류(잉여류)들이 원래 집합을 서로소인 조각들로 정확히 파티션함을 확인.
MOD = 5
universe = list(range(-6, 12)) # 동치관계 검증에 쓸 표본 집합
def related(a, b):
return (a - b) % MOD == 0
def is_reflexive(xs):
return all(related(x, x) for x in xs)
def is_symmetric(xs):
return all(related(a, b) == related(b, a) for a in xs for b in xs)
def is_transitive(xs):
return all(
not (related(a, b) and related(b, c)) or related(a, c)
for a in xs for b in xs for c in xs
)
print(f"mod {MOD} 합동 관계 검증 (표본 {len(universe)}개):")
print(" 반사성 :", is_reflexive(universe))
print(" 대칭성 :", is_symmetric(universe))
print(" 추이성 :", is_transitive(universe))
# 동치류(잉여류) 계산: 같은 나머지를 갖는 원소끼리 묶는다.
classes = {r: [] for r in range(MOD)}
for x in universe:
classes[x % MOD].append(x)
print(f"\n{MOD}개의 동치류(잉여류)로 파티션:")
for r, members in classes.items():
print(f" [{r}] = {members}")
# 파티션 검증: 동치류들이 서로소이고, 합쳐서 universe 전체가 되는지.
all_members = [x for members in classes.values() for x in members]
pairwise_disjoint = len(all_members) == len(set(all_members))
covers_universe = set(all_members) == set(universe)
print("\n서로소(중복 없음)?", pairwise_disjoint, " / 전체를 덮음?", covers_universe)
Exercise
Pick a criterion for treating two orders or transactions as "the same," verify reflexivity, symmetry, and transitivity for it, and construct a counterexample where transitivity breaks.
Practical Connection
Transaction-hash- or nonce-based duplicate detection, and merging equivalent states in a state machine, are all instances of equivalence classes — and in Verex, the identifiers used to point at "the same market" or "the same outcome" are themselves a definition of what counts as equal.
Where it lands in Jayverse
- Verex: write out, and test, what defines "same market" and "same outcome." Formally check reflexivity, symmetry and transitivity for the chosen equality fields, and add a counterexample test (same question, different resolution source) that must NOT be treated as equal.
- Rabbit/Wallet: test transitivity specifically for nonce/tx-hash replay protection. A dedup rule that is reflexive and symmetric but not transitive can still merge two different transactions as "equivalent" — add a test that catches this shape directly.
- Bridge: define "same transfer" across the lock and mint legs as an explicit relation. State which fields must match for a retry to be treated as the same transfer as an earlier one, so dedup logic can't accidentally collapse two different transfers into one.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| enumerate | 낱낱이 열거하다, 하나씩 나열하다 · 집합의 원소나 쌍을 빠짐없이 나타낼 때. "it enumerates which pairs of elements are related" |
| correspond one-to-one | 일대일로 대응하다 · 두 개념 사이에 정확히 짝이 맞아떨어질 때. "the two correspond one-to-one" |
| well-defined | (수학적으로) 잘 정의된 · 결과가 대표 원소 선택에 따라 달라지지 않을 때. "well-defined only if the result doesn't depend on which representative" |
| representative (element) | 대표 원소 · 한 동치류를 대표해서 고르는 원소. "which representative element you pick" |
| disjoint | 서로 겹치지 않는 · 집합들이 공통 원소 없이 나뉠 때. "disjoint equivalence classes" |
| canonical | 전형적인, 대표적인 · 해당 개념을 가장 잘 보여주는 표준 사례를 가리킬 때. "the canonical equivalence relation" |
| essence of | ~의 본질 · 어떤 실무 문제의 핵심이 사실 이 개념이라고 짚을 때. "the essence of deduplication, cache keys, and replay protection" |
| Cartesian product | 데카르트 곱(Cartesian product) · 두 집합의 모든 순서쌍을 모은 집합, 이진관계는 이 곱집합의 부분집합으로 정의됨. "a subset of the Cartesian product" |
| quotient set | 몫집합(quotient set) · 한 집합을 동치관계로 나눴을 때 생기는 모든 동치류들의 집합. "is called the quotient set" |
| residue class | 잉여류(residue class) · 정수를 n으로 나눈 나머지가 같은 원소들의 동치류, congruence modulo n의 구체적 예. "its equivalence classes are the residue classes" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.