Exchange order of "almost all" quantifiers Is it always true that
$$\forall^\star x\, \forall^\star y\,P(x,y) \Leftrightarrow \forall^\star y\, \forall^\star x\,P(x,y)$$
where $x,y$ are taken from (distinct) measure spaces, $P$ is a measurable predicate, and the $\forall^\star$ quantifier is "almost all"? I am ok with assuming that both measure spaces are complete probability spaces.
(I think it is true and follows from Tonelli's theorem, but not sure that I'm correct.)
 A: Ok, let me first give you the proof in the case that $M := \{(x,y) \in X\times Y \mid P(x,y)\}$ is measurable.
Denote the measures on $X,Y$ by $\mu, \nu$. We will also assume that $\mu, \nu$ are $\sigma$-finite, so that the Fubini-Tonelli-Theorem is applicable. This is of course true if both measures are probability measures.
Let us assume $\forall^{\ast} x \in X \forall^{\ast} y\in Y: P(x,y)$. Using Fubini-Tonelli, we derive
$$
\int_Y \int_X \chi_{M^c} (x,y) d\mu(x) d\nu(y) = \int_X \int_Y \chi_{M^c} (x,y) d\nu(y) d\mu(x).
$$
By our assumption, there is a null-set $N \subset X$ such that for every $x \in X\setminus N$ there is a null-set $N_x \subset Y$ such that $P(x,y)$ holds for all $y \in Y \setminus N_x$. This means $(x,y) \notin M^c$ for all $y \in Y \setminus N_x$, i.e. if $\chi_{M^c}(x,y) = 1$, then $y \in N_x$. This shows that $\chi_{M^c}(x,y)$ vanishes outside the null-set $N_x$ for every $x \in X\setminus N$.
Thus $\int_Y \chi_{M^c}(x,y) d\nu(y) = 0$ for $x \in X\setminus N$. As $N$ is a null-set, we get
$$
\int_X \int_Y \chi_{M^c}(x,y) d\nu(y) d\mu(x) = 0.
$$
By the above equation, we derive
$$
\int_Y \int_X \chi_{M^c} (x,y) d\mu(x) d\nu(y) = 0.
$$
But the function $y \mapsto \int_X \chi_{M^c}(x,y) d\mu(x)$ is non-negative. The vanishing of the integral thus implies that there is a null-set $N' \subset Y$ with $\int_X \chi_{M^c}(x,y) d\mu(x) = 0$ for all $y \in Y \setminus N'$.
Not the function $\chi_{M^c}(\cdot, y)$ is again non-negative, so that we get a null-set $N'_y \subset X$ with $\chi_{M^c}(x,y) = 0$ for all $x \in N'_y$.
But this means $(x,y) \in M$, i.e. $P(x,y)$ holds for all $y \in Y \setminus N'$ and all $x \in X \setminus N'_y$, i.e.
$$
\forall^{\ast} y \in Y \forall^{\ast} x \in X: P(x,y).
$$
Now to the counter-example in the case that $M$ is not measurable:
The following counterexample for the non-measurable case is Found in Rudin, Real and Complex Analysis, 8.9:
We assume that the continuum hypothesis (cf. http://en.wikipedia.org/wiki/Continuum_hypothesis ) holds, i.e. we assume that every uncountable subset of $\mathbb{R}$ is in bijection with $\mathbb{R}$.
This implies that the cardinality of $\Bbb{R}$ (or of $[0,1]$) is the first uncountable ordinal (cf. http://en.wikipedia.org/wiki/First_uncountable_ordinal ), so that there is a bijection $j : [0,1] \rightarrow \alpha$, where $\alpha$ is well-ordered and such that $\{x \in \alpha \mid x \leq y\}$ is countable for each $y \in \alpha$.
Now let
$$
Q := \{(x,y) \in [0,1] \times [0,1] \mid j(x) \leq j(y)\}
$$
This implies that
$$
Q_x := \{y \in [0,1] \mid (x,y) \in Q\} = \{y \in [0,1] \mid j(x) \leq j(y)\}
$$
contains all but countably many points of $[0,1]$ for each $x \in [0,1]$, whereas $Q^y$ (defined analogously) contains only coutably many points of $[0,1]$ for each $y \in Y$.
This shows
$$
\int_{[0,1]} \int_{[0,1]} \chi_Q (x,y) dx \, dy = \int_{[0,1]} |Q^y| \, dy = 0,
$$
but
$$
\int_{[0,1]} \int_{[0,1]} \chi_Q (x,y) dy \, dx = \int_{[0,1]} |Q_x| \, dx = \int_{[0,1]} 1 \, dx = 1.
$$
Now argument of the proof above shows that $\forall^{\ast} y \in Y \forall^{\ast} x\in X: (x,y) \notin Q$ holds, but the statement with the quantifiers exchanged does not hold.
