[proofplan] We write the graph map as $S(x)=(x,T(x))$ and first verify that it is measurable for the product $\sigma$-algebra. The two marginal identities follow directly from the definition of pushforward measure by testing on measurable rectangles $A\times Y$ and $X\times B$. Finally, the integral identity is proved from the definition of the nonnegative integral: first for indicators, then for simple functions, and then by the standard monotone simple approximation of a nonnegative measurable function. [/proofplan]

[step:Verify that the graph map is measurable] Define \begin{align*} S:(X,\mathcal A)\to(X\times Y,\mathcal A\otimes\mathcal B),\quad S(x)=(x,T(x)). \end{align*} To prove that $S$ is measurable, it suffices to check preimages of measurable rectangles, since $\mathcal A\otimes\mathcal B$ is generated by sets of the form $A\times B$ with $A\in\mathcal A$ and $B\in\mathcal B$. For such $A$ and $B$, \begin{align*} S^{-1}(A\times B)=A\cap T^{-1}(B). \end{align*} Because $A\in\mathcal A$ and $T^{-1}(B)\in\mathcal A$ by measurability of $T$, the intersection $A\cap T^{-1}(B)$ belongs to $\mathcal A$. Hence $S$ is measurable, so the pushforward measure $\pi:=S_\#\mu$ is well-defined on $(X\times Y,\mathcal A\otimes\mathcal B)$. Since $\mu$ is a probability measure, \begin{align*} \pi(X\times Y)=\mu(S^{-1}(X\times Y))=\mu(X)=1. \end{align*} Thus $\pi$ is a probability measure on $X\times Y$. [/step]

[step:Compute the first marginal of the induced measure] Let $p_X:X\times Y\to X$ denote the first coordinate projection, defined by $p_X(x,y)=x$. The first marginal of $\pi$ is $(p_X)_\#\pi$. Let $A\in\mathcal A$. Since $p_X^{-1}(A)=A\times Y$, the definition of pushforward gives \begin{align*} (p_X)_\#\pi(A)=\pi(A\times Y). \end{align*} Using $\pi=S_\#\mu$, \begin{align*} \pi(A\times Y)=\mu(S^{-1}(A\times Y)). \end{align*} For every $x\in X$, one has $S(x)=(x,T(x))\in A\times Y$ if and only if $x\in A$. Hence \begin{align*} S^{-1}(A\times Y)=A. \end{align*} Therefore \begin{align*} (p_X)_\#\pi(A)=\mu(A). \end{align*} Since this holds for every $A\in\mathcal A$, the first marginal of $\pi$ is $\mu$. [/step]

[step:Compute the second marginal of the induced measure] Let $p_Y:X\times Y\to Y$ denote the second coordinate projection, defined by $p_Y(x,y)=y$. The second marginal of $\pi$ is $(p_Y)_\#\pi$. Let $B\in\mathcal B$. Since $p_Y^{-1}(B)=X\times B$, the definition of pushforward gives \begin{align*} (p_Y)_\#\pi(B)=\pi(X\times B). \end{align*} Using $\pi=S_\#\mu$, \begin{align*} \pi(X\times B)=\mu(S^{-1}(X\times B)). \end{align*} For every $x\in X$, one has $S(x)=(x,T(x))\in X\times B$ if and only if $T(x)\in B$. Hence \begin{align*} S^{-1}(X\times B)=T^{-1}(B). \end{align*} Therefore \begin{align*} (p_Y)_\#\pi(B)=\mu(T^{-1}(B)). \end{align*} By the hypothesis $T_\#\mu=\nu$, the right-hand side equals $\nu(B)$. Thus \begin{align*} (p_Y)_\#\pi(B)=\nu(B). \end{align*} Since this holds for every $B\in\mathcal B$, the second marginal of $\pi$ is $\nu$. The first marginal of $\pi$ is $\mu$ and the second marginal of $\pi$ is $\nu$, so by the definition of $\Pi(\mu,\nu)$ we have $\pi\in\Pi(\mu,\nu)$. [/step]

