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.
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/.