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.