Difference between revisions of "Invariant of an equivalence relation"
From Maths
(Created page with "{{Stub page|grade=A|msg=Find more references and flesh out}} ==Definition== Let {{M|S}} be a set and let {{M|\sim\subseteq S\times S}} be an equivalence relation on {{...") |
m (→Terminology: Adding third encountered term with justification) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | : '''Note: ''' see [[invariant]] for other uses of the term. | ||
{{Stub page|grade=A|msg=Find more references and flesh out}} | {{Stub page|grade=A|msg=Find more references and flesh out}} | ||
| + | __TOC__ | ||
==Definition== | ==Definition== | ||
| − | Let {{M|S}} be a [[set]] and let {{M|\sim\subseteq S\times S}} be an [[equivalence relation]] on {{M|S}}, let {{M|W}}<ref group="Note">Think of {{M|W}} as {{M|W\text{hatever} }} - as usual (except in [[Linear Algebra (subject)|Linear Algebra]] where {{M|W}} is quite often used for [[vector spaces]]</ref> be any set and let {{M|f:S\rightarrow W}} be any [[function]] from {{M|S}} to {{M|W}}. Then{{rALASR}}: | + | Let {{M|S}} be a [[set]] and let {{M|\sim\subseteq S\times S}} be an [[equivalence relation]]<ref group="Note">keep in mind that [[equality]] is itself an equivalence relation</ref> on {{M|S}}, let {{M|W}}<ref group="Note">Think of {{M|W}} as {{M|W\text{hatever} }} - as usual (except in [[Linear Algebra (subject)|Linear Algebra]] where {{M|W}} is quite often used for [[vector spaces]]</ref> be any set and let {{M|f:S\rightarrow W}} be any [[function]] from {{M|S}} to {{M|W}}. Then{{rALASR}}: |
* We say "{{M|f}}'' is an invariant of ''{{M|\sim}}" if<ref group="Note" name="definition">See "''[[definitions and iff]]''"</ref>: | * We say "{{M|f}}'' is an invariant of ''{{M|\sim}}" if<ref group="Note" name="definition">See "''[[definitions and iff]]''"</ref>: | ||
** {{M|1=\forall a,b\in S[a\sim b\implies f(a)=f(b)]}} - in other words, {{M|f}} is [[constant on]] the [[equivalence classes]] of {{M|\sim}}. | ** {{M|1=\forall a,b\in S[a\sim b\implies f(a)=f(b)]}} - in other words, {{M|f}} is [[constant on]] the [[equivalence classes]] of {{M|\sim}}. | ||
| Line 13: | Line 15: | ||
* "''{{M|\sim}} is invariant under {{M|f}}''" | * "''{{M|\sim}} is invariant under {{M|f}}''" | ||
** This makes sense as we're saying the {{M|a\sim b}} property holds (doesn't vary) "under" (think "image of {{M|A}} under {{M|f}}"-like terminology) {{M|f}}, that {{M|1=f(a)=f(b)}} | ** This makes sense as we're saying the {{M|a\sim b}} property holds (doesn't vary) "under" (think "image of {{M|A}} under {{M|f}}"-like terminology) {{M|f}}, that {{M|1=f(a)=f(b)}} | ||
| + | * "''{{M|\sim}} invariance of {{M|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== | ==Examples and instances== | ||
* [[Homotopy invariance of path concatenation]] | * [[Homotopy invariance of path concatenation]] | ||
Latest revision as of 18:58, 9 November 2016
- Note: see invariant for other uses of the term.
Stub grade: A
This page is a stub
This page is a stub, so it contains little or minimal information and is on a to-do list for being expanded.The message provided is:
Find more references and flesh out
Contents
Definition
Let [ilmath]S[/ilmath] be a set and let [ilmath]\sim\subseteq S\times S[/ilmath] be an equivalence relation[Note 1] on [ilmath]S[/ilmath], let [ilmath]W[/ilmath][Note 2] be any set and let [ilmath]f:S\rightarrow W[/ilmath] be any function from [ilmath]S[/ilmath] to [ilmath]W[/ilmath]. Then[1]:
- We say "[ilmath]f[/ilmath] is an invariant of [ilmath]\sim[/ilmath]" if[Note 3]:
- [ilmath]\forall a,b\in S[a\sim b\implies f(a)=f(b)][/ilmath] - in other words, [ilmath]f[/ilmath] is constant on the equivalence classes of [ilmath]\sim[/ilmath].
Complete invariant
With the setup of [ilmath]S[/ilmath], [ilmath]W[/ilmath], [ilmath]\sim[/ilmath] and [ilmath]f:S\rightarrow W[/ilmath] as above define a "complete invariant" as follows[1]:
- "[ilmath]f[/ilmath] is a complete invariant of [ilmath]\sim[/ilmath]" if[Note 3]:
- [ilmath]\forall a,b\in S[a\sim b\iff f(a)=f(b)][/ilmath] - in other words, [ilmath]f[/ilmath] is constant on and distinct on the equivalence classes of [ilmath]\sim[/ilmath].
Terminology
It's hard to be formal in English, however we may say any of the following:
- "[ilmath]f[/ilmath] is an invariant of [ilmath]\sim[/ilmath]"[1]
- "[ilmath]\sim[/ilmath] is invariant under [ilmath]f[/ilmath]"
- This makes sense as we're saying the [ilmath]a\sim b[/ilmath] property holds (doesn't vary) "under" (think "image of [ilmath]A[/ilmath] under [ilmath]f[/ilmath]"-like terminology) [ilmath]f[/ilmath], that [ilmath]f(a)=f(b)[/ilmath]
- "[ilmath]\sim[/ilmath] invariance of [ilmath]f[/ilmath]"
- 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
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 [ilmath]S[/ilmath], [ilmath]C\in\mathcal{P}(S)[/ilmath], such that there exists a unique [ilmath]c\in C[/ilmath] such that [ilmath]c\sim s[/ilmath]
- An equivalent condition to the axiom of choice is that every partition has a set of representatives that's closely related. Be warned
Notes
- ↑ keep in mind that equality is itself an equivalence relation
- ↑ Think of [ilmath]W[/ilmath] as [ilmath]W\text{hatever} [/ilmath] - as usual (except in Linear Algebra where [ilmath]W[/ilmath] is quite often used for vector spaces
- ↑ 3.0 3.1 See "definitions and iff"
References
Grade: A
This page requires references, it is on a to-do list for being expanded with them.
Please note that this does not mean the content is unreliable, it just means that the author of the page doesn't have a book to hand, or remember the book to find it, which would have been a suitable reference.
The message provided is:
The message provided is:
More on the fundamentals of mathematics would be good
