Difference between revisions of "Invariant of an equivalence relation"

Latest revision as of 18:58, 9 November 2016

Note: see invariant for other uses of the term.

Definition

Let $S$ be a set and let $\sim\subseteq S\times S$ be an equivalence relation^{[Note 1]} on $S$, let $W$^{[Note 2]} be any set and let $f:S\rightarrow W$ be any function from $S$ to $W$. Then^[1]:

• We say "$f$ is an invariant of $\sim$" if^{[Note 3]}:
  • $\forall a,b\in S[a\sim b\implies f(a)=f(b)]$ - in other words, $f$ is constant on the equivalence classes of $\sim$.

Complete invariant

With the setup of $S$, $W$, $\sim$ and $f:S\rightarrow W$ as above define a "complete invariant" as follows^[1]:

• "$f$ is a complete invariant of $\sim$" if^{[Note 3]}:
  • $\forall a,b\in S[a\sim b\iff f(a)=f(b)]$ - in other words, $f$ is constant on and distinct on the equivalence classes of $\sim$.

Terminology

It's hard to be formal in English, however we may say any of the following:

• "$f$ is an invariant of $\sim$"^[1]
• "$\sim$ is invariant under $f$"
  • This makes sense as we're saying the $a\sim b$ property holds (doesn't vary) "under" (think "image of $A$ under $f$"-like terminology) $f$, that $f(a)=f(b)$
• "$\sim$ invariance of $f$"
  • This works better when the relations have names, eg "equality invariance of Alec's heuristic" (that's a made up example) and this would be a proposition or a claim.

Examples and instances

• Homotopy invariance of path concatenation
  • Homotopy invariance of loop concatenation

TODO: Create a category and start collecting

See also

• Complete system of invariants - a finite set of complete invariants really.
• Set of canonical forms - a subset of $S$, $C\in\mathcal{P}(S)$, such that there exists a unique $c\in C$ such that $c\sim s$
  • An equivalent condition to the axiom of choice is that every partition has a set of representatives that's closely related. Be warned

Notes

1. Jump up ↑ keep in mind that equality is itself an equivalence relation
2. Jump up ↑ Think of $W$ as $W\text{hatever}$ - as usual (except in Linear Algebra where $W$ is quite often used for vector spaces
3. ↑ ^{Jump up to: 3.0 3.1} See "definitions and iff"

References

1. ↑ ^{Jump up to: 1.0 1.1 1.2} Advanced Linear Algebra - Steven Roman