Equivalence relation

The equivalence relation is an abstract binary relation between the elements of a given set, which behaves similarly to the equality relation .

Content

Definition

Equivalence relation ( $\sim$ ${\ displaystyle \ sim}$ ) on the set $X$ ${\ displaystyle X}$ Is a binary relation for which the following conditions are met:

reflexivity : $a\sim a$ ${\ displaystyle a \ sim a}$ for anyone $a$ ${\ displaystyle a}$ at $X$ ${\ displaystyle X}$ ;
symmetry : if $a\sim b$ ${\ displaystyle a \ sim b}$ then $b\sim a$ ${\ displaystyle b \ sim a}$ ;
transitivity : if $a\sim b$ ${\ displaystyle a \ sim b}$ and $b\sim c$ ${\ displaystyle b \ sim c}$ then $a\sim c$ ${\ displaystyle a \ sim c}$ .

Record of the form " $a\sim b$ ${\ displaystyle a \ sim b}$ "Reads like" $a$ ${\ displaystyle a}$ is equivalent to $b$ ${\ displaystyle b}$ ".

Related definitions

Equivalence class $[a]\subset X$ ${\ displaystyle [a] \ subset X}$ element $a\in X$ ${\ displaystyle a \ in X}$ called a subset of elements equivalent $a$ ${\ displaystyle a}$ ; i.e,

[a]=\{\,x\in X\mid x\sim a\,\}

{\ displaystyle [a] = \ {\, x \ in X \ mid x \ sim a \, \}}

.

From the above definition it immediately follows that if $b\in [a]$ ${\ displaystyle b \ in [a]}$ then $[a]=[b]$ ${\ displaystyle [a] = [b]}$ .

The quotient set is the set of all equivalence classes of a given set $X$ ${\ displaystyle X}$ for a given ratio $\sim$ ${\ displaystyle \ sim}$ denoted by $X/{\sim }$ ${\ displaystyle X / {\ sim}}$ .

For element equivalence class $a$ ${\ displaystyle a}$ The following notation is used: $[a]$ ${\ displaystyle [a]}$ , $a/{\sim }$ ${\ displaystyle a / {\ sim}}$ , ${\overline {a}}$ ${\ displaystyle {\ overline {a}}}$ .

Set of equivalence classes with respect to $\sim$ ${\ displaystyle \ sim}$ is a partitioning set .

Examples

Equality (" $\;=$ ${\ displaystyle \; =}$ "), A trivial equivalence relation on any set, in particular, real numbers .
Comparison modulo (“a ≡ b (mod n)”).
In euclidean geometry
- Congruence ratio (" $\cong$ ${\ displaystyle \ cong}$ ").
- Attitude of similarity (" $\ \sim$ ${\ displaystyle \ \ sim}$ ").
- The ratio of parallel lines (" $\|$ ${\ displaystyle \ |}$ ").
Equivalence of functions in mathematical analysis :
It is said that the function $f(x)$ ${\ displaystyle f (x)}$ equivalent to function $g(x)$ ${\ displaystyle g (x)}$ at $x\rightarrow x_{0}$ ${\ displaystyle x \ rightarrow x_ {0}}$ if it allows view $f(x)=\alpha (x)g(x)$ ${\ displaystyle f (x) = \ alpha (x) g (x)}$ where $\alpha (x)\rightarrow 1$ ${\ displaystyle \ alpha (x) \ rightarrow 1}$ at $x\rightarrow x_{0}$ ${\ displaystyle x \ rightarrow x_ {0}}$ . In this case, write $f(x)\sim g(x)$ ${\ displaystyle f (x) \ sim g (x)}$ , recalling, if necessary, that this is a comparison of functions with $x\rightarrow x_{0}$ ${\ displaystyle x \ rightarrow x_ {0}}$ . If a $g(x)\neq 0$ ${\ displaystyle g (x) \ neq 0}$ at $x\neq x_{0}$ ${\ displaystyle x \ neq x_ {0}}$ equivalence of functions $f(x)$ ${\ displaystyle f (x)}$ and $g(x)$ ${\ displaystyle g (x)}$ at $x\rightarrow x_{0}$ ${\ displaystyle x \ rightarrow x_ {0}}$ obviously equivalent to the ratio $\lim _{x\rightarrow x_{0}}{\frac {f(x)}{g(x)}}=1$ ${\ displaystyle \ lim _ {x \ rightarrow x_ {0}} {\ frac {f (x)} {g (x)}} = 1}$ .
Equivalence of norms on vector space.
The ratio of equal power sets.
Isomorphism of groups , rings , vector spaces
Category equivalence .
Isomorphism in a certain category defines an equivalence relation on this category.

Equivalence classes

The set of all equivalence classes corresponding to the equivalence relation $\sim$ ${\ displaystyle \ sim}$ denoted by $X/{\sim }$ ${\ displaystyle X / {\ sim}}$ and is called factor set with respect to $\sim$ ${\ displaystyle \ sim}$ . In this case, the surjective mapping

p\colon x\mapsto [x]

{\ displaystyle p \ colon x \ mapsto [x]}

called natural mapping (or canonical projection ) $X$ ${\ displaystyle X}$ on the factor set $X/{\sim }$ ${\ displaystyle X / {\ sim}}$ .

Let be $X$ ${\ displaystyle X}$ and $Y$ ${\ displaystyle Y}$ - sets $f\colon X\to Y$ ${\ displaystyle f \ colon X \ to Y}$ - mapping, then binary relation $x\sim y$ ${\ displaystyle x \ sim y}$ defined by rule

x\sim y\iff f(x)=f(y),\quad x,y\in X

{\ displaystyle x \ sim y \ iff f (x) = f (y), \ quad x, y \ in X}

,

is an equivalence relation on $X$ ${\ displaystyle X}$ . With this mapping $f$ ${\ displaystyle f}$ induces mapping ${\overline {f}}\colon X/{\sim }\to Y$ ${\ displaystyle {\ overline {f}} \ colon X / {\ sim} \ to Y}$ defined by rule

{\overline {f}}([x])=f(x)

{\ displaystyle {\ overline {f}} ([x]) = f (x)}

or, which is the same,

({\overline {f}}\circ p)(x)=f(x)

{\ displaystyle ({\ overline {f}} \ circ p) (x) = f (x)}

.

This results in a mapping factorization . $f$ ${\ displaystyle f}$ on a surjective mapping $p$ ${\ displaystyle p}$ and injective mapping ${\overline {f}}$ ${\ displaystyle {\ overline {f}}}$ .

Literature

A. I. Kostrikin , Introduction to Algebra. M .: Science, 1977, 47-51.
A.I. Maltsev , Algebraic systems, Moscow : Nauka, 1970, 23-30.
Equality type relation (equivalence relation) // Big Soviet Encyclopedia (in 30 tons) / A. M. Prokhorov (ch. Red.). - 3rd ed. - M: Owls. Encyclopedia, 1974. - T. XVIII. - p. 629. - 632 p.