2
$\begingroup$

I've come across the following fact many times, and I used to take it for granted. However, I cannot think of a both beautiful and rigorous proof of it:

Fact 1:For two non-empty finite sets $A,B$ and map $f:A\times B\to \mathbb R,$ If we have $\big[\exists x_1\neq x_2\in A\times B,\ s.t. f(x_1)=f(x_2)=X\big]\Longrightarrow X=0,$

then we have $\displaystyle\sum_{x\in A}\sum_{y\in B} f(x,y)=\sum_{z\in f(A\times B)} z.$

Question: I know that we can prove this fact using induction, but is there some more beautiful proof of this fact? Thanks in advance.

Edit: I find that this fact also holds when $A,B$ are at most countable sets, and $f\geqslant 0.$

Update: Fact 1 is just a special case of the following fact:

Fact 2: For non-empty finite set $A$ and map $A\to \mathbb R,$ if we have $\big[\exists x_1,x_2\in A,\ s.t. f(x_1)=f(x_2)=X\big]\Longrightarrow X=0,$ then we have $\displaystyle\sum_{x\in A} f(x)=\sum_{z\in f(A)} z.$


Proof: According to @Christian Blatter's answer, we have$$\displaystyle\sum_{x\in A} f(x)=\sum_{z\in f(A)-\left\{0\right\}} \mathrm{Card}\big(f^{-1}(z)\big)z,$$ here $f^{-1}(z):=\left\{x\in A|\ f(x)=z\right\}.$
According to the assumption of fact 2, we have $\mathrm{Card}\big(f^{-1}(z)\big)=1$ for each $z\in f(A)-\left\{0\right\}.$ Thus we have$$\displaystyle\sum_{x\in A} f(x)=\sum_{z\in f(A)-\left\{0\right\}} z=\sum_{z\in f(A)} z.$$End of Proof


In addition, the following fact could be proved similarly:

Fact 3: For two non-empty finite sets $A, B$ and map $\sigma:A\to B,\ \psi:B\to \mathbb R,$ let $f=\psi\circ \sigma,$ denote the set of all zeros of a real-valued function $g$ as $\mathrm{Kel}(g),$ and the image set of a real-valued function $g$ as $\mathrm{Im}(g),$ then

a) if we have $\big[\exists x_1,x_2\in A,\ s.t. \sigma(x_1)=\sigma(x_2)=X\big]\Longrightarrow X\in \mathrm{Kel}(\psi),$ then we have $$\displaystyle\sum_{x\in A} f(x)=\sum_{z\in \mathrm{Im}(\sigma)} \psi(z).$$ b) if we have $\big[\exists x_1,x_2\in B,\ s.t. \psi(x_1)=\psi(x_2)=X\big]\Longrightarrow X=0,$ and $\sigma$ is injective, then we have $$\displaystyle\sum_{x\in A} f(x)=\sum_{z\in \psi\big(\mathrm{Im}(\sigma)\big)} z=\sum_{z\in \mathrm{Im}f} z.$$

$\endgroup$
1
$\begingroup$

Even though the "beauty" of a proof is subjective to a certain degree, I still post my answer using .

It suffices to establish a bijection between the support of $f:A \times B \to \Bbb{R}$ (part of the domain which gives nonzero function value) and the nonzero image $f(A\times B)\setminus\{0\}$. (We ignore the terms $z=f(x,y)=0$, which have no contribution to the sums.) $$\text{supp}(f):=\{(x,y)\in A\times B \mid f(x,y)\ne0\} \leftrightarrow \{z \in f(A \times B) \mid z \ne 0\}=f(A\times B)\setminus\{0\}$$

Rewrite the set on the RHS as $\{f(x,y)\in\Bbb{R}\mid x \in A, y \in B, f(x,y)\ne0\}$. Obviously, the bijection to be constructed is $\tilde{f}:\text{supp}(f) \to f(A\times B)\setminus\{0\}$. By abuse of notation, we'll denote $\tilde{f}$ (defined on the support of $f$) as $f$.

  • surjectivity is guaranteed by the very definition of the set on the RHS
  • injectivity is assumed: if there are two different elements $(x_1,y_1),(x_2,y_2) \in \text{supp}(f)$ giving the same function value $f(x_1,y_1) = f(x_2,y_2)$, then the assumption in the question implies $f(x_1,y_1)=f(x_2,y_2)=0$, which contradicts the very definition of $\text{supp}(f)$.

