Are commuting operators a function of the other? Say you have 2 operators (can be assumed observable), does $[A,B]$ imply that either $B = f(A)$ or $A = f(B)$ for some function $f$?
This is true in the case of a spin-1/2 Hilbert space, as any observable can be decomposed in a linear combination of the 3 Pauli matrices and the identity, and therefore if $A = \sigma_z$ then $B$ cannot contain neither $\sigma_x$ nor $\sigma_y$.
Another trivial case is if $B = 1$ in any Hilbert space, since it can be written as $B = A^0$.
I assume the first step to proving this (assumed true) would be to consider their shared eigenbasis.
 A: Your assertion is false as there are various elementary counterexamples already pointed out in the other answers.
The general result (due to von Neumann) is the following one. A pair of selfadjoint operators $A$ and $B$ strongly commute, which means that their spectral measures commute, if and only if  there is a third selfadjoint operator $C$ such that $A=f(C)$ and $B=g(C)$ for a pair of (Borel-measurable) functions $f,g : \mathbb{R} \to \mathbb{R}$.
In general $f$ and $g$ are not invertible, there are trivial examples. $A=X^2$ and $B=X^3- kX$ where $C=X$ is the standard position operator in $L^2(R, dx)$ and $k$ a dimensional coefficient. Here you cannot write $A$ as function of $B$ or vice versa. Also in finite dimension, consider $\mathbb{C}^3$ and the angular momentum operator $C=L_z$ and next take $A=L_z^2$ and $B= L_z^3-\hbar^2 L_z$, there is no way to write one as a function of the other.
For a proof in the general case, see the book by Riesz and Nagy on functional analysis or the book by Varadarajan on the Geometric structure of Quantum Theory.
In finite dimension strongly commutativity is equivalent to standard commutativity of the operators.
A: Counterexample: If $A:{\cal H}\to {\cal H}$ and $B:{\cal K}\to {\cal K}$, then
$$A\otimes {\bf 1}_{\cal K}: {\cal H}\otimes{\cal K} \to {\cal H}\otimes{\cal K}$$
and
$${\bf 1}_{\cal H}\otimes B: {\cal H}\otimes{\cal K} \to {\cal H}\otimes{\cal K}$$
commute, but they are not functions of each other.
A: There is a counter example. Consider a $4\times 4 $ Hilbert space, and two degenerate observables $A = \mathrm{diag}(a_1, a_d,a_d, a_4)$ and $B = \mathrm{diag}(b_d, b_2,b_3, b_d)$, with $a_1 \neq a_4$ and $b_2\neq b_3$. Then $A$ cannot be a function of $B$ since it would imply $f(b_d) = a_1 = a_4$ and $B$ cannot be a function of $A$ as it would imply $f(a_d) = b_2 = b_3$, which are both contradictions to the initial assumption.
