Problem with defintion of an equivalence relation induced by an arbitrary class

45 Views Asked by At

I think I have a problem with a definition of an equivalence relation induced by an arbitrary class - I am not sure where I picked the definition up from, indeed I may even have made it up and convinced myself I had seen it somewhere;

Definition (wrong?)

For an arbitrary class $\mathcal{A}$ of subsets of $\Omega$ let $\omega'\sim_{\mathcal{A}}\omega''$ denote that $\omega'$ is equivalent to $\omega''$ (mod $\mathcal{A}$);

$\omega'\equiv\omega''(\text{mod }\mathcal{A})\iff 1_{A}(\omega')=1_{A}(\omega''),\forall A\in\mathcal{A}$

Then $\sim_{\mathcal{A}}$ is an equivalence relation on $\Omega$ induced by the class $\mathcal{A}$, where $[w]_{\mathcal{A}}$ denotes the equivalence class represented by $\omega$, that is $\omega'\sim_{\mathcal{A}}\omega$ for all $\omega\in [w]_{\mathcal{A}}$. Let the class of all equivalence classes (the quotient set) be denoted $\Omega\backslash \sim_{\mathcal{A}}:=\{[w]_{\mathcal{A}}:\omega\in\Omega\}$. Since $\sim_{\mathcal{A}}$ is an equivalence relation then it partitions $\Omega$, that is $\Omega=\dot{\cup}_{[w]_{\mathcal{A}}\in \{\Omega\backslash \sim_{\mathcal{A}}\}}[w]_{\mathcal{A}}$ where the dot denotes a disjoint union.

I mention here my understanding about duplicate equivalence classes given the statement about partitions (and partitions become my issue a little later): Although $\omega\sim_{\mathcal{A}}\omega'$ implies $[w]_{\mathcal{A}}=[w']_{\mathcal{A}}$, the quotient set $\Omega\backslash \sim_{\mathcal{A}}$ is, from a set theoretic perspective, still always a disjoint collection of equivalence classes since $\Omega\backslash \sim_{\mathcal{A}}$ is just a set (where the elements are sets), and sets do not "recognise" duplication (i.e the set $B=\{a,a,b\}$ satisfies the axiom [?] that $a\in B \Longleftrightarrow \exists a\in B$ is true, even though there is duplication of the element $a$). My understanding may be off here, although I do not see the quotient set being explicitly defined to contain only the unique equivalence classes so I figure the definition of a set does the work behind the scenes?.

So what is the problem with the above definition of $\sim_{\mathcal{A}}$? Suppose $\Omega=\{\omega_{1},\omega_{2},\omega_{3},\omega_{4}\}$ and $\mathcal{A}=\{A_{1},A_{2},A_{3}\}$ where $A_{1}=\{\omega_{1},\omega_{2}\}$, $A_{2}=\{\omega_{1},\omega_{2},\omega_{4}\}$ and $A_{3}=\{\omega_{2}\}$. Then using the above definition $[w_{1}]_{\mathcal{A}}=\{\omega_{1}\}$, $[w_{2}]_{\mathcal{A}}=\{\omega_{2}\}$, $[w_{3}]_{\mathcal{A}}=\emptyset$ and $[w_{4}]_{\mathcal{A}}=\{\omega_{4}\}$ and so $\Omega\backslash \sim_{\mathcal{A}}=\{\emptyset,\{\omega_{1}\},\{\omega_{2}\},\{\omega_{4}\}\}$. The problem here is that $\omega_{4}\not\in\Omega\backslash \sim_{\mathcal{A}}$ so $\Omega\backslash \sim_{\mathcal{A}}$ does not partition $\Omega$. I have seen another definition of the relation $\sim_{\mathcal{A}}$ that states (again I cannot recall where);

Definition (correct?)

$[\omega]_{\mathcal{A}}:=\bigcap\{A:\omega\in A\in\mathcal{A}\}\cap\bigcap\{\Omega\backslash A:\omega\not\in A\in\mathcal{A}\}$

If I apply this definition I get $[w_{3}]_{\mathcal{A}}=A_{1}^{c}\cap A_{2}^{c}\cap A_{3}^{c}=\{\omega_{3},\omega_{4}\}\cap \{\omega_{3}\}\cap\{\omega_{1},\omega_{3},\omega_{4}\}=\{\omega_{3}\}$. The other equivalence classes remain the same as before and so $\Omega\backslash \sim_{\mathcal{A}}=\{\{\omega_{1}\},\{\omega_{2}\},\{\omega_{3}\},\{\omega_{4}\}\}$ which is a partition of $\Omega$ (the finest partition).

My question therefore is what is missing form the first definition, since the second must be correct given it produces a partition as claimed by the theory? Clearly $\omega_{3}\sim_{\mathcal{A}}\omega_{3}$ fails in the first definition.

1

There are 1 best solutions below

5
On BEST ANSWER

I assume that in your example $[w_k]_{\mathcal{A}}$ is supposed to be $[\omega_k]_{\mathcal{A}}$, as otherwise the objects $w_k$ are undefined. It is not true that $[\omega_3]_{\mathcal{A}}=\varnothing$: the relation that you defined at the top is reflexive, so $[\omega_3]_{\mathcal{A}}=\{\omega_3\}$. The fact that $1_A(\omega_3)=0$ for each $A\in \mathcal{A}$ simply says that $\omega_3$ is equivalent to those members of $\Omega$ that belong to none of the sets in $\mathcal{A}$. If we add a fifth element, $\omega_5$, to $\Omega$ without changing $\mathcal{A}$, then

$$[\omega_3]_{\mathcal{A}}=[\omega_5]_{\mathcal{A}}=\{\omega_3,\omega_5\}\,.$$