# Couple of questions about a proof of an algorithm

$M$ is a set of men and $W$ is a set of women.

Initially all m in M and w in W are free
While there is a man m who is free and hasn’t proposed to
every woman
Choose such a man m
Let w be the highest-ranked woman in m’s preference list
to whom m has not yet proposed
If w is free then
(m, w) become engaged
Else w is currently engaged to m'
If w prefers m' to m then
m remains free
Else w prefers m to m'
(m, w) become engaged
m' becomes free
Endif
Endif
Endwhile
Return the set S of engaged pairs


Claim: The algorithm above terminates after at most $n^2$ iterations of While loop.

Proof: In the case of the present algorithm, each iteration consists of some man proposing (for the only time) to a woman he has never proposed to before. So if we let $P(t)$ denote the set of pairs $(m, w)$ such that $m$ has proposed to $w$ by the end of iteration $t$, we see that for all $t$, the size of $P(t + 1)$ is strictly greater than the size of $P(t)$. But there are only $n^2$ possible pairs of men and women in total, so the value of $P(\cdot)$ can increase at most $n^2$ times over the course of the algorithm. It follows that there can be at most $n^2$ iterations.

My questions:

1. $P(t)$ contains at least $1$ and at most $n^2$ elements. Correct?

2. $P(t)$ is the set after $t$ iterations and $P(\cdot)$ is the set after unknown number of iterations? I mean $P(t)$ is special case of more general $P(\cdot)$, correct? Else what is $P(\cdot)$?

3. What's the point of mentioning $|P(t)| < |P(t +1)|$ for all $t$?

2. Don't look too hard for a deep difference between "$P(t)$" and "$P(\cdot)$". In fact, I think the proof would be just as good if it said $P(t)$ even where your rendering has $P(\cdot)$.
3. That's the crucial point of the proof -- $|P(t)|$ is always a (non-negative) integer, and if it increases in each execution of the loop, it must increase by at least $1$. So if the loop executes for more than $n^2$ iterations $|P(t)|$ will eventually become greater than it can be, which is absurd.
But we can't conclude that unless we know that $|P(t)|$ is in fact strictly increasing.
In my opinion it would be a bit crisper to notice that $|P(t)|=t$ exactly, so a contradiction results if $t>n^2$. But there's nothing wrong with the reasoning here.