Difference between revisions of "Equivalence class"

From CS2800 wiki
Line 1: Line 1:
 +
<noinclude>[[Category:Relations]]</noinclude>
 
Consider the following [[equivalence relation]] <math>R</math> on the set <math>A := \{a,b,c,d,e,f\}</math>:
 
Consider the following [[equivalence relation]] <math>R</math> on the set <math>A := \{a,b,c,d,e,f\}</math>:
  

Revision as of 17:45, 19 September 2018

Consider the following equivalence relation [math]R [/math] on the set [math]A := \{a,b,c,d,e,f\} [/math]:

Equivalence-relation.svg

Notice that the elements of [math]A [/math] are split up into three groups, with everything in one group related to everything else in the same group, and nothing in one group related to anything in any other group.

In this example, the three groups are [math]\{a,b,c\} [/math], [math]\{d,e\} [/math] and [math]\{f\} [/math].

In fact, this is a general phenomenon, and the groups often represent something important. For example, if [math]A [/math] were a set of people and R was the is-related-to relation, then the groups of related people would be called "families".

In general, the groups are referred to as equivalence classes. Formally, we have the following definition:


Definition: Equivalence class
If [math]R [/math] is an equivalence relation on a set [math]A [/math], then the equivalence class of [math]a [/math] by [math]R [/math] (written [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7_R}{⟦a⟧_R} [/math]) is the set of elements [math]b \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] with [math]\href{/cs2800/wiki/index.php/ARb}{aRb} [/math].


In other words, [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7_R}{⟦a⟧_R} \href{/cs2800/wiki/index.php/Definition}{:=} \{b \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A \href{/cs2800/wiki/index.php/%5Cmid}{\mid} \href{/cs2800/wiki/index.php/ARb}{aRb}\} [/math]

Note: I usually use the symbols [ and ] instead of ⟦ and ⟧, but the wiki syntax makes this difficult. You may use either notation.

When [math]R [/math] is clear from context, we just write ⟦a⟧.

In the above example, we have three equivalence classes: [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} = \{a,b,c\} = \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} = \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦c⟧} [/math], [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦d⟧} = \{d,e\} = \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦e⟧} [/math], and [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦f⟧} = \{f\} [/math].


Definition: A/R
If [math]R [/math] is an equivalence relation on a set [math]A [/math], then A mod R (written [math]\href{/cs2800/wiki/index.php/A/R}{A/R} [/math]) is the set of all equivalence classes of [math]A [/math] by [math]R [/math]. In other words, [math]\href{/cs2800/wiki/index.php/A/R}{A/R} := \{\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A\} [/math].

Continuing the above example, we have [math]\href{/cs2800/wiki/index.php/A/R}{A/R} = \{\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧}, \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦d⟧}, \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦f⟧}\} [/math]. Note that [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} [/math] is also in [math]\href{/cs2800/wiki/index.php/A/R}{A/R} [/math], but we don't need to list it separately, since it is equal to [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} [/math].

One more piece of terminology:


Definition: representative
If [math]c \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/A/R}{A/R} [/math] is an equivalence class of [math]A [/math] by [math]R [/math], and [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math], we say that [math]a [/math] is a representative of [math]c [/math] if [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} c [/math]. Note that [math]a [/math] is a representative of [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} [/math].