I suppose I really meant "why should one expect that f might be injective anyway?" Once you're no longer in the context of a set like N which is very familiar, there's just no obvious reason for the theorem to be false.