Vitali relation, $a,b\in\Bbb R;\ a\sim b\iff a-b\in\Bbb Q$, is used to prove that there exists a non-measurable set of reals: we look at $A=\Bbb R/\sim$, from each $a\in A$ we take $b_a\in a$, then $\bigcup_{a\in A}\{b_a\}$ is the desired set.
This construction require choice function for the power set of $\Bbb R$, and without some kind of axiom of choice there is no guarantee such function exists(it can be seen by, for example, Solovay's model).
I remember reading the following:
In $\sf ZF$, $\Bbb R/\sim$ has a linear order implies the existence of of non-measurable subset of the reals.
This fact will also imply that compactness implies non-measurable set of reals, so my question is: what proof is there for the above theorem?
Taking help from @Noah comment and from @Wojowu:
Let's assume the contrary, that is, $\mathbb R/\sim$ is linearly ordered but every subset $\mathbb R^2$ is measurable we may use the ergodicity:
Let $\prec$ be the linear order of $\mathbb R/\sim$, and define $x\triangleleft y\iff [x]_\sim\prec[y]_\sim$. Then either $\triangleleft$ has measure $0$ or $\triangleleft^c=\{(a,b)∈\mathbb R^2\mid [a]_\sim\succ[b]_\sim\}\cup\{(a,b)∈\mathbb R^2\mid [a]_\sim=[b]_\sim\}$.
We may notice that $\{(a,b)∈\mathbb R^2\mid [a]_\sim=[b]_\sim\}=\bigcup_{q\in\mathbb Q}\{(x,y)∈\mathbb R^2\mid x-y=q\}$, which is countable union of lines, so has measure $0$, and $\{(a,b)∈\mathbb R^2\mid [a]_\sim\succ[b]_\sim\}$ has the same measure as $\triangleleft$, so in both cases we get that the measure of $\mathbb R^2$ is $0$, which is contradiction.