So let any secure MAC (message authentication code) be given.
Intuitively, I think it is clear that the probability of getting the same tag on two different messages is very small, i.e. negligible. I want to prove this statement mathematically.
How can we
(a) formulate this in an exact manner (because, negligible in what? I guess negligible in $|k|$, where $k$ is the chosen key - I am not sure about this)
(b) (once we have a precise formulation) prove this statement?
Supposing that this probability is not negligible, we'll have to construct a PPT adversary $\mathcal A$ that, somehow, is able to "beat" the system (which would be in contradiction with the fact that the MAC is secure).