# Prove that "equiprobable" is an equivalence relation

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

• How many elements does $R$ have? So how many values can $P$ take? Jun 3, 2019 at 5:55
• @user10354138 erm I'm not sure.. the question doesn't state, does it? Can you give me some more hints?
– amV
Jun 3, 2019 at 6:03
• Please use Mathjax when writing math :) Jun 3, 2019 at 6:04
• @RiccardoSvenRisuleo I will, thanks
– amV
Jun 3, 2019 at 6:05
• The equivalence class of an event $A\subseteq R$ is the set of all events $B\subseteq R$ which are equiprobable to $A$. Under the uniform distribution, the only condition to be satisfied is that $A$ and $B$ contain the same number of outcomes. You might as well label each equivalence class by the size of its elements! Jun 3, 2019 at 6:17

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\}$$.

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.

• can you explain a little bit about the set of the image of P? why is it {0, 1/n^2, ... (n^2-1)/n^2, 1}? Sorry I'm not quite good at this
– amV
Jun 3, 2019 at 7:00
• I have repaired my answer. Jun 3, 2019 at 8:25
• Where does the "+ 1" come from for the cardinality of the relation? I'm a little unclear on that part Dec 15, 2020 at 17:11
• @quantumferret Do you agree that set $\{0,1,2,\dots m\}$ has $m+1$ elements? Here $m=2^{n^2}$. Dec 15, 2020 at 18:37
• @drhab would it be incorrect for me to think of it in terms of a probability space (Ω, F, P)? Ω would be |X x X| = n^2 and F = 2^(n^2), so F = m? Dec 16, 2020 at 13:06