Triangle inequaility for sets of same cardinality

[mnb96]

Hello,
given a set $$\Omega$$, we consider all its subsets $A_1,A_2,A_3,\ldots$ with same cardinality k.

Do you have some hint in order to prove the following:

$$\forall A_x,A_y,A_z\subseteq \Omega$$ such that $$|A_x|=|A_y|=|A_z|=k$$

$$|A_x-A_z| \leq |A_x-A_y|+ |A_y-A_z|$$

Thanks

 

[mnb96]

Maybe I solved it by myself.
For the sake of brevity I'll write $X=A_x$, $Y=A_y$, $Z=A_z$.

By reductio-ad-absurdum let's assume that:

$$|X-Z|>|X-Y|+|Y-Z|$$

re-writing it in different form, we have that:

$$|X|-|X \cap Z| > |X|+|Y|-|X \cap Y|-|Y\cap Z|$$

Now, recalling the inclusion-exclusion formula for three sets X,Y,Z, we can write:

$$|X|-|X \cap Z| > |X\cup\ Y\cup Z| - |Z| + |X\cap Z| - |X\cap Y\cap Z|$$

Simply re-arranging the terms, and using the inclusion-exclusion formula for the leftmost term yields:

$$|X \cup Z| + |X\cap Y\cap Z| > |X\cup\ Y\cup Z| + |X\cap Z|$$

Now, it is easy to observe that $|X \cup Z| \leq |X\cup\ Y\cup Z|$ and $|X \cap Y\cap Z| \leq |X\cap\ Z|$, so the leftmost term is always less than or equal to the rightmost term: we reached a contradiction with the initial hypothesis and the statement is proved.

--Interestingly we have not used the fact that |X|=|Y|=|Z|, so apparently the statement holds in general.