[step:Prove the integral identity from the pushforward definition]Let \begin{align*} c:X\times Y\to[0,\infty] \end{align*} be $\mathcal A\otimes\mathcal B$-measurable. Since $S$ is measurable, the composition \begin{align*} c\circ S:X\to[0,\infty],\quad (c\circ S)(x)=c(x,T(x)), \end{align*} is $\mathcal A$-measurable. First let $E\in\mathcal A\otimes\mathcal B$ and consider the indicator function $\mathbb{1}_E:X\times Y\to[0,\infty]$. By the definition of pushforward measure, \begin{align*} \int_{X\times Y}\mathbb{1}_E(x,y)\,d\pi(x,y)=\pi(E)=\mu(S^{-1}(E)). \end{align*} Also, \begin{align*} \int_X \mathbb{1}_E(S(x))\,d\mu(x)=\int_X \mathbb{1}_{S^{-1}(E)}(x)\,d\mu(x)=\mu(S^{-1}(E)). \end{align*} Thus the identity holds for indicator functions. By linearity of the integral for nonnegative simple functions, if \begin{align*} \varphi:X\times Y\to[0,\infty] \end{align*} is an $\mathcal A\otimes\mathcal B$-measurable [simple function](/page/Simple%20Function), then \begin{align*} \int_{X\times Y}\varphi(x,y)\,d\pi(x,y)=\int_X \varphi(S(x))\,d\mu(x). \end{align*} Choose a sequence of nonnegative $\mathcal A\otimes\mathcal B$-measurable simple functions \begin{align*} \varphi_n:X\times Y\to[0,\infty] \end{align*} such that $0\leq \varphi_n\leq \varphi_{n+1}$ for every $n\in\mathbb N$ and $\varphi_n(x,y)\to c(x,y)$ for every $(x,y)\in X\times Y$. Then $\varphi_n\circ S:X\to[0,\infty]$ is nonnegative, $\mathcal A$-measurable, increasing in $n$, and satisfies \begin{align*} \varphi_n(S(x))\to c(S(x))=c(x,T(x)) \end{align*} for every $x\in X$. By the definition of the integral of a nonnegative measurable function as the limit of increasing simple approximations, \begin{align*} \int_{X\times Y} c(x,y)\,d\pi(x,y)=\lim_{n\to\infty}\int_{X\times Y}\varphi_n(x,y)\,d\pi(x,y). \end{align*} For each $n$, the simple-function case gives \begin{align*} \int_{X\times Y}\varphi_n(x,y)\,d\pi(x,y)=\int_X \varphi_n(S(x))\,d\mu(x). \end{align*} Taking the limit again by the definition of the nonnegative integral, \begin{align*} \lim_{n\to\infty}\int_X \varphi_n(S(x))\,d\mu(x)=\int_X c(S(x))\,d\mu(x). \end{align*} Since $c(S(x))=c(x,T(x))$, we obtain \begin{align*} \int_{X\times Y} c(x,y)\,d\pi(x,y)=\int_X c(x,T(x))\,d\mu(x). \end{align*}[/step]

[guided]The goal is to justify the formula for integrals without assuming it as a black-box change-of-variables theorem. The only input is the definition of $\pi$ as the pushforward $S_\#\mu$, where \begin{align*} S:(X,\mathcal A)\to(X\times Y,\mathcal A\otimes\mathcal B),\quad S(x)=(x,T(x)). \end{align*} Because $c:X\times Y\to[0,\infty]$ is $\mathcal A\otimes\mathcal B$-measurable and $S$ is measurable, the composition \begin{align*} c\circ S:X\to[0,\infty],\quad (c\circ S)(x)=c(x,T(x)), \end{align*} is $\mathcal A$-measurable, so the right-hand integral is well-defined. We begin with an indicator function because the pushforward definition directly computes the measure of a preimage. Let $E\in\mathcal A\otimes\mathcal B$ and let $\mathbb{1}_E:X\times Y\to[0,\infty]$ be its indicator. Then \begin{align*} \int_{X\times Y}\mathbb{1}_E(x,y)\,d\pi(x,y)=\pi(E). \end{align*} Since $\pi=S_\#\mu$, the definition of pushforward gives \begin{align*} \pi(E)=\mu(S^{-1}(E)). \end{align*} On the other hand, the composed indicator satisfies \begin{align*} \mathbb{1}_E(S(x))=\mathbb{1}_{S^{-1}(E)}(x) \end{align*} for every $x\in X$. Hence \begin{align*} \int_X \mathbb{1}_E(S(x))\,d\mu(x)=\int_X\mathbb{1}_{S^{-1}(E)}(x)\,d\mu(x)=\mu(S^{-1}(E)). \end{align*} The two expressions are equal, so the integral identity holds for indicators. Now pass from indicators to simple functions. Let \begin{align*} \varphi:X\times Y\to[0,\infty] \end{align*} be an $\mathcal A\otimes\mathcal B$-measurable simple function. It can be written as a finite nonnegative linear combination of indicators of measurable sets. Applying the indicator identity to each measurable set and using finite additivity and linearity of the nonnegative simple integral gives \begin{align*} \int_{X\times Y}\varphi(x,y)\,d\pi(x,y)=\int_X \varphi(S(x))\,d\mu(x). \end{align*} Finally let $c:X\times Y\to[0,\infty]$ be the given nonnegative measurable cost. Choose nonnegative $\mathcal A\otimes\mathcal B$-measurable simple functions \begin{align*} \varphi_n:X\times Y\to[0,\infty] \end{align*} with $0\leq\varphi_n\leq\varphi_{n+1}$ for every $n\in\mathbb N$ and $\varphi_n(x,y)\to c(x,y)$ for every $(x,y)\in X\times Y$. Composing with $S$ preserves the monotonicity and pointwise convergence: \begin{align*} \varphi_n(S(x))\to c(S(x))=c(x,T(x)) \end{align*} for every $x\in X$. By the construction of the nonnegative measurable integral from increasing simple approximations, \begin{align*} \int_{X\times Y} c(x,y)\,d\pi(x,y)=\lim_{n\to\infty}\int_{X\times Y}\varphi_n(x,y)\,d\pi(x,y). \end{align*} For each $n$, the simple-function identity gives \begin{align*} \int_{X\times Y}\varphi_n(x,y)\,d\pi(x,y)=\int_X \varphi_n(S(x))\,d\mu(x). \end{align*} Taking limits on the right-hand side using the same construction of the nonnegative integral gives \begin{align*} \lim_{n\to\infty}\int_X \varphi_n(S(x))\,d\mu(x)=\int_X c(S(x))\,d\mu(x). \end{align*} Substituting $S(x)=(x,T(x))$ yields \begin{align*} \int_{X\times Y} c(x,y)\,d\pi(x,y)=\int_X c(x,T(x))\,d\mu(x). \end{align*}[/guided]