Since the sets $A$ and $B$ are finite, so as their direct product $A \times B$. Finally we have $$\sum_{(x,y)\in \text{supp}(f)} f(x,y) = \sum_{z\in f(A\times B)\setminus\{0\}} z,$$ which is equivalent to the desired equality.

$\endgroup$
  • $\begingroup$ Your proof is correct, but it still takes me quite a long time to figure out why it works... $\endgroup$ – painday Jan 11 '18 at 16:01
  • 1
    $\begingroup$ @painday Proving indices are pointing to the same objects is a word game if you don't find this obvious. We emphasized that $A \times B$ is finite since in infinite case, bijection between indices doesn't mean pointing to the same terms (think of a sum over integers and over even integers). $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 11 '18 at 16:09
  • $\begingroup$ Right, and I think the key point of the proof is that $\tilde f:\mathrm{supp }f\to f(A\times B)-\left\{0\right\}$ is a bijection. I really like the idea of "support of a function". $\endgroup$ – painday Jan 11 '18 at 16:14
  • $\begingroup$ @painday When I wrote this, I had a much simpler sentence in mind: "cut off the zero and get a bijection". I start developing the habit of writing sentences after reading some pages from Paul Halmos' autobiography I wanna be a mathematician. Btw, I found the equation in the alternative solution presents the idea of "number of elements" clearer than mine. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 11 '18 at 16:23
  • 1
    $\begingroup$ Yeah, the cardinal number is a very clear concept. But that method could not be extended to the infinite condition, while your proof could be extended to the positive term series. $\endgroup$ – painday Jan 11 '18 at 16:35
2
$\begingroup$

Since $A$ and $B$ are finite the set $R:=f(A\times B)\subset{\mathbb R}$ is finite as well. It is then obvious that $$\sum_{(x,y)\in A\times B} f(x,y)=\sum_{z\in R}\bigl|f^{-1}(\{z\})\bigr|\>z=\sum_{z\in R}z\ ,$$ as $\bigl|f^{-1}(\{z\})\bigr|=1$ for all $z\in R\setminus\{0\}$, by assumption.

(Here $\bigl|f^{-1}(\{z\})\bigr|$ denotes the number of pairs $(x,y)$ satisfying $f(x,y)=z$.)

$\endgroup$
  • $\begingroup$ $\bigl|f^{-1}(\{0\})\bigr|$ can be greater than $1$, this doesn't affect the sum though. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 11 '18 at 15:07
  • 1
    $\begingroup$ @GNUSupporter: Thank you for spotting and reporting my blunder. $\endgroup$ – Christian Blatter Jan 11 '18 at 15:10
0
$\begingroup$

To extend the fact into infinite condition, we assume that at least one of $A,B$ is countable set, and $f\geqslant 0.$

According to the answer by @GUN Supporter, we can prove that $\widetilde f:\mathrm{supp}f\to f(A\times B)-\left\{0\right\},\ t\mapsto f(t)$ is bijective, thus for any bijection $\sigma:\mathbb N\to \mathrm{supp} f,$ and any bijection $\tau:\mathbb N\to f(A\times B)-\left\{0\right\},$ just let $\psi=\tau^{-1}\circ \tilde f\circ \sigma,$ then $\psi$ is a bijection, and we have $$\tilde f\circ \sigma=\tau\circ \psi.$$ Recall the fact that we can change the order of the terms of a positive series freely without affecting its convergence, now we have $$\sum_{i=1}^{\infty} \big(\tilde f\circ \sigma\big)(i)=\sum_{i=1}^{\infty}\big(\tau\circ \psi\big)(i)=\sum_{i=1}^{\infty}\tau(i),$$ for any bijection $\sigma,\tau.$ Now we obtain that $$\sum_{(x,y)\in \mathrm{supp}f}f(x,y)=\sum_{z\in f(A\times B)-\left\{0\right\}} z,$$ or $$\sum_{x\in A}\sum_{y\in B} f(x,y)=\sum_{z\in f(A\times B)} z.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.