We (collectively) salt passwords, then hash them; maybe even run them through something like PBKDF2 first (depending on how the password will be used).
The end result is that we have a string $p$ and map it to a fixed-length string $p'$ using a surjective transformation with the property that it is difficult to find any particular $p$ that maps to a given $p'$.
The fact that there are $\aleph_0$ possible $p$ strings and only a finite amount of possible $p'$ strings means that there is an infinite number of $p$ strings that map to any particular $p'$.
The difficulty of guessing a password when the attacker has access to the salted hash comes from the fact that the $p\to p'$ mapping function is relatively expensive, limiting the rate at which attempts can be made to find a suitable $p$ for $p'$. (Essentially, the attacker is brute forcing a hash collision, not guessing the actual password.)
Intuitively, increasing the length of $p$ seems to increase the number of attempts required to find it; however, since the attacker isn't actually trying to find the original $p$, just some $p_1$ that has the same hash, I wonder to what extent we can guarantee that increasing the length of $p$ really increases the time required to obtain a collision; both in general and in practical particular cases.
Mathematically: if we have a $p_0$ salted password with length $x$ that maps to $p'_0$, what's the likelihood of a $p_1$ string with length $<x$ to map to the same $p'_0$?
Do PBKDF2 and/or mainstream cryptographic hash functions contain some mechanism to decrease this likelihood?
I don't think it can be possible to guarantee this in the general case where passwords can be arbitrarily long. If the salted password is longer than the hash length $\ell$, then there are going to be several passwords that map to the same hash; assuming that the hashes are approximately evenly distributed, we exhaust the entirety of hash space just with passwords of length $\ell+1$, which means that some passwords of length $\ell$ will also map to some of the same hashes.
This means that there is a critical length $\ell_c$ above which adding more characters to the password doesn't increase the time required to obtain it a collision.
I think in most cases this isn't a practical problem because password hashes can be very long; humans are unlikely to choose passwords longer than $\ell_c$, if $\ell_c$ is on the order of hash length.
However, I feel (and I realize I should be able to work this out from first principles) that increasing password length doesn't actually scale guessing difficulty exponentially, as one would intuitively think, because the likelihood of a hash collision with a shorter string also increases with increasing password length. I feel certain that someone has actually worked out the math and I'd be interested in the result, I probably chose the wrong search terms because I couldn't immediately find it.
I'm also interested in a practical aspect: if I use a realistically long password of ~15 characters, what are the chances that a much shorter string will map to the same hash, effectively weakening my password? Is this purely a question of luck (with astronomical chances)?
EDIT: some naïve math, mostly ignoring salts for now: if the hash is, say, 64 characters long, then there are 256^64 different hashes. All passwords shorter than 16 characters will map to 256^16-1 different hashes, and passwords that are exactly 16 characters long will map to 256^16 different hashes. The chance of these sets overlapping is a birthday problem, but we're not interested in the probability of any short and any long password having the same hash, only the probability of a specific long password having the same hash as any short password, so we can ignore the birthday aspect and the odds do look very good.
EDIT: formalizing my question above: given a $p_0$ password of length $x$, and a $p_1$ password of length $x+1$, we tend to believe the expected value of the time required to crack $p_1$ using brute force would be 256 times the expected value of time required to crack $p_0$, but what is the actual ratio, also considering hash collisions? It must be a function of $x$, approaching 1 as $x$ approaches the length of the hash. Again, this looks quite easy to work out but probably someone has already done it, and I don't like doing math enough to also like redoing it :).
EDIT: I realize most of this is not of any practical concern. My interest is "academic" (in the informal sense).