Let $X$ be a set of cardinality $n$ and let $R$ be the set of all relations over $X$. Consider the probability space $(R,P)$ with uniform distribution, that is, $P[\{R_1\}]] = P[\{R_2\}]$ for all $ R_1,R_2 \in R$. Define the relation ”equiprobable” on the set of all events of $(R, P)$ as follows: Events $A$ and $B$ are equiprobable iff $P[A] = P[B]$.
a. Prove that ”equiprobable” is an equivalence relation.
b. How many equivalence classes does this relation define?
Here is my attempt at a, can anyone help me check?
-
Reflexive: $R_1 ,\in R$, then $P[\{R_1\}] = P[\{R_1\}]$, which is equiprobable $\Rightarrow$ $R_1\,R\, R_1$ $\Rightarrow$ reflexive
-
Transitive: $R_1,R_2,R_3 \in R$, suppose $P[\{R_1\}] = P[\{R_2\}\,] \& \,P[\{R_2\}] = P[\{R_3\}] \,\Rightarrow\, P[\{R_1\}] = P[\{R_3\}] \,\Rightarrow\, R_1 \,R \,R_3 \,\Rightarrow $transitive
-
Symmetric: $R_1, R_2 \in R$, $ P[\{R_1\}] = P[\{R_2\}]$ $\Rightarrow$ $P[\{R_2\}] = P[\{R_1\}]$ $\Rightarrow$ $R_2\, R\, R_1$ $\Rightarrow$ symmetric
I don't know how to solve b, and my teacher gave me a hint but I'm still a lot confused about equivalence classes
If $R_1$ and $R_2$ are equiprobable, is there any relation between $|R_1|$ and $|R_2|$?
This is just my guess: $|R_1| = |R_2|$ because they are equivalence relations, so the size of them are equal?
Please help me understand this
Best Answer
In general if $f:A\to B$ is some function then a relation $S$ over $A$ that is prescribed by: $$xSy\iff f(x)=f(y)$$can "immediately" be recognized as an equivalence relation on base of the observations that $f(x)=f(x)$ for every $x\in A$, $f(x)=f(y)\implies f(y)=f(x)$ for all $x,y\in A$ and $f(x)=f(y)\wedge f(y)=f(z)\implies f(x)=f(z)$ for all $x,y,z\in A$.
You did that in your attempt with function $P$.
Further the equivalence class represent by $a\in A$ is the set $\{x\in A\mid f(x)=f(a)\}$.
The cardinality of the set of equivalence classes equals the cardinality of the image of the function, i.e. the set $\{f(x)\mid x\in A\}$. This because there is a one-to-one relation between the image and the set of equivalence classes: every element $y$ of this image corresponds with equivalence class $\{x\mid f(x)=y\}$.
Application in your situation:
The set of outcomes is $R=\wp\left(X\times X\right)$. From the fact that $X$ has $n$ elements we conclude that $X\times X$ has $n^{2}$ elements, and secondly that $R=\wp\left(X\times X\right)$ has $2^{n^{2}}$ elements.
Further $P$ is an additive function $\wp\left(R\right)\to\mathbb{R}$ determined by $P\left(\left\{ r\right\} \right)=2^{-n^{2}}$ for every $r\in R$.
That implies that for event $A\subseteq\wp\left(R\right)$ we have $P\left(A\right)=\sum_{r\in A}P\left(\left\{ r\right\} \right)=\left|A\right|2^{-n^{2}}$ where $\left|A\right|$ can take the values $\left\{ 0,1,2,\dots,2^{n^{2}}\right\} $.
We conclude that the cardinality of the image of function $P$ is: $$2^{n^{2}}+1$$ and as shown above this is also the number of equivalence classes.