> This doesn't really get you to the maximum, because f might be computing max(x, y) + 5, but it does show the idea.

Perhaps { int | _ >= x && _ >= y && (_ == x || _ == y) } ?

I just proved in Coq that if all of these always hold for a function, the function coincides exactly with the max function.