# Information-theoretic interpretation of bijections

Let us consider two sets $$A$$ and $$B$$. Suppose there exists a bijection $$\phi:A\to B$$ so that any $$b\in B$$ uniquely determines an element $$a = \phi^{-1}(b)\in A$$. In this sense, we can claim that the set $$B$$ gives us the full information' of $$A$$ since every element in $$A$$ can be characterized by the element in $$B$$.

My question is, how can we interpret this bijection between two sets using information theory? How should we define probability distributions on $$A$$ and $$B$$ and use information theory to say there is a bijection between $$A$$ and $$B$$'?

Saying that $$X$$ is a random variable and $$Y=f(x)$$ where $$f$$ is a (measurable) bijection is equivalent to say that the conditional entropies are equal to zero, $$H(Y|X)=H(X|Y)=0$$, this also implies that the mutual information is equal to their entropies $$I(X,Y)=H(X)=H(Y)$$.
• Hi Giovanni, thanks for the reply! In my question, I can define arbitrary random variables $X$ and $Y$ on the sets $A$ and $B$, respectively. Is there a specific way to determine the injection of the `deterministic' elements in $A$ and $B$? – mw19930312 Jul 16 at 20:30
• I don't understand what you mean by 'determine the injection'. However, if there is a uniform distribution over $A$ and if $f$ is injective (deterministic) map to $B$. If $f$ is injective then for a uniform random variable $X$ over the set $A$, $H(X)=\log |A| =\log |f(X)|$. which should be equal to $|B|$. – lebesgue Jul 16 at 20:39
• @lebesgue Thanks for the discussion. Maybe I should be more specific. Suppose we have r.v.s $X$ and $Y = f(x)$ where $f$ is a bijection. Then shall we say there also exists a bijection between the event spaces associated with these two r.v.s? – mw19930312 Jul 17 at 16:54