Thanks for the clarification with the template. What I wanted to say was the following:
\forall s,t in ISet< Tuple< A,B>>: (s.a==t.a) -> (s.b==t.b)
I guess it was somehow unclear. I finally solved it the following way (previously not knowing that it is possible to nest Contract.Exist and Contract.ForAll and after some logic reformulating)
ISet<Tuple<A,B> set;
Contract.Invariant(Contract.ForAll(set, s => s != null && Contract.ForAll(set, t => t != null && ((s.Item1 != t.Item1)||(s.Item2 == t.Item2)))));